IV. Genetic Algorithm

Basic Description

Genetic algorithms are inspired by Darwin's theory of evolution. The solution to a problem is evolved rather than designed directly.

The algorithm starts with a set of solutions (represented by chromosomes) called a population. Solutions from one population are selected and used to form a new population. The idea is that the new population will be better than the old one. Solutions selected to create new solutions (offspring) are chosen according to their fitness: the more suitable they are, the greater their chance of reproducing.

This process is repeated until some condition is satisfied, for example a maximum number of generations is reached or the best solution no longer improves.

Example
As you already know from the chapter about search space, problem solving can often be expressed as finding the extreme of a function. That is exactly the kind of problem shown here. A function is given, and the GA tries to find its minimum.
You can try running the genetic algorithm in the demonstration below by pressing the Start button. The graph represents a search space, and the vertical lines represent solutions (points in the search space). The red line is the best solution; the green lines are the other ones.
Start begins the algorithm, Step performs one step (that is, creates one new generation), Stop halts the algorithm, and Reset restores the original population.

Outline of the Basic Genetic Algorithm

  1. [Start] Generate a random population of n chromosomes (suitable solutions for the problem)
  2. [Fitness] Evaluate the fitness f(x) of each chromosome x in the population
  3. [New population] Create a new population by repeating the following steps until the new population is complete
    1. [Selection] Select two parent chromosomes from the population according to their fitness (the better the fitness, the greater the chance of being selected)
    2. [Crossover] With a crossover probability cross over the parents to form a new offspring (children). If no crossover is performed, the offspring is an exact copy of the parents.
    3. [Mutation] With a mutation probability, mutate the new offspring at each locus (position in the chromosome).
    4. [Accepting] Place the new offspring in the new population
  4. [Replace] Use the newly generated population for the next run of the algorithm
  5. [Test] If the end condition is satisfied, stop and return the best solution in the current population
  6. [Loop] Go to step 2

Some Comments

As you can see, the outline of the basic GA is very general. There are many things that can be implemented differently in various problems.

The first question is how to create chromosomes and what type of encoding to choose. Closely related to this are crossover and mutation, the two basic operators of a GA. Encoding, crossover, and mutation are introduced in the next chapter.

The next question is how to select parents for crossover. This can be done in many ways, but the main idea is to favor better parents in the hope that they will produce better offspring. You might also notice that creating a new population using only offspring can cause the loss of the best chromosome from the previous population. This is true, so-called elitism is often used. This means that at least one best solution is copied unchanged into the new population, allowing the best solution found to survive until the end of the run.

Some of these questions will be discussed later.

You may also be wondering why genetic algorithms work. This can be partly explained by Holland's Schema Theorem, although the theorem has also been criticized in recent years. If you want to learn more, consult other resources.