Crossover and mutation are the primary engines of innovation in a Genetic Algorithm. They are responsible for generating novel solutions and exploring the search space. Crossover is analogous to biological reproduction, combining traits from two parents to create offspring, thereby exploiting the genetic material of good solutions. Mutation, on the other hand, introduces small, stochastic modifications, facilitating the exploration of new and uncharted areas of the search space.

8.1 Crossover (Recombination)

The crossover operator takes two or more selected parents and produces one or more offspring by combining their genetic material. It is typically applied with a high probability, denoted as pc.

Crossover Operators

• One-Point Crossover: A single crossover point is randomly selected along the length of the chromosomes. The “tails” of the two parent chromosomes are then swapped to produce two new offspring.
• Multi-Point Crossover: This is a generalization of one-point crossover where two or more crossover points are selected. The segments between alternating points are then swapped between the parents.
• Uniform Crossover: Instead of swapping large segments, uniform crossover treats each gene independently. For each gene position, a virtual coin is flipped to decide which parent will contribute its allele to the offspring.
• Whole Arithmetic Recombination: This operator is used for integer or real-valued representations. It produces offspring by taking a weighted average of the two parents. The formulas are:
  • Child1 = α * Parent1 + (1-α) * Parent2
  • Child2 = α * Parent2 + (1-α) * Parent1 When α is set to 0.5, the operator produces two identical children representing the midpoint between the parents.
• Davis’ Order Crossover (OX1): This specialized operator is designed for permutation-based representations, like those used in the Traveling Salesman Problem. It works by preserving the relative ordering of genes from the parents. For example:

• 1. Consider two parents and two random crossover points (marked by |): P1: [8 4 7 | 3 6 2 | 5 1] P2: [0 1 2 | 4 5 3 | 6 7]
  2. Copy the segment from the first parent directly to the first offspring: Child1: [ _ _ _ | 3 6 2 | _ _ ]
  3. Fill the remaining positions from the second parent, in order, skipping any numbers already present (3, 6, 2). Start from the second crossover point and wrap around: P2 contains 6, 7, 0, 1, 2, 4, 5, 3. Skipping existing numbers, we take 7, 0, 1, 4, 5. Child1: [ 7 0 1 | 3 6 2 | 4 5 ]
  4. The process is repeated with the parents’ roles reversed to create the second offspring.

8.2 Mutation (Variation)

Mutation is a small, stochastic modification applied to a single chromosome to introduce new genetic material and maintain diversity within the population. It is applied with a very low probability, pm, because a high mutation rate would effectively reduce the GA to a random search.

Mutation is crucial for the exploration of the search space. It can reintroduce alleles that may have been lost from the population or create entirely new ones, allowing the GA to escape local optima. It has been observed that mutation is essential for the ultimate convergence of a GA.

Mutation Operators

• Bit Flip Mutation: Used for binary encodings. One or more random bits in the chromosome are selected and flipped from 0 to 1 or 1 to 0.
• Random Resetting: Used for integer representations. A randomly chosen gene is assigned a new, random value from its set of permissible alleles.
• Swap Mutation: Used for permutation encodings. Two gene positions are chosen at random, and their alleles are interchanged.
• Scramble Mutation: Used for permutation encodings. A random subset of genes is selected, and their positions within that subset are shuffled randomly.
• Inversion Mutation: Used for permutation encodings. A random subset of genes is selected, and the order of the genes within that subset is reversed.

Once new offspring have been created through crossover and mutation, the final step in a generation’s cycle is to decide which individuals will survive to form the population for the next generation.