Hybrid Metaheuristic Approach to the Constrained Bi-Objective Minimum Spanning Tree

Dana  Faiq Abd; Haval  Mohammed Sidqi; Omed  Hasan Ahmed

doi:10.25098/9.2.29

Authors

Dana Faiq Abd Department of Computer Science, College of Science, Charmo University, Sulaimani, Iraq& Department of Information Technology, College of Science and Technology, University of Human Development, Sulaimani, Iraq
Haval Mohammed Sidqi Technical College of Informatics, Sulaimani Polytechnic University, Sulaimani, Iraq
Omed Hasan Ahmed Department of Information Technology, College of Science and Technology, University of Human Development, Sulaimani, Iraq

DOI:

https://doi.org/10.25098/9.2.29

Keywords:

Bi-objective Minimum Spanning Tree (MST), hybrid algorithm, constrained minimum spanning tree, Network design optimization, Pareto front diversity

Abstract

The constrained bi-objective Minimum Spanning Tree (MST) problem seeks to minimize edge weight and hop count under strict cost and delay limits. Geometry-based evolutionary algorithms, particularly AGE-MOEA, provide a distinctive advantage because they replace traditional crowding-distance survival with geometry-aware scoring based on normalized Lᵖ distances. This mechanism explicitly models the geometric structure of the Pareto front, allowing solutions to be distributed evenly across irregular or non-convex trade-off surfaces, which enhances both diversity and convergence stability. Building on this principle, we propose a Hybrid MOCPO-AGE-MOEA that integrates the exploration strength of Multi-Objective Crested Porcupine Optimization (MOCPO) with the geometry-aware survival of AGE-MOEA. The hybrid achieves novelty through multi-level integration: alternating engines across iterations to balance exploration and exploitation, cross-injecting operators for greater adaptability, and applying feasibility-first repair to guarantee valid spanning trees underweight and hop constraints. The contributions of this study are threefold: (i) formal unification of bio-inspired exploration with geometry-based survival, (ii) a feasibility-preserving framework that ensures strict constraint satisfaction, and (iii) a balanced performance profile combining Pareto diversity, hop reduction, and competitive runtime. Experiments extend earlier benchmarks from 50-node graphs to more challenging 70-node instances, where the Hybrid consistently outperforms competitors by producing nearly three times higher Pareto diversity and the lowest hop counts, thereby confirming its scalability, robustness, and deep algorithmic strength.

References

L. Amorosi, and J. Puerto, “Two‐phase strategies for the bi‐objective minimum spanning tree problem,” International Transactions in Operational Research, vol. 29, no. 6, pp. 3435-3463, 2022.

P. Correia, L. Paquete, and J. R. Figueira, “Finding multi-objective supported efficient spanning trees,” Computational Optimization and Applications, vol. 78, no. 2, pp. 491-528, 2021.

I. A. Carvalho, and A. A. Coco, “On solving bi-objective constrained minimum spanning tree problems,” Journal of Global Optimization, vol. 87, no. 1, pp. 301-323, 2023.

P. M. de las Casas, A. Sedeño-Noda, and R. Borndörfer, “New dynamic programming algorithm for the multiobjective minimum spanning tree problem,” Computers & Operations Research, vol. 173, pp. 106852, 2025.

S. Majumder, P. S. Barma, A. Biswas, P. Banerjee, B. K. Mandal, S. Kar, and P. Ziemba, “On multi-objective minimum spanning tree problem under uncertain paradigm,” Symmetry, vol. 14, no. 1, pp. 106, 2022.

X. Lai, “On Performance of a Simple Multi-objective Evolutionary Algorithm on the Constrained Minimum Spanning Tree Problem,” International Journal of Computational Intelligence Systems, vol. 15, no. 1, pp. 57, 2022.

V. P. Prakash, C. Patvardhan, and A. Srivastav, “A novel hybrid multi-objective evolutionary algorithm for the bi-objective minimum diameter-cost spanning tree (bi-mdcst) problem,” Engineering Applications of Artificial Intelligence, vol. 87, pp. 103237, 2020.

F. Shi, F. Neumann, and J. Wang, “Time complexity analysis of evolutionary algorithms for 2-hop (1, 2)-minimum spanning tree problem,” Theoretical Computer Science, vol. 893, pp. 159-175, 2021.

