Genetic Algorithms

GAs owe their name to an early emphasis on representing and manipulating individuals at the level of genotype. In Holland’s original work [Holl75], GAs were proposed to understand adaptation phenomena in both natural and artificial systems and they have three key features that distinguish themselves from other computational methods modeled on natural evolution:

1. The use of bitstring for representation
2. The use of crossover as the primary method for producing variants
3. The use of proportional selection

Genetic Algorithms are the most popular technique in evolutionary computation research. In the traditional genetic algorithm, the representation used is a fixed-length bit string. Each position in the string is assumed to represent a particular feature of an individual, and the value stored in that position represents how that feature is expressed in the solution. Usually, the string is “evaluated as a collection of structural features of a solution that have little or no interactions” [Ange96]. The analogy may be drawn directly to genes in biological organisms. Each gene represents an entity that is structurally independent of other genes.

The more classical reproduction operator used is one point crossover, in which two strings are used as parents and new individuals are formed by swapping a sub-sequence between the two strings (see Figure 1).

 Figure 1. Bit-String Crossover of Parents a) & b) to form Offspring c) & d)

Another popular operator is bit-flipping mutation, in which a single bit in the string is flipped to form a new offspring string (see Figure 2).

 Figure 2. Bit-Flipping Mutation of Parent a) to form Offspring b)

A great variety of other crossover and mutation operators has also been developed. A primary distinction that may be made between the various operators is whether or not they introduce any new information into the population. Crossover, for example, does not while mutation does. All operators are also constrained to manipulate the string in a manner consistent with the structural interpretation of genes. For example, two genes at the same location on two strings may be swapped between parents, but not combined based on their values.

Traditionally, individuals are selected to be parents probabilistically based upon their fitness values, and the offspring that are created replace the parents. For example, if N parents are selected, then N offspring are generated which replace the parents in the next generation.

These methods are used to solve design optimization problems including discrete design parameters and then real parameter optimization problems. Early applications of GAs are optimization of gas pipeline control [Gold89], structural design optimization [Gold89], aircraft landing strut weight optimization [Ming86], keyboard configuration design [Glov86], etc. It should be mentioned that GAs have contributed to establish the schema theorem and recognize the role and importance of crossover through attentive theoretical analysis.

back to home