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

7 Constraint Handling Heuristics for Evolution
Strategies

Whenever the search space is restricted due to constraints of the underlying prob-
lem, the EA has to make use of heuristic extensions which are called constraint
handling methods. Constraint handling is very relevant to practical applications.
A constraint is a restriction on possible value combinations of variables. EAs and
in particular ES are used for constrained numerical parameter optimization. The
optimum quite often lies on the constraint boundary or even in a vertex of the
feasible search space. In such cases the EA frequently suffers from premature
convergence because of a low success probability near the constraint boundaries.
We prove premature step size reduction for a (1+1)-EA under simplified condi-
tions, analyzing the success rates at the constraint boundary and the expected
changes of the step sizes.
First of all, in section 7.1 the numerical NLP-problem is defined. After a short
survey of constraint-handling techniques in 7.2, premature fitness stagnation is
proven theoretically for simplified conditions and experimentally analyzed in
section 7.3. In section 7.4 we present a new constraint-handling method, the
death penalty step control evolution strategy (DSES). The DSES uses an adap-
tive mechanism that controls the reduction of a minimum step size depending
on the distance to the infeasible search space. In section 7.5 we introduce a
biologically inspired concept of sexual selection and pairing for handling con-
straints. A number of modifications is necessary to prevent an explosion or the
mentioned stagnation of step sizes and to improve the eciency of the approach.
In 7.6 we present the nested angle evolution strategy (NAES). This is a meta-
evolutionary approach, in which the angles of the correlated mutation of an inner
problem-solving ES are adapted by an outer ES. All techniques are experimen-
tally evaluated on selected test problems and compared with the results of an
existing penalty-based constraint-handling method.

7.1 The NLP Problem

In general, the constrained continuous nonlinear programming problem is de-
fined as follows: In the N -dimensional search space IR N find a solution x =

( x 1 ,x 2 ,...,x N ) T , which minimizes f ( x ):