Multifactorial evolutionary algorithm for solving clustered tree problems: competition among Cayley codes
Tóm tắt
The Multifactorial Evolutionary Algorithm (MFEA) has emerged as an effective variant of the evolutionary algorithm. MFEA has been successfully applied to deal with various problems with many different types of solution encodings. Although clustered tree problems play an important role in real life, there haven’t been much research on exploiting the strengths of MFEA to solve these problems. One of the challenges in applying the MFEA is to build specific evolutionary operators of the MFEA algorithm. To exploit the advantages of the Cayley Codes in improving the MFEA’s performance, this paper introduces MFEA with representation scheme based on the Cayley Code to deal with the clustered tree problems. The new evolutionary operators in MFEA have two different levels. The purpose of the first level is to construct a spanning tree which connects to a vertex in each cluster, while the objective of the second one is to determine the spanning tree for each cluster. We focus on evaluating the efficiency of the new MFEA algorithm on known Cayley Codes when solving clustered tree problems. In the aspect of the execution time and the quality of the solutions found, each encoding type of the Cayley Codes is analyzed when performed on both single-task and multi-task to find the solutions of one or two different clustered tree problems respectively. In addition, we also evaluate the effect of those encodings on the convergence speed of the algorithms. Experimental results show the level of effectiveness for each encoding type and prove that the Dandelion Code outperforms the remaining encoding mechanisms when solving clustered tree problems.
Tài liệu tham khảo
Back T (1996) Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms. Oxford University Press, Oxford
Bali KK, Ong YS, Gupta A, Tan PS (2019) Multifactorial evolutionary algorithm with online transfer parameter estimation: Mfea-II. IEEE Trans Evol Comput 24:69–83
Binh HTT, Thanh PD, Trung TB, Thao LP (2018) Effective multifactorial evolutionary algorithm for solving the cluster shortest path tree problem. In: 2018 IEEE congress on evolutionary computation (CEC). IEEE, pp 819–826
Binh HTT, Thanh PD, Thang TB (2019) New approach to solving the clustered shortest-path tree problem based on reducing the search space of evolutionary algorithm. Knowl Based Syst 180:12–25
Chandra R, Gupta A, Ong YS, Goh CK (2016) Evolutionary multi-task learning for modular training of feedforward neural networks. In: International conference on neural information processing, Springer, pp 37–46
Da B, Gupta A, Ong YS, Feng L (2016) Evolutionary multitasking across single and multi-objective formulations for improved problem solving. In: 2016 IEEE congress on evolutionary computation (CEC), IEEE, pp 1695–1701
Derrac J, García S, Hui S, Suganthan PN, Herrera F (2014) Analyzing convergence performance of evolutionary algorithms: a statistical approach. Inf Sci 289:41–58
D’Emidio M, Forlizzi L, Frigioni D, Leucci S, Proietti G (2019) Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem. J Comb Optim 38:165–184
Franz R (2006) Representations for genetic and evolutionary algorithms. Springer, Berlin
Gupta A, Mańdziuk J, Ong YS (2015) Evolutionary multitasking in bi-level optimization. Complex Intell Syst 1(1–4):83–95
Gupta A, Ong YS, Feng L (2016a) Multifactorial evolution: toward evolutionary multitasking. IEEE Trans Evol Comput 20(3):343–357
Gupta A, Ong YS, Feng L, Tan KC (2016b) Multiobjective multifactorial optimization in evolutionary multitasking. IEEE Trans Cybern 47:1652–1665
Julstrom BA (2005) The blob code is competitive with edge-sets in genetic algorithms for the minimum routing cost spanning tree problem. In: Proceedings of the 7th annual conference on Genetic and evolutionary computation, ACM, pp 585–590
Lin CW, Wu BY (2017) On the minimum routing cost clustered tree problem. J Comb Optim 33(3):1106–1121
Mestria M, Ochi LS, de Lima Martins S (2013) GRASP with path relinking for the symmetric euclidean clustered traveling salesman problem. Comput Oper Res 40(12):3218–3229
Myung YS, Lee CH, Tcha DW (1995) On the generalized minimum spanning tree problem. Networks 26(4):231–241
Ong YS, Gupta A (2016) Evolutionary multitasking: a computer science view of cognitive multitasking. Cogn Comput 8(2):125–142
Palmer C, Kershenbaum A (1994) Representing trees in genetic algorithms. IEEE, Orlando, FL, USA, pp 379–384. https://doi.org/10.1109/ICEC.1994.349921, http://ieeexplore.ieee.org/document/349921/
Perfecto C, Bilbao MN, Del Ser J, Ferro A, Salcedo-Sanz S (2016) Dandelion-encoded harmony search heuristics for opportunistic traffic offloading in synthetically modeled mobile networks. In: Harmony search algorithm, Springer, pp 133–145
Raidl GR, Julstrom BA (2003) Edge sets: an effective evolutionary coding of spanning trees. IEEE Trans Evol Comput 7(3):225–239
Reinelt G (1991) TSPLIB—A traveling salesman problem library. ORSA J Comput 3(4):376–384
Thanh PD (2019) CluSPT instances. Mendeley Data v3. https://doi.org/10.17632/b4gcgybvt6.3
Thanh PD, Dung DA, Tien TN, Binh HTT (2018) An effective representation scheme in multifactorial evolutionary algorithm for solving cluster shortest-path tree problem. In: 2018 IEEE congress on evolutionary computation (CEC), IEEE, pp 811–818
Thompson E, Paulden T, Smith DK (2007) The dandelion code: a new coding of spanning trees for genetic algorithms. IEEE Trans Evol Comput 11(1):91–100
Wu BY, Lin CW (2014) Clustered trees with minimum inter-cluster distance. In: 2014 IEEE 17th International conference on computational science and engineering (CSE), IEEE, pp 1138–1141
Wu BY, Lin CW (2015) On the clustered Steiner tree problem. J Comb Optim 30(2):370–386
Yuan Y, Ong YS, Gupta A, Tan PS, Xu H (2016) (2016) Evolutionary multitasking in permutation-based combinatorial optimization problems: Realization with tsp, qap, lop, and jsp. In: Region 10 conference (TENCON). IEEE, IEEE, pp 3157–3164