L. Wang, Q. Cao, Z. Zhang, S. Mirjalili, and W. Zhao, “Artificial rabbits optimization: A new bio-inspired meta-heuristic algorithm for solving engineering optimization problems,” Engineering Applications of Artificial Intelligence, vol. 114, pp. 105082, 2022.

H. Bali, A. Gill, A. Choudhary, D. Anand, F. S. Alharithi, S. M. Aldossary, and J. L. V. Mazón, “Multi-objective energy efficient adaptive whale optimization based routing for wireless sensor network,” Energies, vol. 15, no. 14, pp. 5237, 2022.

G. Fritsche, and A. Pozo, "Cooperative based hyper-heuristic for many-objective optimization." pp. 550-558.

D. Adalja, P. Patel, N. Mashru, P. Jangir, Arpita, R. Jangid, G. Gulothungan, and M. Khishe, “A new multi objective crested porcupines optimization algorithm for solving optimization problems,” Scientific Reports, vol. 15, no. 1, pp. 14380, 2025.

L. Yang, J. Cao, K. Li, Y. Zhang, R. Xu, and K. Li, “A many-objective evolutionary algorithm based on interaction force and hybrid optimization mechanism,” Swarm and Evolutionary Computation, vol. 90, pp. 101667, 2024.

I. A. Carvalho, and M. A. Ribeiro, “An exact approach for the minimum-cost bounded-error calibration tree problem,” Annals of Operations Research, vol. 287, no. 1, pp. 109-126, 2020.

J. W. Daykin, N. Mhaskar, and W. Smyth, “Computation of the suffix array, Burrows-Wheeler transform and FM-index in V-order,” Theoretical Computer Science, vol. 880, pp. 82-96, 2021.

I. A. Carvalho, “On the statistical evaluation of algorithmic's computational experimentation with infeasible solutions,” Information Processing Letters, vol. 143, pp. 24-27, 2019.

I. Akgün, and B. Ç. Tansel, “New formulations of the hop-constrained minimum spanning tree problem via miller–tucker–zemlin constraints,” European Journal of Operational Research, vol. 212, no. 2, pp. 263-276, 2011.

E. G. De Sousa, A. C. Santos, and D. J. Aloise, “An exact method for solving the bi-objective minimum diameter-cost spanning tree problem,” RAIRO-Operations Research, vol. 49, no. 1, pp. 143-160, 2015.

T. Wang, X. Wang, Z. Wang, C. Guo, B. Moran, and M. Zukerman, “Optimal tree topology for a submarine cable network with constrained internodal latency,” Journal of Lightwave Technology, vol. 39, no. 9, pp. 2673-2683, 2021.

K. Yamaoka, T. Nakashima, Y. Wakabayashi, and N. Ono, “Minimum-spanning-tree-based time delay estimation robust to outliers,” IEEE Access, vol. 11, pp. 121284-121294, 2023.

J. Augustine, S. Gilbert, F. Kuhn, P. Robinson, and S. Sourav, “Latency, capacity, and distributed minimum spanning trees,” Journal of Computer and System Sciences, vol. 126, pp. 1-20, 2022.

H. Geng, Z. Zhou, J. Shen, and F. Song, “A dual-population-based NSGA-III for constrained many-objective optimization,” Entropy, vol. 25, no. 1, pp. 13, 2022.

A. Panichella, "An improved Pareto front modeling algorithm for large-scale many-objective optimization." pp. 565-573.

K. Qiao, J. Liang, K. Yu, C. Yue, H. Lin, D. Zhang, and B. Qu, “Evolutionary constrained multiobjective optimization: Scalable high-dimensional constraint benchmarks and algorithm,” IEEE Transactions on Evolutionary Computation, vol. 28, no. 4, pp. 965-979, 2023.

Y. Yan, Q. Zhao, Z. Qin, and G. Sun, “Integration of development and advertising strategies for multi-attribute products under competition,” European Journal of Operational Research, vol. 300, no. 2, pp. 490-503, 2022.

Y. Xu, and L. Zhang, “Target-based Distributionally Robust Minimum Spanning Tree Problem,” arXiv preprint arXiv:2311.10670, 2023.

S. Cerf, B. Doerr, B. Hebras, Y. Kahane, and S. Wietheger, “The first proven performance guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a combinatorial optimization problem,” arXiv preprint arXiv:2305.13459, 2023.

A. Panichella, "An adaptive evolutionary algorithm based on non-euclidean geometry for many-objective optimization." pp. 595-603.