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

1 2

Fig. 7.2. The state transitions of Γ 1 and Γ 2 , its probabilities at the constraint boundary
and the influence on the step size σ

boundary is decreased. This condition also contributes to an iterative reduc-
tion of the distance to the constraint boundary before reaching the optimum.
From the probability of each state transition and the step size change, an ex-
pected step size change can be derived. Figure 7.2 shows the probabilities for the
state transitions of Γ 1 and Γ 2 , together with the change of step size σ for each
transition.
In each state, there are only two possibilities: staying in the same state or
leaving the state. Hence, the state transitions are geometrically distributed. We
are able to determine the expected change of the step sizes. The probability to
leave state Γ 1 is 1 p ).

Each iteration the step size is increased by γ . When leaving to state Γ 2 the step
size is decreased by γ − 1 . The probability to leave state Γ 2 is p , so the expected
number of iterations to stay is 1 /p with a step decrease by γ − 1 . Returning to
state Γ 1 leads to a step increase by γ . From these considerations we can now
determine the expected development of γ :

− p , so the expected number of iterations to stay is 1 / (1 −

1 1

p

1 1

p

γ − 1 γ −

p −

E ( γ )= γ · · · γ = γ (7.21)

1 − p 1 −

1 1

Lemma 7.1 has proven that p< 1 / 2, so

p − p < 0and 1 −

1 1

p

p −

E ( γ )= γ < 1

(7.22)

1 −

The expected change of step size σ is E ( γ ) < 1 in each generation, so the steps
are decreasing at the constraint boundary. For small success probabilities, see
lemma 7.1, the decrease becomes quite high.

We proved the step size reduction theoretically for the (1+1)-EA and experi-
mentally for a (15,100)-ES in section 7.3.1. In the next sections we present three
heuristics to overcome the problem of premature step size reduction.