Comparing finite and infinite population models of a genetic algorithm using the minimum deceptive problem

Genetic algorithms (GAs) are general purpose algorithms designed to search irregular, poorly understood spaces. They are population based and use the ideas of evolution and survival of the fittest. For the finite population case, we model a genetic algorithm by representing the possible populations by the states of a Markov Chain. For the infinite population case, we use a model developed by Vose and Liepins [1]. We do not use previous models of GAs because they are incomplete in that they do not incorporate the effects of mutation which is a critical part of the evolutionary process. We consider the relationships between these models and an actual GA by investigating two minimal deceptive problems. The results of our computer simulations follow theoretical predictions and also reveal an unexpected effect of mutation on the deceptive problem.