You are previewing Programming Collective Intelligence.

# Genetic Algorithms

Another set of techniques for optimization, also inspired by nature, is called genetic algorithms. These work by initially creating a set of random solutions known as the population. At each step of the optimization, the cost function for the entire population is calculated to get a ranked list of solutions. An example is shown in Table 5-1.

Table 5-1. Ranked list of solutions and costs

Solution

Cost

[7, 5, 2, 3, 1, 6, 1, 6, 7, 1, 0, 3]

4394

[7, 2, 2, 2, 3, 3, 2, 3, 5, 2, 0, 8]

4661

...

...

[0, 4, 0, 3, 8, 8, 4, 4, 8, 5, 6, 1]

7845

[5, 8, 0, 2, 8, 8, 8, 2, 1, 6, 6, 8]

8088

After the solutions are ranked, a new population—known as the next generation—is created. First, the top solutions in the current population are added to the new population as they are. This process is called elitism. The rest of the new population consists of completely new solutions that are created by modifying the best solutions.

There are two ways that solutions can be modified. The simpler of these is called mutation, which is usually a small, simple, random change to an existing solution. In this case, a mutation can be done simply by picking one of the numbers in the solution and increasing or decreasing it. A couple of examples are shown in Figure 5-3.

The other way to modify solutions is called crossover or breeding. This method involves taking two of the best ...