Modeling genetic algorithm dynamics for OneMax and deceptive functions.

摘要

In this dissertation, we develop a model predicting dynamics of the counting-ones (OneMax) and a form of deceptive function problems. The model describes the mean allele and, in the case of deceptive function, mean deceptive block values. The genetic algorithm (GA) that is being modeled consists of two-point crossover, fitness proportional selection and mutation operators. The model is developed to estimate the average GA dynamics, but it can be used for an individual run of the GA.; First, we develop the model for the OneMax problem with very high crossover rates. Then, we modify the model by using statistics of very early generations from GA runs, to describe the complete dynamics for different (lower) crossover rates of the OneMax problem. In the development of the model, we introduce a new quantity that measures the effect of the crossover operation and is independent of generation, for practical purposes. Then, the model is generalized to cover other cases of the OneMax, such as weighted OneMax, as well as a form of deceptive function problem, for high enough crossover rates. The model is also modified to include Boltzmann selection with fixed or scaled selection pressures.; The model can be applied to OneMax and deceptive function problems even when the crossover, mutation and the selection pressures (in the case of Boltzmann scaling) are changed at predetermined generations during a GA run. Since our model estimates the mean value (and, mean deceptive block value for deceptive function) at each locus at any generation, it can be used to determine a suitable migration time as well as the migration rate for parallel genetic algorithms (in the island model case) when migrations are allowed at any generation for our benchmark problems.; Although the problems for which our model proved successful were rather simple or idealized, they were often sufficiently involved to capture interesting nontrivial features of the GA dynamics. The author hopes to extend the approach to model solution of more representative real-world problems with various degrees of OneMax similarity and various amounts of deception.; At the end of the dissertation, an attempt to develop a stochastic differential equation model to predict the evolution of the fitness distribution for the OneMax problem is also presented. Although our attempt was not successful, it shows a strong connection between fitness evolution and certain diffusion equations and points toward the possibility of the existence of a diffusion-type equation that could describe the OneMax and maybe other type of GA dynamics.