mcMSTEmoaBG {mcMST}

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

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

...

[any]
Further parameters passed to mutator.

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

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)

See Also

Mutators mutSubgraphMST and mutEdgeExchange

Other mcMST EMOAs: mcMSTEmoaZhou()

Other mcMST algorithms: mcMSTEmoaZhou(), mcMSTPrim()

Examples

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