Library tutorials & articles

An Introduction to Genetic Algorithms

Mutation and Crossover

As their names suggest, mutation and crossover are terms which derive from evolution.  Firstly mutation, the theory is simple, in the same way that human beings and animals vary from generation to generation, random bits (genes!) are randomly altered from 1 to 0 and vice versa each time we loop back to the start (generation!).  Imagine a group of 5 guesses (population!), guesses 1 to 5:

By randomly mutating the last 4 characters in guess3 to 1000 a slightly different guess is produced.  This mutation is necessary to ensure that all the solutions do not become the same too quickly.

Crossover is like breeding animals or humans, in that two guesses are selected (parents!) to combine and form two different guesses (children!), imagine two guesses which are selected at random from our five above:

guess1 – 1, 9 - 00011001
guess4 – 3, 5 - 00110101

They are split in half and the bits after the split are swapped over to produce two different guesses:
 
0001        0101
0011        1001

Then stuck back together two make two new guesses:

guess1 – was 1,9 - 00011001 – now 00010101 = 1, 5
guess2 – was 3,5 – 00110101 – now 00111001 = 3, 9

Comments

  1. 25 Oct 2008 at 16:18
    I think your math is slightly off... in your example you derice 23 and 75.5 from formulars that don't arrived at these... what am I missing ??? 5*4 = 20, 20/2 = 10, 10 + 1 = 11, 11 + 6 = 17
  2. 26 Apr 2007 at 20:30
    I think that's a basic knowledge of GAs.
    Can give to us about detail of GAs, and another important application of this algorithm especially in Robot?


  3. 01 Jan 1999 at 00:00

    This thread is for discussions of An Introduction to Genetic Algorithms.

Leave a comment

Sign in or Join us (it's free).

Rob Bickel

We'd love to hear what you think! Submit ideas or give us feedback