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

can be bound in depth. Crossover exhibits a greater importance than mutation
in GP. In most cases it is run with probability 0 . 9. Crossover means the ex-
change of subtrees of two parents. GP programs may result in big trees. In order
to avoid the generation of frequently used subprograms, the so called automat-
ically defined functions (ADFs) were introduced, which are frequently evolved
subprograms. An effect often observed in GP is bloat [141]. It means that big
programs are result of the evolutionary process. This effect is also called survival
of the fattest .

Particle Swarm Optimization

Why do particle swarm optimization algorithms (PSOAs) and EAs both belong
into the field of EC? They follow similar concepts of exploration and exploitation
of the search space. In particular, the continuous PSOA is very similar to a
(1+ λ )-ES, see section 2.2. The algorithmic structure as well as the operators are
quite similar. As a consequence, concepts from EAs can extend particle swarm
optimization, e.g. self-adaptation. Furthermore, genetic operators inspired by
particle swarm optimization can be designed.
Particle swarm optimization is a population based optimization approach,
which was introduced by Kennedy and Eberhart [69]. It was originally introduced
as an alternative to the standard GA. Particle swarm optimization was inspired
by insect swarms, as the latter consist of a number of particles moving in the
search space. Similar to ES each particle x represents a candidate solution for
a numerical problem. Each particle is assigned with a velocity v . The following
two equations exhibit the working principle of PSOAs:

x = x + v , (2.6)

and

v = v + φ 1 ( pb − x )+ φ 2 ( b − x ) (2.7)

The variables φ 1 and φ 2 produce random numbers, whereas pb is the best solu-
tion of the particle's history and b is the best solution of all particles' histories.
Several enhancements of the above PSOA equations have been proposed. E.g.
the velocity can be extended by an inertia term as proposed by Shi and Eberhart
[139]

v = w v + φ 1 ( pb

− x )+ φ 2 ( b − x ) . (2.8)

Shi and Eberhart propose to decrease this term if no improvement is obtained
within consecutive time steps. They also proposed to replace the worst particle
by an elite particle, the best of the whole swarm. There have been attempts to
evolve particle swarm equations with genetic programming [108].

Similarities Between EAs and PSOAs

Like EAs, PSOAs are population based heuristics that contain randomized as-
pects. Table 2.1 summarizes the comparison between EA and PSOA concepts.