Abstract
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 of a connected graph , 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.
Affiliated Institutions
Related Publications
A fast and elitist multiobjective genetic algorithm: NSGA-II
Multi-objective evolutionary algorithms (MOEAs) that use non-dominated sorting and sharing have been criticized mainly for: (1) their O(MN/sup 3/) computational complexity (wher...
Scalable multi-objective optimization test problems
After adequately demonstrating the ability to solve different two-objective optimization problems, multi-objective evolutionary algorithms (MOEAs) must show their efficacy in ha...
Approximating the Set of Pareto-Optimal Solutions in Both the Decision and Objective Spaces by an Estimation of Distribution Algorithm
Most existing multiobjective evolutionary algorithms aim at approximating the Pareto front (PF), which is the distribution of the Pareto-optimal solutions in the objective space...
Skeletal graphs for efficient structure from motion
We address the problem of efficient structure from motion for large, unordered, highly redundant, and irregularly sampled photo collections, such as those found on Internet phot...
Why Propensity Scores Should Not Be Used for Matching
We show that propensity score matching (PSM), an enormously popular method of preprocessing data for causal inference, often accomplishes the opposite of its intended goal—thus ...
Publication Info
- Year
- 2025
- Type
- article
- Volume
- 17
- Issue
- 1
- Pages
- 1-13
- Citations
- 0
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
0
OpenAlex
0
Influential
0
CrossRef
Cite This
Asma Boumesbah,
Mohamed El‐Amine Chergui
(2025).
A hybrid approach to approximate the Pareto front of the MOST problem.
Croatian Operational Research Review
, 17
(1)
, 1-13.
https://doi.org/10.17535/crorr.2026.0009
Identifiers
- DOI
- 10.17535/crorr.2026.0009