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

Exploration and Exploitation

All EC methods have the following two basic principles in common:

• Exploration of the search domain in order to find the optimum. The explo-

ration part of an EC algorithm is covered by the genetic operators mutation
and crossover. Mutation is supposed to diversify existing candidate solutions
with means of random variation. Crossover or recombination on the one hand
produces new candidate solutions by combining features of at least two solu-
tions. On the other hand, it hereby exploits discovered knowledge, which is
the essential part of the second key feature:

• Exploitation of knowledge about the fitness landscape which could have been

discovered within the past optimization process. The selection operators
achieve this objective by choosing the fittest mates for reproduction (par-
ent selection) or by letting the fittest solutions survive (survival selection).

Objective and Strategy Variables

In the language of EC candidate solutions are called individuals. The solution
is called phenotype, while the representation of a candidate solution is called
genotype. It consists of objective variables on which the optimization heuristic
works. Canonical genetic algorithms work on binary representations of objective
variables, i.e. b =( b 1 ,...,b N )

N ,where b i denotes a gene and N is
the length of the chromosome. A Population

∈{ 0 , 1 }

P is a set of chromosomes. For

agene b i , the index i denotes the locus of b i , whereas the potential

values 0 and 1 are alleles of b i . Numerical or continuous representations, e.g.
ES, work with vectors of continuous objective variables x =( x 1 ,x 2 ,...,x n )

∈{ 0 , 1 }

∈
IR N . Representations for combinatorial search spaces are versatile. The most
famous ones are simple ordering problems, where the quality of the solution
only depends on the order of the solution's components. A typical combinatorial
problem is the traveling salesman problem (TSP) [45], which is also used as a test
problem in chapter 6. Some problems might require a mixture of the mentioned
representations.

Mutation

Mutation is the source for evolutionary changes. In biology mutation of the DNA
occurs during copy processes or due to influences of the environment. Offspring
individuals are not exact copies of their parents, but the variation is also a source
for innovation. In binary representations mutation is bit flipping with a certain
probability. For numerical search spaces mutation can be implemented as an
addition of a random number based on a certain probability density function. In
genetic programming (GP) mutation is the exchange of a subtree by a random
subtree. Mutation produces small changes in the chromosome with high proba-
bility, bigger changes with decreasing probability. Mutation operators ought to
fulfill the three established rules of reachability, unbiasedness and scalability [16],