Page 96 - Data Science Algorithms in a Week

80 Fred K. Gruber

the nondeterministic version, the fitter individual is selected with certain probability.
Tournament selection is becoming a popular selection method because it does not have
the problems of fitness-proportionate selection and because it is adequate for parallel
implementations (Bäck et. al., 2000).
Other selections methods include rank-based selection, Boltzman selection, steady
state selection, sigma scaling and others. For a complete survey of the different selection
methods the reader can refer to Bäck et. al. (2000) and Mitchell (1998).

Operators

There are two main types of operators Bäck et. al. (2000): unary, e.g., mutation and
higher order operators, e.g., crossover. Crossover involves two or more individuals that
are combined together to form one or more individual. The simplest crossover type is
one-point crossover as shown in Figure 3:

Parent1: 1 0 1 1 0 0 0 1 0 1 0 0 0 1
Parent2: 1 0 1 0 1 0 1 0 0 1 1 1 1 1

One point
crossover
point
Child 1: 1 0 1 1 0 0 1 0 0 1 1 1 1 1
Child 2: 1 0 1 0 1 0 0 1 0 1 0 0 0 1

Figure 3. One-point crossover.
This operator has an important shortcoming: positional bias—the bits in the extremes
are always exchanged. This type of crossover is rarely used in practice (Bäck et. al 2000).
Two-point crossover is a variation of the previous operator as illustrated in Figure 4:

Parent1: 1 0 1 1 0 0 0 1 0 1 0 0 0 1
Parent2: 1 0 1 0 1 0 1 0 0 1 1 1 1 1

Two point
crossover
point
Child 1: 1 0 1 1 0 0 0 1 0 1 0 0 0 1
Child 2: 1 0 1 0 1 0 1 0 0 1 1 1 1 1

Figure 4. Two-point crossover.