Genetic Algorithms#

Quick definition#

Genetic Algorithms (GA) are part of the Evolutionnary Algorithms (EA) family. It consists in algorithms which are inspired by nature mechanisms such as reproduction, mutation, recombination and selection. The key element is to have a low computationnal need to determine the capability of the solution to fulfill the needs.

GA is a probabilistic approach of EA.

Description#

The cycle is composed by following stages:

  • Population initialization

  • Evaluation

  • Check if termination criteria is reached, if not continue

  • Reproduction

  • Crossover

  • Mutation

  • Back to termination criteria and end if reached

Depending of the objective, it could have some variations, especially in the way the mutations are integrated or a form of elitism could occurs (keep best individuals through generations without mutations).

digraph {
   label="Genetic algorithm cycle";

   node[shape="box", style="rounded"]
      start; end;
   node[shape="box", style=""]
      population; evaluation; selection; reproduction; mutation; best;
   node[shape="diamond", style=""]
      if_termination;

   start -> population;
   population -> evaluation;
   evaluation -> if_termination;
   if_termination -> selection[label="no"];
   if_termination -> best[label="yes"];
   best -> end;
   selection -> reproduction;
   reproduction -> mutation;
   mutation -> evaluation;

   if_termination[label="Is termination\nreached?"]
   population[label="Population\ninitialisation"]
   evaluation[label="Evaluate\npopulation"]
   reproduction[label="Reproduction"]
   mutation[label="Mutations"]
   best[label="Keep best\nindividual(s)"]
}

Begin by generating a random (or pseudo-random, see further) population of individuals which encode the problem in a gene. This gene is generally a list of numbers (binary or real), each of them encoding a parameter (p0 to pn).

Then define a function which evaluate how an individual fulfill the criteria. This will give a score to sort all the population.

A test is performed to check if any of the individual could be good, it’s the evaluation.

Odd are high that on the firsts iterations it’s not the case, so a selection is performed to get the best individuals and mating them, creating a crossover of their genes. This process could involve different ways of pairing individuals, depending of the objective.

Random mutations could then occurs on childrens and sometimes parents, again depending of the implementation. This bring new genes, aka new characteristics into the genes pool constitued by the initial population.

Finally when the termination criteria is achieved, the best(s) individual(s) is(are) keeped as solution(s).

Ressources#

The internet is full of documentation, here a list of some well written contents (more or less Python oriented):

Examples#

One can find a few examples in the dedicated SPL repo.

Algorithm Genetic Algorithm