Descriptif
Les métaheuristiques sont des algorithmes de recherche stochastiques faisant partie des principales classes de solveur en optimisation non-linéaire. Employés sur des problèmes « difficiles » pour lesquels il est impossible de garantir des solutions optimales, ces méthodes permettent néanmoins de trouver des solutions approchées et sont classiquement employées sur des applications d'aide à la décision. Ce cours explore dans un premier temps les classes de problèmes sur lesquels il peut être pertinent d'employer des métaheuristiques en insistant sur l'importance de la modélisation.
Conçues à l'origine sur la base de métaphores (algorithmes évolutionnaires, recuit simulé, essaims, colonies de fourmis, etc.), leur conception s'est mathématisée et met en jeu des outils mathématiques allant de la géométrie aux statistiques. Nous verrons comment aller au-delà des métaphores pour comprendre les aspects communs étant au cœur de ces méthodes, avec un focus sur quelques aspects parmi les plus utiles en pratique.
Enfin, au-delà de la conception algorithmique, nous verrons pourquoi il est nécessaire d'employer une méthode empirique de validation issue des sciences expérimentales et comment mener une étude applicative rigoureuse en employant les dernières avancées en matière d'ingénierie algorithmique.
Objectifs pédagogiques
- Comprendre les avantages et les inconvénients des métaheuristiques pour l'optimisation « difficile ».
- Savoir concevoir une métaheuristique d'optimisation pour les principales classes de problèmes, depuis la modélisation jusqu'au paramétrage.
- Savoir estimer les performances de solveurs métaheuristiques.
effectifs minimal / maximal:
10/30Diplôme(s) concerné(s)
Pour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole Nationale Supérieure de Techniques Avancées
Bases en Python, optimisation mathématique et statistiques
Format des notes
Numérique sur 20Littérale/grade européenPour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole Nationale Supérieure de Techniques Avancées
Vos modalités d'acquisition :
Projet dans un cadre de compétition amicale
Le rattrapage est autorisé (Max entre les deux notes écrêté à une note seuil)- le rattrapage est obligatoire si :
- Note initiale < 6
- le rattrapage peut être demandé par l'étudiant si :
- 6 ≤ note initiale < 10
- Crédits ECTS acquis : 1.5 ECTS
Le coefficient de l'UE est : 1
La note obtenue rentre dans le calcul de votre GPA.
L'UE est évaluée par les étudiants.
Programme détaillé
1) Histoire des métaheuristiques, principales classes de problèmes, types d'applications envisageables. Implémentation d'un algorithme génétique « hors-ordinateur ».
2) Tenants et aboutissants de la modélisation d'un problème d'optimisation non-linéaire. Implémentation d'un problème booléen et d'un problème numérique.
3) Relations modèles-algorithmes, gestion de contraintes. Implémentation d'un problème de voyageur de commerce et d'un solveur « colonies de fourmis ».
4) Épluchage d'une métaphore : de la biologie à la géométrie de l'information. Implémentation d'un solveur numérique simple.
5) Validation empirique, outils d'ingénierie algorithmique. Implémentation d'un banc d'expérimentation.
6) Présentation d'un problème « boite-noire », mise en place d'une compétition. Implémentation libre.
7) Implémentation libre.
8) Examen. Présentation des résultats de la compétition et analyse collaborative.