Optimisation Stochastique Évolutionnaire

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.