![](https://csdnimg.cn/release/download_crawler_static/11439024/bg4.jpg)
4 IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2000. TEC#311R
from its unconstrained one because the initial low r
g
value would drive search towards the unconstrained
global optimum and thus further away from the constrained one.
The traditional constraint-handling technique used in evolution strategies falls roughly into the category
of over-penalization since all infeasible individuals are regarded worse than feasible ones [20], [4], [11]. In
fact, canonical evolution strategies (ES) allow only feasible individuals in the initial population. To perform
constrained optimization an ES may be used to find a feasible initial population by minimizing the penalty
function ([20], page 115). Once a feasible population is found, the ES algorithm will then minimize the
objective function and reject all infeasible solutions generated.
It has been widely recognized that neither under- nor over-penalization is a good constraint-handling tech-
nique and there should be a balance between preserving feasible individuals and rejecting infeasible ones [7].
In other words, ranking should be dominated by a combination of objective and penalty functions and so the
penalty coefficient
r
g
should be within the bounds:
r
g
< r
g
< r
g
. It is worth noting that the two bounds
are not fixed. They are problem dependent and may change from generation to generation as they are also
determined by the current population.
A simple way to measure the balance of dominance of objective and penalty functions is to count how
many comparisons of adjacent pairs are dominated by the objective and penalty function respectively. Such a
number of comparisons can be computed for any given
r
g
by counting the number of critical penalty coefficients
given by (8) which are greater than
r
g
. If we have a predetermined preference for the number of adjacent
comparisons that should be dominated by the penalty function then a corresponding penalty coefficient could
be found.
It is clear from the analysis in this section that all a penalty method tries to do is to obtain the right balance
between objective and penalty functions so that the search moves towards the optimum in the feasible space,
not just towards the optimum in the combined feasible and infeasible space. One way to achieve such balancing
effectively and efficiently is to adjust such balance directly and explicitly. This is what stochastic ranking,
described in the next section, does.
B. Stochastic Ranking
Since the optimal
r
g
is hard to determine, a different approach is used here to balance the dominance of
the objective and penalty function. We introduce a probability P
f
of using only the objective function for
comparisons in ranking in the infeasible regions of the search space. That is, given any pair of two adjacent
individuals, the probability of comparing them (in order to determine which one is fitter) according to the
objective function is 1 if both individuals are feasible, otherwise it is P
f
. This appears to be similar to the use
of a probability by Surry and Radcliffe [23] in deciding the outcome of competitions between two individuals
in tournament selection. Our technique is, however, quite different because we use rank-based selection and
we do not have any extra computational cost for self-adapting P
f
. More importantly, the motivation of
stochastic ranking comes from the need for balancing objective and penalty functions directly and explicitly
in optimization. Surry and Radcliffe’s method [23] does not attempt to balance the dominance of penalty and
objective functions in a population.
Ranking is achieved by a bubble-sort-like procedure
2
in our work. The procedure provides a convenient
way of balancing the dominance in a ranked set. In our bubble-sort-like pro cedure, λ individuals are ranked
by comparing adjacent individuals in at least λ sweeps
3
. The procedure is halted when no change in the rank
ordering occurs within a complete sweep. Figure 1 shows the stochastic bubble sort procedure used to rank
individuals in a population.
The probability of an adjacent individual winning a comparison, i.e., holding the higher rank, in the ranking
procedure is
P
w
=
P
fw
P
f
+ P
φw
(1
− P
f
) (9)
given that at least one individual is infeasible. P
fw
is the probability of the individual winning according to
the objective function and
P
φw
is the probability of the individual winning according to the penalty function.
2
It can be regarded as the stochastic version of the classic bubble sort.
3
It would be exactly λ
sweeps if the comparisons were not made stochastic.