TABLE DES MATIÈRES

1 Problèmes, algorithmes, complexité calculatoire
1.1 Complexité calculatoire
1.2 Analyse des algorithmes
1.3 Problèmes de décision et classes de complexité
1.4 La complexité des problèmes d'optimisation
1.5 Avons-nous besoin de métaheuristiques ?
2 Espace de recherche
2.1 Espace de recherche
2.2 Exemples
2.3 Meta-heuristiques et heuristiques
2.4 Principe de fonctionnement
2.5 Mouvements et transformation élémentaires
2.6 Métaheuristiques à population
2.7 Exemple de méthodes d'exploration
2.8 Echantillonnage de probabilités non uniformes et permutations aléatoires
3 Recherche Tabou
3.1 Principes de base
3.2 Un exemple simple
3.3 Convergence
3.4 Liste tabou, temps d’interdiction et mémoires à court et long termes
3.5 Paramètres de guidage
3.6 Problèmes d’affectation quadratique
4 Le recuit simulé
4.1 Motivations
4.2 Les principes de l’algorithme
4.3 Exemples
4.4 Convergence
4.5 Illustration de la convergence du recuit
4.6 Guide pratique
4.7 La méthode du Parallel Tempering
5 La méthode des colonies de fourmis
5.1 Motivation
5.2 Les phéromones : une méthode naturelle d’optimi-sation
5.3 Simulation informatique du mouvement des four-mis
5.4 Algorithme informatique d’optimisation
5.5 Les métaheuristiques «Ant System» et «Ant Colony System»
6 Optimisation pas essaim de particules
6.1 La méthode PSO
6.2 Principe de la méthode
6.3 Pourquoi ça marche ?
6.4 Exemples à deux dimensions

7 Lucioles, coucous et vols de Lévy
7.1 Introduction
7.2 Le théorème limite central et les distributions de Lévy
7.3 Lucioles : principes
7.4 La recherche "coucou"
8 Les algorithmes évolutionnaires : fondements
8.1 Introduction
8.2 Algorithmes génétiques
8.3 Bases théoriques des algorithmes génétiques
8.4 Stratégies d’évolution
9 Les algorithmes évolutionnaires : extensions
9.1 Introduction
9.2 La sélection
9.4 Programmation génétique linéaire
9.5 Populations structurées
9.6 Représentations et opérateurs spécialisés
9.7 Algorithmes évolutionnaires hybrides
10 Transition de Phase dans les problèmes d’opti-misation
10.1 Introduction
10.2 Le problème k-XORSAT
10.3 Modèle statistique de problèmes k-XORSAT
10.4 Élimination de Gauss
10.5 L’espace des solutions
10.6 Comportement d’une métaheuristique de re-cherche
11 Performance et limitations des métaheuris-tiques
11.1 Analyse empirique des performances d’une métaheuristique
11.2 Les théorèmes «No Free Lunch» et leurs consé-quences
12 Analyse statistique des espaces de recherche
12.1 Structure fine d’un espace de recherche
12.2 Mesures globales
12.3 Corrélation fitness-distance (CFD)
12.4 Promenades aléatoires et fonctions d’autocor-rélation de la fitness
12.5 Réseau des optima
Annexes