Des travaux du LIX présentés à la conférence AAAI 2022

Si l'une des tâches des informaticiens consiste à concevoir des algorithmes, une autre tâche tout aussi importante consiste à garantir qu’ils fonctionnent comme prévu. Cette garantie provient de la compréhension théorique de l'algorithme et de preuves mathématiques. « Mais pour presque tous les algorithmes utilisés dans des applications, de telles preuves n'existent pas », explique Benjamin Doerr, professeur au Laboratoire d'informatique de l'Ecole Polytechnique (*LIX). Avec Weijie Zheng de la Southern University of Science and Technology en Chine et Yufei Liu, étudiante en Bachelor à l'Ecole Polytechnique, ils ont fourni une première analyse théorique d'un algorithme appelé NSGA-II.

NSGA-II est l'acronyme de "Non-Dominated Sorting Genetic Algorithm II". Il s’agit de l'algorithme évolutionnaire multi-objectif le plus utilisé. Il fournit des solutions aux problèmes d'optimisation où plusieurs objectifs concurrents entrent en jeu. Un exemple simple : si vous voulez acheter une voiture électrique à bas prix tout en ayant une grande autonomie, quels sont les meilleurs de paramètres pour la voiture (capacité de la batterie, taille des roues, etc.) ?

Le NSGA-II est un algorithme évolutionnaire, c’est-à-dire inspiré des principes de l'évolution biologique. Il part d'une "population" de taille fixe de solutions possibles, autrement dit d'ensembles de paramètres pour la voiture dans notre exemple. En appliquant de petites modifications des paramètres de ces solutions, à la manière de « mutations » chez les êtres vivants, l’algorithme crée un nombre égal de nouvelles solutions possibles. Ensuite, il sélectionne les meilleures solutions par rapport aux objectifs pour obtenir une nouvelle population de même taille que la population de départ. Puis ces étapes sont répétées.

L’établissement de la nouvelle population à partir de l'ancienne constitue le cœur de NSGA-II. Tout d'abord, il sélectionne toutes les solutions "non dominées", ce qui signifie qu’aucune autre solution n'est meilleure pour les deux objectifs. Ces solutions sont directement incluses dans la nouvelle population. Ensuite, il sélectionne les solutions qui ne sont dominées par aucune des solutions restantes, et ainsi de suite. Finalement, il atteint le point où certaines solutions doivent être sélectionnées pour la génération suivante, mais pas toutes. Pour les trier, NSGA-II utilise un critère mathématique de départage appelé "distance de crowding".

Ces étapes de tri ont constitué un défi d'analyse selon Benjamin Doerr. « Les populations de grande taille représentent toujours un défi. Il est impossible de suivre avec précision la dynamique complexe de la population. Mais de petites différences dans la population peuvent avoir des effets drastiques. C'est particulièrement vrai pour l'étape de sélection ». Néanmoins, dans les travaux présentés à la conférence AAAI 2022, l'équipe a pu effectuer une analyse du temps d'exécution de NSGA-II, c'est-à-dire qu'elle a déterminé théoriquement le temps que prend NSGA-II pour trouver toutes les solutions pertinentes pour deux problèmes de référence. Fait intéressant, ils montrent que l'algorithme peut rejeter des solutions pertinentes même lorsque la taille de la population est aussi grande que le nombre de solutions pertinentes. Ce n'est peut-être pas un problème pour l'utilisation pratique de NSGA-II aujourd'hui, car le fait de commencer avec une population plus grande peut surmonter ce problème. « Toutefois, cela signifie que le mécanisme de départage n'est pas parfait, explique Benjamin Doerr. Il s'agit d'informations importantes, notamment pour le développement futur de cet algorithme, et nous allons continuer à travailler dessus. »

*LIX : une unité mixte de recherche CNRS, École polytechnique - Institut Polytechnique de Paris