v2.3.2 (2860)

Cours scientifique - IA308 : Optimisation et Méta-heuristiques

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.

nombre d'heure en présentiel

24

nombre de blocs

8

effectifs minimal / maximal

10/30

Diplô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 20

Littérale/grade européen

Pour 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
L'UE est acquise si Note finale >= 10
  • Crédits ECTS acquis : 2 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.

Mots clés

Optimisation continue et discrète, Démarche épistémologique, Colonie de fourmis
Veuillez patienter