v1.11.0 (682)

Cours scientifique - SOD324 : Méta-Heuristiques

Domaine > Mathématiques et leurs applications.

Descriptif

De nombreux problèmes de recherche opérationnelle sont « difficiles », en particulier les problèmes d’optimisation en variables 0-1 ou entières (PLNE). Ce cours présente deux approches de résolution. La première propose de résoudre de façon approchée des problèmes de grandes tailles à l’aide de métaheuristiques, en particulier les méthodes de voisinage comme la recherche tabou ou le recuit simulé. La présentation des méthodes s'appuiera sur divers problèmes réels de RO.
La deuxième approche est la recherche d’une solution exacte (optimale) par des méthodes arborescentes (branch and bound) qui utilisent souvent la programmation linéaire et des relaxations pour le calcul de bornes.
Le cours comporte également la réalisation d’un projet incluant la programmation d’une métaheuristique.

nombre d'heure en présentiel

22

nombre de blocs

7

Volume horaire par type d'activité pédagogique : types d'activité

  • Cours magistral : 7
  • Bloc de 1/2 journée en salle info : 13
  • Contrôle Final : 2

Diplôme(s) concerné(s)

Pour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole nationale supérieure de techniques avancées

OROC-RO-PM   Programmation Mathématique

Format des notes

Numérique sur 20

Littérale/grade américain

Pour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole nationale supérieure de techniques avancées

Vos modalités d'acquisition :

 - Examen.
- Soutenance du projet.

Le rattrapage est autorisé (Max entre les deux notes écrêté à une note seuil)
  • le rattrapage est obligatoire si :
    Note initiale < 6
  • le rattrapage peut être demandé par l'étudiant si :
    6 ≤ note initiale < 10
L'UE est acquise si Note finale >= 10
  • Crédits ECTS acquis : 1.5 ECTS
  • Scientifique acquis : 1.5

Le coefficient de l'UE est : 1.5

La note obtenue rentre dans le calcul de votre GPA.

L'UE est évaluée par les étudiants.

Programme détaillé

1. CM:
Séance 1
Introduction. Présentation des métaheuristiques à voisinages: recuit simulé et méthode tabou.
Autres types de métaheuristiques (algorithmes génétiques). Exercices.
Présentation du projet.
2. Bloc de module en salle info:
Séance 2
Applications des métaheursitiques. TD/TP travail en groupe sur des mini projets.
Résolution de problèmes simples (recherche de voisinages, calcul des variations de coûts).
3. Bloc de module en salle info:
Séance 3
Travail sur le projet.
4. CM:
Séance 4
Compléments sur les structures de voisinages et sur les méthodes à population.
5. Bloc de module en salle info:
Séance 5
Exercices et application des métaheuristiques à des problématiques d’allocation de fréquences
6. Contrôle:
Séance 6
Contrôle/QCM
7. Bloc de module en salle info:
Séance 6 bis
Soutenance du projet en salle info





Mots clés

Optimisation Combinatoire, Recuit Simulé, Recherche Tabou, méthodes arborecentes, programmatin linéaire en nombres entiers
Veuillez patienter