Les inscriptions sont closes
  • Fin d'inscription
  • Inscription close
  • Début du Cours
  • 08 sep 2014
  • Fin du cours
  • 10 nov 2014
  • Effort estimé
  • 5 h/semaine
  • Langue
  • Français

L’objectif de ce MOOC est de découvrir comment optimiser par évolution artificielle et algorithmes génétiques parallèles des problèmes difficiles et multicritères pour obtenir de manière régulière des résultats compétitifs avec l’intelligence humaine en ingénierie et sciences appliquées.

Les algorithmes évolutionnaires (algorithmes génétiques, stratégies d’évolution, programmation génétique) sont parmi les meilleurs algorithmes actuels d’optimisation approchée. Ils sont de plus en plus utilisés dans l’industrie pour leur performance et leur capacité à trouver rapidement de bonnes solutions à des problèmes difficiles, mal posés, multi-critères et pour leur capacité à exploiter des ordinateurs parallèles, massivement parallèles et des écosystèmes de calcul potentiellement hétérogènes.


De nombreux problèmes sont “difficiles”, au sens où l’on ne leur connaît pas de solution simple et malheureusement, cela concerne de nombreux problèmes industriels (optimisation de tournées pour livrer des colis, comment tailler des diamants pour minimiser les pertes, comment trouver le modèle mathématique d’un aéronef, comment trouver des lois de commandes prédictives, comment trouver des solutions à des problèmes inverses, ...). En mécanique des fluides, par exemple Navier, Stokes (et Barré de Saint-Venant) ont réussi à trouver des équations permettant de décrire le comportement de particules dans un gaz peu dense. Ces équations (gourmandes en temps de calcul) peuvent être utilisées pour déterminer la portance et la traînée d’un profil d’aile d’avion mais ce qu’on souhaiterait typiquement obtenir, c’est l’inverse : quel profil d’aile d’avion permettrait de faire décoller un nouvel avion de ligne à, disons 250km/h ?

Et bien on ne peut malheureusement pas utiliser ces équations à l’envers. Le seul moyen de trouver un profil permettant de faire décoller l’avion de ligne à 250km/h consiste à dessiner un profil, puis utiliser les équations de Navier-Stokes dans le sens “direct” pour déterminer la portance (et la traînée) du profil que l’on essaie. Si les résultats ne sont pas ceux que l’on attend, il faut recommencer l’opération (essayer un autre profil) et évaluer à nouveau, dans un processus essai-erreur où l’expérience du concepteur est alors prépondérante.

Essayer tous les profils d’aile d’avion réalisables est impossible : il y en a trop. C’est pareil dans le cas d’un problème d’optimisation de tournées : c’est un problème connu sous le nom du “Voyageur de Commerce” et qui fait partie de la classe des problèmes NP-Complets sujets à des explosions combinatoires, pour lesquels on arrive vite à des limites faisant qu’il est impossible de trouver la tournée optimale de manière déterministe.

Que faire alors ? Une recherche aléatoire (appelée pudiquement “Monte-Carlo”) est souvent utilisée par les industriels mais c’est une approche frileuse car n’écartant volontairement aucune des solutions possibles avec des résultats mathématiquement liés au nombre d’essais effectués. On est sûrs de trouver la solution optimale si l’on fait un nombre infini d’essais.

L’approche présentée dans ce MOOC est celle de l’évolution artificielle. C’est une approche inspirée de la nature qui a l’avantage de bien équilibrer l’exploitation de bonnes solutions trouvées tout en garantissant qu’on continuera à explorer de nouvelles solutions pour le meilleur compromis EvE : Exploitation versus Exploration.

Dans cette approche, on décide délibérément de s’éloigner d’une recherche aléatoire dans l’espoir de trouver de bonnes solutions plus vite qu’avec une méthode de Monte Carlo, au prix du risque de passer à côté de la meilleure solution possible.


À l'issue de ce cours

  • Les participants qui ne savent pas programmer auront compris le fonctionnement des algorithmes évolutionnaires et sauront quand et comment les utiliser pour résoudre des problèmes industriels.
  • Les participants qui savent déjà programmer en C ou C++ sauront mettre en œuvre des algorithmes évolutionnaires capables d'optimiser des problèmes continus, discrets et combinatoires ainsi que des expressions de fonctions approximant des données. Pour les problèmes multi-objectifs, ils sauront comment les résoudre.

