mcMST (version 1.1.1)

mcMSTPrim: 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)

Value

[list] List with component pareto.front.

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.

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)