Calculate the offspring from parents P1 and P2 using the cycle crossover (CX) method.

Show all your working.

The partially matched crossover (PMX) operator is a genetic operator that can be used with a genetic algorithm written to solve the travelling salesman problem.

PMX combines two chromosomes (parents) to produce a new chromosome (offspring).

Outline how the parental characteristics (cities) are preserved when two offspring are generated through PMX crossover.

Award [4 max].

Solution 1

Award [1] for B D in correct place
Award [1] for G I F J in correct place
Award [1] for C E in correct place
Award [1] for A H in correct place

Solution 2

Award [1] for D G in correct place
Award [1] for I F J B in correct place
Award [1] for A C in correct place
Award [1] for H E in correct place 

Note to examiners: allow follow through errors, so that if a candidates’ logic is correct from the point of an error, they are awarded marks that point onwards.

Award [4 max].

Offspring 1
PMX algorithm randomly selected sub-sequence of P1 is copied into the first offspring;
P2 contributes the remaining cities to the first offspring;
To ensure that P2 cities are not duplicated, they are mapped against P1;

Offspring 2
The remaining cities in P1 (i.e. not copied to offspring 1) are copied into the second offspring;
P2 contributes the remaining cities to the second offspring;
To ensure that P2 cities are not duplicated, they are mapped against P1;

Award [1] for this alternative offspring 2 solution if offspring 1 is correctly described

Alternative Offspring 2
The process for offspring 1 is repeated but with a different P1 random subsequence;

Mark as [2 max] for Offspring 1 and [2 max] for Offspring 2

Accept a correct example that explains the process but not replicated from the case study.

This question asked candidates to calculate offspring from two given parents using the cycle crossover (CX) method. An example was given in the case study so candidates would not have to memorize the procedure, just apply it to a new set of data. The majority of answers correctly showed the generated offspring but approximately one-third made mistakes. Very few candidates received zero marks.

This asked candidates to describe how the partially matched crossover (PMX) operator could produce two offspring. Most candidates received two of the 4 available marks. Very few candidates received all 4 marks because they only described how the method created one offspring. The case study describes PMX with an example that shows only one offspring and candidates were expected to do additional reading to understand that this method can produce a second offspring.