Crossover operator

Reproduction by crossover

Since we have ensured (using a selection process) that the fitter individuals tend to survive then the average fitness for the whole population will have also risen. It is these individuals who will mate to form the next generation.

Nature

In nature the next generation is produced using a mating process. This is performed by two parents creating some offspring. The offspring will consist of the genetic material of both parents. There are three options regarding the fitness of the offspring, they can be weaker, the same or fitter than their parents. If they are weaker they will tend to die out – if they are stronger their chances of survival are better. It is of general note that the stronger the parents are in terms of fitness then the fitter the offspring will be. The variation caused by this process allows the offspring to search out different available niches, find better fitness values and subsequently better solutions.

Replicating nature

The job that GAs have in this case is to try and replicate this process. The usual implementation is with crossover. There are no fixed methods associated with crossover. The only general requirement is that the offspring carry forward the important genetic material of the parents, whilst introducing enough variation that they can potentially become more fitter. The crossover method emulates this process by exchanging chromosome patterns between individuals to create offspring for the next generation.

Image of: Fig 3. A typical simple crossover method

Fig 3. A typical simple crossover method

Example

An example of one method is shown in Figure 3 above, which carries forward the example 10 bit individuals introduced in the roulette wheel selection process. In this case we select two parents from the general population. We next take a random value between 0 and 1. This is measured against the crossover probability of Px (usually about 0.7). This emulates the fact that not all individuals mate every generation. If the random value is greater than Px the parents are simply placed into the next generation unaltered. If the value is less than Px crossover takes place.

Crossover begins by generating two random numbers in the range of the number of bits that make up the chromosome length. In the example in Figure 3, we have generated values of 3 and 7. A gene slice is then taken from both parents and exchanged. These then form two offspring - the child chromosomes, which are then placed into the next generation. Mating is deemed to have taken place and chromosome patterns exchanged. Figure 3 shows that in this example the two parent chromosomes with fitness values of 6.82 and 8.48 form two children. Their fitness values are 5.06 and 8.95. So a weaker child and a stronger child have been created in this instance. We may assume that the stronger child will survive and provide better overall fitness to the next generation. The weaker one will also progress but will have less chance of surviving.

There are many different types of crossover methods used in GAs. The above is a simple example of one approach. The only basic premise for a crossover method is that some genetic material should be crossed over to create a new generation.

The children and unmated parents generated using this part of the overall algorithm are then potentially subjected to a mutation operator.

Contact the EDC

For further details of the EDC's activities please get in touch with us through our contact page.

Commercial Research at Newcastle University

A full list of commercially available research facilities for Newcastle University can be found on the Services for Business web pages.