×

Evolutionary algorithm and multifactorial evolutionary algorithm on clustered shortest-path tree problem. (English) Zbl 1483.68510

Summary: In literature, Clustered Shortest-Path Tree Problem (CluSPT) is an NP-hard problem. Previous studies focus on approximation algorithms which search for an optimal solution in relatively large space. Thus, these algorithms consume a large amount of computational resources while the quality of obtained results is lower than expected. In order to enhance the performance of the search process, this paper proposes two different approaches which are inspired by two perspectives of analyzing the CluSPT. The first approach intuition is to narrow down the search space by reducing the original graph into a multi-graph with fewer nodes while maintaining the ability to find the optimal solution. The problem is then solved by a proposed evolutionary algorithm. This approach performs well on those datasets having small number of edges between clusters. However, the increase in the size of the datasets would cause the excessive redundant edges in multi-graph that pressurize searching for potential solutions. The second approach overcomes this limitation by breaking down the multi-graph into a set of simple graphs. Every graph in this set is corresponding to a mutually exclusive search space. From this point of view, the problem could be modeled into a bi-level optimization problem in which the search space includes two nested search spaces. Accordingly, the Nested Local Search Evolutionary Algorithm (N-LSEA) is introduced to search for the optimal solution of glscluspt, the upper level uses a simple Local Search algorithm while the lower level uses the Genetic Algorithm. Due to the neighboring characteristics of the local search step in the upper level, the lower level reduced graphs share the common traits among each others. Thus, the Multi-tasking Local Search Evolutionary Algorithm (MLSEA) is proposed to take advantages of these underlying commonalities by exploiting the implicit transfer across similar tasks of multi-tasking schemes. The improvement in experimental results over N-LSEA via this multi-tasking scheme inspires the future works to apply M-LSEA in graph-based problems, especially for those could be modeled into bi-level optimization.

MSC:

68W50 Evolutionary algorithms, genetic algorithms (computational aspects)
90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming

Software:

