{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,25]],"date-time":"2026-06-25T07:20:23Z","timestamp":1782372023740,"version":"3.54.5"},"reference-count":32,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T00:00:00Z","timestamp":1672444800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Natural Science Foundation of China","award":["62263017"],"award-info":[{"award-number":["62263017"]}]},{"name":"National Natural Science Foundation of China","award":["202002AC080001"],"award-info":[{"award-number":["202002AC080001"]}]},{"name":"Provincial Major Research Program of Yunnan","award":["62263017"],"award-info":[{"award-number":["62263017"]}]},{"name":"Provincial Major Research Program of Yunnan","award":["202002AC080001"],"award-info":[{"award-number":["202002AC080001"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>The quadratic minimum spanning tree problem (QMSTP) is a spanning tree optimization problem that considers the interaction cost between pairs of edges arising from a number of practical scenarios. This problem is NP-hard, and therefore there is not a known polynomial time approach to solve it. To find a close-to-optimal solution to the problem in a reasonable time, we present for the first time a clustering-enhanced memetic algorithm (CMA) that combines four components, i.e., (i) population initialization with clustering mechanism, (ii) a tabu-based nearby exploration phase to search nearby local optima in a restricted area, (iii) a three-parent combination operator to generate promising offspring solutions, and (iv) a mutation operator using L\u00e9vy distribution to prevent the population from premature. Computational experiments are carried on 36 benchmark instances from 3 standard sets, and the results show that the proposed algorithm is competitive with the state-of-the-art approaches. In particular, it reports improved upper bounds for the 25 most challenging instances with unproven optimal solutions, while matching the best-known results for all but 2 of the remaining instances. Additional analysis highlights the contribution of the clustering mechanism and combination operator to the performance of the algorithm.<\/jats:p>","DOI":"10.3390\/e25010087","type":"journal-article","created":{"date-parts":[[2023,1,2]],"date-time":"2023-01-02T04:51:22Z","timestamp":1672635082000},"page":"87","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Clustering-Enhanced Memetic Algorithm for the Quadratic Minimum Spanning Tree Problem"],"prefix":"10.3390","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6412-7949","authenticated-orcid":false,"given":"Shufan","family":"Zhang","sequence":"first","affiliation":[{"name":"Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jianlin","family":"Mao","sequence":"additional","affiliation":[{"name":"Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Niya","family":"Wang","sequence":"additional","affiliation":[{"name":"Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dayan","family":"Li","sequence":"additional","affiliation":[{"name":"Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chengan","family":"Ju","sequence":"additional","affiliation":[{"name":"Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2022,12,31]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/j.disopt.2017.09.003","article-title":"The quadratic minimum spanning tree problem and its variations","volume":"27","author":"Zhang","year":"2018","journal-title":"Discrete Optim."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1002\/net.21787","article-title":"Polyhedral results, branch-and-cut and Lagrangian relaxation algorithms for the adjacent only quadratic minimum spanning tree problem","volume":"71","author":"Pereira","year":"2018","journal-title":"Networks"},{"key":"ref_3","first-page":"4","article-title":"Metaheuristic approaches for the quadratic minimum spanning tree problem","volume":"39","author":"Palubeckis","year":"2010","journal-title":"Inf. Technol. Control"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1016\/j.ejor.2019.12.042","article-title":"Dynamic intersection of multiple implicit Dantzig\u2013Wolfe decompositions applied to the adjacent only quadratic minimum spanning tree problem","volume":"284","author":"Pereira","year":"2020","journal-title":"Eur. J. Oper. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"e12364","DOI":"10.1111\/exsy.12364","article-title":"Rough-fuzzy quadratic minimum spanning tree problem","volume":"36","author":"Majumder","year":"2019","journal-title":"Expert Syst."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1007\/s10878-017-0184-3","article-title":"A characterization of linearizable instances of the quadratic minimum spanning tree problem","volume":"35","author":"Punnen","year":"2018","journal-title":"J. Comb. Optim."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1002\/1520-6750(199204)39:3<399::AID-NAV3220390309>3.0.CO;2-0","article-title":"The quadratic minimum spanning tree problem","volume":"39","author":"Assad","year":"1992","journal-title":"Naval Res. Log. (NRL)"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"11597","DOI":"10.1016\/j.amc.2012.05.043","article-title":"Solving the quadratic minimum spanning tree problem","volume":"218","author":"Cordone","year":"2012","journal-title":"Appl. Math. Comput."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/j.cor.2015.04.020","article-title":"Lower bounds and exact algorithms for the quadratic minimum spanning tree problem","volume":"63","author":"Pereira","year":"2015","journal-title":"Comput. Oper. Res."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1016\/j.cor.2015.06.005","article-title":"Lower bounds for the quadratic minimum spanning tree problem based on reduced cost computation","volume":"64","author":"Rostami","year":"2015","journal-title":"Comput. Oper. Res."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1016\/j.ejor.2019.07.038","article-title":"Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem","volume":"280","author":"Pereira","year":"2020","journal-title":"Eur. J. Oper. Res."},{"key":"ref_12","unstructured":"Sotirov, R., and Verch\u00e9re, M. (2021). The quadratic minimum spanning tree problem: Lower bounds via extended formulations. arXiv."},{"key":"ref_13","first-page":"1","article-title":"A review of population-based meta-heuristic algorithms","volume":"5","author":"Beheshti","year":"2013","journal-title":"Int. J. Adv. Soft Comput. Appl."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/S0305-0548(97)00039-7","article-title":"An effective genetic algorithm approach to the quadratic minimum spanning tree problem","volume":"25","author":"Zhout","year":"1998","journal-title":"Comput. Oper. Res."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"3182","DOI":"10.1016\/j.ins.2010.05.001","article-title":"A swarm intelligence approach to the quadratic minimum spanning tree problem","volume":"180","author":"Sundar","year":"2010","journal-title":"Inf. Sci."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1762","DOI":"10.1016\/j.cor.2010.01.004","article-title":"The quadratic minimum spanning tree problem: A lower bounding procedure and an efficient search algorithm","volume":"37","author":"Punnen","year":"2010","journal-title":"Comput. Oper. Res."},{"key":"ref_17","unstructured":"Cordone, R., and Passeri, G. (2008, January 13\u201315). Heuristic and exact algorithms for the quadratic minimum spanning tree problem. Proceedings of the 7th Cologne-Twente CTW08 Workshop on Graphs and Combinatorial Optimization, Gargnano, Italy."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1080\/0740817X.2013.768785","article-title":"Tabu search with strategic oscillation for the quadratic minimum spanning tree","volume":"46","author":"Lozano","year":"2014","journal-title":"IIE Trans."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/j.engappai.2015.08.012","article-title":"A three-phase search approach for the quadratic minimum spanning tree problem","volume":"46","author":"Fu","year":"2015","journal-title":"Eng. Appl. Artif. Intell."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Hao, J.K. (2012). Memetic algorithms in discrete optimization. Handbook of Memetic Algorithms, Springer.","DOI":"10.1007\/978-3-642-23247-3_6"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/j.cor.2017.09.008","article-title":"A hybrid dynamic programming and memetic algorithm to the traveling salesman problem with hotel selection","volume":"90","author":"Lu","year":"2018","journal-title":"Comput. Oper. Res."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"103890","DOI":"10.1016\/j.engappai.2020.103890","article-title":"An effective memetic algorithm for the generalized bike-sharing rebalancing problem","volume":"95","author":"Lu","year":"2020","journal-title":"Eng. Appl. Artif. Intell."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"664","DOI":"10.1016\/j.neucom.2017.06.053","article-title":"A review of clustering techniques and developments","volume":"267","author":"Saxena","year":"2017","journal-title":"Neurocomputing"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1007\/s00453-012-9717-4","article-title":"Analysis of agglomerative clustering","volume":"69","author":"Ackermann","year":"2014","journal-title":"Algorithmica"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Yang, X.S. (2012, January 3\u20137). Flower pollination algorithm for global optimization. Proceedings of the International Conference on Unconventional Computing and Natural Computation, Orl\u00e9ans, France.","DOI":"10.1007\/978-3-642-32894-7_27"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Neri, F. (2012). Diversity management in memetic algorithms. Handbook of Memetic Algorithms, Springer.","DOI":"10.1007\/978-3-642-23247-3"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1504\/IJICA.2014.066493","article-title":"Evolutionary algorithms for the bi-objective adjacent only quadratic spanning tree","volume":"6","author":"Maia","year":"2014","journal-title":"Int. J. Innov. Comput. Appl."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"385","DOI":"10.12720\/jcm.9.5.385-390","article-title":"Uncertain Quadratic Minimum Spanning Tree Problem","volume":"9","author":"Zhou","year":"2014","journal-title":"J. Commun."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1016\/j.ejor.2021.12.019","article-title":"Learning-driven feasible and infeasible tabu search for airport gate assignment","volume":"302","author":"Li","year":"2021","journal-title":"Eur. J. Oper. Res."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Zhou, Q., Hao, J.K., Jiang, Z.Z., and Wu, Q. (2022). Adaptive Feasible and Infeasible Evolutionary Search for the Knapsack Problem with Forfeits. SSRN Electron. J.","DOI":"10.2139\/ssrn.4263608"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1016\/j.ejor.2021.04.032","article-title":"Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: A state-of-the-art","volume":"296","author":"Mamaghan","year":"2021","journal-title":"Eur. J. Oper. Res."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Zhang, J., Liu, C., Yan, J., Li, X., Zhen, H.L., and Yuan, M. (2022). A Survey for Solving Mixed Integer Programming via Machine Learning. arXiv.","DOI":"10.1016\/j.neucom.2022.11.024"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/1\/87\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:49:16Z","timestamp":1760147356000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/1\/87"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,31]]},"references-count":32,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,1]]}},"alternative-id":["e25010087"],"URL":"https:\/\/doi.org\/10.3390\/e25010087","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,31]]}}}