mcMSTEmoaZhou: Pruefer-EMOA for the multi-objective MST problem.

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

Pruefer-EMOA for the multi-objective MST problem.

Description

Evolutionary multi-objective algorithm to solve the multi-objective minimum spanning tree problem. The algorithm adopts the so-called Pruefer-number as the encoding for spanning trees. A Pruefer-number for a graph with nodes V = \{1, \ldots, n\} is a sequence of n - 2 numbers from V. Cayleys theorem states, that a complete graph width n nodes has exactly n^{n-2} spanning trees. The algorithm uses mutation only: each component of an individual is replaced uniformly at random with another node number from the node set.

Usage

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

Arguments

instance	[grapherator] Multi-objective graph.
mu	[integer(1)] Population size.
lambda	[integer(1)] Number of offspring generated in each generation. Default is mu.
mut	[ecr_mutator] Mutation operator. Defaults to mutUniformPruefer, i.e., each digit of the Pruefer encoding is replaced with some probability with a random number from V = \{1, \ldots, n\}.
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.

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.

References

Zhou, G. and Gen, M. Genetic Algorithm Approach on Multi-Criteria Minimum Spanning Tree Problem. In: European Journal of Operational Research (1999).

See Also

Mutator mutUniformPruefer

Other mcMST EMOAs: mcMSTEmoaBG()

Other mcMST algorithms: mcMSTEmoaBG(), mcMSTPrim()

mcMST documentation built on April 1, 2023, 12:19 a.m.