Description
Multi-Objective Minimum Spanning Tree via NSGA-II with Local Search.
Description
Solves the Multi-Criteria Minimum Spanning Tree (mc-MST) problem on complete weighted graphs by combining the Non-dominated Sorting Genetic Algorithm II (NSGA-II) with optional Pareto local search operators. Chromosomes are represented as Prufer sequences so that every random individual decodes to a valid spanning tree (Cayley's theorem), avoiding repair operators. Four solver variants are provided: pure NSGA-II ("base"), Path Relinking ("PR"), Pareto Local Search ("PLS"), and Tabu Search ("TS"). The package supports 2 and 3 objective formulations and provides convenience functions to plot Pareto fronts and best-compromise spanning trees. This package is the reference implementation of the method described in Parraga-Alava, Inostroza-Ponta and Dorn (2017) <doi:10.1109/CEC.2017.7969432>.