Initiation Recherche

ING 2, EiLCO - 2016/2017

But

S'initier au domaine de recherche de l'optimisation stochastique. 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 :

  • TP noté, 50%,
  • 1 écrit terminal, 50%.

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 les algorithmes de stratégie d'évolution : (1+1) et (mu/mu,lambda)
  18. Connaitre l'influence du step-size (sigma) dans ces algorithmes
  19. Connaitre le principe du réglage du step-size à l'aide de la rêgle du 1/5 success rule.
  20. Savoir coder dans un langage les algorithmes de stratégies d'évolution précédents
  21. Connaitre la notion d'optimum local pour l'optimisation numérique

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 Intro. pb. optimisation / modélisation cours td tp
02 Algorithmes de recherche locale (1) cours notes R td code R ks5 ks1000
03 Algorithmes de recherche locale (2) cours td td tp

haut

Bibliographie

Quelques repères biblio- /webo- graphiques qui vont se complèter au fur et à mesure :

haut

dernière modification : 2 mai 2017