Genetic algorithms are a robust, domain-independent problem solving technique inspired by the notion of evolution through survival of the fittest. They solve problems with nothing more than a "genetic" code that can describe the space of possible solutions and some measure of the fitness of the possible solution represented by a particular code. Simple operators mimic population genetics, with provisions for combining "parent" codes to generate "offspring" codes (called crossover). The operators normally allocate more offspring to fitter parents and subject the offspring to some chance of random mutation. Over time, the fitness of the population (and of its best individual) should evolve toward whatever the fitness function dictates as optimal. Genetic algorithms have proven useful for learning, process control, classifier systems, and function optimization. Applications have included the Traveling Salesman Problem (TSP), scheduling problems, bounded layout of 2-D figures, and warehouse location, among many others.The genetic codes are represented as strings of bits, while the operators can be as simple as randomly flipping a bit (mutation) or cutting two strings at the same point and combining the head of the first string with the tail of the second and vice versa (to generate offspring that represent a mix of their parent's attributes). The representation is compact and the operations are efficient — and both are independent of the particular problem to be solved. The simplicity and generality of genetic algorithms, as well as their demonstrated effectiveness, have led to increasing interest.
How GAs Work
The basic operation of a genetic algorithm is straightforward. The following pseudocode spells out the steps.1. Create an initial population (usually just random bit strings)
2. Select (based on fitness) two strings as parents
3. Generate their offspring (using crossover and mutation)
4. Determine which strings to retain, and which to abandon
5. Repeat steps 2-4 until some termination condition is satisfied.
Genetic algorithms often repeat steps 2 and 3 until they have created an entire new generation of strings and then replace the parent generation en masse.
A Simple Example
Normally the bit string in a genetic algorithm encodes some representation of possible solutions to a problem, such as a string of 64 bits representing a possible tour of 16 cities, with each 4-bit subsequence representing a particular city. The simplest example would be to let a bit string represent itself, and define fitness as containing the most ones. This is referred to as the "Counting 1s" problem in the GATools examples and as the "Traditional" GA example in the Genitor system. A random population is generated, perhaps 11100110, 10100111, 01000100, 10011001 (fitness values are 5, 5, 2, 4 respectively). The first and second strings are more fit and so are more likely to be selected as parents. If crossover occurs after their third bit, then the offspring strings 11100111 and 10100110 are created. One of the offspring has six ones, and is the most fit individual produced so far. Creating an offspring is referred to as a trial. Such selection and crossover would continue until an optimum individual was created or the program had exceeded the specified limit for the number of trials.