Genetic Algorithm

Defining the Genetic Algorithm¶

When discussing how cBots could be optimised, we have mentioned that cBots can be refined using the 'generic algorithm' method. In this guide, we explain exactly what it is and how it works.

The generic algorithm method is based on the natural selection theory. This theory states that only the fittest individuals survive for subsequent reproduction.

In cBot optimisation, each optimisation pass is considered an 'individual'. To evaluate individual passes, the genetic algorithm calculates a certain fitness score for each pass and compares this score against all other passes.

For it to work, the generic algorithms needs an initial population. To generate it, the optimiser will run several different passes with randomised parameters. After creating its initial population, the algorithm will start the process of finding the fittest optimisation pass. This process continues until the fitness scores of 'child' passes start stagnating and converging. At this point, the algorithm is stopped.

Genetic Algorithm Stages¶

Any genetic algorithm has the following stages.

graph TB
  B([Selection]) ==> C([Crossover]);
  C ==> D([Mutation]);
  D ==> B;

The stages are explained as follows.

Selection¶

During this stage, the algorithm finds two fittest optimisation passes using their respective fitness scores.

Crossover¶

After finding the two fittest optimisation passes, the algorithm uses them to create new 'child' (or 'offspring') passes by using combinations of the parameter values of both of the 'parent' passes.

Mutation¶

At this stage, the algorithm 'mutates' the 'offspring' passes by randomly modifying one or more parameter values.

After the mutation stage, the optimiser will run a new 'offspring' optimization pass. Subsequently, it will repeat all stages but only if the fitness score of an 'offspring' pass was higher than the last fittest optimisation pass. Such an outcome would mean that there is room for improvement, indicating that optimisation should continue.

Otherwise, the algorithm will increase its stagnation counter. If the stagnation counter reaches the value of the algorithm stagnation period parameter, the optimisation process will be automatically stopped.

Genetic Algorithm Parameters¶

The genetic algorithm has several parameters that it uses during its lifetime. These parameters cannot be changed.