Computational complexity of elitist population-based evolutionary algorithms : a thesis presented in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Computer Science at Massey University, Palmerston North, New Zealand
Evolutionary Algorithms (EAs) are a modern heuristic algorithm that have proven
efficiency on a large number of real-life problems. Despite the rich history of applications
understanding of both how and why EAs work is lagging far behind. This
is especially true for one of the main components of EAs, that is hypothesized by
many to underlie their efficiency: population.
The first problem considered in this thesis is the introduction of a recombination
operator, K-Bit-Swap (KBS) and its comparison to mainstream operators,
such as mutation and different types of crossover. A vast amount of statistical evidence
is presented that shows that EAs using KBS outperform other algorithms
on a whole range of problems. Two problems are selected for a deep theoretical
analysis: OneMax and Royal Roads.
The main problem of modeling EAs that use both population and a pool of parents
is the complexity of the structures that arise from the process of evolution. In
most cases either one type of species is considered or certain simple assumptions
are made about fitness of the species.
The main contribution of this thesis is the development of a new approach to
modeling of EAs that is based on approximating the structure of the population
and the evolution of subsets thereof. This approach lies at the core of the new tool
presented here, the Elitism Levels Traverse Mechanism that was used to derive
upper bounds on the runtime of EAs. In addition, lower bounds were found using
simpler assumptions of the underlying distribution of species in the population.The second important result of the approach is the derivation of limiting distributions
of a subset of the population, a problem well-known in areas such as
epidemiology. To the best of the author's knowledge, no such findings have been
published in the EA community so far.