Genetic algorithms

Genetic algorithms

Search procedures based on the mechanics of natural selection and genetics. Such procedures are known also as evolution strategies, evolutionary programming, genetic programming, and evolutionary computation. Genetic algorithms are increasingly solving difficult search, optimization, and machine-learning problems that have previously resisted automated solution. They can solve hard problems quickly and reliably, are easy to interface to existing simulations and models, are extensible, and are easy to hybridize.

Motivation

Just as natural selection and genetics have filled a variety of niches by creating genotypes (sets of chromosomes) that result in well-adapted phenotypes (or organisms), so too can genetic algorithms solve many artificial problems by creating strings (artificial chromosomes) that result in better solutions. Users ultimately turn to genetic algorithms for robustness, that is, for algorithms that are broadly applicable, relatively quick, and sufficiently reliable. This emphasis on robustness contrasts starkly with the philosophy of operations research, where new algorithms must be tailored to specific problems. The need to invent a new method for each new problem class is daunting, and users look for methods that can solve complex problems without this requirement. See Operations research

Mechanics

For concrete exposition, the discussion is limited to a simple genetic algorithm that processes a finite population of fixed-length, binary strings. A simple genetic algorithm consists of three operators: selection, crossover, and mutation.

Selection is the survival of the fittest within the genetic algorithm. The key notion is to give preference to better individuals. Of course, for selection to function, there must be some way of determining what is good. This evaluation can come from a formal objective function, or it can come from the subjective judgment of a human observer or critic.

If genetic algorithms were to do nothing but selection, the trajectory of populations could contain nothing but changing proportions of the strings in the original population. To do something more sensible, the algorithm needs to explore different structures. A primary exploration operator used in many genetic algorithms is crossover. Simple, one-point crossover proceeds in three steps: (1) two individuals are chosen from the population by using the selection operator, and these two structures are considered to be mated; (2) a cross site along the string length is chosen uniformly at random; and (3) position values are exchanged between the two strings following the cross site.

In a binary-coded genetic algorithm, mutation is the occasional (low probability) alteration of a bit position, and with other codes a variety of diversity-generating operators may be used. When used together with selection and crossover, mutation acts both as an insurance policy against losing needed diversity and as a hill-climbing algorithm.

---

genetic algorithms - genetic algorithm