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.
mcMSTEmoaZhou(instance, mu, lambda = mu, mut = mutUniformPruefer,
selMating = ecr::selSimple, selSurvival = ecr::selNondom,
ref.point = NULL, max.iter = 100L)[ecr_result] List of type ecr_result
with the following components:
The ecr_optimization_task.
Logger object.
Indizes of the non-dominated solutions in the last population.
(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.
Matrix of decision space values resulting with objective values given in pareto.front.
Last population.
Character string describing the reason of termination.
[mcGP]
Multi-objective graph problem.
[integer(1)]
Population size.
[integer(1)]
Number of offspring generated in each generation.
Default is mu.
[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\}\).
[ecr_selector]
Mating selector.
Default is selSimple.
[ecr_selector]
Survival selector.
Default is link[ecr]{selNondom}.
[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.
[integer(1)]
Maximal number of iterations.
Default is 100.
Zhou, G. and Gen, M. Genetic Algorithm Approach on Multi-Criteria Minimum Spanning Tree Problem. In: European Journal of Operational Research (1999).
Mutator mutUniformPruefer
Other mcMST EMOAs: mcMSTEmoaBG
Other mcMST algorithms: mcMSTEmoaBG,
mcMSTPrim