Hannah Clough MSc Dissertation 2015/16

A Runtime Analysis for the (1 + (lambda,lambda)) Genetic Algorithm

Supervised by D.Sudholt

Abstract

Although genetic algorithms have been around for some time, their rigorous analyses have not, and hence a full understanding of how individual algorithms work is limited. In recent times researchers have begun to analyse  more closely how these algorithms work on optimising  simple functions, which then ultimately lead to a better general understanding of the mechanisms of each algorithm.

My analysis included conducting rigorous mathematical methods to find the runtime of the (1 + (lambda,lambda)) GA, a fairly recent GA which uses mutation before crossover - with the idea that by allowing for larger mutation rates, we can explore the search space quicker, and any bad results found can be "corrected" by means of crossover. I have found that for some values for the mutation and crossover rates on the Jump-k function, this may not be true, but I have also discovered results which may suggest that this theory is not lost and that indeed for larger mutation rates, this algorithm could potentially run quicker when trying to optimise  functions with a so-called "jump". This also leads to the speculation surrounding other similar functions with this "jump" property.