Les algorithmes génétiques expliqués

L'évolution a produit des yeux, des ailes et des cerveaux sans concepteur, simplement en gardant ce qui fonctionne et en le faisant varier. Un algorithme génétique emprunte cette idée pour résoudre des problèmes sur ordinateur. Il n'a pas besoin de comprendre le problème, seulement de distinguer une meilleure réponse d'une moins bonne, ce qui en fait un outil puissant lorsque l'espace des réponses possibles est trop vaste et trop étrange pour être exploré autrement.

Des fusées partant du bas d'un terrain et contournant un mur pour atteindre une cible verte, avec le meilleur vol tracé en pointillés
Des fusées partant du bas d'un terrain et contournant un mur pour atteindre une cible verte, avec le meilleur vol tracé en pointillés

L'idée

Dans les années 1960 et 1970, John Holland, à l'université du Michigan, a transformé la théorie de Darwin en algorithme, décrit dans son livre « Adaptation in Natural and Artificial Systems » de 1975. À la même époque, Ingo Rechenberg et Hans-Paul Schwefel ont développé en Allemagne les stratégies d'évolution pour la conception technique. La recette commune : entretenir une population de solutions candidates, leur attribuer un score, laisser les meilleures se reproduire avec variation, et répéter sur de nombreuses générations.

John Holland, qui a décrit les algorithmes génétiques dans son livre Adaptation in Natural and Artificial Systems de 1975.
John Holland, qui a décrit les algorithmes génétiques dans son livre Adaptation in Natural and Artificial Systems de 1975.

Les gènes et la population

Chaque candidat est décrit par un chromosome, une liste de gènes. Dans le terrain de jeu, les gènes d'une fusée sont ses poussées, une pour chaque instant de son vol ; dans d'autres problèmes, ce pourraient être les bits d'un nombre, l'ordre des villes sur un itinéraire ou les dimensions des pièces d'une conception. La première génération est aléatoire : elle explore largement l'espace des réponses, mais n'en contient presque aucune de bonne.

La fonction de fitness

La fitness est le nombre unique qui indique la qualité d'un candidat, et c'est la seule chose que l'algorithme sait du problème. Pour les fusées, elle récompense avant tout une arrivée précoce, puis une fin de vol près de la cible, et elle pénalise les crashs. Une fonction de fitness bien choisie guide la recherche en douceur vers de bonnes réponses ; une fonction mal pensée récompense la mauvaise chose, et l'algorithme exploitera la moindre faille qu'elle laisse ouverte.

La sélection

Les parents sont choisis de façon que les candidats les plus aptes aient plus d'enfants, mais les plus faibles gardent une chance, car leurs gènes peuvent contenir des éléments utiles. La sélection par roulette donne à chaque candidat une part de roue proportionnelle à sa fitness ; la sélection par tournoi en tire quelques-uns au hasard et prend le meilleur. Une sélection plus forte accélère les progrès, mais rend aussi la population plus homogène, ce qui peut mettre fin à la recherche trop tôt.

Croisement et mutation

Le croisement combine deux parents : ici, un enfant prend la première partie de ses gènes chez un parent et le reste chez l'autre, de sorte que les premières manœuvres d'une fusée peuvent rencontrer les dernières d'une autre. La mutation remplace quelques gènes au hasard. Le croisement recombine ce que la population possède déjà ; la mutation apporte ce qu'elle n'a jamais eu. Le théorème des schémas de Holland décrit comment de courts blocs de construction de bons gènes se répandent dans la population sous l'effet de ce mélange de sélection et de recombinaison.

Élitisme, exploration et exploitation

Copier sans changement les quelques meilleurs candidats dans la génération suivante, l'élitisme, garantit que la meilleure réponse n'est jamais perdue. Tout algorithme génétique doit trouver l'équilibre entre l'exploration, essayer de nouvelles régions de l'espace de recherche, et l'exploitation, affiner ce qui est déjà bon. Trop peu de variation, et la population converge vers une seule réponse médiocre ; trop, et elle ne se stabilise jamais. La taille de la population, le taux de mutation et la pression de sélection sont les boutons qui règlent cet équilibre.

Les optima locaux

Un algorithme génétique ne suit que la fitness, il peut donc être trompé. Quand le chemin vers la meilleure réponse passe d'abord par de moins bonnes, la population gravit la colline la plus proche et y reste : un optimum local. Derrière les murs décalés du terrain de jeu, les fusées qui s'écrasent sous la cible obtiennent un meilleur score que celles qui se détournent pour trouver le passage, si bien que la population s'entasse contre le mur. Parmi les remèdes : des populations plus grandes, une mutation plus forte, le maintien de la diversité de la population et, surtout, une meilleure fonction de fitness.

Explorez par vous-même

Ouvrez le terrain de jeu d'algorithme génétique pour faire évoluer des fusées autour d'un mur, d'un passage, de piliers, de murs décalés ou de murs que vous dessinez vous-même. Modifiez la population, le taux de mutation, la durée de vie et la méthode de sélection, activez et désactivez l'élitisme, et suivez dans le graphique à quelle vitesse augmente la part des fusées qui atteignent la cible, ou pourquoi elle n'augmente pas.

Questions fréquemment posées

Un algorithme génétique est-il une forme d'intelligence artificielle ?

Il appartient au domaine plus large de l'IA et de l'apprentissage automatique, en tant que méthode de recherche et d'optimisation. Il n'apprend pas à partir d'exemples comme un réseau de neurones ; il améliore des solutions candidates par essais et sélection. Les deux sont souvent combinés, par exemple en faisant évoluer la structure ou les poids de réseaux de neurones, une approche appelée neuroévolution.

Un algorithme génétique trouve-t-il toujours la meilleure réponse ?

Non. C'est une heuristique : il trouve généralement de bonnes réponses à des problèmes difficiles, mais il ne garantit pas la meilleure et ne prouve pas à quel point il s'en approche. Pour les problèmes où une méthode exacte est assez rapide, cette méthode est préférable.

Quelle est la différence entre un algorithme génétique et les stratégies d'évolution ?

Ce sont tous deux des algorithmes évolutionnaires. Les algorithmes génétiques classiques mettent l'accent sur le croisement de chromosomes en forme de chaînes ; les stratégies d'évolution travaillent surtout avec la mutation de nombres réels et adaptent souvent elles-mêmes l'amplitude de leurs mutations au fil du temps. Les méthodes modernes mélangent les idées des deux.

Pourquoi les fusées sont-elles si maladroites au début ?

Leurs premiers gènes sont des poussées entièrement aléatoires, qui se compensent en moyenne, si bien que les fusées dérivent. Ce n'est qu'une fois que la sélection a conservé les rares fusées qui poussaient par hasard à peu près dans la bonne direction, et que le croisement a combiné leurs bons tronçons, qu'apparaissent des vols coordonnés.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Ouvrir le terrain de jeu d'algorithme génétique