Recherche Opérationnelle, Optimisation
Master 1 I2L en apprentissage - 2016/2017
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 et TP notés, 40%,
- 2 écrits intermédiaires, 10%, les 11/10/2016 et 7/11/2016 de moins de 30 minutes.
- 1 écrit terminal le 13/01/2017, 50%.
Enoncé du projet 1 pdf et code à rendre avant le 06/01/2017 à 23h59.
Cette UE compte pour 4 crédits ECTS.
Les énoncés des devoirs de l'année passée : ici.
haut
Équipe d'enseignants
Sébastien Verel
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
- Savoir définir un problème d'optimisation numérique
- Connaitre l'algorithme de descente de gradient à pas fixe
- Connaitre les algorithmes de stratégie d'évolution : (1+1) et (mu/mu,lambda)
- Connaitre l'influence du step-size (sigma) dans ces algorithmes
- Connaitre le principe du réglage du step-size à l'aide de la rêgle du 1/5 success rule.
- Savoir coder dans un langage les algorithmes de stratégies d'évolution 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 | TD | TP |
|---|---|---|---|---|
| 01 | Intro. pb. optimisation / modélisation | cours annexe |
td | tp |
| 02 | Algorithmes de recherche locale (1) | cours notes R | td code R | ks5 ks1000 cor cor |
| 03 | Algorithmes de recherche locale (2) | cours | td td | tp |
| 04 | Algorithmes évolutionnaires | cours | td | tp cor |
| 05 | Optimisation numérique et Stratégies d'évolution | cours | part1 cor | part2 cor | 06 | Optimisation multiobjective | cours | td | tp |
Bibliographie
Quelques repères biblio- /webo- graphiques qui vont se complèter au fur et à mesure :
- Métaheuristiques pour l'optimisation difficile, Johann Dréo, Alain Pétrowski, Patrick Siarry, Eric Taillard, 2003.
- Aide mémoire R, Aymeric Duclert, 2011.
- Comment rédiger un rapport ou une publication scientique., Alexandre Buttler, Université de France-Comté, 2002.
dernière modification : 6 septembre 2016