Genetic Algorithms: Operators

TL;DR

Every genetic algorithm is built from 4 basic phases: population generation and then selection (evaluation), mutation and crossover repeated in loop. There are many other steps that can be added and variations, but the classic genetic algorithm contains only that four.

Please check short schema too understand how the genetic algorithms work:

As I mentioned before, we can see here 4 steps that create a full algorithm:

1. Generation - generate an initial population or generate missing individuals.
2. Selection - evaluate each individual in population and choose only the number of the best ones.
3. Crossover - make a mix of individuals, exchange individual "genetic code" to simulate natural processes.
4. Mutation - randomly change some of individuals to mimic real mutations which can be met in nature - evolution.

We can stop algorithm after the specific STOP criteria have been satisfied. Below some examples:

• Stop algorithm after fixed number of generations - populations.
• Stop algorithm when the best calculated evaluation is not changing with given precision. We define a value which denotes how precise should be the result e.g. 0.00001, to stop simulation when difference between previous the best individual and current the best individual is equal or lower than this value.

At the end, the best of all individuals that we found over the generations becomes our solution.

Now let's make short intro to the GA (Genetic Algorithms) nomenclature.

Chromosome / Individual / Gene

In GA (genetic algorithms) the solutions of problem are called individuals and are presented in any arbitrary selected form. Because in real evolution world each individual is represented by a set of genes, we will call our individual a chromosome. Chromosome describes unambiguously single individual by a set of genes. Each gene is a part of chromosome locating him in a space of all solutions of problem. Let's assume that chromosome is a point on a Google map, it could be represented (just for example) by two genes like below:

or by 3 in 3D space:

.

Population

Population is a group of individuals leaving in the same environment - using optimization language - the same space of solutions. Population in our case is a set of chromosomes that creates a current space of found solutions. The size of population may vary for different problems that optimization is solving.

Operators: classic selection

Natural selection in real life denotes that only the strongest individuals can survive. The same idea was brought to the GA's. The evaluation of chromosome fitness is a key. We always need to have evaluation function that will give us a number or group of parameters saying that this individual is better than other. 

Let's make an example. We define an objective function at first:

          \[ f(x,y)=x \cdot sin(y) + y \cdot sin(x) \]

We want to find a maximum of that function in defined space (rectangle 8x8):

          \[ x \in \{ 0 \dots 8\}, y \in \{ 0 \dots 8\}. \]

In this way, we will favor chromosomes that has bigger evaluation result of function f(x,y). We will maximize the function:

 \[ eval(x,y)=max(f(x,y)). \]

How it works? We go through the population, calculating the value of function \( f(x,y) \) for each chromosome. 

The selection will simply sort whole population by the value of \( eval(x,y) \) function and remove some fixed or random number of the weakest individuals. In that way we always eliminate the worst individuals. Easy, isn't it? Yeah, but this is only one of possibilities and not the best solution, we can call it a classic selection. 

Other selection types

Image a fact that in real life all weak animals will always die. That's how it may work in the simplest selection. We just choose the worse individuals and remove them - kill them. Normally selection is a very complex process in nature. To make the GA selection closer to it, a lot of variations of selection operator were created. It's not in the scope of this post to describe them all, but take a look on some examples. I will try to explain them in my future posts of this series.

• Roulette wheel selection,
• Tournament selection,
• Elitists selection,
• Rank selection,
• Boltzman selection,
• ... and many variations of them.

Operators: uniform mutation

In real live we can observe genetic mutation very often. Example, moles on the skin, but also more serious changes like genetic disease. Mutation introduces something new into chromosome, shows new way in an exploration space. Without mutation we would find easy solutions only, we won't be able to find surprising solutions hidden somewhere. I will show you the simplest mutation - uniform mutation. How it works? It's simple, we need to define the mutation probability first. A default value can be for us 25%, for computation it will be 0.25. Next step is to find one random gene within whole population, then we check if the gene should be mutated. There is a formula to check it:

1. Assume a probability value \( p_c = 0.25 \)
2. Find a random number in range \( rnd = 0 \dots 1 \)
3. If \( rnd < p_c \) then mutate gene

And how to mutate the gene? We need to know the possible values range for gene, and simple randomize new gene in available range and replace it by this random value. This way we create a mutated gene. 

NOTE: Please be aware that this is just a basic framework description. There exist many variations of mutation and even some of them create invalid genes which are outside the available range. That kind of mutations helps to find solutions that normally can be unreachable.

Operators: crossover (binary chromosomes)

The last operator I want to describe is crossover. When the mutation give us the fresh wind of changes, here crossover is used to exchange the genetic material. In genetic terminology it is a breaking of chemical bonds and exchanging the parts between chromosomes. In our example the chemical bonds are rather virtual and we can locate them between genes in chromosome. For genetic algorithm this operator is used to create new children. Below you can see how one-point crossover works.

Crossover is very specific operator because in some cases it may generate invalid individuals - outside the solutions space or the ones that makes no sense from the perspective of problem we're solving. Here we focus on simple binary chromosomes (genes are 0 or 1) or chromosomes that can be easily exchanged in parts giving valid individual as a result.

Summary

I tried to present you in the simplest words how the genetic algorithm operators works. In the next posts of this series I will explain how to encode the numeric solution / value in the chromosome using various representations.