Evolution artificielle, optimisation et apprentissage
- les algorithmes évolutionnaires, qui comprennent :
- les algorithmes génétiques (appliqués aux problèmes discrets et combinatoires),
- les stratégies d'évolution (appliquées aux problèmes continus),
- la programmation génétique (appliquée aux problèmes d'apprentissage et de fouille de données),
- l'optimisation évolutionnaire multi-objectifs (pour tous les problèmes industriels qui doivent optimiser plusieurs critères antagonistes à la fois),
- l'optimisation par colonies de fourmis,
- les approches émergentes (BOIDS, optimisation par essaim particulaire).
L'équipe est actuellement au meilleur niveau international dans l'utilisation de cartes graphiques massivement parallèles (GPGPU) pour le calcul scientifique par évolution artificielle et pour l'intelligence artificielle, en étant la première à obtenir des accélérations d'environ trois ordres de grandeur par rapport à un coeur de CPU moderne sur des problèmes d'optimisation génériques avec la plateforme EASEA (EAsy Specification of Evolutionary Algorithms). Typiquement, une journée de calcul sur un ordinateur comportant plusieurs cartes GPU devient équivalente à plusieurs années de calcul sur un ordinateur compatible PC moderne, ce qui permet de s'attaquer à des problèmes impossibles à aborder par d'autres techniques.
Le but poursuivi est ambitieux : il consiste à implémenter une véritable intelligence artificielle compétitive avec l'intelligence humaine sur un ordinateur de type PC équipé de plusieurs cartes graphiques.
Deux types de projets sont menés de front : des projets fondamentaux portant sur l'adaptation des algorithmes évolutionnaires aux caractéristiques de ces nouvelles cartes, et des projets appliqués qui permettent de tester les algorithmes élaborés sur des problèmes réels, souvent bien différent des problèmes jouets de type benchmarks.
Sommaire |
Principales personnes travaillant dans la thématique
Wolfgang Banzhaf
Professeur invité
Deepak Sharma
Post-doctorant
Lidia Yamamoto
Post-doctorante
Olivier Kuhn
Doctorant
Ogier Maitre
Doctorant
Stéphane Querry
Doctorant
Frédéric Krüger
Etudiant en Master 2 ILC
A ces personnes viennent s'ajouter :
- Julien Blaise, (étudiant de M1 effectuant un TER de 150h sur le portage de l'algorithme des mouches sur carte embarquée en C),
- Farzad Sehat, (étudiant de M1 effectuant un TER de 150h sur le portage de l'algorithme des mouches sur carte embarquée en LISAAC),
- Xavier Hennequin (étudiant de M1 effectuant un TER de 150h sur le portage du langage FIFTH sur carte GPGPU),
- Sébastien Freimann (étudiant de M1 effectuant un TER de 150h sur le portage du langage PUSH sur carte GPGPU),
- Cédric den Drijver (étudiant de M2, en apprentissage à l'INSA sur l'optimisation de poutrelles béton pour Lafarge dans le cadre d'une collaboration à l'occasion de la thèse de Céline Conrardy).
Projets
ECOMAPS (Evolutionary Computation on Massively Parallel Systems)
Le projet ECOMAPS a pour but de revisiter les différents paradigmes évolutionnaires pour les adapter à la parallélisation massive, notamment sur cartes GPGPU (General Purpose Graphic Processing Units) et de les intégrer dans le langage EASEA (cliquer ici pour une rapide explication).
Il comprend trois volets :
Poursuite du développement du langage EASEA (EAsy Specification of Evolutionary Algorithms, (Collet et al., 2001) permettant à un algorithme évolutionnaire de s'exécuter sur cartes GPGPU General Purpose Graphic Processing Unit sans que le programmeur n'ait besoin de savoir programmer les cartes. Le développement de la plateforme de calcul évolutionnaire massivement parallèle EASEA est actuellement assuré par :
- Ogier Maitre pour les algorithmes évolutionnaires et la programmation génétique, et
- Frédéric Kruger pour CMA-ES (Covariance Matrix Adapatation Evolutionary Strategy, utilisée pour les problèmes continus), les algorithmes mémétiques(algorithmes hybridés avec une recherche locale pour une évolution Lamarckienne) et la parallélisation en îlots sur clusters de machines hybrides.
La plateforme EASEA intègre les derniers développements algorithmiques de l'équipe. Il est disponible sur Sourceforge.
- - Adaptation de la Programmation Génétique Linéaire à l'exécution sur cartes GPGPU
- La Programmation Génétique Linéaire, développée par Wolfgang Banzhaf (cf. Brameier & Banzhaf, 2007) semble particulièrement bien adaptée à l'architecture des processeurs GPU. Ogier Maitre et Wolfgang Banzhaf travaillent à modifier la Programmation Génétique Linéaire pour profiter des spécificités de ces cartes massivement parallèles. Le résultat sera intégré au langage EASEA (cf. ci-dessous).
- - Implémentation d'un algorithme de chimie virtuelle sur GPGPU
- La chimie virtuelle est un paradigme qui peut servir non seulement à simuler des réactions chimiques, mais qui peut aussi être utilisé pour résoudre des problèmes scientifiques. Le sujet du post-doc de Lidia Yamamoto consiste à porter la chimie virtuelle sur cartes GPU.
ARA (Administrateur Réseaux Artificiel)
- Post-doc de Deepak Sharma financé par OSEO pour la société Kelerio. La société Kelerio administre des réseaux pour des entreprises clientes. Le but du projet ARA est de créer un Administrateur Réseaux artificiel capable de détecter des pannes et d'y remédier avant qu'elles ne surviennent.
Une collaboration a lieu sur ce sujet avec Cécilia Zanni-Merck et Philippe Bouché du LGeCo (INSA de Strasbourg).
RENZEO (Recherche de Nouvelles Zéolites)
BETON (optimisation de structures béton)
Cédric den Drijver effectue un stage en apprentissage financé par l'INSA de Strasbourg dans le cadre d'une collaboration autour de la thèse de Céline Conrardy financée par Lafarge. Le but de cet apprentissage est d'optimiser des structures béton (poutrelles, par exemple) par Programmation Génétique sur GPGPU en les évaluants par éléments finis.
Thèses en cours
- - Algorithmes génétiques et programmation génétique sur carte GPGPU
- Thèse d'Ogier Maitre, dirigée par Pierre Collet et co-encadrée par Nicolas Lachiche).
Travaux réalisés :
- Parallélisation d'un algorithme évolutionnaire standard sur carte GPGPU : Ce travail a permis d'obtenir des accélérations proportionnelles à la puissance des cartes GPGPU par rapport à un processeur moderne de type Pentium (typiquement, x100 sur une carte NVidia GTX260 à 700 GFlops, cf. caractéristiques des cartes NVIDIA). La puissance des cartes GPGPU devient appliquable à tout problème d'optimisation abordable par évolution artificielle. Les résultats ont été inclus dans le langage EASEA, qui permet d'obtenir l'accélération par parallélisation automatique d'un algorithme évolutionnaire sans que l'utilisateur n'ait besoin de savoir programmer la carte (Ogier et al. 2009, 2009b).
- Parallélisation de l'évaluation d'arbres standards de Programmation Génétique sur carte GPGPU : des accélérations de l'ordre de x100 à x250 sont obtenues sur une demi-carte NVidia GTX295 sur de très grandes populations avec seulement 32 cas d'apprentissage. Cette avancée est majeure car elle permet d'appliquer la puissance des cartes GPGPU à des problèmes d'apprentissage automatique, ouvrant ainsi la voie à une intelligence artificielle compétitive avec l'intelligence humaine sur un PC standard équipé de cartes GPGPU (Koza 2003).
Travaux en cours et futurs dans le cadre de la thèse :
- Couplage de l'exécution parallèle d'arbres de PG avec un moteur évolutionnaire standard permettant de paralléliser un algorithme de Programmation Génétique standard sur GPGPU et son intégration dans EASEA (en cours).
- Développement d'un algorithme de Programmation Génétique adapté à l'architecture des GPGPU. Un bon candidat est la Linear Genetic Programming (Brameier et al. 2007).
- Adaptation du paradigme aux très grandes populations en s'inspirant probablement des travaux de (Poli et al. 2007) sur le sujet.
Sujets de TER de M1 2009-2010 en rapport avec la thèse :
- Programmation Génétique en Fifth sur carte GPGPU (Xavier Hennequin).
- Programmation Génétique en Push sur carte GPGPU (Sébastien Freymann).
- - Optimisation stochastique par méthodes évolutionnaires appliquée à la conduite d’engins autonomes (et notamment les drones)
- Thèse de Stéphane Querry, dirigée par Pierre Collet et financée par la société POLYVIONICS. Ce projet comporte plusieurs volets :
- Optimisation de trajectoires par évolution artificielle.
- Optimisation des fonctions mathématiques de la représentation d'état non linéaire d'un engin par programmation génétique.
- Optimisation des équations du filtrage de Kalman pour mieux intégrer le bruit spécifique associé à un engin particulier.
Sujets de projet 150h de M2 en rapport avec la thèse :
- Portage de l'algorithme des Mouches sur carte embarquée en C (Julien Blaise) et en LISAAC (Farzad Sehat).
La soutenance consistera à faire tourner l'algorithme sur le Casque à Mouches ci-contre spécialement réalisé pour le projet :-)
- - Modélisation et optimisation des pratiques collaboratives
- Thèse d'Olivier Kuhn, dirigée par Pierre Collet et Parisa Ghodous, en cotutelle avec le LIRIS de l'Université de Lyon, sur financement CIFRE PROSTEP).
Travaux réalisés :
- Conception d'une ontologie d'application pour la représentation et l'inférence de connaissances liées aux modèles CAD et aux templates.
- Calcul de séquences de mise à jour de modèles pour la répercussion des modifications appliquées aux templates.
Travaux en cours :
- Extension de la problématique aux environnements collaboratifs afin de résoudre rapidement les problèmes liées aux templates ainsi que leur mise à jour au sein des produits.
Liste des Publications
Animation Scientifique
- Du 7 au 11 juillet 2010, l'équipe présentera un tutoriel de 2h sur l'utilisation de cartes GPGPU pour l'évolution artificielle à la conférence mondiale sur l'évolution artificielle Gecco'10.
- Le 26 mars 2010, l'équipe effectuera trois présentations aux 20è Journées Evolutionnaires à Paris VI.
- Le 25 février, Ogier Maitre présentera les travaux de l'équipe à l'occasion de la première journée GPU de Strasbourg, organisée par le Centre d'Etudes du Calcul Parallèle et de la Visualisation.
- Du 20 au 24 janvier 2009, l'équipe sera présente au 4è Symposium franco-Japonais Frontiers of Science organisé par le CNRS et la Japan Society for the Promotion of Science (qui a pour but de promouvoir les échanges entre 80 scientifiques français et japonais de haut niveau) par l'intermédiaire de Pierre Collet, qui présidera la session Evolution Artificielle et Vie Artificielle.
- Du 26 au 28 novembre 2009, la thématique Evolution artificielle, Optimisation et Apprentissage de l'équipe FDBT a organisé la 9è Conférence Internationale sur l'Evolution Artificielle EA'09.
- Du 8 au 11 juin 2009, l'équipe a été présente à la 4è école d'été sur l'Evolution Artificielle, avec :
- Un tutoriel d'Introduction aux Algorithmes Evolutionnaires.
- L'animation d'une après-midi de travaux pratiques sur la mise en oeuvre d'algorithmes génétiques sur cartes massivement parallèles GPGPU.
- Le 31 mai 2009, Pierre Collet a présenté l'évolution artificielle sur cartes GPGPU en tant que conférencier invité à la 12è conférence polonaise sur l'Evolution Artificielle et l'Optimisation Globale.
- Le 24 avril 2009, Pierre Collet a effectué un séminaire sur l'utilisation du langage EASEA pour implémenter des algorithmes évolutionnaires sur des cartes GPGPU en tant que conférencier invité de l'Université de Nottingham, dans l'équipe de Natalio Krasnogor.
- Le 10 avril 2009, à l'occasion des 19è Journées sur l'Evolution Artificielle, l'équipe a effectué 3 présentations sur l'évolution artificielle.
- Le 26 mars 2009, Pierre Collet a présenté l'utilisation des cartes GPGPU pour l'optimisation à l'occasion de la 3ème Journée de l'Optimisation à l'Université de Technologie de Belfort Montbéliard.
- Du 16 au 19 juin 2008, l'équipe a été présente à la 3è école d'été sur l'Evolution Artificielle (fondée par Pierre Collet) avec un exposé sur l'Evolution artificielle Interactive et l'animation d'une table ronde sur les relations entre l'Evolution Artificielle et l'Industrie.
- Le 14 mars 2008, à l'occasion des 18è journées sur l'Evolution Artificielle, Pierre Collet a fait un exposé sur le chaînon manquant entre l'industrie et la recherche en optimisation.
- Pierre Collet a été Président de l'Association Evolution Artificielle de 2003 à 2008 et fait maintenant partie du "Comité des Sages" de l'association.
- Du 29 au 31 octobre 2007, Pierre Collet a co-organisé la 8è Conférence Internationale sur l'Evolution Artificielle EA'08.
Principales Collaborations
- Department of Computer Science, Memorial University of Newfoundland, St John, Canada
- Venue du Pr Wolfgang Banzhaf dans l'équipe pendant 6 mois (d'avril 2010 à septembre 2010) pour y développer la chimie artificielle sur carte GPGPU.
- Instituto de Tecnologia Quimica , Universidad Politecnica de Valencia (Espagne)
- Collaboration sur la recherche de nouvelles zéolites, avec plusieurs articles de conférence et de journaux scientifiques soumis.
- Indian Institute of Technology of Kharagpur (Inde)
- avec la venue du doctorant Arijit Biswas pendant 8 mois (d'avril 2009 à décembre 2009) dans l'équipe dans le cadre d'une bourse franco-indienne Sandwitch. Un article de journal international a été soumis.
- Laboratoire d'InfoRmatique en Image et Système d'informations, Université de Lyon
- co-tutelle de la thèse d'Olvier Kuhn (cf. ci-dessus).
- Société PROSTEP France et Allemagne
- Thèse CIFRE d'Olivier Kuhn.
- Société POLYVIONICS
- Thèse de Stéphane Querry.
- Equipe Image et Calcul Parallèle Scientifique (ICPS) du LSIIT, dirigée par Philippe Clauss
- Un papier a été accepté à EuroPar'09 (Ogier et al. 2009b).
- Projet INRIA ALEA, Centre de Recherche Bordeaux Sud Ouest et Service ORL de l'Hôpital Avicenne
- plusieurs articles de journaux et chapitres de livre publiés.
- Bristol Institute of Technology, University of the West of England
- collaboration avec l'équipe d'Andy Adamatzky, et plusieurs articles publiés.
---
L'utilisation de méthodes évolutionnaires tisse des liens évidents avec la thématique Bioinformatique Théorique de l'équipe, notamment concernant l'étude d'opérateurs génétiques destinés à modifier le génotype des individus que l'on fait évoluer. Jusqu'à maintenant, l'évolution artificielle ne s'inspire de l'évolution naturelle que dans les grandes lignes. Le rapprochement avec la thématique Bioinformatique Théorique permet aux informaticiens d'accéder à des connaissances beaucoup plus précises sur les mécanismes génétiques biologiques, pour affiner les modèles qu'ils utilisent, et inversement, les biologistes peuvent apprendre de l'expérience in silico des chercheurs en évolution artificielle.
Les liens sont très forts aussi avec la thématique Fouille de données et classification, car les méthodes évolutionnaires permettent aussi de créer des classifieurs et extracteurs de connaissance (supervisés ou non) par programmation génétique, par exemple (cf. thèses de Sébastien Derivaux et Jonathan Weber).
Anciens membres
- - Arijit Biswas 04/09 - 12/09
- Optimisation du processus d'extraction de Manganèse de nodules polymétalliques extraits de fonds sous-marins :Dans le cadre de sa thèse de l'Indian Institute of Technology de Kharagpur (Inde) dirigée par les Professeurs Nirupam Chakraborti et Prodip Sen, Arijit Biswas a obtenu une bourse franco-indienne Sandwitch qui lui a permis de passer 8 mois en France dans l'équipe FDBT (entre avril 2009 et décembre 2009) dans le but d'apprendre à utiliser la Programmation Génétique (spécialité de l'équipe) et de l'appliquer à son sujet de thèse.<p>A l'issue de son séjour, les résultats précédemment obtenus (et publiés) par Arijit à l'aide de réseaux neuronaux ont été améliorés par Programmation Génétique. Un article de revue internationale est en préparation.
