Constraint Handling Heuristics for Evolution Strategies - Self-Adaptive Heuristics for Evolutionary Computation - page 129

parameters μ, μ ,λ and λ : further experiments showed that we can reduce the
number of fitness function calls by decreasing the population sizes, e.g. with a
[3 / 2 , 15(3 / 2 , 15)]-NAES. But smaller population sizes are not always sucient
to guarantee the diversity in the outer population that is necessary to find the
correct rotation angles.

7.6.3 Outlook: Covariance Matrix Adaptation by Feasibility

Classification

In the previous section 7.6 we introduced the idea of rotating the axes of the
mutation ellipsoid parallel to the constraint boundary. But the angle of the ro-
tation can also be calculated: similar to the CMA-ES [54] we propose to sample
the search space at the constraint boundary and calculate the hyperplane that
separates feasible from infeasible points. On way to learn the separating hyper-
plane is the perceptron algorithm [120]. Transforming the feasible and infeasible
sample points x j into the sample points z j =( x 1 ,...,x N , 1) the perceptron
algorithm is looking for the N+1 dimensional vector w that separates the two
classes z i w T > 0forthefeasiblepointsfromand z i w T < 0 for the infeasible
ones. The algorithm terminates after correct classification or after k max itera-
tions. The output w is an approximation of a hyperplane, which lies tangential to
the infeasible region. In the next step we propose to adapt the mutation ellipsoid
such that its principal axes lie parallel to the hyperplane. If all samples are fea-
sible, the ES or CMA-ES works in its basic form. But if the number of infeasible
samples is bigger than one, we rotate the mutation ellipsoid until it is parallel
to the separating hyperplane. At least in the case of linear constraints we think
the proposed sketch of a constrained handling technique might me successful.

7.7 Summary

1. Constraint handling for EC offers a huge potential for heuristics. The prema-
ture step size reduction and the resulting premature fitness stagnation could
be shown experimentally for two traditional constraint-handling techniques,
death penalty and a dynamic penalty function.
2. We proved step size reduction for a (1+1)-EA under simplified conditions.
The proof is based on a success rate analysis considering a simplified EA
model on linear functions. The situation at the constraint boundary can be
modeled by two different states. From the success rates and the possible state
transitions, the expected step size changes in every step can be derived.
3. Three new constraint-handling techniques were introduced with the aim of
preventing an ES to suffer from premature fitness stagnation. We analyzed
the two heuristics TSES and DSES experimentally on known constrained
problems from literature and compared effectivity and eciency.
4. The DSES is based on a least mutation strength together with an adap-
tation technique to reduce . The parameters and ϑ define the speed of
the -reduction process. Before applying the DSES it has to be considered,