Izvorni znanstveni članak
https://doi.org/10.17535/crorr.2026.0009
A hybrid approach to approximate the Pareto front of the MOST problem
Asma Boumesbah
orcid.org/0000-0001-5896-0002
; Faculty of Mathematics, University of Science and Technology Houari Boumediene, RECITS Laboratory, Algiers, Algeria.
*
Mohamed El-Amine Chergui
; Faculty of Mathematics, University of Science and Technology Houari Boumediene, RECITS Laboratory, Algiers, Algeria.
* Dopisni autor.
Sažetak
This study introduces a hybrid NSGA-II algorithm with Multi-VNS for approximating the Pareto front of the multi-objective spanning tree (MOST) problem, building on recent approaches that have adapted NSGA-II combined with local search heuristics. By exploiting the property that a spanning tree is acyclic and that the addition of an edge generates a unique cycle, our mutation operator adds edges to a given spanning tree $T$ of a connected graph $G$, thereby reducing the size of the MOST problem. By applying the exact mutation operator with low probability, this reduced problem is solved, producing a set of mutant solutions. The NSGA-II selection operator then approximates the Pareto front, which is further refined by a Multi-VNS metaheuristic to balance diversification and intensification. Comparative experiments with both exact and approximate methods demonstrate promising results.
Ključne riječi
hybridization methods; metaheuristics; multi-objective spanning tree problem
Hrčak ID:
340600
URI
Datum izdavanja:
9.12.2025.
Posjeta: 578 *