Population Size, Building Blocks, Fitness Landscape and Genetic Algorithm Search Efficiency in Combinatorial Optimization: An Empirical Study
Jarmo T. Alander · 2019
In this chapter we analyse empirically genetic algorithm search efficiency on several combinatorial optimisation problems in relation to building blocks and fitness landscape. The test set includes five problems of different types and difficulty levels, all with an equal chromosome length of 34 bits. Four problems were quite easy for genetic algorithm search while one, a folding problem, turned out to be a very hard one due to the uncorrected fitness landscape. The results show that genetic algorithms are efficient in combining building blocks if the fitness landscape is well correlated and if the population size is large enough. An empirical formula for the average number of generations needed for optimization and the corresponding risk level for the test set and population sizes are also given.