Multi-Objective Minimum Spanning Tree via NSGA-II with Local Search

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) .


Reference manual

It appears you don't have a PDF plugin for this browser. You can click here to download the reference manual.

install.packages("momst")

0.1.1 by Jorge A. Parraga-Alava, 3 months ago


https://github.com/jorgeklz/momst, https://jorgeklz.github.io/momst/


Report a bug at https://github.com/jorgeklz/momst/issues


Browse source code at https://github.com/cran/momst


Authors: Jorge A. Parraga-Alava [aut, cre] (ORCID:


Documentation:   PDF Manual  


GPL (>= 3) license


Imports stats, utils, graphics

Suggests igraph, knitr, rmarkdown, testthat


See at CRAN