Cours IFT6751 -- Hiver 2010

Métaheuristiques en optimisation
Professeur: Jean-Yves Potvin

Description du cours

Le cours portera sur des méthodes de résolution heuristiques "modernes" qui s’inspirent de l’intelligence artificielle et de certaines métaphores naturelles afin de s’attaquer à des problèmes complexes d’optimisation. Ces méthodes sont connues sous le vocable de métaheuristiques parce qu’elles offrent un cadre général de résolution qui est ensuite adapté au type de problèmes que l’on veut résoudre.

De façon plus précise, la première partie du cours traitera de la recherche tabou, la seconde des algorithmes génétiques, et la troisième des réseaux de neurones, en particulier les réseaux de Hopfield et les réseaux élastiques. D’autres métaheuristiques seront aussi brièvement introduites comme le recuit simulé et les systèmes de colonies de fourmis. Nous nous intéresserons à l’application de ces diverses méthodes pour résoudre des problèmes d'optimisation combinatoire, plus particulièrement des problèmes de confection de tournées de véhicules.

Les étudiants seront appelés à réaliser des projets d'implantation de certaines des méthodes mentionnées plus haut. Il faut noter qu'aucune connaissance préalable de ces méthodes n'est exigée et que toute la documentation nécessaire sera fournie au cours.

Syllabus

Le syllabus présente un plan détaillé des sujets couverts semaine par semaine ainsi que le mode d'évaluation du cours.

Documents de base

Introduction

Introduction aux techniques de recherche

Tournées de véhicules

Algorithms for Vehicle Routing and Scheduling Problems with Time Window Constraints
Dynamic Vehicle Routing and Dispatching

Recherche Tabou

Tabu Search - Part I
Tabu Search - Part II
An Introduction to Tabu Search

Algorithmes génétiques

Introduction
Notions de base
Fondements mathématiques
Genetic Algorithms for the Traveling Salesman Problem
Evolutionary Algorithms for Vehicle Routing

Programmation génétique

Genetic Evolution and Co-Evolution of Computer Programs

Systèmes de colonies de fourmis

The Ant System: Optimization by a Colony of Cooperating Agents
Ant Algorithms for Discrete Optimization

Réseaux de neurones

The Traveling Salesman Problem: A Neural Network Perspective

Devoirs


Présentations


Livres de référence