L’apprentissage automatique ose les algorithmes évolutionnaires
⏱ 4 minLes algorithmes évolutionnaires adaptent les principes du darwinisme à la résolution de problèmes d’optimisation. Ils ont aussi des applications en apprentissage automatique.
« L’idée est ancienne, assure Marc Schoenauer, directeur de recherche Inria, co-responsable de l’équipe TAU au Laboratoire Interdisciplinaire des Sciences du Numérique (LISN, CNRS & université Paris-Saclay). Mais elle n’était pas très applicable à l’époque, dans les années 1960, car elle nécessite de fortes puissances de calcul. » Depuis plus de trente ans, les travaux de ce chercheur en intelligence artificielle se situent à la frontière entre optimisation stochastique et apprentissage automatique.
« Il s’agit au départ d’une méthode d’optimisation stochastique inspirée de la sélection naturelle, explique Marc Schoenauer. Le principe est simple. Pour résoudre un problème donné, on considère des générations successives d’une population d’individus qui sont des tentatives de solutions au problème posé. Et à chaque génération, on fait trois choses. Tout d’abord on évalue l’efficacité de chaque individu-solution. Puis on applique une sélection : les individus les plus aptes ont plus de chances de survivre. Enfin, on renouvelle la population, en introduisant aléatoirement de la variation. On s’inspire des deux grands mécanismes qui font cela dans la nature : les mutations (erreurs de copie) et la recombinaison engendrée par la reproduction sexuée. »
Une méthode d’optimisation inspirée du darwinisme
L’approche évolutionnaire (traduction de « evolutionary » préférable à « évolutionniste ») s’applique fort bien à des problèmes d’optimisation. Prenons un exemple. « Supposons que l’on recherche la forme optimale d’un nez d’avion, propose Marc Schoenauer. Elle est définie par un certain nombre de paramètres comme sa longueur, etc. Chaque individu de notre population sera représenté par les valeurs de ce jeu de paramètres. Pour évaluer l’aptitude, l’efficacité de chaque nouvel individu, on fait appel à la simulation numérique : le nez d’avion passe en soufflerie numérique. Dans la phase de sélection, on conservera surtout les individus les plus performants. Après quoi la génération suivante est engendrée. Par clonage, avec un taux de mutation, et/ou en combinant les paramètres – les gènes – de deux parents. »
Cette approche n’est pas dénuée de difficultés, signale le chercheur. « Comme avec bien d’autres méthodes d’optimisation, l’algorithmique évolutionnaire est confrontée au problème classique des optima locaux. Pour éviter que la population se retrouve cantonnée autour d’un optimum local, il faut bien ajuster les paramètres définissant la variabilité et la sélection à chaque génération. Pour éviter ce piège, il est important de pouvoir garder, d’une génération à l’autre, des d’individus peu adaptés. La sélection ne doit pas être trop élitiste et il faut que les mutations soient parfois violentes. »
Trouver les bons équilibres
Pour bien exploiter le potentiel de ces approches, il faut savoir trouver les bons équilibres. « On se trouve régulièrement face au dilemme “exploitation vs exploration”, ajoute Marc Schoenauer. Si chaque nouvelle génération résulte surtout de mutations importantes, qui produisent des individus très différents de leurs parents, cela favorise l’exploration de nouveaux territoires, mais empêche la convergence vers un optimum, fût-il local. À l’inverse, si les nouvelles générations sont essentiellement des croisements assez similaires à leurs parents, cela favorise l’exploitation de l’acquis… et la stagnation dans un optimum local. » On fait d’ailleurs souvent évoluer au cours du temps les paramètres qui définissent les modalités de reproduction et de sélection à chaque génération.
L’appellation « algorithmes évolutionnaires » regroupe en fait plusieurs grandes familles historiques. Il y a notamment les « algorithmes génétiques », qui travaillent sur des individus représentés par des chaînes de bits. Il y a aussi la « programmation génétique » : c’est alors une population de programmes, représentés par des arbres, qui se reproduit avec des mutations et/ou des combinaisons et subit la pression d’une fonction d’évaluation. Une approche proposée dès 1965 tombe sous la dénomination des « stratégies d’évolution »…
Des secteurs d’applications diversifiés
Les applications des algorithmes évolutionnaires relèvent essentiellement de problèmes d’optimisation. La liste est longue : optimisation de formes, de process, d’emplois du temps, d’allocation de ressources, de parcours dans un graphe (dont le fameux problème du voyageur de commerce), rotations d’équipages, problèmes du sac-à-dos (Knapsack Problem : maximiser la valeur des objets emportés en respectant un poids limite), etc. Mais la démarche évolutionnaire s’applique également à quelques domaines assez éloignés de l’optimisation, comme le partitionnement de données (data clustering), ainsi que la fouille de données (data-mining).
Les algorithmes évolutionnaires font l’objet de plusieurs conférences mondiales. L’ACM (Association for Computing Machinery) organise notamment chaque année la Genetic and Evolutionary Computation Conference (GECCO). Mais il y a aussi le Congress on Evolutionary Computation de l’IEEE, EvoStar et quelques autres. GECCO 2021 était organisée à Lille, en juillet dernier. Des contributions relatives à des approches évolutionnaires appliquées à l’apprentissage automatique étaient au rendez-vous.
Apprentissage automatique… évolutionnaire
« On constate un renouveau de l’intérêt pour les algorithmes évolutionnaires qui accompagne les progrès du deep learning, assure Marc Schoenauer. Pour commencer, ils s’avèrent très utiles pour optimiser l’architecture de réseaux de neurones. » Mais aussi bien d’autres choses. On parle désormais de Evolutionary Machine Learning (apprentissage automatique évolutionnaire), des Evolving Neural Networks (réseaux de neurones évolutifs), de Neuroevolution… La célèbre revue ACM Computing surveys a publié le mois dernier un article[1] intitulé “Evolutionary Machine Learning: A Survey”, qui fait le tour du sujet. Il distingue neuf types de contributions de l’approche évolutionnaire à l’apprentissage automatique, allant de l’optimisation des réseaux de neurones à l’apprentissage par renforcement en passant par les classeurs.
Les algorithmes évolutionnaires viennent aujourd’hui offrir leurs services pour améliorer les performances des modèles d’apprentissage automatique et la qualité de leurs résultats. Nous évoquerons plus en détail ces contributions dans un prochain article.
Pierre Vandeginste
1. Akbar Telikani et al. “Evolutionary Machine Learning: A Survey”. ACM Comput. Surv., Oct 2021. doi
Image a la une : ©Creative Commons
