Genetic Algorithms Crossover

After selection, individuals from the mating pool are recombined (or crossed over) to create new, hopefully better, offspring. In the Genetic Algorithms literature, many crossover methods have been designed (Goldberg, 1989b; Booker et al., 1997; Spears, 1997) and some of them are described in this section. Many of the recombination operators used in the literature are problem-specific and in this section we will introduce a few generic (problem independent) crossover operators. It should be noted that while for hard search problems, many of the following operators are not scalable, they are very useful as a first option.

Figure A.1. One-point, two-point, and uniform crossover methods.
k-point Crossover. One-point, and two-point crossovers are the simplest and most widely applied crossover methods. In one-point crossover, illustrated in Figure A.1, a crossover site is selected at random over the string length, and the alleles on one side of the site are exchanged between the individuals. In two-point crossover, two crossover sites are randomly selected. The alleles between the two sites are exchanged between the two randomly paired individuals. Two-point crossover is also illustrated in Figure A.1. The concept of one-point crossover can be extended to k-point crossover, where k crossover points are used, rather than just one or two. Uniform Crossover. Another common recombination operator is uniform crossover (Syswerda, 1989; Spears and De Jong, 1994). In uniform crossover, illustrated in Figure A.1, every allele is exchanged between the a pair of randomly selected chromosomes with a certain probability, pe, known as the swapping probability. Usually the swapping probability value is taken to be 0.5.

UniformOrder-Based Crossover.The k-point and uniform crossover methods described above are not well suited for search problems with permutation codes such as the ones used in the traveling salesman problem. They often create offspring that represent invalid solutions for the search problem. Therefore, when solving search problems with permutation codes, a problem-specific repair mechanism is often required (and used) in conjunction with the above recombination methods to always create valid candidate solutions.
Order-Based Crossover. The order-based crossover operator (Davis, 1985) is a variation of the uniform order-based crossover in which two parents are randomly selected and two random crossover sites are generated (see Figure A.2). The genes between the cut points are copied to the children. Starting from the second crossover site copy the genes that are not already present in the offspring from the alternative parent (the parent other than the one whose genes are copied by the offspring in the initial phase) in the order they appear. For example, as shown in Figure A.2, for offspring C1, since alleles C, D, and E are copied from the parent P₁, we get alleles B, G, F, and A from the parent P₂. Starting from the second crossover site, which is the sixth gene, we copy alleles B and G as the sixth and seventh genes respectively. We then wrap around and copy alleles F and A as the first and second genes.

Figure A.2. Illustration of order-based crossover.
Partially Matched Crossover (PMX). Apart from always generating valid offspring, the PMX operator (Goldberg and Lingle, 1985) also preserves orderings within the chromosome. In PMX, two parents are randomly selected and two random crossover sites are generated. Alleles within the two crossover sites of a parent are exchanged with the alleles corresponding to those mapped by the other parent.

Figure A.3. Illustration of cycle crossover.
CycleCrossover (CX). We describe cycle crossover (Oliver et al., 1987) with help of a simple illustration (reproduced from Goldberg (1989b) with permission). Consider two randomly selected parents P₁ and P₂ as shown in Figure A.3 that are solutions to a traveling salesman problem. The offspring C1 receives the first variable (representing city 9) from P₁. We then choose the variable that maps onto the same position in P₂. Since city 9 is chosen from P₁ which maps to city 1 in P₂, we choose city 1 and place it into C1 in the same position as it appears in P₁ fourth gene), as shown in Figure A.3. City 1 in P₁ now maps to city 4 in P₂, so we place city 4 in C₁ in the same position it occupies in P1 (sixth gene). We continue this process once more and copy city 6 to the ninth gene of C₁ from P₁. At this point, since city 6 in P₁ maps to city 9 in P₂, we should take city 9 and place it in C₁, but this has already been done, so we have completed a cycle; which is where this operator gets its name. The missing cities in offspring C₁ is filled from P₂. Offspring C₂ is created in the same way by starting with the first city of parent P₂ (see Figure A.3).

www.CodeNirvana.in