The dynamics of a genetic algorithm under stabilizing selection

Rattray, Magnus The dynamics of a genetic algorithm under stabilizing selection. Complex Systems, 9 (3), pp. 213-234.


A formalism recently introduced by Prugel-Bennett and Shapiro uses the methods of statistical mechanics to model the dynamics of genetic algorithms. To be of more general interest than the test cases they consider. In this paper, the technique is applied to the subset sum problem, which is a combinatorial optimization problem with a strongly non-linear energy (fitness) function and many local minima under single spin flip dynamics. It is a problem which exhibits an interesting dynamics, reminiscent of stabilizing selection in population biology. The dynamics are solved under certain simplifying assumptions and are reduced to a set of difference equations for a small number of relevant quantities. The quantities used are the population's cumulants, which describe its shape, and the mean correlation within the population, which measures the microscopic similarity of population members. Including the mean correlation allows a better description of the population than the cumulants alone would provide and represents a new and important extension of the technique. The formalism includes finite population effects and describes problems of realistic size. The theory is shown to agree closely to simulations of a real genetic algorithm and the mean best energy is accurately predicted.

Divisions: Aston University (General)
Additional Information: Data checked by Susan Doughty 1/7/09 Publisher not answering permission request. item posted with no full-text EW 6/7/09 (c in E)
Uncontrolled Keywords: statistical mechanics,genetic algorithms,subset combinatorial optimization problem,non-linear energy function,single spin flip dynamics,stabilizing selection,population biology,cumulant,genetic algorithm


Full text not available from this repository.

Export / Share Citation


Additional statistics for this record