An Analysis of the Interacting Roles of Population Size and Crossover in Genetic Algorithms.pdf

An Analysis of the Interacting Roles of Population Size and Crossover in Genetic Algorithms Kenneth A. De Jong William M. Spears kdejong@aic.gmu.edu spears@aic.nrl.navy.mil Computer Science Dept. AI Center - Code 5510 George Mason University Naval Research Laboratory Fairfax, VA 22030, USA Washington, D.C., USA Abstract In this paper we present some theoretical and empirical results on the interacting roles of population size and crossover in genetic algorithms. We summarize recent theoretical results on the disruptive effect of two forms of multi-point crossover: n- point crossover and uniform crossover. We then show empirically that disruption analysis alone is not sufficient for selecting appropriate forms of crossover. How- ever, by taking into account the interacting effects of population size and crossover, a general picture begins to emerge. The implications of these results on implemen- tation issues and performance are discussed, and several directions for further research are suggested. 1. Introduction One of the unique aspects of the work involving genetic algorithms (GAs) is the impor- tant role that recombination plays in the design and implementation of robust adaptive sys- tems. In most GAs, individuals are represented by fixed-length strings and recombination is implemented by means of a crossover operator which operates on pairs of individuals (parents) to produce new strings (offspring) by exchanging segments from the parents’ strings. Traditionally, the number of crossover points (which determines how many segments are exchan