“Imitating what takes place in nature over several generations, evolutionary algorithms enable selection of the best solutions to a problem within a set”
Human beings have always drawn from nature to develop new technologies and techniques. This highly fertile process of innovation is known as “bioinspiration” or “biomimicry”. Since the mid 1960’s, scientists and engineers have been taking inspiration from Charles Darwin’s theory on the evolution of species that the English naturalist developed in his 1859 book “On the Origin of Species”, in order to develop algorithms capable of finding better solutions to complex optimization problems: evolutionary algorithms.
From Darwin to algorithms
They take inspiration in particular from natural selection, the motor of adaptive change of species, whereby selection of the individuals most likely to survive in a given environment takes place. This mechanism is based on three fundamental principles: variation, adaptation, and inheritance.
According to the principle of variation, a population of living beings is heterogeneous, meaning there are differences between individuals of a same species. These are referred to as variations or traits. For example, the size and shape of the beak of finches observed by Darwin on the Galapagos Islands are traits that vary within these related species of small birds.
Some traits are more advantageous than others as they enable the individuals that have them to survive and reproduce better than their counterparts within their environment. This is the principle of adaptation.
Finally, according to the principle of inheritance, these traits are passed on from one generation to the next, which leads to their spread throughout the population until they become common to all its members. Giraffes’ long necks, a selective advantage enabling them to reach the high leaves of trees in the African savannas, are thus the result of a slow evolution.
Selection, evolution, evaluation
On the basis of these three principles, evolutionary algorithms rely on an iterative process that consists in evolving and evaluating a large set of solutions called “population of individuals”. This process is comprised of several steps.
The first step consists in building (usually randomly) an initial population of heterogeneous individuals with each individual representing a possible solution to the optimization problem posed. Then, the aptitude of each individual to quickly and efficiently solve this problem is evaluated. The function that one aims to optimize is called “fitness”. Individuals with the highest “fitness” (i.e., the best adapted) are thus selected.
The next step consists in applying a crossing operator: the selected individuals (the “parents”) reproduce, giving birth to a new generation of individuals (the “children”) who share part of their characteristics. These children then undergo a mutation, whereby characteristics are added, deleted, or modified. They are evaluated in turn and a new population replaces the initial population.
The process is repeated until a certain level of performance is reached or until a set number of operations have been carried out.
Thus, by imitating what takes place in nature over several generations, evolutionary algorithms enable selection of the best solutions to a problem within a set: those that provide the best results reproduce and the others are eliminated. These algorithms are called “approximation algorithms”, meaning they make it possible to find good quality solutions, getting close to the optimum, but are not necessarily the optimal solution.
From video games to finance
There are three main families of evolutionary algorithms: evolution strategies, genetic programming, and genetic algorithms; with the latter being the most popular.
Initiated by American scientist John Henry Holland and popularized by computer scientist David Goldberg, they are used for combinatorial optimization and have applications in operational research, artificial intelligence, etc.
They are of interest, for example, for researchers attempting to solve the travelling salesperson problem: what is the best route enabling a traveler to visit a given number of cities?
In general, we seek to minimize travel time or distance covered. The applications of this famous problem are numerous: transport of people or goods, logistics management, trajectory optimization in robotics, or industrial task planning, etc.
More generally, genetic algorithms, often combined with artificial neural networks, are used in video games, to teach a computer program to play (“Flappy Bird”, or “Mario”, etc.); in finance, for optimizing portfolios or predicting the performances of shares; in autonomous driving, for multicriteria optimization of an autonomous vehicle’s trajectories; they are also applied to air traffic management.
However, these algorithms have certain limits, namely a long calculation time, in particular during the crucial evaluation stage.
Sources
Algorithme génétique: Darwin au service de l’intelligence artificielle [Genetic algorithm: Darwin at the service of artificial intelligence] https://toiledefond.net/algorithme-genetique-darwin-intelligence-artificielle/
Algorithmes Évolutionnistes: Applications à des problèmes de données [Evolutionary Algorithms: Applications to data problems] https://blog.octo.com/algorithmes-evolutionnistes-applications-a-des-problemes-de-donnees-1/
Le problème du voyageur de commerce [The travelling salesperson problem] https://interstices.info/le-probleme-du-voyageur-de-commerce/
