The crossover of enumerated chromosomes depends upon their representation type.  For chromosomes using repeating representation, there is no restriction on the gene value before and after crossover, because any gene may have any value from the alphabet independent of the value of all other genes.  In this case, the crossover of enumerated chromosomes is similar to the crossover of continuous chromosomes with binary alleles.

Figure A.4  An example of the crossover operator for two individuals with enumerated chromosomes.  Each individual has a single chromosome consisting of eight genes, each with an alphabet size of eight.  Enumerated chromosomes can have repeating representation, so after the crossover operation the offspring can contain duplicate gene values.  The vertical bar marks the crossover point.

Note that the new offspring of two enumerated chromosomes using repeating representation consist of genes with duplicate values.  This type of crossover swaps parts of two chromosomes between each of two mates involved in the reproduction process.  Such a crossover operator is a simple computational analog of the exchange of genetic information in real life during the reproduction of biological cells.

Enumerated chromosomes using the unique representation have a strong constraint:  after the crossover operation, they must not contain genes with equal values, i.e., there must not be duplicate genes in the new offspring.  Otherwise, if there are duplicate values in the new offspring, such an individual will be in conflict with the conditions of the problem.  For example, in the TSP problem, the repeating crossover operator is applied to the following two mates:

1-5-2-8-7-4-3-6 and 4-2-5-8-1-3-6-7

With the crossing point between the third and fourth genes, we will create two new offspring:

1-5-2-8-1-3-6-7 and 4-2-5-8-7-4-3-6

The new offspring do not correspond to the main condition of the TSP problem:  the first offspring contains double 1s and the second one contains double 4s.  Remember that according to the TSP conditions, each city must be visited only once.  Therefore, we need to invent a new type of crossover for enumerated genes with unique representation.  This new type of crossover is called Partially-Matched Crossover (PMX)[Ref. 4].

Figure A.5  Example of the Partially-Matched Crossover (PMX) operator for two individuals with single 8-gene chromosomes each.  The alphabet size of the genes is equal to 8.  An enumerated chromosome has unique representation, and after PMX crossover the new offspring never contain duplicate gene values.  Two vertical bars mark the two crossover points.

In PMX, two chromosomes are aligned as two strings of genes and two different crossing points are randomly chosen along the strings (in classic repeating crossover there is only one crossing point).  These two points enclose a matching section of one or more genes of a chromosome.  This matching section is transferred from one mate chromosome into another mate chromosome.  PMX proceeds by position wise exchanges.  These exchanges are illustrated by Figure A.5.

The section of mate 1 consisting of the string 2-8-7 is moved into the offspring.  Two neighboring sections of mate 2 (the left consisting of 4-2 and the right consisting of 3-6-7) cannot be moved directly into the offspring.  Therefore, swapping takes place.  The 2 and 5 and the 1 and 7 exchange places in mate 2.  The 8 is already in place so no exchange is required.  After such exchanges, the left and right sections of mate 2 are ready to be directly copied into the offspring.

The parameter that is called crossover rate (as for continuous chromosomes) regulates the degree of chromosome mixing.  This parameter sets the probability that the crossover operator will be applied to a pair of corresponding chromosomes.  If this probability is equal to 0, the contents of all enumerated chromosomes are simply copied from one mate to its offspring.  If we would like to have on the average one crossover operation per all enumerated chromosomes of an individual, we may use the probability equal to 1/n, where n stands for the number of enumerated chromosomes per individual.

The probability of crossover of an individual consisting of multiple enumerated chromosomes is calculated by:

ind_cross_rate=1-(1-crossover_rate)^n,

where crossover_rate stands for the probability of crossover per chromosome, ind_cross_rate stands for the probability of crossover per individual, and n is the summary number of all enumerated chromosomes in an individual.

Usually, values in the range 0.8-1.0 are appropriate for the crossover_rate.  For example, if an individual consists of three enumerated chromosomes, and if the crossover_rate=0.8, then the total probability of crossover of such an individual is equal to 0.992.  If the population numbers 200 individuals, then in every generation the average number of crossovers will be equal to 198.