Mutation effects in genetic algorithms with offspring selection applied to combinatorial optimization problems

In this paper the authors describe the effects of mutation in genetic algorithms when used together with offspring selection to solve combinatorial optimization problems. In the initial definition of offspring selection stated by Affenzeller et al., offspring selection is applied to each solution after its creation using crossover and optional mutation. Thereby a solution is immediately accepted for the next generation only if it is able to outperform its parental solutions in terms of quality. It has been shown in several publications by Affenzeller et al. that this additional selection step leads to a better maintenance of high quality alleles and therefore to a better convergence behavior and a superior final solution quality. Due to the application of offspring selection after crossover and mutation, both operations become directed by the quality of the created solutions. This is in fact a different interpretation of mutation compared to classical genetic algorithms where mutation is used in an undirected way to introduce new genetic information into the search process. In this contribution the authors propose a new version of offspring selection by applying it after crossover, but before mutation. In a series of experiments the similarities and differences of these two approaches are shown and the interplay between mutation and offspring selection is analyzed.