A runtime analysis method unifying evolutionary algorithms on discrete search spaces
Malalanirainy Rakotoson, T
Date: 2 August 2021
Thesis or dissertation
Publisher
University of Exeter
Degree Title
PhD in Computer Science
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) ...
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.
Doctoral Theses
Doctoral College
Item views 0
Full item downloads 0