What is a genetic algorithm?

A genetic algorithm is an optimization method that imitates the mechanisms of natural selection and aims to iteratively improve populations of potential solutions. Genetic algorithms are used in a wide variety of fields, ranging from the optimization of technical systems to Machine learning.

What do we mean by genetic algorithms?

Genetic algorithms, or Genetic Algorithms (GA), are a global heuristic to solve decision -making problems, based on the principles of natural selection and genetics. Genetic algorithms are part of evolutionary algorithms and use mechanisms inspired by natural selection processes to gradually improve solutions to complex problems. This means that we simulate the « survival of the most apt », which is based on the following principles:

1. Individuals compete for resources and to reproduce.
2. The most efficient or stronger individuals generate more descendants than the others.
3. The genes of the most « fit » parents are transmitted from generation to generation. They often produce descendants whose genetic sequences are more advantageous than their own.
4. As the best genes are transmitted in the long term, each generation is better suited to its environment than the previous one.

Genetic algorithms generate a population of individuals, each constituting a potential solution to the problem posed. Those who adapt the best to their environment survive and reproduce. Each individual is coded in the form of a chromosome, expressed as a character string (whether in characters, bits, float Or interest). In addition, these chromosomes decompose into genes, which represent specific characteristics, such as hair color. The variants of a gene, for example blond, brown or black, are called alleles.

To get closer to the optimal solution, genetic algorithms launch an iterative process in several stages of calculation and reproduction. Chromosomes are modified and combined on several generations or iterations by different genetic operators (selection, crossing or recombination, mutation) in order to gradually find better solutions. This means that genetic algorithms are close to a good global solution by the Combination of good partial solutions.

The process of iteration is typically divided into different tasks:

1. The optimization problem is encoded in the form of a binary chromosome.
2. The genetic algorithm creates a population of individuals and initializes it randomly. The starting population is also called generation 0.
3. Each individual is assigned an aptitude score in the form of a real number.
4. Using a predefined selection variant, the genetic algorithm selects parents in the population.
5. The descendants are created on the basis of genetic information from both parents.
6. The genetic characteristics of descendants (alleles) can mutate, which leads to the inversion of their values.
7. The population increases according to newly created descendants. If the size of the population exceeds the fixed limit, a replacement scheme determines which individuals are no longer part of all the solutions.
8. As long as no stop criterion is fulfilled, the genetic algorithm repeats stages 3 to 7 to get closer to the optimal solution of the problem. The stop criterion can however be designed in a very different way. Some algorithms go through a number of generations, while others are active until there is no more improvement compared to the previous generation.

Adaptation

The adaptation score of an individual indicates his competitiveness. The objective of genetic algorithm is to identify the individual with optimal ability (or almost). Individuals with better scores are more likely to be selected to generate descendants. As a result, new generations have better partial solutions on average than the previous ones.

Which operators use genetic algorithms?

Genetic algorithms use different operators to develop the starting population. The basic mechanisms that allow evolution are selection, recombination and mutation. The different operators of the genetic algorithms are presented in more detail below.

Selection (selection operator)

The selection determines which individuals are allowed to generate descendants and how many descendants are authorized to them. The selection of parents is based on the physical aptitude score, the genetic algorithm favoring individuals with good scores.

Recombination (overcrowding or crossover operator)

New individuals are created by Recombination. The genetic algorithm chooses random crossing sites. The genes are then exchanged in the corresponding places, which gives rise to descendants with new characteristics. The preview below shows an example of a recombination:

• Parent 1 genes: HAS|B| C | D | E |F
• Parent genes 2: G | H |I|J|K| L
• Offspring genes: HAS|B|I|J|K|F

Mutation (mutation operator)

The basic idea of ​​mutations is to introduce random modifications into certain genes, and therefore to modify the potential solution of a decision problem. This helps maintain diversity within the population and to avoid premature convergence. Here is an example of a mutation:

• Genes before mutation: a | b | c | d | e | f
• Genes after mutation: a | b |L| D |T| F

In which areas are genetic algorithms used?

Genetic algorithms are mainly used in fields where traditional analytical methods reach their limits. This is mainly the case for problems with a large and complex solutions space. For example, in Deep Learninggenetic algorithms are used to optimize the weights of neural networks.

Genetic algorithms are also used in production planning, where they allow you to find optimal resource hours and benefits. In the economy and finance, genetic algorithms are used both in the context of portfolio optimization and for the development of complex commercial strategies. Another application area is adjusting hyperparameters from machine learning. Although they are not always the most effective method, genetic algorithms are considered a very versatile optimization technique because of their flexibility.

Example of application of genetic algorithms

Suppose that the task of a genetic algorithm is to generate a target character string, for example  » The Fittest Survive « , Framed from a random character string of the same length. In this example, the different characters (A to Z, A to Z, 0 to 9 and special characters) represent the genes. The character string can however be considered as a chromosome or a solution. The adaptation score represents the number of characters that depart from the target character string. Consequently, individuals with a weak score are favored. The following table shows what the output could look in this case:

However, it should be noted that the output may vary, because the genetic algorithm starts with random character strings.