Introduction

What limit can we put to this power, acting during long ages and rigidly scrutinizing the whole constitution, structure and habits of each creature -- favoring the good and rejecting the bad? I can see no limit to this power in slowly and beautifully adapting each form to the most complex relations of life.

-- Charles Darwin, On the Origin of Species

The Genetic Algorithm

    procedure genetic_algorithm {
       set time t = 0;
       initialize the population, P(t);
       while the termination condition is not met do {
           evaluate the fitness of each member of P(t);
           select most fit members from P(t);
           produce the offspring of pairs of members using genetic operator;
           replace the weakest candidates of P(t) with these offspring;
           set time t = t + 1;
       }
    }

Example: The Traveling Salesman Problem

How should we represent the path?

Instead, let's adopt a decimal representation, where the path is represented by numeric names for each of the 9 cities: (1 9 2 4 6 5 7 8 3), for N = 9. Thus all possible paths through the 9 cities is represented by an ordering of the nine digits, 1 to 9.

Suppose our initial population consists of a random set of possible paths.

Genetic Operators

parent1 = (1 9 2 | 4 6 5 7 | 8 3)

parent2 = (4 5 9 | 1 8 7 6 | 2 3)

You could define two children using the following crossover rule. First start by initializing each child with the middle segment of the parents:

child1 = (x x x | 4 6 5 7 | x x)

child2 = (x x x | 1 8 7 6 | x x)

Then, starting from the second cut point of one parent, copy the cities from the other parent in the same order as they occur in the first parent. For example, the sequence of cities from parent2 is: 2 3 4 5 9 1 8 7 6. Then, remove cities that occur in the first parent. Thus when copying from parent2 to parent1 we have to remove 4 6 5 7. This will give: 2 3 9 1 8, which is then copied into the new child:

child1 = (2 3 9 | 4 6 5 7 | 1 8)

child2 = (8 3 9 | 1 8 7 6 | 2 4)

This crossover rule guarantees that the children are possible solution paths.

Another type of genetic operator is called inversion, in which some the middle segment of the solution path is inverted. This is like a genetic mutation.

child1 = (2 3 9 | 7 5 6 4 | 1 8)

child2 = (8 3 9 | 6 7 8 1 | 2 4)

Evaluating the Individuals

Selecting the Next Generation

Some Links Worth Exploring

Java GA Toolkit (Examples)

Tutorial with Demos

JGAP: Java Package for GAs

Knowledge Representation and Search in Genetic Algorithms