Evolving Solutions With Genetic Algorithms

1.   Genetic Algorithms (GAs) initialize by generating random attempts at a solution to the problem the GA hopes to solve.  Each of these possible solutions is known as an individual and for the purposes of the Genetic Algorithm is coded as a string of characters ("genes") sometimes called a chromosome.

Examples:
    The decimal number 935 might be coded as the binary string 1110100111.
    The path from London to Paris to Munich to Venice might be coded as LPMV.

The collection of all individuals (that is, potential solutions) together is known as a population.  All of the individuals "alive" at a given time form a generation.

2.   A fitness function (usually unique to each GA) judges the individual solutions based on how well they solve the problem at hand.  For example, a fitness function for a mathematical optimization problem will judge as fit those individuals or chromosomes that produce the numerically largest (or smallest) results within necessary restrictions.  A fitness function in a GA that determines the shortest distance between several cities will judge as fit those solutions which produce the shortest paths.
3.   Selection and Recombination:
   Selection followed by Reproduction, provides the link between successive generations of solutions.  Parents that will produce the next generation are chosen by weighted random formulae based on their fitness as determined by the fitness function.  Fit individuals may reproduce several times per generation, while less fit solutions may not have a chance to pass on their genes.  Because the best individuals are only favored and not guaranteed to recombine, a factor of elitism is sometimes introduced to insure that the very best genetic material survives the reproduction stage.

The two main recombination techniques are crossover and mutation.

Crossover produces two children by cutting the chromosomes of each parent at random crossover points and rearranging them to create offspring, as shown by the accompanying animation.

This animation illustrates one point crossover, named as such because each of the parents is cut in one place.  A GA using two point crossover cuts the parent strings in two places before rearranging them.  Another technique, uniform crossover, forms the child by randomly selecting either one of the corresponding parents' genes for each gene to be filled on the child's chromosome, as illustrated below.  Two point crossover and uniform crossover are sometimes considered more productive than simple one point crossover.

Of the individuals selected for reproduction (as opposed to those usually unfit individuals discarded before this stage), not all may actually undergo crossover.  Between 100% to 60% of selected individuals in each generation reproduce sexually via crossover.  The remainder are duplicated or cloned, so that the child has exactly the same chromosome as the parent.

After crossover and cloning are complete, a small number (often less than 1%) of individuals suffer mutation.  A mutated individual has one or more of its genes altered, as demonstrated in the animation.  Mutation helps the GA avoid premature convergence.



There is an approximately 275KB animated GIF showing the entire process of creating a new generation of solutions with selection, crossover, and mutation. Highly Recommended.

Also see some variations to the simple reproduction and selection described above.
 
 

Back to Main