When using genetic algorithms to solve TSP type problems, we cannot use ordinary crossovers and mutations since these lead to new solutions that are not tours. For example, if we start with the two tours for a 9-city TSP:

(9 4 3 1 6 8 2 5 7)

(1 6 5 7 2 9 8 3 4)

and do an ordinary crossover at position 4 we get:

(9 4 3 1 2 9 8 3 4)

(1 6 5 7 6 8 2 5 7)

Because of the repeating cities, neither is a valid tour. In the following question we do three crossovers which are designed to give valid tours (most of the time).

So suppose that a genetic algorithm is used to find a solution to a 9-city travelling salesman problem and the following strings have been selected as parents:

Parent 1 : (9 4 1 3 6 8 2 5 7)

Parent 2 : (1 6 5 2 7 9 8 3 4)

In each of the following cases give the two offspring that are generated. If the offspring are not viable explain why and what happened.

(i) A partially mapped crossover operator (PMX) is used with the mapping defined on positions 3 to 6 (that is, consider positions 3,4,5,6).

(ii) The C1 crossover operator is used with crossover at position 4.

(iii) The crossover template 110101011 is used.