GTSP-LIB
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Angelo, J.S., Krempser, E., Barbosa, H.J., 2014. Differential evolution assisted by a surrogate model for bilevel programming problems, in: 2014 IEEE Congress on Evolutionary Computation (CEC), IEEE, pp. 1784-1791.
[2] Bali, K. K.; Ong, Y.-S.; Gupta, A.; Tan, P. S., Multifactorial evolutionary algorithm with online transfer parameter estimation: Mfea-ii, IEEE Trans. Evol. Comput., 24, 1, 69-83 (2019)
[3] Bard, J. F., Practical Bilevel Optimization: Algorithms and Applications, vol. 30 (2013), Springer Science & Business Media
[4] Binh, H. T.T.; Thanh, P. D.; Thang, T. B., 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 (2019)
[5] H.T.T. Binh, P.D. Thanh, T.B. Trung, L.P. Thao, Effective multifactorial evolutionary algorithm for solving the cluster shortest path tree problem, in: 2018 IEEE Congress on Evolutionary Computation (CEC), IEEE, 2018, pp. 819-826.
[6] Camacho-Vallejo, J.-F.; Mar-Ortiz, J.; López-Ramos, F.; Rodríguez, R. P., A genetic algorithm for the bi-level topological design of local area networks, PloS One, 10, 6, Article e0128067 pp. (2015)
[7] Carrasco, J.; García, S.; Rueda, M. M.; Das, S.; Herrera, F., Recent trends in the use of statistical tests for comparing swarm and evolutionary computing algorithms: practical guidelines and a critical review, Swarm Evol. Comput. (2020), 100665
[8] Cheng, M.-Y.; Gupta, A.; Ong, Y.-S.; Ni, Z.-W., Coevolutionary multitasking for concurrent global optimization: with case studies in complex engineering design, Eng. Appl. Artif. Intell., 64, 13-24 (2017)
[9] D’Emidio, M.; Forlizzi, L.; Frigioni, D.; Leucci, S.; Proietti, G., Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem, J. Combinat. Optim., 38, 1, 165-184 (2019) · Zbl 1426.90244
[10] Derrac, J.; García, S.; Molina, D.; Herrera, F., A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms, Swarm Evol. Comput., 1, 1, 3-18 (2011)
[11] Dror, M.; Haouari, M.; Chaouachi, J., Generalized spanning trees, Eur. J. Oper. Res., 120, 3, 583-592 (2000) · Zbl 0985.90076
[12] Eiben, A. E.; Smith, J. E., Introduction to Evolutionary Computing, vol. 53 (2003), Springer · Zbl 1028.68022
[13] L. Feng, W. Zhou, L. Zhou, S. Jiang, J. Zhong, B. Da, Z. Zhu, Y. Wang, An empirical study of multifactorial pso and multifactorial de, in: 2017 IEEE Congress on Evolutionary Computation (CEC), IEEE, 2017, pp. 921-928.
[14] R. Franz, Representations for genetic and evolutionary algorithms, 2006.
[15] Gupta, A.; Mańdziuk, J.; Ong, Y.-S., Evolutionary multitasking in bi-level optimization, Complex Intell. Syst., 1, 1-4, 83-95 (2015)
[16] Gupta, A.; Ong, Y.-S.; Feng, L., Multifactorial evolution: toward evolutionary multitasking, IEEE Trans. Evol. Comput., 20, 3, 343-357 (2016)
[17] Hansen, P.; Jaumard, B.; Savard, G., New branch-and-bound rules for linear bilevel programming, SIAM J. Sci. Stat. Comput., 13, 5, 1194-1217 (1992) · Zbl 0760.65063
[18] Helsgaun, K., Solving the bottleneck traveling salesman problem using the lin-kernighan-helsgaun algorithm, Comput. Sci. Res. Rep., 143, 1-45 (2011)
[19] M.M. Islam, H.K. Singh, T. Ray, A memetic algorithm for solving single objective bilevel optimization problems, in: 2015 IEEE Congress on Evolutionary Computation (CEC), IEEE, 2015, pp. 1643-1650
[20] B.A. Julstrom, 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, 2005, pp. 585-590
[21] H. Jung, S. Choi, B.B. Park, H. Lee, S.H. Son, Bi-level optimization for eco-traffic signal system, in: 2016 International Conference on Connected Vehicles and Expo (ICCVE), IEEE, 2016, pp. 29-35
[22] Lin, C.-W.; Wu, B. Y., On the minimum routing cost clustered tree problem, J. Combinat. Optim., 33, 3, 1106-1121 (2017) · Zbl 1372.90096
[23] Mathieu, R.; Pittard, L.; Anandalingam, G., Genetic algorithm based approach to bi-level linear programming, RAIRO-Oper. Res., 28, 1, 1-21 (1994) · Zbl 0857.90083
[24] Mestria, M.; Ochi, L. S.; de Lima Martins, S., Grasp with path relinking for the symmetric euclidean clustered traveling salesman problem, Comput. Oper. Res., 40, 12, 3218-3229 (2013) · Zbl 1348.90548
[25] Migdalas, A., Bilevel programming in traffic planning: models, methods and challenge, J. Global Optim., 7, 4, 381-405 (1995) · Zbl 0844.90050
[26] Myung, Y.-S.; Lee, C.-H.; Tcha, D.-W., On the generalized minimum spanning tree problem, Networks, 26, 4, 231-241 (1995) · Zbl 0856.90117
[27] V. Oduguwa, R. Roy, Bi-level optimisation using genetic algorithm. In: 2002 IEEE International Conference on Artificial Intelligence Systems, 2002. (ICAIS 2002), IEEE, 2002, pp. 322-327.
[28] Ong, Y.-S.; Gupta, A., Evolutionary multitasking: a computer science view of cognitive multitasking, Cogn. Comput., 8, 2, 125-142 (2016)
[29] C.C. Palmer, A. Kershenbaum, Representing trees in genetic algorithms, in: Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence, IEEE, 1994, pp. 379-384
[30] T. Paulden, D.K. Smith, Recent advances in the study of the dandelion code, happy code, and blob code spanning tree representations, in: 2006 IEEE International Conference on Evolutionary Computation, IEEE, 2006, pp. 2111-2118.
[31] C. Perfecto, M.N. Bilbao, J. Del Ser, A. Ferro, S. Salcedo-Sanz, Dandelion-encoded harmony search heuristics for opportunistic traffic offloading in synthetically modeled mobile networks, in: Harmony Search Algorithm, Springer, 2016, pp. 133-145.
[32] Pop, P.; Matei, O.; Pintea, C., A two-level diploid genetic based algorithm for solving the family traveling salesman problem, (Proceedings of the Genetic and Evolutionary Computation Conference (2018)), 340-346
[33] Prisco, J., Fiber optic regional area networks in new york and dallas, IEEE J. Select. Areas Commun., 4, 5, 750-757 (1986)
[34] Raidl, G. R.; Julstrom, B. A., Edge sets: an effective evolutionary coding of spanning trees, IEEE Trans. Evol. Comput., 7, 3, 225-239 (2003)
[35] Smith, S. L.; Imeson, F., Glns: an effective large neighborhood search heuristic for the generalized traveling salesman problem, Comput. Oper. Res., 87, 1-19 (2017) · Zbl 1391.90535
[36] Thanh, P. D., CluSPT instances, Mend. Data, v3 (2018), URL:https://data.mendeley.com/datasets/b4gcgybvt6/3
[37] P.D. Thanh, H.T.T. Binh, N.B. Long, et al., A heuristic based on randomized greedy algorithms for the clustered shortest-path tree problem, in: 2019 IEEE Congress on Evolutionary Computation (CEC), IEEE, 2019, pp. 2915-2922
[38] Thanh, P. D.; Binh, H. T.T.; Trung, T. B., An efficient strategy for using multifactorial optimization to solve the clustered shortest path tree problem, Appl. Intell., 1-26 (2020)
[39] P.D. Thanh, D.A. Dung, T.N. Tien, H.T.T. Binh, An effective representation scheme in multifactorial evolutionary algorithm for solving cluster shortest-path tree problem. In: 2018 IEEE Congress on Evolutionary Computation (CEC), IEEE, 2018, pp. 811-818.
[40] D. Thierens, P.A. Bosman, Hierarchical problem solving with the linkage tree genetic algorithm, in: Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation, ACM, 2013, pp. 877-884
[41] Thompson, E.; Paulden, T.; Smith, D. K., The dandelion code: a new coding of spanning trees for genetic algorithms, IEEE Trans. Evol. Comput., 11, 1, 91-100 (2007)
[42] Wu, B. Y.; Lin, C.-W., On the clustered steiner tree problem, J. Combinat. Optim., 30, 2, 370-386 (2015) · Zbl 1327.90271
[43] Yin, Y., Genetic-algorithms-based approach for bilevel programming models, J. Transp. Eng., 126, 2, 115-120 (2000)
[44] Y. Yuan, Y.-S. Ong, A. Gupta, P.S. Tan, H. Xu, Evolutionary multitasking in permutation-based combinatorial optimization problems: Realization with tsp, qap, lop, and jsp, in: Region 10 Conference (TENCON), 2016 IEEE, IEEE, 2016, pp. 3157-3164
[45] Zhang, T.; Chen, Z.; Zheng, Y.; Chen, J., An improved simulated annealing algorithm for bilevel multiobjective programming problems with application, J. Nonlinear Sci. Appl., 9, 6, 3672-3685 (2016) · Zbl 1338.65173
[46] T. Zhang, T. Hu, Y. Zheng, X. Guo, An improved particle swarm optimization for solving bilevel multiobjective programming problem. J. Appl. Math. (2012). · Zbl 1244.90251
[47] L. Zhou, L. Feng, J. Zhong, Y.-S. Ong, Z. Zhu, E. Sha, Evolutionary multitasking in combinatorial search spaces: A case study in capacitated vehicle routing problem, in: 2016 IEEE Symposium Series on Computational Intelligence (SSCI), IEEE, 2016, pp. 1-8.
[48] Zhuang, L.; Chen, X.; Guan, X., A bi-level optimization for an hvac system, Cluster Comput., 20, 4, 3237-3249 (2017)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.