Yan Ge MSc Dissertation 2015/16

Experiments for the (1+(lambda,lambda)) Genetic Algorithm in Combinatorial Optimization Problems

Supervised by D.Sudholt

Abstract

Evolutionary algorithms have been applied to many research fields and provide satisfied solutions to provided problems. This dissertation aims to compare the power of three evolutionary algorithms (EAs), including (1+ λ) evolutionary algorithm (EA), (1+ (λ, λ)) genetic algorithm (GA) and standard GA, with the changes in offspring size. Furthermore, I will try to explore the best offspring size in order to maximize their power when EAs are applied to three combinatorial optimization problems.The result of the research shows that (1+ λ) EA outperforms the other two algorithms especially when the offspring size is small. (1+ (λ, λ)) GA is better than standard GA in the most of scenarios except when partition problem is handled. Additionally, the performance of (1+ λ) EA and (1+ (λ, λ)) GA with large offspring size have identical performance when they are used to handle maximum three satisfaction problem (MAX-3SAT). Besides, I analyze the best value of offspring size from two perspectives which are contribution rate and fix-budget perspective. Based on the contribution rate, the small values of offspring size are adapted for pursuing the high velocity increase of fitness. By contrast, fix-budget perspective suggests practitioners to choose large value of offspring size in order to achieve fitness as much as possible within the limited optimization time.