Comparing Finite and Infinite Population Models of a Genetic Algorithm Using the Minimum Deceptive Problem

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. 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1991
Accession Number
ADA238679

Entities

People

  • Allen E. Nix

Organizations

  • University of Tennessee system

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Computational Science
  • Computer Simulations
  • Computers
  • Demographic Cohorts
  • Genetic Algorithms
  • Markov Chains
  • Markov Models
  • Mathematical Models
  • Models
  • Mutations
  • Probability
  • Probability Distributions
  • Random Variables
  • Simulations
  • Steady State

Fields of Study

  • Mathematics

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Agent-Based Social Robotics and Mobile-Assisted Learning in Virtual Environments.
  • Molecular and genetic basis of cancer.

Technology Areas

  • AI & ML
  • AI & ML - Bayesian Inference
  • AI & ML - Machine Learning Algorithms
  • Biotechnology
  • Space