Université de Strasbourg
FUN
date_range Starts on May 4, 2015
event_note End date June 28, 2015
list 8 sequences
assignment Level : Introductive
chat_bubble_outline Language : French
card_giftcard 256 points
Users' reviews
-
starstarstarstarstar

Key information

credit_card Free access
verified_user Free certificate
timer 32 hours in total

About the content

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.

  • 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.

more_horiz Read more
more_horiz Read less
report_problem

Prerequisite

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).

dns

Syllabus

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

record_voice_over

Intructors

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.

store

Content designer

The University of Strasbourg in Strasbourg, Alsace, France, is the second largest university in France (after Aix-Marseille University), with about 43,000 students and over 4,000 researchers.

The present-day French university traces its history to the earlier German-language Universität Straßburg, which was founded in 1538, and was divided in the 1970s into three separate institutions: Louis Pasteur University, Marc Bloch University, and Robert Schuman University. On 1 January 2009, the fusion of these three universities reconstituted a united University of Strasbourg, which is now amongst Europe's best in the League of European Research Universities.

assistant

Platform

France Université Numérique is the broadcaster of the online courses of French higher education institutions and their partners.

It operates several platforms of diffusion, of which the best known, FUN MOOC, is the first French-speaking academic platform worldwide. Thanks to many partner institutions, this platform offers a vast catalog of courses enriched daily with various themes and current events.

You are the designer of this MOOC?
What is your opinion on this resource ?
Content
0/5
Platform
0/5
Animation
0/5