“Mimant ce qui se réalise dans la nature sur plusieurs générations, les algorithmes évolutionnistes permettent de sélectionner les meilleures solutions à un problème au sein d’un ensemble.”
Les êtres humains ont toujours puisé dans la nature pour développer de nouvelles techniques et technologies. Ce processus d’innovation très fécond est connu sous le nom de “bio-inspiration” ou “biomimétisme”. C’est dans ce cadre que, depuis la moitié des années 1960, scientifiques et ingénieurs s’inspirent de la théorie de Charles Darwin sur l’évolution des espèces, formulée par le naturaliste anglais en 1859 dans son livre “L’Origine des espèces”, pour mettre au point des algorithmes capables de trouver de meilleures solutions à des problèmes d’optimisation complexes : les algorithmes évolutionnistes.
De Darwin aux algorithmes
Plus précisément, ils s’inspirent de la sélection naturelle, moteur de la transformation adaptative des espèces, par laquelle s’opère un tri des individus les plus aptes à survivre et à se reproduire dans un milieu donné. Ce mécanisme repose sur trois principes fondamentaux : le principe de variation, le principe d’adaptation, le principe d’hérédité.
Selon le principe de variation, une population d’êtres vivants est hétérogène, c’est-à-dire qu’il existe des différences entre les individus de la même espèce. On parle de variations ou de traits. Par exemple, la taille et la forme du bec des pinsons observés par Darwin sur les îles Galápagos sont des traits qui varient au sein de ces espèces apparentées de petits oiseaux.
Certains traits sont plus avantageux que d’autres. Ils permettent aux individus qui les possèdent de mieux survivre et se reproduire que leurs congénères dans leur environnement. C’est le principe d’adaptation.
Enfin, selon le principe d’hérédité, ces traits se transmettent d’une génération à l’autre, ce qui entraîne leur propagation dans la population jusqu’à ce qu’ils deviennent communs à tous ses membres. Le long cou des girafes, avantage sélectif leur permettant d’atteindre les feuilles hautes des arbres des savanes africaines, et donc de mieux se nourrir, résulte ainsi d’une lente évolution.
Sélection, évolution, évaluation
Sur la base de ces trois principes, les algorithmes évolutionnistes s’appuient sur un processus itératif qui consiste à faire évoluer et à évaluer un large ensemble de solutions appelé “population d’individus”. Ce processus comprend plusieurs étapes.
La première étape consiste à construire (généralement de manière aléatoire) une population initiale d’individus hétérogène, chaque individu représentant une solution possible au problème d’optimisation posé. On évalue ensuite l’aptitude de chaque individu à résoudre ce problème efficacement et rapidement. La fonction que l’on cherche à optimiser est appelée “fitness”. On sélectionne alors les individus ayant la “fitness” la plus élevée ‒ les plus adaptés.
L’étape suivante consiste à appliquer un opérateur de croisement : les individus sélectionnés (les “parents”) se reproduisent, donnant naissance à une nouvelle génération d’individus (“les enfants”) partageant une partie de leurs caractéristiques. Ces enfants subissent alors une mutation, lors de laquelle on ajoute, supprime ou modifie des caractéristiques. Ils sont à leur tour évalués et une nouvelle population remplace la population initiale.
On répète le processus jusqu’à atteindre un certain seuil de performance ou après avoir réalisé un nombre d’opérations déterminé.
Ainsi, mimant ce qui se réalise dans la nature sur plusieurs générations, les algorithmes évolutionnistes permettent de sélectionner les meilleures solutions à un problème au sein d’un ensemble : celles donnant les meilleurs résultats se reproduisent ; les autres sont éliminées. Ces algorithmes sont dits “d’approximation”, c’est-à-dire qu’ils permettent de trouver des solutions de bonne qualité, se rapprochant de l’optimum, mais pas nécessairement la solution optimale.
Du jeu vidéo à la finance
Il existe trois grandes familles d’algorithmes évolutionnistes : les stratégies d’évolution, la programmation génétique et les algorithmes génétiques. Ces derniers sont les plus populaires.
Initiés par le scientifique américain John Henry Holland et popularisés par le chercheur en informatique David Goldberg, ils sont utilisés pour l’optimisation combinatoire et trouvent des applications en recherche opérationnelle, en intelligence artificielle, etc.
Ils intéressent par exemple les chercheurs pour tenter de résoudre le problème du voyageur de commerce : quel est le meilleur chemin permettant à un voyageur de visiter un nombre de villes donné ?
On cherche généralement à minimiser le temps de trajet ou la distance parcourue. Les applications de ce célèbre problème sont nombreuses : transport de personnes ou de marchandises, gestion logistique, optimisation de trajectoires en robotique ou planification des tâches industrielles…
Plus généralement, les algorithmes génétiques, souvent combinés à des réseaux de neurones artificiels, sont utilisés en jeu vidéo, pour apprendre à un programme informatique à jouer (à “Flappy Bird” ou “Mario”, par exemple) ; en robotique, pour la programmation d’un robot (comportement, apprentissage) ; en finance, pour l’optimisation de portefeuilles ou la prévision des performances d’actions ; en conduite autonome, pour l’optimisation multicritère des trajectoires d’un véhicule autonome ; ou encore sont appliqués à la gestion du trafic aérien.
Ces algorithmes présentent toutefois certaines limites, notamment un temps de calcul long, en particulier lors de l’étape cruciale d’évaluation.
Sources
Algorithme génétique : Darwin au service de l’intelligence artificielle https://toiledefond.net/algorithme-genetique-darwin-intelligence-artificielle/
Algorithmes Évolutionnistes : Applications à des problèmes de données https://blog.octo.com/algorithmes-evolutionnistes-applications-a-des-problemes-de-donnees-1/
Le problème du voyageur de commerce https://interstices.info/le-probleme-du-voyageur-de-commerce/
