A runtime analysis method unifying evolutionary algorithms on discrete search spaces

Abstract

This thesis aims to develop a unified runtime analysis of: EA 1 with no mutation and with a standard crossover, (1 + 1) EA, and EA with both a mutation and a standard crossover. To this end, we determined for each algorithm a class of problems they efficiently solve. Polynomially quasi-concave problems on the Hamming (resp. Manhattan) space, that are already known to be easy for EA with no mutation and with a non-standard crossover, were shown to be easy for EA with no mutation and with a standard crossover. A class of problems that is determined by its balls of radius ρ, is defined for each the following algorithms: (1 + 1) EA and EA with both a mutation and a standard crossover. Each of these classes is shown to only contain easy problems for an instantiation of a gener- alization of the algorithm they correspond to. Unlike the class of quasi-concave fitness landscapes, these classes are not affected by the choice of representation. We conclude that if the definition of a class of problems is built upon particular metrics, then the runtime result is affected by the choice of representation.