Chapter 32. Genetic Algorithms

Key Topics

• Biological Evolution in a Nutshell

• Genetics and Representation

• Genetic Algorithms

• Genetic Operators and Evolutionary Policies

• Advanced Issues

• Discussion

Evolutionary algorithms are a collection of solutions based on the theory of evolution. As such, genetic algorithms are a popular process that can optimize parameters in multidimensional space. Genetic algorithms use a simulation of the problem to determine the fittest solutions among the population. Improvements of the results over time are encouraged by only letting the fittest individuals survive and contribute to the gene pool.

For example, Quake 3 uses a genetic algorithm to adjust the weapon strategies [Waveren01]. Different parameters, such as the ideal distance for using the weapons, are optimized based on the performance. This evolutionary approach allows the behaviors to be adjusted to the game design in postproduction.

This chapter covers the following topics:

• Biological evolution and natural selection as the inspiration for an artificial model

• The importance of representation in genetic algorithms (the concepts of genotypes and phenotypes)

• An outline of the algorithm used in artificial evolution

• The details of specific genetic operators and evolutionary policies at each stage of the evolution