Résolution de problèmes d'optimisation
Master 1 informatique I2L - 2020/2021
But
S'initier à la démarche de modélisation d'un problème pour le résoudre de manière informatique. Cet enseignement présente de nombreuses méthodes de résolution de problèmes et s'appuie sur des exemples pratiques.
hautEvaluation
L'évaluation comprend :
- Projets, 30%,
- 2 écrits intermédiaires, 20%, les 23/11/2020 de 45 minutes, et le xx/01/2021.
- 1 écrit terminal le xx/02/2021, 50%.
Cette UE compte pour 5 crédits ECTS.
haut
Équipe d'enseignants
Sébastien Verel et Alexandre Chotard.
Pour contacter un des intervenants : contacts.
Vous pouvez contacter l'équipe pour tout ce qui concerne cet enseignement et votre orientation.
Objectifs
Ils sont mis à jour régulièrement :
- Savoir définir un problème d'optimisation combinatoire
- Connaitre des exemples de problème d'optimisation (maxSAT, TSP, QAP, knapsack, etc.)
- Savoir modéliser un problème en un problème d'optimisation.
- Connaitre le principe d'une recherche locale à solution unique.
- Connaitre la recherche aléatoire
- Savoir comparer statistiquement deux algorithmes de recherche stochastiques.
- Savoir définir une marche aléatoire
- Connaitre les heuristiques "Hill-Climbing"
- Connaitre la notion d'optimum local
- Connaitre le dilemme exploration / exploitation
- Savoir définir les métaheuristiques classiques (recuit simulé, recherche taboue, iterated local search)
- Savoir définir les principes des algorithmes évolutionnaires
- Connaitre les différents types d'algorithmes évolutionnaires
- Savoir coder dans un langage les algorithmes d'optimisation précédents
- ...
Supports de Cours et de TP
Voici l'ensemble des supports de cours et des émoncés des TP.
| Séance | Titre | cours | TP/TD | Cor. |
|---|---|---|---|---|
| 01 | Introduction à l'optimisation | cours | td ks5 ks1000 | 02 | Modélisation: exemples discrets | cours | td chr12a bur26a | cor |
| 03 | Algorithmes de recherche locale | cours notes R | td codeR R-hc | cor |
| 04 | Metaheuristiques | cours | td pdf tp | |
| 05 | Algorithmes évolutionnaires | cours | td | cor |
| 06+ | Partie: Optimisation numérique | voir A. Chotard |
Bibliographie
Quelques repères bibliographiques :
- Métaheuristiques - Une introduction aux métaheuristiques pour l'optimisation, Bastien Shopard et Marco Tomassini, 2018.
- Métaheuristiques pour l'optimisation difficile, Johann Dréo, Alain Pétrowski, Patrick Siarry, Eric Taillard, 2003.
- Aide mémoire R, Aymeric Duclert, 2011.
dernière modification : 3 septembre 2020