Genetic algorithms are stochastic algorithms iterative that operate on individuals from an initial population.
The process comes from genetic evolution. We start with a population of arbitrarily chosen initial potential solutions. We assess their relative performance (fitness). On the basis of these performances, we create a new population of potential solutions using the operators. This cycle is repeated until with a satisfactory solution.
Genetic programming and genetic algorithms
The crosses and mutations of genetic algorithms do not necessarily give admissible solutions to the problem. They operate by altering, copying, replacing, etc., the solution vector of one or more individuals to form a new one.
We are looking for the maximum of f (x) = 4x * (1-x) over the interval [0,1]. We take an initial population of 4 elements encoded on 8 bits (which will be converted into a value between 0 and 1). The new generations will always include 4 individuals. The value table for the initial generation is as follows:
% / total
Element represents individuals, f (x) the value of the objective function, % / total is the percentage of the value of the objective function of an element compared to the sum of the values of the objective function, accumulation is the sum of percentages. We therefore ultimately have the importance of each individual given the value of the objective function.
Now that the evaluation is done, we need to select individuals for the cross. Since we have a scale of importance of each individual, we can draw lots of individuals. Indeed, the greater the objective value of an individual, the more likely he is to be drawn. We draw four random numbers between 0 and 1: 0.34, 0.02, 0.64 and 0.77. We therefore selected these individuals: 11011110, 10111010, 01101100, 01101100.
We have selected the parents, it is now necessary to cross. For that, we choose a random marker in the bit string, and we swap the right part of the string:
The population of the next generation is made up of the four children thus created. In general, we will avoid making a cross between two identical individuals.