mcMSTPrim {mcMST} | R Documentation |
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 |
[ |
n.lambdas |
[ |
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)