Genetic algorithm

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

The population evolves from generation k to generation k + 1 using three operators:

  • a Selection operator
  • a Crossroad operator
  • a Mutation operator.

The process comes from genetic evolution. We start with a population of initial potential solutions arbitrarily chosen. Their relative performance (fitness) is evaluated. Based on these performances, a new population of potential solutions is created using the operators. This cycle is repeated until it reaches a satisfactory solution.

Genetic programming

schema_simple_algorithme_genetique

  1. Randomly generated core population: n solution vectors (individuals)
  2. Evaluation of each individual, this evaluation returns a quantitative value (fitness)
  3. Selection by lot of a subset of individuals by biased wheel, rank, tournament or eugenics. Each individual has a probability of being chosen proportional to its evaluation (or adaptation problem).
  4. Crossings and mutations of selected individuals.

Crosses and mutations do not necessarily provide acceptable 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 perform crosses and mutations as simply as possible, we will encode 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 have 4 individuals. The value of the initial generation is:

Individuals
f(x)
% / total
sum
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

f(x) represents the value of the objective function, %/total is the percentage of the value of the objective function of an element in function of the sum of the values of the objective function. In the end, we therefore 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 crossover. Since we have a scale of importance for each individual, we can draw individuals. Indeed, the higher the objective value of an individual, the more likely he is to be drawn. Four random numbers are drawn between 0 and 1: 0.34, 0.02, 0.64 and 0.77. We have selected these individuals: 11011110, 10111010, 01101100, 01101100.

We have selected the parents, we must now perform the crossing. For this, we choose a random marker in the bit string, and we swap the right part of the string:

gene

The population of the next generation consists of four children created. In general, we will avoid crossing between two identical individuals.

 

Publicités