En poursuivant votre navigation, vous acceptez l'utilisation de cookies destinés à des fins de mesure d'audience, à améliorer la performance de ce site et à vous proposer des services et contenus personnalisés. En savoir plus

X

La sélection naturelle appliquée aux machines

Trois élèves de l'École polytechnique présenteront leurs travaux sur les algorithmes génétiques et évolutionnaires lors de la conférence mondiale dédiée au sujet en juillet prochain à Kyoto. Ces algorithmes possèdent de nombreuses applications en intelligence artificielle, mais leur compréhension théorique reste à ce jour limitée.

Gautier Izacard, Raphaël Dang-Nhu et Thibault Dardinier, trois élèves de l’École polytechnique, ont mené leur projet de recherche de 3e année en informatique sur les algorithmes génétiques et évolutionnaires. Inspirés par la théorie de l’évolution de Charles Darwin, ces algorithmes imitent les mécanismes biologiques de reproduction, de mutation et de recombinaison des gènes.
« Pour un problème d’optimisation où l’on cherche à maximiser ou minimiser une quantité en faisant les meilleurs choix - trouver le trajet le plus court entre deux points par exemple - l’idée est de partir d’une solution quelconque, au hasard, puis de la faire évoluer de manière aléatoire en vérifiant qu’elle s’améliore à chaque étape, de manière à simuler la sélection naturelle », indique Raphaël Dang-Nhu, élève du cycle ingénieur. Cette méthode possède l’avantage de s’appliquer à tout type de problèmes, même ceux pour lesquels il n'existe pas de méthode exacte, puisqu’un algorithme génétique, contrairement à un algorithme exact, va chercher à trouver une solution approchée. Par ailleurs, comme la solution s’améliore progressivement, la qualité du résultat final dépend du temps dont l’algorithme a disposé.

Des applications concrètes pour l'exploration de Mars ou le robot de Sony
Ces algorithmes évolutionnaires ont donné lieu à de nombreuses applications concrètes. « Globalement, les problèmes liés au machine learning sont souvent des problèmes d’optimisation déguisés et peuvent bénéficier de ces algorithmes », précise Raphaël Dang-Nhu. Ils ont été utilisés pour développer des méthodes permettant d'optimiser les déplacements du robot Pathfinder qui explore Mars, mais aussi pour apprendre à marcher au robot Aibo de la firme Sony en perfectionnant le système de commande de la machine. Autre utilisation : ces algorithmes permettent également de développer des intelligences artificielles dans le domaine des jeux vidéo.

Un projet théorique pour mieux comprendre leur efficacité
Si l’utilisation de ces algorithmes est donc largement répandue, l’approche théorique de cette méthode reste limitée. « Il est important d’approfondir les résultats qui existent au sujet de ces algorithmes évolutionnaires, de façon à obtenir davantage de garanties de leur efficacité, souligne Raphaël. Le but de notre projet est d’étudier comment réagissent ces algorithmes lorsque les problèmes qu'ils doivent optimiser reposent sur des données imparfaites, ou lorsque le problème évolue avec le temps ». Pour cela, les élèves ont développé une approche générale pour étudier ce type de problèmes et déterminer le temps moyen nécessaire à un algorithme génétique pour trouver la meilleure solution.

Leurs travaux, encadrés par Benjamin Doerr, chercheur au laboratoire d’informatique de l’X, seront présentés à la conférence GECCO à laquelle participeront Thibault et Raphaël du 15 au 19 juillet prochain à Kyoto. « Nous espérons nos résultats de recherche permettront aux utilisateurs des algorithmes évolutionnaires de mieux comprendre la performance de leur application », précisent les étudiants.