Les techniques algorithmiques de l’IA | Les algorithmes évolutionnaires

Les algorithmes évolutionnaires : la sélection naturelle au service de l’intelligence artificielle 

Écrit par Simon Du Perron – auxiliaire de recherche au Laboratoire de cyberjustice.

L’une des facultés les plus remarquables de l’intelligence artificielle est sa capacité à apprendre et à se perfectionner sur la base du traitement des données. La présente série de billets de blogue fait état de plusieurs techniques algorithmiques ayant été développées afin de permettre à une machine de s’améliorer en tirant profit de son expérience. Nous aborderons, dans le présent billet, la technique des algorithmes évolutionnaires qui est directement inspirée des travaux du naturaliste anglais Charles Darwin.

La théorie de l’évolution, développée dans le célèbre ouvrage De l’origine des espèces, postule que le principal moteur de l’évolution est le processus de sélection naturelle. Cette notion, que l’on qualifie parfois comme la « persistance du plus apte », désigne le fait que les traits qui favorisent la survie et la reproduction d’une espèce voient leur fréquence s’accroître d’une génération à l’autre. L’on peut synthétiser cette notion avec les affirmations suivantes :

• les organismes démontrent certaines variations dans tous les aspects de leur biologie et de leur comportement;
• ces variations sont héréditaires, c’est-à-dire héritées des parents et transmises aux descendants;
• ces variations héréditaires vont affecter positivement ou négativement la survie et la reproduction, dépendamment de l’environnement dans lequel vit l’organisme;
• les individus ayant les variations les plus favorables par rapport à leur environnement vont vivre plus longtemps et laisser plus de descendants possédants eux aussi ces variations;
• après plusieurs générations, ces variations favorables vont se retrouver chez tous les individus de la population.

L’expression « algorithmes évolutionnaires » ou « algorithmes évolutionnistes » (evolutionary algorithms en anglais) désigne une famille d’algorithmes qui s’inspirent de la théorie de l’évolution pour résoudre divers problèmes complexes. Ce domaine a connu son lot de développements au cours des 60 dernières années et il regroupe aujourd’hui une très grande variété d’algorithmes. Ceci étant, quatre courants ont principalement contribué à l’essor de cette technique algorithmique :

• 1965 : Ingo Rencherberg et Hans-Paul Schwefel développent les stratégies d’évolution, une méthode permettant de résoudre divers problèmes d’optimisation, qui constitue la première forme d’algorithme évolutionnaire.

• 1966 : Lawrence J. Fogel, Alvin J. Owens et Michael John Walsh développent la programmation évolutionnaire, un algorithme d’apprentissage conçu pour faire évoluer des automates à états finis.

• 1975 : John Holland conçoit les premiers algorithmes génétiques qui constituent, encore aujourd’hui, les plus populaires des algorithmes évolutionnaires. Ces algorithmes appliquent la notion de sélection naturelle à un ensemble de solutions potentielles au problème donné. Nous décrirons davantage leur fonctionnement dans les lignes qui suivent.

• 1989 : John R. Koza développe la programmation génétique, une forme particulière d’algorithmes génétiques conçue pour la construction automatique de programmes informatiques. Ici, les solutions prennent la forme de programmes informatiques et leur aptitude est déterminée en fonction de leur capacité à résoudre un problème de calcul.

• 1993 : l’expression « Evolutionary Computation » (« calcul évolutionnaire ») gagne en notoriété avec la publication d’une revue éponyme par le MIT.  

À l’image de la sélection naturelle, le fonctionnement des algorithmes évolutionnaires est axé sur un processus itératif que nous proposons de diviser en cinq étapes :

• Initialisation : la première phase consiste à générer la population initiale d’« individus », qui prennent la forme de solutions possibles au problème à résoudre.  Cette population peut être générée de façon aléatoire ou, si l’on possède de l’information sur la tâche à accomplir, celle-ci peut être composée de solutions que l’on estime être optimales.  Il est important que la population initiale englobe un large éventail de solutions, car elle constitue le bassin génétique de l’algorithme.

