Métaheuristiques
Réf. 187066
La solution exacte de certains problèmes d'optimisation ne peut être obtenue. Pas de souci, les métaheuristiques peuvent vous donner une solution approchante.
- Durée : 15 semaines
- Effort : 120 heures
- Rythme: ~8 heures/semaine
- Langues: NA
Ce que vous allez apprendre
À la fin de ce cours, vous saurez :
- Choisir une méthode de résolution d'un problème d'optimisation ;
- Adapter un algorithme d'une métaheuristique à un problème donné ;
- Maîtriser l'usage des principal s métaheuristiques ;
- …
Description
Le module Métaheuristiques comprend 8 session qui sont des unités de travail pour l'étudiant :
• S1 - Introduction : présentation de problèmes d'optimisation
• S2 - Méthodes exactes : revue des principales méthodes
• S3 - Présentation des métaheuristiques
• S4 - Méthodes locales I : recherche locale et méthode GRASP
• S5 - Méthodes locales II : Algorithme du recuit simulé et méthode Tabou
• S6 - Algorithmes génétiques
• S7 - Insectes sociaux
• S8 - Essaims particulaires
Chaque session comprend un cours sous forme vidéo, pages Web et fichier pdf téléchargeable ainsi que des exercices avec solutions. La résolution des exercices s'appuie en général sur l'utilisation facultative d'un site "laboratoire algorithmique"
Le module s'adresse à des étudiants de niveau master et demande au total 90 à 120 h de travail étalées sur 15 semaines.
Format
Chaque session est prévue pour être étudiée au long de 2 semaines (sauf la session S3 : une semaine) à raison de 6 à 8h de travail effectif.
Prérequis
• Niveau de mathématiques du premier cycle universitaire,
• Notions certaines d'algorithmique.
Evaluation et Certification
L'évaluation est laissée à la responsabilité de l'enseignant qui peut donner des devoirs au long de la formation.
Plan de cours
- Présentation de quelques problèmes d'optimisation. Ces problèmes seront résolus de manière exacte ou approche par les algorithmes présentés dans les sessions suivantes. Cette session donne lieu à un exercice portant sur un problème nouveau.
- Dans cette session quelques méthodes "exactes" (c'est-à-dire donnant la solution exacte du problème) sont présentées : programmation linéaire et algorithme du simplexe, méthode Branch and Bound, programmation dynamique. Cette session donne lieu à des exercices
- Une classification est proposée. Cette session comporte un QCM.
- Présentation du principe de la recherche locale : descente locale et algorithme GRASP. Cette session comporte des exercices.
- Dans cette session sont présentées deux métaheuristiques, l'algorithme du recuit simulé et la méthode Tabou. Cette session comporte des exercices.
- Cette session présente, après rappel rapide sur l'évolution des espèces, les opérations de croisement et de mutation, puis de sélection des meilleures solutions. Le cycle de génération de population est décrit et quelques applications à des problèmes présentés en S1 sont proposées. Cette session comporte des exercices.
- Après quelques généralités sur les méthodes employées par les insectes, la méthode des colonies de fourmis est présentée en détail, l'algorithme standard AS et ses variantes. Suivent ensuite quelques applications aux problèmes du S1. Cette session comporte des exercices.
- Cette métaheuristique est présentée dans son principe et dans sa version de base. Quelques variantes d'amélioration du modèle sont aussi présentées. Enfin quelques applications aux problèmes du S1 sont proposées.. Cette session comporte des exercices.
