logo
v2.12.0 (512)

Cours scientifiques - APM_5RO03_TA : Méta-heuristiques

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.

22 heures en présentiel

Diplôme(s) concerné(s)

Parcours de rattachement

Format des notes

Numérique sur 20

Littérale/grade européen

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