Recherche Opérationnelle, Optimisation

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.

haut

Evaluation

L'évaluation comprend :

• Projets et TP notés, 40%,
• 1 écrit intermédiaire, 10%, les 20/11/2018 de 30 minutes. pdf
• 1 écrit terminal le 11/01/2019, 50%.

Projet: à rendre avant le 20 décembre 2018 minuit.
L'énoncé du projet pdf et une présentation qui peut être utile : pdf.
Codes source : code original avec versions java et c++: zip. Code amélioré plus rapide seulement en version c++ : https://gitlab.com/verel/firing-squad-synchronization-problem.git.


Cette UE compte pour 4 crédits ECTS.

Les énoncés des devoirs de l'année passée : TD 2017/18.

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.

haut

Objectifs

Ils sont mis à jour régulièrement :

1. Savoir définir un problème d'optimisation combinatoire
2. Connaitre des exemples de problème d'optimisation (maxSAT, TSP, QAP, knapsack, etc.)
3. Savoir modéliser un problème en un problème d'optimisation.
4. Connaitre le principe d'une recherche locale à solution unique.
5. Connaitre la recherche aléatoire
6. Savoir comparer statistiquement deux algorithmes de recherche stochastiques.
7. Savoir définir une marche aléatoire
8. Connaitre les heuristiques "Hill-Climbing"
9. Connaitre la notion d'optimum local
10. Connaitre le dilemme exploration / exploitation
11. Savoir définir les métaheuristiques classiques (recuit simulé, recherche taboue, iterated local search)
12. Savoir définir les principes des algorithmes évolutionnaires
13. Connaitre les différents types d'algorithmes évolutionnaires
14. Savoir coder dans un langage les algorithmes d'optimisation précédents
15. Savoir définir un problème d'optimisation numérique
16. Connaitre l'algorithme de descente de gradient à pas fixe
17. Connaitre l'algorithme de descente de gradient stochastique
18. Connaitre l'algorithmes de descente de gradient basé sur les moments
19. Connaitre les algorithmes de stratégie d'évolution : (1+1) et (mu/mu,lambda)
20. Connaitre l'influence du step-size (sigma) dans ces algorithmes
21. Connaitre le principe du réglage du step-size à l'aide de la rêgle du 1/5 success rule.
22. Savoir coder dans un langage les algorithmes de stratégies d'évolution précédents

haut

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	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
04bis	Algorithmes évolutionnaires	cours	td	cor
05	Analyse des données et argumentation numérique	cours	tp data	cor
06	Modélisation: exemples de problèmes d'optimisation numérique	cours
07	Introduction à l'optimisation numérique	cours	tp	cor
08	Méthodes d'optimisation avancées à base du gradient	cours	url code	cor
09	Stratégies d'évolution	cours	tp	cor

haut

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.

haut

Horaires

12h de CM, 12h de TD, et 15h de TP.


Consulter l'emploi du master : edt

haut