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 les métaheuristiques, des méthodes de résolution approchée des problèmes de grandes tailles, en particulier les méthodes de voisinage comme la recherche tabou ou le recuit simulé et les méthodes par population comme les algorithmes génétiques. La présentation des méthodes s'appuiera sur divers problèmes réels de RO.
Le cours comporte également la réalisation d’un projet incluant la programmation d’une métaheuristique.
Objectifs pédagogiques
- Cours magistral : 7
- Cours d'improvisation et théatre : 13
- Contrôle : 2
effectifs minimal / maximal:
8/40Diplô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
SOD321 - Optimisation Discrète
Format des notes
Numérique sur 20Littérale/grade européenPour 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 :
- Soutenance du projet.
- le rattrapage est obligatoire si :
- Note initiale < 6
- le rattrapage peut être demandé par l'étudiant si :
- 6 ≤ note initiale < 10
- Crédits ECTS acquis : 1.5 ECTS
- Scientifique acquis : 1.5
Le coefficient de l'UE est : 1
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 de recherche taboue.
Autres types de métaheuristiques. Exercices. Présentation du projet.
2. Bloc de module en salle info:
Séance 2
Applications des métaheuristiques. 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