Genetic Programming: What is crossover and mutation?

In my last post (What is a chromosome), I described what a chromosome was, but didn't really say what you could do with one. At the beginning of a GP program, you create an initial pool of chromosomes (or the Primordial Soup, if you prefer) which is the basis for a multitude of variations. This is accomplished through crossover and mutation. Crossover takes the chromosome from one parent and merges it with that of another creating two new children. Here is an example of crossover using three inputs:

Mother -> inputs(5, 10, 3) -> Binary(101, 1010, 0011) -> Chromosome(10110100011)
Father -> inputs(4, 2, 13) -> Binary(100, 0010, 1101) -> Chromosome(10000101101)

Now, since our chromosome has a length of 11 lets return a random value between 1 and 9. This ensures that at least the first or last bit from each parent will be passed on to each of the children (we are assuming a 0 based array). Let's say our random number is 4. Our chromosomes will be split in the following manner:

Mother(0): 10110; Mother(1):100011
Father(0): 10000; Father(1): 101101

Combine Mother(0) with Father(1) and Mother(1) with Father(0) to create a two new binary strings:

Mother(0) + Father(1) : 10110 101101-> 10110101101 (Child1)
Mother(1) + Father(0) : 10000 100011 -> 10000100011 (Child2)

Time to mutate! For each of the two children strings select a random number beteen 0 and 10 (the length of the binary string). Using the random value as an index, invert the appropriate bit.

Child1: Random Value=2: 10 1 10101101 -> 10 0 10101101
Child2: Random Value=9: 100001000 1 1 -> 100001000 0 1

Now we can decode our chromosome. We know that the first 3 characters describe the first value, the next 4 describe the second value and the last 4 describe the third value. Let's decode

Child1: 100, 1010, 1101 -> 4, 10, 13
Child2: 100, 0010, 0001 -> 4, 2, 1

You can well imagine how this process running continually over several generations could generate a vast number of combinations.