IV. Genetic Algorithm

Basic Description

Genetic algorithms are inspired by Darwin's theory of evolution. Solution to a problem solved by genetic algorithms uses an evolutionary process (it is evolved).

Algorithm begins with a set of solutions (represented by chromosomes) called population. Solutions from one population are taken and used to form a new population. This is motivated by a hope, that the new population will be better than the old one. Solutions which are then selected to form new solutions (offspring) are selected according to their fitness - the more suitable they are the more chances they have to reproduce.

This is repeated until some condition (for example number of populations or improvement of the best solution) is satisfied.

Example
As you already know from the chapter about search space, problem solving can be often expressed as looking for the extreme of a function. We solve exactly this problem here - a function is given and GA tries to find the minimum of the function.
Try to run genetic algorithm in the following applet by pressing the Start button. The graph represents a search space and vertical lines represent solutions (points in search space). The red line is the best solution, green lines are the other ones.
The Start button starts the algorithm, Step button performs one step (i.e. forming one new generation), Stop button stops the algorithm and Reset button resets the population.

Here is applet, but your browser does not support Java. If you want to see applets, please check browser requirements.





Outline of the Basic Genetic Algorithm

  1. [Start] Generate 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 following steps until the new population is complete
    1. [Selection] Select two parent chromosomes from a population according to their fitness (the better fitness, the bigger chance to be selected)
    2. [Crossover] With a crossover probability cross over the parents to form new offspring (children). If no crossover was performed, offspring is the exact copy of parents.
    3. [Mutation] With a mutation probability mutate new offspring at each locus (position in chromosome).
    4. [Accepting] Place new offspring in the new population
  4. [Replace] Use new generated population for a further run of the algorithm
  5. [Test] If the end condition is satisfied, stop, and return the best solution in 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 parameters and settings that can be implemented differently in various problems.

The first question to ask is how to create chromosomes and what type of encoding to choose. We then address Crossover and Mutation, the two basic operators of GA. Encoding, crossover and mutation are introduced in 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 select the better parents (best survivors) in the hope that the better parents will produce better offspring.

You may think that generating populations from only from two parents may cause you to loose the best chromosome from the last population. This is true, and so elitism is often used. This means, that at least one of a generation's best solution is copied without changes to a new population, so the best solution can survive to the succeeding generation.

You might be wandering, why genetic algorithms work. It can be partially explained by the Schema Theorem (Holland), however, this theorem has been criticized in recent times. If you want to know more, check other resources.

           
(c) Marek Obitko, 1998