Phan Trung Hai Nguyen Undergraduate Dissertation 2015/16

Runtime Analysis of Memetic Evolutionary Algorithms

Supervised by D.Sudholt

Abstract

Memetic  Algorithm (MA) is an incorporation of one or more intensifying local search algorithms into an evolutionary framework, which could be an Evolutionary Algorithm or Genetic Algorithm, in order to add exploitative ability in addition to exploration of the evolutionary framework. The local search is often invoked after a certain number of generations, local search frequency , and run for a fixed number of iterations, local search depth . This hybridisation has been proven to be very robust and useful for tackling a significant number of real-world problems across various domains, not only in Engineering but also in Medicines and Economics. 

Here we introduce (1+1) Memetic  Algorithm ((1+1)MA), which is the simplest variant of all  Memetic  Algorithms. This algorithm works with a population of size one and produces only one offspring in each generation. This algorithm employs standard mutation as the only genetic operator, which always flips each bit in the parent's bit-string with a mutation probability. We try to find upper bounds on the expected running time of the algorithm on some problems. As a result, we expect to get new insights into the algorithm and might improve its efficiency.

In order to achieve these aims, we considered three typical problems namely OneMax , LeadingOnes and Hurdle. In the first stage, we tried to solve these problems using three simple local search algorithms: first ascent , steepest ascent and randomised local search , and came up with upper bounds on the expected runtime of these algorithms on three problems. Next we applied (1+1) Evolutionary Algorithm ((1+1)EA) to address these problems and analysed its complexity. Finally, we investigated the behaviour of (1+1)MA by combining the results obtained from the first two stages. This is due to the fact that (1+1)MA is actually the integration of one of three local search algorithms mentioned above into an evolutionary framework, whose behaviour is quite similar to (1+1)EA. In addition, the Hurdle problem is very interesting as it is a good example where both (1+1)EA and (1+1)MA beat the simple local searches.