Evolutionary Algorithms - Self-Adaptive Heuristics for Evolutionary Computation - page 15

Termination Conditions

When an EA should terminate depends on the demands defined by the user and
on practical conditions. Typical termination conditions for EAs are

• the fitness has reached a predefined quality,

• fitness convergence, i.e. no fitness improvement is achieved after a predefined

number of generations,

• objective variable convergence, which is usually equivalent to fitness conver-

gence in non-dynamic search domains

•

strategy variable convergence,

• maximum number of generations or fitness function calls is reached, or

• maximum amount of time has passed.

The termination condition must be defined accurately for the comparison of
approaches.

Fitness Landscapes

Several kinds of fitness landscapes with certain features exist. In the following,
the most important types of fitness landscapes are introduced.
•

Unimodal - an unimodal fitness landscape owns only one global optimum.

• Multimodal - in contrast to unimodal fitness landscapes, multimodal own

multiple local optima and one or more global optima. The danger for EC
algorithms is to get stuck in local optima without being able to find the
global one.

• Dynamic - in dynamic fitness landscapes, the fitness changes over time. So,

the global optimum may be moving. The task of an optimizer is to find and
follow the moving optimum.

• Constrained - in constrained fitness landscapes, parts of the search space

are infeasible. Several problems for an EC algorithm occur. In heavily con-
strained search spaces feasible solutions have to be created. Feasible parts
of the search space may not be connected and it can be dicult for an EA
to jump between these parts. Another problem is the situation when optima
lie at the boundary of the infeasible search space, in particular when they
are located in a vertex of the feasible space. This problem is described and
analyzed in chapter 7.

• Multi-objective - for multi-objective optimization problems not only one, but

a whole set of objectives has to be optimized. One task may be to identify a
Pareto set of non-dominated solutions.
For each fitness landscape heuristic modifications of EAs exist.

2.1.6 Types of Evolutionary Algorithms

The following part gives a brief outline of common types of EAs. As already
mentioned, they grow together. The subsequent section will introduce ES.