Cover by Toby Segaran

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

O'Reilly logo

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.

Examples of mutating a solution

Figure 5-3. Examples of mutating a solution

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required