What is the genetic algorithm?

DNAThe genetic algorithm is a search technique, or recipe, for finding solutions to complex problems. In this case complex problems are problems with intermediate or partial solutions that can be used as starting points for better solutions. There are many problems like this where trying an incremental change is more likely to lead to a better solution than trying a completely new random guess. The genetic algorithm also combines approximate solutions to find better solutions. This recombination is profoundly important because the results of simultaneous searches can be used to accelerate the search for better solutions.

The genetic algorithm can be expressed in biological terms:

  1. From a population of organisms representing the current best solutions to a problem, select some of the best organisms to generate new organisms.
  2. Use slight modifications (mutations) and new combinations (sexual reproduction or recombination) to generate new organisms to replace some of the existing organisms.
  3. This is one generation. Repeat many times.

Since in most interesting problems there is not sufficient time to search through all possible solutions, the best bet is very often a variation on an existing partial solution. Nature follows the same approach to improve the genes for survival against competitors and a changing environment.

Mutation allows the search to improve by making usually small random changes. Recombination allows the search to be run in parallel by sharing information between genetic lineages which would otherwise be unable to share the improvements each lineage had independently discovered from its small random changes.


Assembly languageThere are, of course, an infinite number of variations on the genetic algorithm that can be used for optimization. Each variation gives more or less emphasis to the steps in the process. Within these variations the genetic algorithm encompasses an enormous variety of more specialized techniques, but no variation of the algorithm is best for all situations. Reducing or removing recombination, for example, leads to an algorithm like simulated annealing which accepts or rejects random changes based on how much they improve the current solution. Increasing mutation leads to a Monte Carlo search which attempts new random solutions and tends to disregard older solutions under the assumption that they are not helpful. For any problem, the more that is known about potential solutions the more the search technique can be specialized.

Many profound ideas, when reduced to their essence sound like common sense. The genetic algorithm consists of starting from all that one currently knows (partial solutions) and testing random changes and new combinations of that knowledge. It involves simultaneous testing, like parallel processing, when that is possible. This obviousness hints at the generality of the algorithm. It is not only used in the struggle to survive in nature but also in neural processes  - in our own brains. There the electrical signals that are our thoughts are selected to survive as they evolve from small variations and new combinations of slightly older thoughts. This happens at the electrical and chemical level while we experience them as thoughts. It is a Genetical process.

        Gator     Back to