XI. Crossover and Mutation

---

Introduction

Crossover and mutation are the two basic operators of a GA. The performance of a GA depends heavily on them. The type and implementation of these operators depend on the encoding and on the problem itself.

There are many ways to perform crossover and mutation. This chapter gives only a few examples and suggestions for applying them to several encodings.

---

Binary Encoding

Crossover

Single point crossover - one crossover point is selected. The binary string from the beginning of the chromosome to the crossover point is copied from one parent, and the rest is copied from the second parent.

11001011+11011111 = 11001111

Two point crossover - two crossover points are selected. The binary string from the beginning of the chromosome to the first crossover point is copied from one parent, the part from the first to the second crossover point is copied from the second parent, and the rest is copied from the first parent.

11001011 + 11011111 = 11011111

Uniform crossover - bits are randomly copied from either the first or the second parent.

11001011 + 11011101 = 11011111

Arithmetic crossover - some arithmetic operation is performed to create a new offspring.

11001011 + 11011111 = 11001001 (AND)

Mutation

Bit inversion - selected bits are inverted.

11001001 =>  10001001

Permutation Encoding

Crossover

Single point crossover - one crossover point is selected. Up to this point, the permutation is copied from the first parent. Then the second parent is scanned, and each number that is not yet in the offspring is added.
Note: there are several ways to produce the remainder after the crossover point.

(1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) = (1 2 3 4 5 6 8 9 7)

Mutation

Order changing - two numbers are selected and exchanged.

---

Value Encoding

Crossover

All crossover methods from binary encoding can be used.

Mutation

Adding a small number (for real-value encoding) - a small number is added to or subtracted from selected values.

---

Tree Encoding

Crossover

Tree crossover - one crossover point is selected in each parent. The parents are divided at that point and exchange the parts below the crossover point to produce new offspring.

Mutation

Changing operator, number - selected nodes are changed.