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

Author

Allen Eugene Nix

Date of Award

8-1991

Degree Type

Thesis

Degree Name

Master of Science

Major

Computer Science

Major Professor

Michael D. Vose

Abstract

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.

Recommended Citation

Nix, Allen Eugene, "Comparing finite and infinite population models of a genetic algorithm using the minimum deceptive problem. " Master's Thesis, University of Tennessee, 1991.
https://trace.tennessee.edu/utk_gradthes/12489