{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,3]],"date-time":"2025-10-03T00:45:42Z","timestamp":1759452342852,"version":"build-2065373602"},"reference-count":35,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2025,10,2]],"date-time":"2025-10-02T00:00:00Z","timestamp":1759363200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["www.mdpi.com"],"crossmark-restriction":true},"short-container-title":["Computers"],"abstract":"<jats:p>The constrained bi-objective Minimum Spanning Tree (MST) problem is a fundamental challenge in network design, as it simultaneously requires minimizing both total edge weight and maximum hop distance under strict feasibility limits; however, most existing algorithms tend to emphasize one objective over the other, resulting in imbalanced solutions, limited Pareto fronts, or poor scalability on larger instances. To overcome these shortcomings, this study introduces a Hybrid MOCPO\u2013AGE-MOEA algorithm that strategically combines the exploratory strength of Multi-Objective Crested Porcupines Optimization (MOCPO) with the exploitative refinement of the Adaptive Geometry-based Evolutionary Algorithm (AGE-MOEA), while a Kruskal-based repair operator is integrated to strictly enforce feasibility and preserve solution diversity. Moreover, through extensive experiments conducted on Euclidean graphs with 11\u2013100 nodes, the hybrid consistently demonstrates superior performance compared with five state-of-the-art baselines, as it generates Pareto fronts up to four times larger, achieves nearly 20% reductions in hop counts, and delivers order-of-magnitude runtime improvements with near-linear scalability. Importantly, results reveal that allocating 85% of offspring to MOCPO exploration and 15% to AGE-MOEA exploitation yields the best balance between diversity, efficiency, and feasibility. Therefore, the Hybrid MOCPO\u2013AGE-MOEA not only addresses critical gaps in constrained MST optimization but also establishes itself as a practical and scalable solution with strong applicability to domains such as software-defined networking, wireless mesh systems, and adaptive routing, where both computational efficiency and solution diversity are paramount<\/jats:p>","DOI":"10.3390\/computers14100422","type":"journal-article","created":{"date-parts":[[2025,10,2]],"date-time":"2025-10-02T15:07:48Z","timestamp":1759417668000},"page":"422","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Hybrid MOCPO\u2013AGE-MOEA for Efficient Bi-Objective Constrained Minimum Spanning Trees"],"prefix":"10.3390","volume":"14","author":[{"given":"Dana Faiq","family":"Abd","sequence":"first","affiliation":[{"name":"Department of Computer Science, College of Science, Charmo University, Chamchamal 46023, Sulaymaniyah, Iraq"}]},{"given":"Haval Mohammed","family":"Sidqi","sequence":"additional","affiliation":[{"name":"Technical College of Informatics, Sulaimani Polytechnic University, Sulaimaniyah 70236, Iraq"}]},{"given":"Omed Hasan","family":"Ahmed","sequence":"additional","affiliation":[{"name":"Department of Information Technology, University of Human Development, Sulaymaniyah 07786, Iraq"}]}],"member":"1968","published-online":{"date-parts":[[2025,10,2]]},"reference":[{"key":"ref_1","first-page":"534","article-title":"An efficient method to solve minimum spanning tree problem using graph theory and improved ant colony optimization algorithm","volume":"5","author":"Niluminda","year":"2022","journal-title":"N. Am. Acad. Res."},{"key":"ref_2","first-page":"223","article-title":"An approach for solving minimum spanning tree problem using a modified Ant colony optimization algorithm","volume":"10","author":"Niluminda","year":"2022","journal-title":"Am. J. Appl. Math."},{"key":"ref_3","unstructured":"Erlebach, T., de Lima, M.S., Megow, N., and Schl\u00f6ter, J. (2022). Learning-augmented query policies for minimum spanning tree with uncertainty. arXiv."},{"key":"ref_4","unstructured":"Hoeksma, R., Speek, G., and Uetz, M. (2024). Stochastic Minimum Spanning Trees with a Single Sample. arXiv."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/s44196-022-00111-7","article-title":"On Performance of a Simple Multi-objective Evolutionary Algorithm on the Constrained Minimum Spanning Tree Problem","volume":"15","author":"Lai","year":"2022","journal-title":"Int. J. Comput. Intell. Syst."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Cerulli, R., D\u2019Ambrosio, C., Serra, D., and Sorgente, C. (2024). The Budgeted Labeled Minimum Spanning Tree Problem. Mathematics, 12.","DOI":"10.3390\/math12020230"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"e12610","DOI":"10.1111\/exsy.12610","article-title":"Serial and parallel memetic algorithms for the bounded diameter minimum spanning tree problem","volume":"38","author":"Vuppuluri","year":"2021","journal-title":"Expert Syst."},{"key":"ref_8","unstructured":"Mokhtari, Y. (2025). A Heuristic ADMM-based Approach for Tree-Constrained Optimization. arXiv."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1007\/s10589-020-00251-6","article-title":"Finding multi-objective supported efficient spanning trees","volume":"78","author":"Correia","year":"2021","journal-title":"Comput. Optim. Appl."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Liu, H., Guan, X., Wan, X., and Yang, F. (2025). All-Time Dynamic Minimum Spanning Tree for Inter-Satellite Link Optimization in LEO Networks. IEEE Trans. Netw. Serv. Manag.","DOI":"10.1109\/TNSM.2025.3591111"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Pavon, W., Torres, M., and Inga, E. (2024). Integrating minimum spanning tree and MILP in urban planning: A novel algorithmic perspective. Buildings, 14.","DOI":"10.3390\/buildings14010213"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"2523","DOI":"10.1109\/TSG.2022.3164258","article-title":"Modified minimum spanning tree for optimised DC microgrid cabling design","volume":"13","author":"Kebir","year":"2022","journal-title":"IEEE Trans. Smart Grid"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"10918","DOI":"10.1109\/JSEN.2022.3166942","article-title":"An improved approach for wireless sensor networks with mobile sink using dynamic minimum spanning tree","volume":"22","author":"Wei","year":"2022","journal-title":"IEEE Sens. J."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Yang, Y.-R., Chen, Y.-S., Chen, Y.-C., and Wang, P.-C. (2023, January 11\u201313). Efficient Routing in SDN using Minimum Bottleneck Spanning Tree. Proceedings of the 2023 IEEE 6th International Conference on Knowledge Innovation and Invention (ICKII), Sapporo, Japan.","DOI":"10.1109\/ICKII58656.2023.10332635"},{"key":"ref_15","first-page":"3","article-title":"A hybrid genetic algorithm for the degree-constrained minimum spanning tree problem","volume":"24","author":"Singh","year":"2020","journal-title":"Soft Comput. Fusion Found. Methodol. Appl."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"103237","DOI":"10.1016\/j.engappai.2019.103237","article-title":"A novel hybrid multi-objective evolutionary algorithm for the bi-objective minimum diameter-cost spanning tree (bi-mdcst) problem","volume":"87","author":"Prakash","year":"2020","journal-title":"Eng. Appl. Artif. Intell."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/s12293-020-00307-4","article-title":"A PSO-inspired architecture to hybridise multi-objective metaheuristics","volume":"12","author":"Fernandes","year":"2020","journal-title":"Memetic Comput."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"4881","DOI":"10.1007\/s11276-018-01921-4","article-title":"Approximating the Pareto front of a bi-objective problem in telecommunication networks using a co-evolutionary algorithm","volume":"26","year":"2020","journal-title":"Wirel. Netw."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"107476","DOI":"10.1016\/j.measurement.2020.107476","article-title":"Hybrid of Genetic Algorithm and Minimum Spanning Tree method for optimal PMU placements","volume":"154","author":"Devi","year":"2020","journal-title":"Measurement"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/s10898-023-01295-8","article-title":"On solving bi-objective constrained minimum spanning tree problems","volume":"87","author":"Carvalho","year":"2023","journal-title":"J. Glob. Optim."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/j.tcs.2021.09.003","article-title":"Time complexity analysis of evolutionary algorithms for 2-hop (1, 2)-minimum spanning tree problem","volume":"893","author":"Shi","year":"2021","journal-title":"Theor. Comput. Sci."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/s42979-020-0120-y","article-title":"Novel heuristics for the Euclidean leaf-constrained minimum spanning tree problem","volume":"1","author":"Prakash","year":"2020","journal-title":"SN Comput. Sci."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"481","DOI":"10.26554\/sti.2022.7.4.481-485","article-title":"The Diameter and Maximum Link of the Minimum Routing Cost Spanning Tree Problem","volume":"7","author":"Sari","year":"2022","journal-title":"Sci. Technol. Indones."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Bossek, J., and Grimme, C. (2024, January 14\u201318). Generalised Kruskal Mutation for the Multi-Objective Minimum Spanning Tree Problem. Proceedings of the Genetic and Evolutionary Computation Conference, Melbourne, Australia.","DOI":"10.1145\/3638529.3654165"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"11289","DOI":"10.1007\/s00500-021-05913-z","article-title":"Artificial bee colony algorithm using permutation encoding for the bounded diameter minimum spanning tree problem","volume":"25","author":"Singh","year":"2021","journal-title":"Soft Comput."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Zhang, T., Zhou, Y., Zhou, G., Deng, W., and Luo, Q. (2022). Bioinspired bare bones mayfly algorithm for large-scale spherical minimum spanning tree. Front. Bioeng. Biotechnol., 10.","DOI":"10.3389\/fbioe.2022.830037"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"3435","DOI":"10.1111\/itor.13120","article-title":"Two-phase strategies for the bi-objective minimum spanning tree problem","volume":"29","author":"Amorosi","year":"2022","journal-title":"Int. Trans. Oper. Res."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"106852","DOI":"10.1016\/j.cor.2024.106852","article-title":"New dynamic programming algorithm for the multiobjective minimum spanning tree problem","volume":"173","year":"2025","journal-title":"Comput. Oper. Res."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1007\/s10589-019-00154-1","article-title":"Empirical study of exact algorithms for the multi-objective spanning tree","volume":"75","author":"Fernandes","year":"2020","journal-title":"Comput. Optim. Appl."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Montemanni, R., and Smith, D.H. (2025). On Solving the Minimum Spanning Tree Problem with Conflicting Edge Pairs. Algorithms, 18.","DOI":"10.3390\/a18080526"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"7628105","DOI":"10.1155\/2020\/7628105","article-title":"Degree-Constrained k-Minimum Spanning Tree Problem","volume":"2020","author":"Adasme","year":"2020","journal-title":"Complexity"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/s10107-009-0297-2","article-title":"Modelling Hop-Constrained and Diameter-Constrained Minimum Spanning Tree Problems as Steiner Tree Problems over Layered Graphs","volume":"128","author":"Gouveia","year":"2011","journal-title":"Math. Program."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1007\/s11047-018-9685-y","article-title":"A tutorial on multiobjective optimization: Fundamentals and evolutionary methods","volume":"17","author":"Emmerich","year":"2018","journal-title":"Nat. Comput."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Adalja, D., Patel, P., Mashru, N., Jangir, P., Jangid, R., Gulothungan, G., and Khishe, M. (2025). A new multi objective crested porcupines optimization algorithm for solving optimization problems. Sci. Rep., 15.","DOI":"10.1038\/s41598-025-99207-1"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Panichella, A. (2019, January 13\u201317). An adaptive evolutionary algorithm based on non-euclidean geometry for many-objective optimization. Proceedings of the Genetic and Evolutionary Computation Conference, Prague, Czech Republic.","DOI":"10.1145\/3321707.3321839"}],"container-title":["Computers"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-431X\/14\/10\/422\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,2]],"date-time":"2025-10-02T15:18:21Z","timestamp":1759418301000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-431X\/14\/10\/422"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,2]]},"references-count":35,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2025,10]]}},"alternative-id":["computers14100422"],"URL":"https:\/\/doi.org\/10.3390\/computers14100422","relation":{},"ISSN":["2073-431X"],"issn-type":[{"value":"2073-431X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,2]]}}}