mcMSTPrim: Multi-Objective Prim algorithm.

In jakobbossek/rmoco: A Toolbox for the Multi-Criteria Minimum Spanning Tree Problem

Multi-Objective Prim algorithm.

Description

Approximates the Pareto-optimal mcMST front of a multi-objective graph problem by iteratively applying Prim's algorithm for the single-objective MST problem to a scalarized version of the problem. I.e., the weight vector (w_1, w_2) of an edge (i, j) is substituted with a weighted sum \lambda_i w_1 + (1 - \lambda_i) w_2 for different weights \lambda_i \in [0, 1].

Usage

mcMSTPrim(instance, n.lambdas = NULL, lambdas = NULL)

Arguments

instance	[grapherator] Graph.
n.lambdas	[integer(1) | NULL] Number of weights to generate. The weights are generated equdistantly in the interval [0, 1].
lambdas	[numerci] Vector of weights. This is an alternative to n.lambdas.

Value

[list] List with component pareto.front.

Note

Note that this procedure can only find socalled supported efficient solutions, i.e., solutions on the convex hull of the Pareto-optimal front.

References

J. D. Knowles and D. W. Corne, "A comparison of encodings and algorithms for multiobjective minimum spanning tree problems," in Proceedings of the 2001 Congress on Evolutionary Computation (IEEE Cat. No.01TH8546), vol. 1, 2001, pp. 544–551 vol. 1.

See Also

Other mcMST algorithms: mcMSTEmoaBG(), mcMSTEmoaZhou()

Examples

g = genRandomMCGP(30)
res = mcMSTPrim(g, n.lambdas = 50)
print(res$pareto.front)

jakobbossek/rmoco documentation built on March 21, 2023, 9:09 p.m.