DiverGene: Experiments on Controlling Population Diversity in Genetic Algorithm with a Dispersion Operator
Anna Strzeżek, Ludwik Trammer, Marcin Sydow
DOI: http://dx.doi.org/10.15439/2015F411
Citation: Proceedings of the 2015 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 5, pages 155–162 (2015)
Abstract. We present diverGene - a novel, diversity-aware population selection operator for genetic algorithm - to be used especially for particularly complex and multi-criteria optimisation problems. Genetic algorithm is one of the most known evolutionary algorithms for solving hard optimisation problems. Many attempts have been made to improve its convergence rate and quality of the result. In this paper we propose a novel extension of the selection operator that makes it possible to control the level of diversity in the population. We discuss its theoretical background, including its computational hardness and propose an efficient way of computing it. The approach is implemented and tested on three hard optimisation problems: Knapsack Problem, Travelling Salesman Problem and a relatively new Travelling Thief Problem that might be viewed as the composition of the latter two. We report experimental results that seem to indicate that the novel approach has a potential to improve the quality of the results for some hard optimisation problems.