Keiran Jarvis Undergraduate Dissertation 2015/16

Empirical Runtime Analysis of Crossover in Genetic Algorithms

Supervised by D.Sudholt

Abstract

Evolutionary algorithms are a class of algorithms inspired by the process of natural evolution. These algorithms solve problems by optimisation  through the use of a changing population of candidate solutions. New individuals are formed in the population using operators such as crossover or mutation. However there is a general lack of understanding with regard to how evolutionary algorithms perform.

It is believed that crossover enables 'building blocks' from different solutions to be combined into individuals that benefit from blocks of high fitness. This work follows on from Sudholt's 2014 paper, "How Crossover Speeds Up Building Block Assembly in Genetic Algorithms" which provides a clear proof of runtime analysis where crossover is used to combine building-blocks. The purpose of this paper is to further understanding in this area. In this project experiments are run to see whether crossover performs better than mutation only on a problem class similar to the  OneMax  problem, weighted linear functions.

This report contains findings that show genetic algorithms with crossover have trouble improving runtime over mutation only evolutionary algorithms as the range in weights for linear functions increases. Also additional work is covered that tries to improve the algorithms used and also a look into the behaviour  of populations in genetic algorithms.