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

Evolutionary Programming

Evolutionary programming (EP) is similar to evolution strategies (ES) with
respect to certain features. In its original form Fogel, Owens and Walsh [44]
developed EP for higher levels of abstraction. They were designed to produce
deterministic finite automatons, intended to match input to corresponding out-
put data. A typical EP algorithm for real-valued representations works with
vectors and Gaussian perturbation as means of mutation, but without recombi-
nation. The so called meta-EP makes use of self-adaptive mutation which works
as follows: The chromosome a =( x 1 ,...,x N ,σ 1 ,...,σ N ) is mutated into the
successor a using the following equations

x i = x i + σ i · N i (0 , 1) , (2.4)

σ i = σ i · (1 + α · N (0 , 1)) . (2.5)

Usually, the parent selection takes place deterministically while the survivor
selection is a probabilistic.

Genetic Algorithms

Genetic algorithms (GAs) were initially invented by John Holland in the USA in
the sixties for adaptation in natural and artificial systems [58]. Today, the term
genetic algorithms is most frequently used for EC algorithms when thinking of
a string representation of the individuals. The so called canonical or simple GA
works as follows. From a population P of μ individuals μ new individuals are

produced by selecting two parents from with fitness proportional selection.

In a second variation step, these μ individuals are mutated, e.g. with uniform
mutation and afterwards put into the population

P

P . There exists a variety
of genetic operators for the different representation types. Some of them are
introduced in later chapters of this topic. We evolved a reactive rule base for the
control of a human-competitive multi player computer game using GAs [111],
[112], see section 2.3.

Genetic Programming

Genetic programming (GP) is the youngest branch of EC methods. GP is about
the automatic evolvement of computer programs, e.g. to control agents or robots.
Although this idea was not considered to be new, John Koza is seen as its inventor
[70]. The idea is to evolve programs by means of the genetic operators mutation,
crossover and selection of the qualitatively most successful models. The most fa-
mous representation of computer programs for GP are trees, but programs can
also be represented in machine language like assembler. The parameter sets of
a GP program are called Koza-Tableau. Mutation in tree representation means
the replacement of an existing subtree byarandomlygenerated subtree, which