Portail nationalFormationRechercher par discipline

Métaheuristiques

Code UE : US331D

  • Cours
  • 3 crédits

Responsable(s)

Safia KEDAD SIDHOUM

Public, conditions d’accès et prérequis

Connaître les bases de la théorie des graphes, l'algorithme de séparation et évaluation et un langage de programmation.

Présence et réussite aux examens

Pour l'année universitaire 2021-2022 :

  • Nombre d'inscrits : 17
  • Taux de présence à l'évaluation : 100%
  • Taux de réussite à l'évaluation : 100%

Objectifs pédagogiques

L'objectif de l'UE est d'introduire les éléments nécessaires permettant aux étudiants de concevoir et d'appliquer des métaheuristiques (méthodes approchées générales comme le recuit simulé, la méthode Tabou, les algorithmes évolutionnaires, etc.). Ce cours se propose de mettre en relief des éléments communs régissant plusieurs de ces méthodes (par exemple la notion de voisinage ou, de façon équivalente, la notion de transformation élémentaire) ou au contraire les différences essentielles entre différentes familles d'approches (en comparant par exemple les méthodes fondées sur la notion de voisinage et celles s'inspirant de phénomènes observables dans la nature, comme les algorithmes évolutionnaires ou les colonies de fourmis). Ce cours proposera également une étude de cas et une expérimentation via la programmation de certaines métaheuristiques dans le contexte d'un projet. Les étudiants seront ainsi amenés à étudier par eux-mêmes l'adaptation de ces méthodes à un problème d'optimisation difficile pour mieux comparer leurs caractéristiques (qualité de la solution fournie, temps de résolution, simplicité de programmation, ajustement des paramètres...).

Compétences visées

Savoir modéliser des problèmes d'optimisation combinatoire difficiles dans le but de les résoudre en adaptant des métaheuristiques.

Contenu

  • Généralités et définitions, présentation de 2 problèmes d'optimisation utilisés pour les illustrations : les problèmes du voyageur de commerce et du sac à  dos, heuristiques gloutonnes, de réparation et d'amélioration locale
  • Heuristiques à  démarrages multiples, recherche à voisinages variables, exploration de grands voisinages (1/2) : chaînes d'éjection illustrées via l'heuristique de Lin et Kernighan, Exploration de grands voisinages (2/2) : combinaison d'échanges, voisinage défini par un problème d'affectation
  • Recuit simulé, recherche avec tabous, algorithmes évolutionnaires, colonies de fourmis
  • Algorithmes mémétiques, analyse du paysage de recherche, heuristiques landscape-aware

Modalité d'évaluation

  • Projet(s)

Cette UE apparaît dans les diplômes et certificats suivants

Chargement du résultat...
Patientez
Intitulé de la formation
Type
Modalité(s)
Lieu(x)
Intitulé de la formation Master Sciences, technologies, santé mention Informatique Parcours Recherche opérationnelle
Type Diplôme national (DEUST, licence, master, doctorat, diplôme d'Etat)
Lieu(x) Package
Lieu(x) Paris
Entrée Niveau 6 (Bac+3 et 4)
Intitulé de la formation Type Modalité(s) Lieu(x)

Contact

Recherche opérationnelle
2D4P20, 33-1-10, 2 rue Conté
75003 Paris
Tel :01 40 27 22 67
secretariat.ro@cnam.fr
Voir le site

Voir le calendrier, le tarif, les conditions d'accessibilité et les modalités d'inscription dans le(s) centre(s) d'enseignement qui propose(nt) cette formation.

Enseignement non encore programmé