Genetic algorithms

Contents

Genetic algorithms are stochastic algorithms iterative that operate on individuals from an initial population.

In genetic algorithms, the population evolves from generation k to generation k + 1 using three operators:

a Selection operator
a Crossover operator
a Mutation operator.

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

Randomly generated base population: n solution vectors (individuals)
Evaluation of each individual, this evaluation returns a quantitative value (fitness)
Selection by lot of a subset of individuals by a biased wheel, by rank, by tournament or by eugenics. Each individual has a probability of being chosen proportional to his assessment (or adaptation to the problem).
Crossbreeds and Mutations of selected individuals.

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.

Example

In order to be able to carry out crossings and mutations as simply as possible, we are going to encode the individuals by a binary string. The crossing will then be done by a substring, and the mutation by the modification of a bit. This process is called binary encoding.

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:

Element	f (x)	% / total	cumulative
10111010	0.794678	0.79/2.59=0.31	0.31
11011110	0.460693	0.18	0.49
00011010	0.364990	0.14	0.63
01101100	0.9775586	0.37	1.00
–	2.595947	–	–

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.