Learn more about Genetic Algorithm and Direct Search Toolbox

How the Genetic Algorithm Works

On this page…
Outline of the Algorithm Initial Population Creating the Next Generation Plots of Later Generations Stopping Conditions for the Algorithm

Outline of the Algorithm

The following outline summarizes how the genetic algorithm works:

1. The algorithm begins by creating a random initial population.

2. The algorithm then creates a sequence of new populations. At each step, the algorithm uses the individuals in the current generation to create the next population. To create the new population, the algorithm performs the following steps:

   1. Scores each member of the current population by computing its fitness value.

   2. Scales the raw fitness scores to convert them into a more usable range of values.

   3. Selects members, called parents, based on their fitness.

   4. Some of the individuals in the current population that have lower fitness are chosen as elite. These elite individuals are passed to the next population.

   5. Produces children from the parents. Children are produced either by making random changes to a single parent—mutation—or by combining the vector entries of a pair of parents—crossover.

   6. Replaces the current population with the children to form the next generation.

3. The algorithm stops when one of the stopping criteria is met. See Stopping Conditions for the Algorithm.

Back to Top

Initial Population

The algorithm begins by creating a random initial population, as shown in the following figure.

In this example, the initial population contains 20 individuals, which is the default value of Population size in the Population options. Note that all the individuals in the initial population lie in the upper-right quadrant of the picture, that is, their coordinates lie between 0 and 1, because the default value of Initial range in the Population options is [0;1].

If you know approximately where the minimal point for a function lies, you should set Initial range so that the point lies near the middle of that range. For example, if you believe that the minimal point for Rastrigin's function is near the point [0 0], you could set Initial range to be [-1;1]. However, as this example shows, the genetic algorithm can find the minimum even with a less than optimal choice for Initial range.

Back to Top

Creating the Next Generation

At each step, the genetic algorithm uses the current population to create the children that make up the next generation. The algorithm selects a group of individuals in the current population, called parents, who contribute their genes—the entries of their vectors—to their children. The algorithm usually selects individuals that have better fitness values as parents. You can specify the function that the algorithm uses to select the parents in the Selection function field in the Selection options.

The genetic algorithm creates three types of children for the next generation:

• Elite children are the individuals in the current generation with the best fitness values. These individuals automatically survive to the next generation.

• Crossover children are created by combining the vectors of a pair of parents.

• Mutation children are created by introducing random changes, or mutations, to a single parent.

The following schematic diagram illustrates the three types of children.

Mutation and Crossover explains how to specify the number of children of each type that the algorithm generates and the functions it uses to perform crossover and mutation.

The following sections explain how the algorithm creates crossover and mutation children.

Crossover Children

The algorithm creates crossover children by combining pairs of parents in the current population. At each coordinate of the child vector, the default crossover function randomly selects an entry, or gene, at the same coordinate from one of the two parents and assigns it to the child.

Mutation Children

The algorithm creates mutation children by randomly changing the genes of individual parents. By default, the algorithm adds a random vector from a Gaussian distribution to the parent.

The following figure shows the children of the initial population, that is, the population at the second generation, and indicates whether they are elite, crossover, or mutation children.

Back to Top

Plots of Later Generations

The following figure shows the populations at iterations 60, 80, 95, and 100.

As the number of generations increases, the individuals in the population get closer together and approach the minimum point [0 0].

Back to Top

Stopping Conditions for the Algorithm

The genetic algorithm uses the following conditions to determine when to stop:

• Generations — The algorithm stops when the number of generations reaches the value of Generations.

• Time limit — The algorithm stops after running for an amount of time in seconds equal to Time limit.

• Fitness limit — The algorithm stops when the value of the fitness function for the best point in the current population is less than or equal to Fitness limit.

• Stall generations — The algorithm stops when the weighted average change in the fitness function value over Stall generations is less than Function tolerance.

• Stall time limit — The algorithm stops if there is no improvement in the objective function during an interval of time in seconds equal to Stall time limit.

• Function Tolerance — The algorithm runs until the weighted average change in the fitness function value over Stall generations is less than Function tolerance.

• Nonlinear constraint tolerance — The Nonlinear constraint tolerance is not used as stopping criterion. It is used to determine the feasibility with respect to nonlinear constraints.

The algorithm stops as soon as any one of these conditions is met. You can specify the values of these criteria in the Stopping criteria pane in the Optimization Tool. The default values are shown in the pane.

When you run the genetic algorithm, the Run solver and view results panel displays the criterion that caused the algorithm to stop.

The options Stall time limit and Time limit prevent the algorithm from running too long. If the algorithm stops due to one of these conditions, you might improve your results by increasing the values of Stall time limit and Time limit.

Back to Top

Some Genetic Algorithm Terminology

Description of the Nonlinear Constraint Solver

© 1984-2009- The MathWorks, Inc.    -   Site Help   -   Patents   -   Trademarks   -   Privacy Policy   -   Preventing Piracy   -   RSS