Ecole EA 2011

Rechercher dans ce site

Interventions

Invités : 

"Numerous empirical studies have since long demonstrated that Evolutionary Algorithms (EAs) can deliver solutions of high quality on a
wide range of optimisation problems. However, a theoretical foundation that allows the performance of these algorithms to be predicted via
rigorous mathematical analysis has become available only recently.
This tutorial gives an introduction to some of the analytical techniques that has made time-complexity analysis of EAs possible, including
Chernoff bounds, artificial fitness levels, and drift analysis. The techniques will be illustrated by analysing the time-complexity of
simple EAs, first on synthetic toy problems, then on some classical combinatorial optimisation problems.
The tutorial assumes little background knowledge, and provides necessary basics like introductory probability theory, and asymptotic
notation. Ample time is allocated for solving exercises."
"Stochastic local search (SLS) algorithms are among the most powerful techniques for solving computationally hard problems in
many areas of computer science, operations research and engineering. SLS techniques range from rather simple constructive and
iterative improvement algorithms to general-purpose SLS methods (usually called metaheuristics) such as tabu search, iterated
local search, ant colony optimization or evolutionary algorithms.
In this tutorial, we first give a concise introduction into SLS and argue that the development of effective SLS algorithms
requires a sound algorithm engineering methodology. One of the key elements of such an SLS algorithm engineering will be the
exploitation of automatic algorithm configuration techniques in various phases of the algorithm design and development process.
In the remainder of the talk, we will focus therefore on two main topics, namely
- tools for the automatic configuration of SLS algorithms with a particular focus on F-races and iterated racing;
- the design and development of new state-of-the-art SLS algorithms using principled algorithm design steps and automatic algorithm configuration techniques."

Tutoriaux :

  • Anne Auger, Chargée de Recherche, INRIA Saclay - Ile de France, France : "Stratégies d'Evolution" (Archive_TP)
"Les stratégies d'evolutions (ES) sont des algorithmes d'optimisation stochastiques déstinés à l'optimisation continue sans dérivées et basés sur l'échantillonnage de vecteurs gaussiens. Ce cours est centré sur les questions les plus importantes liées aux ES: comment les paramètres des vecteurs gaussiens doivent être choisis ? Et comment ils doivent être mis à jour au cours des itérations ? Les approches les plus connues et efficaces sont présentées en détails, en particulier les approches auto-adaptatives, la règle des 1/5 et l'algorithme Covariance Matrix Adaptation (CMA). Les méthodes sont motivées par rapport aux difficultés rencontrées lorsque l'on doit résoudre un problème non-convexe, non linéaire. Les difficultés les plus courantes liés à l'optimisation sans dérivées sont discutées."
  • Pierre Collet, LSIIT, Université de Strasbourg : "Algorithmes Évolutionnaires parallèles sur GPU" (Archive_TP voir aussi sur SourceForge)
"La Programmation génétique peut être vue comme une instantiation d'un algorithme génétique où les solutions manipulées sont des programmes. Dans ce cours nous verrons les concepts de base introduits par Koza en 1992, et nous ferons un tour des problèmatiques essentielles du domaine, ainsi que des applications, en focalisant plus particulièrement sur les résultats brevetables obtenus ces dernières années."
"L'évolution artificielle s'intéresse aux mécanismes du vivant pour produire de nouvelles méthodes de résolution de problèmes dont le champ d'application est très vaste : problèmes théoriques ou appliqués en combinatoire, économie, recherche opérationnelle, aide à la décision, apprentissage automatique. De nombreux problèmes industriels complexes sont actuellement abordés et traités avec ce type d'approches."