Sanjana Khot Undergraduate Dissertation 2016/17

Analysis of speedups in Evolutionary Algorithms with distributed populations

Supervised by D.Sudholt

Abstract

Evolutionary Algorithms are optimisation techniques inspired by Darwin’s theory of natural evolution. They are stochastic in nature and incorporate random mutations and recombinations to create new solutions and explore the search space. EAs have been found to work well on many hard optimisation problems which makes them relevant and useful for difficult combinatorial problems like planning and scheduling.Recent developments in the technology of parallel computing, such as the development of multiple CPU cores and GPU computing, has provided an impetus to the research of Parallel Evolutionary Algorithms (PEAs). However, there is still a lack of rigorous understanding of the runtime of PEAs, as well as the effect of fundamental parameters on the efficiency of these algorithms.This project draws on the work done on PEAs, especially island models, by Sudholt and documented in the chapter Parallel Evolutionary Algorithms in the Handbook of Computational Intelligence. It aims to further the understanding of island models by implementing them in the Free Evolutionary Algorithm Toolkit (FrEAK) and conducting relevant experiments on them.