Genetic algorithms draw their inspiration from evolution and natural selection. Through the process of natural selection, organisms adapt to optimize their chances for survival in a given environment. Random mutations occur to the genetic description of an organism, which is then passed on to its children. Should a mutation prove helpful, these children are more likely to survive to reproduce. Should it be harmful, these children are less likely to reproduce, so the bad trait will die with them.

Genetic algorithms maintain a ``population'' of solution candidates for the given problem. Elements are drawn at random from this population and allowed to ``reproduce'', by combining some aspects of the two parent solutions. The probability that an element is chosen to reproduce is based on its ``fitness'', essentially a function of the cost of the solution it represents. Eventually, unfit elements die from the population, to be replaced by successful-solution offspring.

The idea behind genetic algorithms is extremely appealing. However, they just don't seem to work as well on practical combinatorial optimization problems as simulated annealing does. There are two primary reasons for this. First, it is quite unnatural to model most applications in terms of genetic operators like mutation and crossover on bit strings. The pseudobiology adds another level of complexity between you and your problem. Second, genetic algorithms take a very long time on non-trivial problems. The crossover and mutation operations make no real use of problem-specific structure, so a large fraction of transitions lead to inferior solutions, and convergence is slow. Indeed, the analogy with evolution, where significant improvements require millions of years, can be quite appropriate.

We will not discuss genetic algorithms further, in order to discourage you from considering them for your applications. However, pointers to implementations of genetic algorithms are provided in Section if you really insist on playing with them.

Mon Jun 2 23:33:50 EDT 1997