Mots-clés

optimisation, problème inverse, algorithme génétique, solution approchée, intelligence artificielle, évolution artificielle

L'enseignant

Pierre Collet

Pierre Collet est Professeur à l’Université de Strasbourg dont il dirige le département d’informatique depuis 2011. Il a été trésorier de l’association Evolution Artificielle de 2001 à 2003 puis président de cette association de 2003 à 2008. Il a présidé les conférences internationales EA’01, EuroGP’06 et a co-organisé de nombreuses autres conférences internationales sur le sujet. Il a co-organisé la première école d’été sur l’évolution artificielle en 2006 et vient de publier un livre avec Shigeyoshi Tsutsui sur l’implémentation d’algorithmes évolutionnaires sur cartes GPGPU, ordinateurs massivement parallèles et écosystèmes de calcul.

Pierre Collet coordonne sur Strasbourg le Campus Numérique des Systèmes Complexes, et avec Cyrille Bertelle de l’Université du Havre, l’UniTwin UNESCO Complex Systems Digital Campus, qui comprend plus de 100 universités, 3 millions d’étudiants et environ 2000 chercheurs.

Format

Le MOOC comprend :

  • une semaine d'introduction au MOOC,
  • 8 chapitres de cours répartis sur 8 semaines.
Dans chaque chapitre vous trouvez plusieurs unités contenant chacune :

  • une pastille vidéo,
  • un QCM,
  • un support de cours,
  • une activité participative.

Un mini-projet sera proposé pour ceux qui savent programmer. Les participants sont invités à échanger et s'entraider sur les forums du MOOC.

évaluation

Un QCM par unité (évaluation continuée intégrale) comprenant un retour ouvert sur le contenu pédagogique.
Un exercice d'application avec la plateforme EASEA.
Ce MOOC permet la délivrance d’une attestation de suivi avec succès.

À qui s’adresse ce cours ?

Décideurs, ingénieurs, scientifiques, mathématiciens (appliqués), informaticiens.

Pré-requis

Bac scientifique et pour ceux qui désireraient mettre en oeuvre un algorithme évolutionnaire : programmation en C/C++ dans le cadre de la plateforme EASEA (ce qui implique un ordinateur sous linux et l’installation de la plateforme EASEA sur cet ordinateur).

Plan du cours

  • Chapitre 0 : Introduction au MOOC
  • Chapitre 1 : Introduction aux problèmes d'optimisation
  • Chapitre 2 : Algorithmes évolutionnaires
  • Chapitre 3 : Plateforme EASEA
  • Chapitre 4 : Algorithmes génétiques, stratégies d'évolution, programmation génétique
  • Chapitre 5 : Proposition de projet
  • Chapitre 6 : Optimisation multi-critères
  • Chapitre 7 : Parallélisation
  • Chapitre 8 : Conclusion

Lectures recommandées

  • Antoine Cornuejols, Laurent Miclet, Apprentissage Artificiel – Concepts et Algorithmes, Eyrolles (2010)
  • Shigeyoshi Tsutsui, Pierre Collet, Massively Parallel Evolutionary Computation on GPGPUs, Springer (2013)
  • Koza, J.R., Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press (1992)
  • Koza, J.R., Genetic Programming II: Automatic Discovery of Reusable Programs, MIT Press (1994)
  • Koza, J.R., Bennett, F.H., Andre, D., and Keane, M.A., Genetic Programming III: Darwinian Invention and Problem Solving, Morgan Kaufmann (1999)
  • Koza, J.R., Keane, M.A., Streeter, M.J., Mydlowec, W., Yu, J., Lanza, G., Genetic Programming IV: Routine Human-Competitive Machine Intelligence, Kluwer Academic Publishers (2003)
  • Poli, R., Langdon, W. B., McPhee, N. F. (2008), A Field Guide to Genetic Programming, freely available via Lulu.com.

Conditions d'utilisation

  • du cours : Licence Creative Commons BY NC ND : l’utilisateur doit mentionner le nom de l’auteur, il peut exploiter l’œuvre sauf dans un contexte commercial et il ne peut apporter de modifications de l’œuvre originale.
  • du contenu produit par les internautes : Licence Creative Commons BY NC ND : l’utilisateur doit mentionner le nom de l’auteur, il peut exploiter l’œuvre sauf dans un contexte commercial et il ne peut apporter de modifications de l’œuvre originale.