jakobbossek/mcMST


Algorithms to solve the multi-criteria minimum spanning tree problem (mcMST) in R

License: BSD-2-Clause

Language: R

Keywords: cran, evolutionary-algorithms, mcmst, minimum-spanning-trees, multi-objective-optimization, r, spanningtrees


mcMST: A Toolbox for the Multi-Criteria Minimum Spanning Tree Problem

CRAN Status Badge CRAN Downloads CRAN Downloads Build Status Build status Coverage Status

Introduction

It is well known, that the single-objective spanning tree problem (MST) is solvable in polynomial time, e.g., by the Prim's algorithm. However, in real-world applications, e.g., in network design, often multiple conflicting objectives have to be considered simultaneously. The multi-criteria version of the MST is NP-hard. The mcMST package for the R programming language contains several methods for solving the multi-criteria spanning tree problem (mcMST).

Key features of the mcMST package are:

  • A multi-objective version of Prim's algorithm.
  • Evolutionary multi-objective algorithms (based on the Prüfer-encoding or direct edge list representation) with several mutation operators.
  • A modular approach for benchmark problem generation (outsourced to R package grapherator.)

Example

Here we first generate a bi-criteria graph problem with n = 25 nodes with grapherator. The first objective is the euclidean distance of node coordinates in the euclidean plane [0, 10] x [0, 10]. The second objective follows a normal distribution (N(5, 1.5)).

library(grapherator) # install from github repo (not yet on CRAN)
set.seed(1)
g = graph(lower = 0, upper = 100)
g = addNodes(g, n = 25, generator = addNodesUniform)
g = addEdges(g, generator = addEdgesDelauney)
g = addWeights(g, generator = addWeightsDistance, method = "euclidean")
g = addWeights(g, generator = addWeightsRandom, method = rnorm, mean = 5, sd = 1.5)
print(g)

Next, we apply the multi-objective evolutionary algorithm proposed by Bossek & Grimme with population size mu = 10 and number of offspring lambda = 10 for max.iter = 100 generations.

library(ggplot2)
res = mcMSTEmoaBG(g, mu = 30L, max.iter = 300L)
ecr::plotFront(res$pareto.front)

See the package vignettes for more details.

Installation Instructions

Install the CRAN release version via:

install.packages("mcMST")

If you are interested in trying out and playing around with the current development version use the devtools package and install directly from GitHub:

install.packages("devtools", dependencies = TRUE)
devtools::install_github("jakobbossek/mcMST")

Contributing to mcMST

If you encounter problems using this software, e.g., bugs or insufficient/misleading documentation, or you simply have a question, feel free to open an issue in the issue tracker. In order to reproduce potential problems, please provide a minimal and reproducible code example.

Contributions to this software package are welcome via pull requests and will be merged at the sole discretion of the author.

Publications

The following publications are strongly related to the package.

Bossek, J., & Grimme, C. (2017). A Pareto-Beneficial Sub-Tree Mutation for the Multi-Criteria Minimum Spanning Tree Problem. In Proceedings of the IEEE Symposium Series on Computational Intelligence, Honolulu, Hawai.

Bossek, J. (2017). mcMST: A Toolbox for the Multi-Criteria Minimum Spanning Tree Problem. The Journal of Open Source Software, 2017.

Related work

The following packages provide methods to solve the single-objective MST problem:

Several packages implement methods to solve multi-criteria optimization problems in general:

Project Statistics

Sourcerank 4
Repository Size 755 KB
Stars 1
Forks 1
Watchers 1
Open issues 3
Dependencies 16
Contributors 2
Tags 3
Created
Last updated
Last pushed

Top Contributors See all

Jakob Bossek George G. Vega Yon

Packages Referencing this Repo

mcMST
A Toolbox for the Multi-Criteria Minimum Spanning Tree Problem
Latest release 1.0.1 - Updated - 1 stars

Recent Tags See all

v1.0.1 September 18, 2017
v1.0.0 July 11, 2017
v1.0.0 July 11, 2017

Something wrong with this page? Make a suggestion

Last synced: 2018-01-16 16:54:50 UTC

Login to resync this repository