• Évaluation :une fois qu’une population a été générée, les individus doivent être évalués selon une fonction d’aptitude. Il s’agit d’une fonction objective qui mesure à quel point l’individu (la solution) est en voie d’atteindre l’objectif pour lequel l’algorithme a été conçu. La conception d’une fonction d’aptitude qui représente fidèlement les différents paramètres de la tâche à accomplir est cruciale puisque c’est elle qui influencera le résultat final de l’algorithme.

• Sélection : on sélectionne ensuite les individus ayant obtenu les meilleurs scores pour participer devenir les « parents » de la prochaine génération traitée par l’algorithme. 

• Croisement et mutation : le processus de reproduction (aussi appelé croisement) donne naissance à une nouvelle population composée d’individus qui partagent les caractéristiques de leurs ascendants. Ces « enfants » subissent alors une étape de mutation qui sert à introduire du nouveau matériel génétique au sein de la population afin d’éviter que celle-ci ne soit une reproduction identique du profil génétique des parents issus de la génération précédente.

• Résultat : on répète ensuite les étapes 2, 3 et 4 jusqu’à atteindre un certain seuil de performance ou après avoir réalisé un nombre d’itérations préalablement déterminé.

Dans le paysage de l’apprentissage automatique, les algorithmes évolutionnaires constituent une technique d’apprentissage non supervisé qui peut être utilisée de façon complémentaire ou alternative aux réseaux de neurones artificiels. Conçue pour résoudre des problèmes d’optimisation, cette technique algorithmique trouve application dans plusieurs domaines notamment pour solutionner certains jeux, pour concevoir des itinéraires, pour développer des voitures autonomes, pour prédire le rendement d’actions cotées en bourses ou encore pour optimiser une chaine d’approvisionnement.

Le mécanisme de la sélection naturelle constitue un puissant vecteur de transformation qui a permis à l’espèce humaine, en l’espace de quelques millions d’années, de passer du primate à l’Homo sapiens. La conception d’algorithmes capable de reproduire cette mécanique naturelle constitue une avancée notable dans le domaine de l’intelligence artificielle. Si les algorithmes évolutionnaires ont permis au robot chien AIBO à apprendre marcher, qui sait jusqu’où ira l’évolution ?

***

Pour aller plus loin :

• Lawrence J. Fogel, Alvin J. Owens et Michael John Walsh, Artificial Intelligence Through Simulated Evolution, New York, John Wiley & Sons, 1966.
• David Edward Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, 1^re éd., Addison-Wesley Publishing Company, 1989.
• John R. Koza, Genetic Programming: On the Programming of Computers by Means of Natural Selection, 1^re éd., Cambridge, A Bradford Book, 1992.
• Thomas Back, Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms, Oxford University Press, 1996.
• A. E. Eiben, M. Schoenauer, « Evolutionary computing », Information Processing Letters, 82 (2006) 1-6.
• List of Issues, Evolutionary Computation, MIT Press Journals, en ligne : https://www.mitpressjournals.org/loi/evco
• Alain Petrowski et Sana Ben-Hamida, Evolutionary Algorithms, 1^re éd., Hoboken, Wiley-ISTE, 2017.

• Lawrence J. Fogel, Alvin J. Owens et Michael John Walsh, Artificial Intelligence Through Simulated Evolution, New York, John Wiley & Sons, 1966.
• David Edward Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, 1^re éd., Addison-Wesley Publishing Company, 1989.
• John R. Koza, Genetic Programming: On the Programming of Computers by Means of Natural Selection, 1^re éd., Cambridge, A Bradford Book, 1992.
• Thomas Back, Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms, Oxford University Press, 1996.
• A. E. Eiben, M. Schoenauer, « Evolutionary computing », Information Processing Letters, 82 (2006) 1-6.
• List of Issues, Evolutionary Computation, MIT Press Journals, en ligne : https://www.mitpressjournals.org/loi/evco
• Alain Petrowski et Sana Ben-Hamida, Evolutionary Algorithms, 1^re éd., Hoboken, Wiley-ISTE, 2017.

Ce contenu a été mis à jour le 11 février 2021 à 10 h 04 min.