R/constraint_vbr.R
constraint_vbr.RdUses the Violation-based Ranking handling method to generate a preference index for the MOEADr framework.
constraint_vbr(bigZ, bigV, type = c("ts", "sr", "vt"), pf = NULL, ...)Matrix of scalarized objective values for each neighborhood and
the incumbent solution (generated by scalarize_values())
Matrix of violation values for each neighborhood and the
incumbent solution (generated in order_neighborhood())
type of c(x) function to use (see c(x) Criteria for details).
probability parameter for type = "sr" (ignored in other modes).
other parameters (unused, included for compatibility with generic call)
[ N x (T+1) ] matrix of preference indices. Each row i contains
a permutation of {1, 2, ..., (T+1)}, where 1,...,T correspond
to the solutions contained in the neighborhood of the i-th subproblem,
B[i, ], and T+1 corresponds to the incumbent solution for that
subproblem. The order of the permutation is defined by the specific strategy
defined by the input variable type).
This function calculates the preference index of a set of neighborhoods
based on the "violation-based ranking" (VBR) constraint handling method. Please
see order_neighborhood() for more information on the preference index
matrix.
The VBR strategy generalizes some well-known methods for handling constraints
in population-based metaheuristics (see Section c(x) Criteria).
This strategy essentially ranks points within for a given subproblem based on
their aggregated function value (f^{agg}(x|w_i)) or their total constraint
violation (v(x)). Specific variations of this strategy differ on the
criteria for using one or the other.
The value used for ranking a given point x can be summarized as:
| Violation | | c(x) criterion | | Rank using: |
v(x) = 0 | | c(x) = * | | f^{agg}(x|w_i) |
v(x) > 0 | | c(x) == TRUE | | f^{agg}(x|w_i) |
v(x) > 0 | | c(x) == FALSE | | v(x) |
Points compared according to their f^{agg}(x|w_i) values (i.e., feasible
points and those for which c(x) = TRUE) are ranked first (i.e., receive
ranks between 1 and n_{feas}, where n_{feas} is the
number of feasible points in the i-th neighborhood), with points that are
compared according to their v(x) values receiving ranks between
(n_{feas} + 1) and T + 1 (T being the size of the neighborhood. The +1
comes from including the incumbent solution in the comparison).
Specific variations of the VBR differ on how the criterion c(x) is implemented. Three variants are currently implemented in the MOEADr package:
| Method | | ID | | c(x) |
Tournament Selection [Deb2000] | | $type = "ts" | | FALSE |
Stochastic Ranking [Runarsson2000] | | $type = "sr" | | runif() < pf |
Violation Threshold [Asafuddoula2014] | | $type = "vt" | | v(x) < eps_v^i |
where \(pf \in [0,1]\) is a user-defined parameter for the "sr" method, and
eps_v^i is subproblem-dependent, adaptive quantity calculated internally
in the routine (see [Asafuddoula2014] and [Campelo2017] for details).
For types "sr" and "vt", it is possible for the algorithm to lose feasible
solutions during its update step, since there is a non-zero probability of
unfeasible solutions replacing feasible ones. In these cases, it is
recommended to set the moead() parameter update$UseArchive = TRUE, so
that an external archive is built with the best feasible solutions found for
each subproblem.
[Deb2000] K. Deb,
"An efficient constraint handling method for genetic algorithm",
Computer Methods in Applied Mechanics and Engineering 186(2–4):311–338, 2000.
[Runarsson2000] T. Runarsson, X. Yao,
"Stochastic ranking for constrained evolutionary optimization",
IEEE Transactions on Evolutionary Computation4(3):284–294, 2000.
[Asafuddoula2014] M. Asafuddoula, T. Ray, R. Sarker, K. Alam,
"An adaptive constraint handling approach embedded MOEA/D,”
2012 IEEE Congress on Evolutionary Computation (CEC).
[Campelo2017] F. Campelo, L.S. Batista, C. Aranha (2020): The MOEADr
Package: A Component-Based Framework for Multiobjective Evolutionary
Algorithms Based on Decomposition. Journal of Statistical Software
doi:10.18637/jss.v092.i06