Self-Adaptation - Self-Adaptive Heuristics for Evolutionary Computation - page 42

• Active Constraints: At the constraint boundary, the infeasible solutions cut

off the mixture distribution M . Hence under certain conditions, successful

samples of move to the constraint boundary with decreasing step sizes

σ . The estimation of distribution process is constricted due to misleading
success rates, see section 7.3.

M

•

DSES: The DSES constraint handling technique proposed in section 7.4 es-
tablishes a minimum step size in order to avoid premature convergence. The
interpretation from the EDA point of view is simple: The goal is to maintain
least variances for the distributions M i . Samples from the distributions do
not approximate the constraint boundary, but can reach the vicinity of the
optimum, see section 7.3.

• TSES: The TSES introduced in section 7.5 is a constraint handling method

for active optima. The TSES makes use of various heuristic modifications in
order to approximate the optimum from two directions, the feasible and the
infeasible region. The integration of knowledge can also be explained from
an EDA perspective.

Every knowledge 3 that is incorporated into an EA, no matter how represented,
is biasing the probability distributions

M i into directions which are supposed
to be beneficial. EA researchers and practitioners design variation operators to
establish this bias. But on the other side the win of performance is a loss of uni-
versality at the same time, because the distribution biases are not advantageous
or not applicable on all kinds of problems.

3.8 Premature Convergence

Premature convergence of the mutation strength belongs to the most frequent
problems of self-adaptive ES. It depends on the initialization of the step sizes,
the learning parameters, the number of successful mutations and features of the
search space. As evolution rewards short term success the evolutionary process
can get stuck in local optima and suffer from premature convergence. Premature
convergence is a result of a premature mutation strength reduction or a decrease
of variance in the population. The problem is well known and experimentally
proved. Only few theoretical works concentrate on this phenomenon, e.g. from
Rudolph [126]. Premature convergence also appears for adaptive step control
mechanisms. In section 7.3 we analyze the success rate situation at the constraint
boundary that frequently leads to premature convergence.
The following causes for premature convergence could be derived. Stone and
Smith [148] came to the conclusion that low innovation rates 4 and high selec-
tion pressure result in low diversity. They investigated Smith's discrete

3 In this context the term knowledge comprises every information that helps to improve
the optimization process. This reaches from heuristic modifications of algorithms,
local search and intelligent initialization to memetic approaches
4 Low innovation rates are caused by variation operators that produce offspring not
far away from their parents, e.g. by low mutation rates.