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

the constrained region cuts off the mutative success area. Consequently, the self-
adaptation process favors smaller step sizes, whose success area is not cut off.
At first, premature step size reduction is analyzed experimentally. Afterwards we
prove theoretically that the step sizes tend to reduce at the constraint boundary.

7.3.1 Experimental Analysis
The premature step size reduction can be shown experimentally on problem 2.40
for the death penalty method and the dynamical penalty function by Joines and
Houck [66], see Table 7.1. Problem 2.40 exhibits a linear objective function and
an optimum with five active linear constraints. Each row of Table 7.1 shows the
results of a (15,100)-ES after 50 runs. As termination condition fitness stagnation
is chosen. If the difference between the fitness value of the best individual of
a generation and the best of the following generation is smaller than a θ =
10 − 12 , then the ES terminates as the magnitude of the steps sizes is too small to
effect further improvements. Both constraint-handling methods are not able to
approximate the optimum of the problem satisfactorily. The standard deviations
dev show that the algorithms produce rather different results in the various runs.

Table 7.1. Experimental results of the death penalty method (DP) and the dynamic
penalty function by Joines and Houck (Dyn) on problem 2.40. The parameter ffc counts
the fitness function calls and cfc the constraint function calls. Both constraint-handling
techniques are not able to approximate the optimum of the problem satisfactorily. The
relatively high standard deviations dev show that the algorithms produce unsatisfac-
torily different results.

best mean worst dev ffc cfc
DP -4948.079 -4772.338 -4609.985 65.2 50624 96817
Dyn -4780.554 -4559.129 -4358.446 85.0 31878 31878

7.3.2 Theoretical Analysis
We consider the two dimensional case of a linear objective function and one
linear constraint with the angle β between the latter and the contour lines of
the fitness function. Figure 7.1 shows a typical situation of individual x in the
neighborhood of the constraint boundary. It shows the success rate situations of
individual x with distance d to the constraint boundary for the three cases: 1.
σ<d ,2. σ>d , σ<s and 3. σ>d , σ>s .
We analyze the behavior of a (1+1)-EA with adaptive step sizes modeled 1 by
the Markovian process ( X t ,σ t ) t≥ 0 generated by
X t +1 = X t + σ t Z t

if f ( X t + σ t Z t ) <f ( X t ) ∧ g ( X t + σ t Z t )=0

(7.4)

X t otherwise

1 As Rudolph [126] states, this EA does not exactly match a (1+1)-EA with self-
adaptive step size control, but it can be transferred to a broader class of EAs.