Ce livre aborde de façon pédagogique les principes de base des métaheuristiques et explique le "pourquoi et comment ça marche" des métaheuristiques classiques (tabou, recuit, fourmis, algorithmes évolutionnaires, etc...). Il discute aussi de la convergence des méthodes, de leurs performances et transitions de phase ainsi que de la structure des espaces de recherche.Ouvrage à destination des lecteurs désireux de se familiariser avec ce sujet à travers un texte pédagogique et illustré d'exemples simples.Les auteurs tentent de mettre en avant les mécanismes communs aux métaheuristiques, cherchant avant tout à comprendre plutôt qu'à utiliser. Ils abordent aussi des chapitres qui sont absents de beaucoup d'ouvrages sur ce sujet, comme l'analyse des performances, les transiti ...
Lire la suite
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
Ce livre aborde de façon pédagogique les principes de base des métaheuristiques et explique le "pourquoi et comment ça marche" des métaheuristiques classiques (tabou, recuit, fourmis, algorithmes évolutionnaires, etc...). Il discute aussi de la convergence des méthodes, de leurs performances et transitions de phase ainsi que de la structure des espaces de recherche.Ouvrage à destination des lecteurs désireux de se familiariser avec ce sujet à travers un texte pédagogique et illustré d'exemples simples.Les auteurs tentent de mettre en avant les mécanismes communs aux métaheuristiques, cherchant avant tout à comprendre plutôt qu'à utiliser. Ils abordent aussi des chapitres qui sont absents de beaucoup d'ouvrages sur ce sujet, comme l'analyse des performances, les transitions de phase, le théorème "no free lunch", les algorithmes lucioles et le "parallel tempering".