Benjamin Cornforth Undergraduate Dissertation 2017/18

Experiments for Convex Evolutionary Search in Combinatorial Optimisation

Supervised by D.Sudholt

Abstract

Combinatorial optimisation is a field of computer science with an insurmountable range of challenges to face. Evolutionary algorithms have provided a step towards tackling some of these challenges with heuristic processes to build adequate solutions to a handful of optimisation problems. Hence, the importance of assessing the effectiveness of Evolutionary Algorithms (EAs) against certain optimisation problems cannot be understated.

This project will investigate the performance of Convex Evolutionary Search (CES), an algorithm published in 2015, across a handful of toy optimisation problems. The optimisation problems experimented with are LeadingOnes, OneMax, Max-Sat, Knapsack and the Jump Number problem. CES will be benchmarked using three other EAs, these are the Compact Genetic Algorithm, the Simple Genetic Algorithm, and stochastic hill-climber - the (1+1) Evolutionary Algorithm.

This project seeks to assess 4 features about CES, the solution quality, the number of generations until convergence of CES, the number of function evaluations until convergence of CES and if convergence occurs at all. These experiments were performed with bespoke software and the results were discussed.