Two levels approach based on multifactorial optimization to solve the clustered shortest path tree problem
- PDF / 7,365,712 Bytes
- 29 Pages / 595.276 x 790.866 pts Page_size
- 87 Downloads / 256 Views
RESEARCH PAPER
Two levels approach based on multifactorial optimization to solve the clustered shortest path tree problem Huynh Thi Thanh Binh1 · Pham Dinh Thanh2 Received: 27 September 2019 / Revised: 8 April 2020 / Accepted: 24 June 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract The Clustered Shortest-Path Tree Problem (CluSPT) has a great meaning in theoretical research as well as a wide range of applications in everyday life, especially in the field of network optimization. Being able to solve the CluSPT will path the way for improving practical systems such as agricultural irrigation and product distribution. Multifactorial Evolutionary Algorithm (MFEA) is a variant of Evolutionary Algorithm (EA) aiming at simultaneously solving multiple factorial tasks which can be diverse in types, dimensionalities and search spaces. The applications of MFEA have yet to be fully exploited, but the realm has recently attracted much interest from the research community, especially those who are working on evolutionary multitasking. Considering these characteristics, this paper describes a new approach using the MFEA for solving the CluSPT. The MFEA has two tasks: the first is solving the CluSPT problem and the second is solving a new problem which is decomposed from the CluSPT problem. The goal of the first task is finding the fittest solution as possible for the CluSPT while the goal of the second task is determining the best tree (w.r.t. cost minimization) which envelops all vertices of the problem. This paper also introduces mutation, crossover and population initialization operators for a proposed MFEA to solve the CluSPT. Each of these operators deals with individuals in two phases, one of which ensures that the resulted individual is a spanning tree and the other phase ensures that each of its clustered sub-graphs is also a spanning tree. As the MFEA had to deal with these two tasks, a decoding method was also created to allow communication between the tasks. To assess the effectiveness of the proposed algorithm and methods, the authors implemented them on both Euclidean and Non-Euclidean instances. Experiment results show that the proposed MFEA outperformed the existing MFEA algorithms on two-thirds instances with average improvement value of 47%. Besides, this paper analysis the convergence trends of each task in generations and the affectation of the number of vertices in the largest cluster on the obtained results by using both the Spearman’s rank correlation coefficient and scatter graphs. Keywords Multifactorial evolutionary algorithm · Clustered shortest-path tree problem · Evolutionary algorithms · Genetic algorithm · Multifactorial optimization
1 Introduction
* Pham Dinh Thanh [email protected], [email protected] Huynh Thi Thanh Binh [email protected] 1
School of Information and Communication Technology, Hanoi University of Science and Technology, Hanoi, Vietnam
Faculty of Natural Science and Technology, Taybac University, Son La, Vietnam
2
Evolutionary Algor
Data Loading...
