mcMSTEmoaBG: Subgraph EMOA for the multi-criteria MST problem.

Description

Evolutionary multi-objective algorithm to solve the multi-objective minimum spanning tree problem. The algorithm relies to mutation only to generate offspring. The package contains the subgraph mutator (see mutSubgraphMST) or a simple one-edge exchange mutator (see mutEdgeExchange). Of course, the user may use any custom mutator which operators on edge lists as well (see makeMutator).

Usage

mcMSTEmoaBG(instance, mu, lambda = mu, mut = NULL, selMating = NULL,
  selSurvival = ecr::selNondom, ref.point = NULL, max.iter = 100L)

Value

[ecr_result] List of type ecr_result

with the following components:

task: The ecr_optimization_task.
log: Logger object.
pareto.idx: Indizes of the non-dominated solutions in the last population.
pareto.front: (n x d) matrix of the approximated non-dominated front where n is the number of non-dominated points and d is the number of objectives.
pareto.set: Matrix of decision space values resulting with objective values given in pareto.front.
last.population: Last population.
message: Character string describing the reason of termination.

Arguments

instance: [mcGP]
Multi-objective graph problem.
mu: [integer(1)]
Population size.
lambda: [integer(1)]
Number of offspring generated in each generation. Default is mu.
mut: [ecr_mutator]
Mutation operator. Default is mutSubgraphMST.
selMating: [ecr_selector]
Mating selector. Default is selSimple.
selSurvival: [ecr_selector]
Survival selector. Default is link[ecr]{selNondom}.
ref.point: [numeric(n.objectives) | NULL]
Reference point for hypervolume computation used for logging. If NULL the sum of the \(n\) largest edges in each objective is used where \(n\) is the number of nodes of instance. This is an upper bound for the size of each spanning tree with \((n-1)\) edges.
max.iter: [integer(1)]
Maximal number of iterations. Default is 100.

References

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

Examples

Run this code

inst = genRandomMCGP(10)
res = mcMSTEmoaBG(inst, mu = 20L, max.iter = 100L)
print(res$pareto.front)
print(tail(getStatistics(res$log)))