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).

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).

{ "reg":[
   {"bits": 1, "name": "p0"},
   {"bits": 1, "name": "p1" },
   {"bits": 12, "name": "..." },
   {"bits": 1, "name": "p14" },
   {"bits": 1, "name": "p15" },
   ],
  "config": { "bits":16,"lanes":1 }
}

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):

A nice introduction to have a quick view of GA key mechanisms
Documentation giving a more detailed view of mechanisms
Full GA implemented without libs, which is nice to understand the principles
Well described full example
A DEAP library example in Jupyter
This one intends to found a binary string which match a reference

Examples

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