Genetic Algorithms

A genetic algorithm is a heuristic optimization method based on the idea of breeding¹. A dog breeder will choose dogs with desirable characteristics (largeness, smallness, spottedness, quickness) to parent future litters, but will spay or neuter dogs that exhibit poor characteristics or are defective. In this way, the population of dogs evolves towards a goal of having desirable characteristics.

A genetic algorithm operates in the same way, except that the individuals being bred are not dogs, but objective vectors. The computer program breeds these individual objective vectors to produce new individuals (i.e., new points in the objective space) in hope of moving the population towards a desired optimum.

The basic procedure is this: the computer creates a population of random individuals. The computer then evaluates the fitness of each individual in the population. Fitness is the objective function of the optimization: it is a measure of how desirable the individual's characteristics are. We want to maximize fitness. So the computer selects the fittest individuals from the population and applies genetic reproductive operations (of which the two most common are called crossover and mutation) to them to produce a new population of individuals: the second generation. The second generation is evaluated and bred again to produce the third generation, and so on. The process continues until it meets a termination criterion: perhaps it has produced a perfect individual, or has reached a maximum number of generations.

The two most common genetic operations are crossover and mutation. Crossover takes two individuals and exchanges some of their variables to produce two children. It is common to choose a single point in the vector, and have the two vectors exchange all variables with a higher index. This is similar to recombination in biology, where pairs chromosomes swap strands of DNA. Fig. 1(a) illustrates crossover.

Mutation takes a single individual and randomly changes one or more variables in it. It is a mechanism to ensure that certain values do not become extinct from a population. (In a nonlinear objective function, a certain value of a certain variable may not be helpful at first, and could die out; but it might be important near the optimum. Hence the need to restore it with mutation.) Fig. 1(b) illustrates mutation.

Figure 1: Crossover (a) and Mutation (b) Operations

Genetic algorithms perform poorly compared to most numerical algorithms: they are more expensive computationally, and may not converge to an optimum. For purely numerical problems, it is almost always better to use some other method.

However, unlike numerical algorithms, the objective space of a genetic algorithm can span things other than numbers. Anything that can be represented digitally can be part of the objective space of a genetic algorithm: bits, integers, discrete numbers, strings of text, web pages, images, current stock prices, configuration layouts, baklava recipes, Shakespearean quotations, anagram generator programs, etc. This makes genetic algorithms very suitable for problems such as configuration optimization problems, where the different configurations cannot easily be captured in a single real number.

It also means genetic algorithms are useful when the objective space is not an orthogonal vector space, but a space of objects spanned by hierarchal tree structures.