Reducing Premature Convergence in Evolutionary
Algorithms
University College, Cork, Ireland, (2 July 1996)Abstract
We define Evolutionary Algorithms to be those
algorithms which employ or model natural evolution.
Generally, when an Evolutionary Algorithm fails to
produce a satisfactory solution to a problem, it is
because the population has prematurely converged to a
suboptimal solution. This thesis seeks to improve the
performance of Evolutionary Algorithms by reducing the
occurrence of premature convergence. All the extensions
presented in this thesis are either naturally occurring
phenomena, or are methods employed by biologists and /
or plant and animal breeders. In all the cases examined
in this thesis, it is shown that the less human control
there is with evolution, the better a population will
perform. A number of standard benchmark problems are
examined, and new, biologically-inspired approaches are
presented. A new selection scheme involving multiple
fitness functions is introduced. This scheme is applied
to the optimisation of multi-objective functions and
multi-modal functions. Genetic Programming is applied
to a new problem area, the autoparallelisation of
serial programs, through the use of techniques
developed in this thesis. The notion of addditive
diploidy, a type of diploidy that occurs naturally in
biology, is introduced and applied to Genetic
Algorithms. Additive diploidy is shown to outperform
traditional, dominance-oriented, diploidy on a
difficult test problem. A new benchmark problem for
Genetic Programming is introduced. This
competition-oriented benchmark permits the direct
comparison of two or more possible solutions. In
producing individuals for this benchmark, Genetic
Programming is also shown to be suitable for the
evolution of event driven programs.