274
D. Irawan and B. Naujoks
Fig. 8.3 Example of recombination: the single point crossover. Part of the chromosomes from two
parents (left) are switched resulting in two offspring (right) with different chromosome sequences
Fig. 8.4 Recombination using uniform crossover. The crossover can happen anywhere within the
chromosome
Fig. 8.5 Recombination using uniform crossover on real values. Similar with the binary counterpart, but instead of the bits, each block is a variable by itself
common one is by swapping gene values. More generally, some transformation
functions are applied to gene values, like in the case in which the new recombining
gene is obtained taking the average value of the corresponding genes belonging to
the parents. One of the most widely used recombination operator is the simulated
binary crossover (SBX) (see [1]).
The simplest recombination operation is single point crossover in binary encoding. In single point crossover, starting from a crossover point, the bit value of
two parent chromosomes is swapped (see Fig. 8.3). In the bit swapping shown in
Fig. 8.3, the offspring genes before the crossover point are unchanged, while after
the crossover point, the genes are swapped. Another variant is uniform crossover
[5] where the crossover is triggered for each bit in the chromosome as shown in
Fig. 8.4.
The recombination operator is also available in real encoding. In principle, the
requirement for a crossover operator is that the offspring are a combination of their
parents. An example of real-valued crossover is the discrete crossover [5] where
the variable values are swapped, similar with the binary chromosome, but instead of
bits, the real values are swapped, illustrated in Fig. 8.5.