Heuristic optimisation

Des problèmes computationallement difficiles se posent dans de nombreux domaines d'application pertinentes de l'intelligence computationnelle tels que l'informatique, la recherche opérationnelle, la bio-informatique et de l'ingénierie. Pour beaucoup de ces problèmes, les techniques de recherche heuristique sont les méthodes les plus réussies. Ce cours présente et discute des techniques d'optimisation heuristiques avec un accent sur les techniques stochastiques de recherche locale. Le cours illustre les principes de ces algorithmes utilisant un certain nombre d' exemples d'applications. Un accent important dans le cours sera également sur les techniques pertinentes pour l'évaluation empirique des algorithmes d'optimisation heuristiques et les problèmes qui se posent dans leur conception et leur développement. Une expérience pratique avec ces techniques algorithmiques seront acquises dans des exercices pratiques.

Computationally hard problems arise in many relevant application areas of computational intelligence such as computer science, operations research, bioinformatics, and engineering. For many such problems, heuristic search techniques are the most successful methods. This course introduces and discusses heuristic optimization techniques with a main focus on stochastic local search techniques. The course illustrates the application principles of these algorithms using a number of example applications. A significant focus in the course will be also on relevant techniques for the empirical evaluation of heuristic optimization algorithms and issues that arise in their design and development. Hands-on experience with these algorithmic techniques will be gained in accompanying practical exercises.

L'objectif principal est de donner aux étudiants une connaissance théorique et pratique de la façon de résoudre effectivement les problèmes d'optimisation difficiles avec des techniques heuristique.

De façon plus détaillée , les objectifs sont

• Renseignez-vous sur les techniques d'optimisation heuristique

• Apprenez comment ceux-ci peuvent être utilisés pour résoudre les problèmes d'optimisation

• Apprendre à analyser des algorithmes heuristiques empiriquement.

• Obtenir une expérience pratique sur la mise en œuvre et l'application des techniques heuristiques

Le cours comprend des conférences, des séances d'exercice, où les élèves approfondissent certains sujets abordés dans les conférences et les tâches pratiques de mise en œuvre. Le cours est enseigné en anglais.

Contribution au profil d'enseignement

• Connaitre les techniques de recherche heuristique disponibles pour résoudre les problèmes computationelles complexes et être capable de déterminer quelle technique heuristique s'applique dans quelle situation.

• Comprendre les principes sous-tendant les techniques de recherche heuristique.

• Comprendre les possibilités offertes et avantages des techniques de recherche heuristique, mais aussi leurs limitations

• Apprendre à évaluer les performances des systèmes computationnels comme des techniques de recherche heuristique et à réaliser des études empiriques correctes.

• Etre attentif aux nouvelles tendances, aux avancées et aux recherches dans le domaine de recherche heuristique; être capable d'évaluer les nouvelles méthodes de recherche heuristique, et être capable d'apprendre à utiliser ces nouvelles méthodes si nécessaire.

Références, bibliographie et lectures recommandées

Le cours est principalement basé sur le livre

Holger Hoos and Thomas Stützle. Stochastic Local Search-Foundations and Applications, Morgan Kaufmann Publishers, San Francisco, California, 2004.

Autre documentation pertinente pour le cours est

Emile H. L. Aarts und Jan Karel Lenstra (editors), Local Search in Combinatorial Optimization. John Wiley and Sons, 1997.

Marco Dorigo und Thomas Stützle, Ant Colony Optimization. MIT Press, 2004.

Zbigniew Michalewicz and David Fogel, How to Solve it: Modern Heuristics. Springer Verlag, 2000.

Vittorio Maniezzo, Thomas Stützle, and Stefan Voß, Matheuristics-Hybridizing Metaheuristics and Mathematical Programming, Springer Verlag, New York, 2009.

El-Ghazali Talbi, Metaheuristics - From Design to Implementation. Wiley, Chichester, UK, 2009.

Michel Gendreau and Jean-Yves Potvin, Handbook of Metaheuristics, Springer Verlag, New York, 2nd edition, 2010.

M. Birattari, Z. Yuan, P. Balaprakash and T. Stützle F-Race and Iterated F-Race: An Overview Technical Report TR/IRIDIA/2009-018, 2009.

Contacts

Thomas Stützle, informations sur la page http://iridia.ulb.ac.be/~stuetzle/Teaching/HO/

Méthode(s) d'évaluation

• Autre

Autre

Examen oral et exercices de programmation des algorithmes heuristiques

Construction de la note (en ce compris, la pondération des notes partielles)

60% examen oral et 40% exercices de programmation

Langue(s) d'évaluation

• anglais