Intitulé de la matière : Techniques Avancées pour l’IA2 (TAI2)
Intitulé de l’UE : UEM2
Crédits : 4
Coefficients :2
Objectifs de l’enseignement
Aborder les problèmes d'optimisation et se familiariser avec les outils d'optimisation permettant la résolution de problématiques théoriques ou pratiques complexes. Acquérir les bases techniques et théoriques pour concevoir, analyser et évaluer les heuristiques et les méta-heuristiques.
Connaissances préalables recommandées: Techniques et structures (graphes, arbres, …) de base pour la résolution des problèmes.
Contenu de la matière
1. Programmation logique et par contraintes
2. Méthodes locales de résolution de problèmes
3. Problèmes de recherche NP-complets, problèmes d'optimisation
4. Recherches locales : voisinage, plus grande pente, liste tabou.
Mise en œuvre : implémentation de la liste tabou, mémoires à moyen / long terme
5. Approximation des problèmes NP-complets
6. Etude de fonctions heuristiques pour le A*
7. Méthodes de résolutions à base des Méta-heuristiques
Travaux pratiques
- Implémentation d'algorithmes de recherche locale
- Implémentation d'algorithmes de recherche de solution à base d’une méta-heuristique
Mode d’évaluation : (Continu :40%, EMD : 60%).
Références
- J. Dréo, A. Petrowski, É. Taillard, P. Siarry, Métaheuristiques pour l‟optimisation difficile, Eyrolles, 2003.
- C. Blum, A. Roli, Metaheuristics in combinatorial optimization: Overview and conceptual comparison, ACM Computing Surveys, 35, 2003.