Dimensional Analysis of Allele-Wise Mixing Revisited

摘要

This paper revisits an important, yet poorly understood, phenomenon of genetic optimisation, namely the mixing or juxtapositioning capacity of recombination, and its relation to selection. Mixing is a key factor in order to determine when a genetic algorithm will converge to the global optimum, or when it will prematurely converge to a suboptimal solution. It is argued that from a dynamical point of view, selection and recombination are involved in a kind of race against time: the number of instances of good building blocks is quickly increased from generation to generation by the selection phase, but in order to create optimal solutions these building blocks have to be juxtaposed by the crossover operator and this also takes some time to occur. If the selection of building blocks goes too fast - relative to the rate at which crossover can juxtapose or mix them - then the population will prematurely converge to a suboptimal solution. Previous work (Goldberg, Deb & Thierens, 1993) made a first step toward a better understanding of mixing in genetic algorithms, and also introduced the use of dimensional analysis in GA modelling. In this paper we extend this work by integrating some of the insights gained from the modelling of the dynamic behaviour of GAs on infinite populations (Mu'hlenbein & Schlierkamp-Voosen, 1993; Thierens & Goldberg, 1994; Back, 1995; Miller & Goldberg, 1995). The resulting dimensional model quantifies the allele-wise mixing process: it specifies the boundary in the GA parameter space between the region of reliable convergence at one side, and the region of premature convergence at the other. Although the model is limited to simple bit-wise mixing, the lessons learned from it are quite general and are also valid for more difficult, building-block based problems.