V. Operators of GA

---

Overview

As you can see from the genetic algorithm outline, crossover and mutation are among the most important parts of a genetic algorithm. Its performance is influenced mainly by these two operators. Before we explain crossover and mutation in more detail, it is useful to say a few things about chromosomes.

---

Encoding of a Chromosome

In some way, a chromosome must contain information about the solution it represents. The most commonly used encoding is a binary string. A chromosome could then look like this:

Each chromosome has one binary string. Each bit in this string can represent some characteristic of the solution. Or the whole string can represent a number - this is what was used in the basic GA demonstration.

Of course, there are many other ways of encoding. This depends mainly on the problem being solved. For example, one can encode integer or real numbers, sometimes it is useful to encode some permutations and so on.

---

Crossover

After deciding which encoding to use, we can move on to crossover. Crossover selects genes from parent chromosomes and creates new offspring. The simplest way to do this is to choose a random crossover point, copy everything before that point from the first parent, and then copy everything after that point from the second parent.

Crossover can then look like this (| is the crossover point):

There are other ways to perform crossover. For example, we can choose more than one crossover point. Crossover can become quite complicated, and it depends heavily on the chromosome encoding. A crossover method designed for a specific problem can improve the performance of the genetic algorithm.

---

Mutation

After crossover is performed, mutation takes place. Its purpose is to prevent the entire population from falling into a local optimum of the problem being solved. Mutation changes the new offspring randomly. For binary encoding, we can switch a few randomly chosen bits from 1 to 0 or from 0 to 1. Mutation can then look like this:

Like crossover, mutation depends on the encoding. For example, when we are encoding permutations, mutation could mean exchanging two genes.