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

Thumbnail Image
Open Access Location
Journal Title
Journal ISSN
Volume Title
Massey University
The Author
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.
Genetic algorithms, Evolutionary programming, Computer science