Optimisation par colonies de fourmis

Auteur(s) :

Solnon, Christine Découvrir l'auteur

Résumé

Le point sur la résolution de problèmes combinatoires grâce à l'optimisation par colonie de fourmis, une méthode qui s'inspire du comportement collectif de ces insectes.

Éditeur(s)
- Hermès science publications
Date
- 2008
Notes
- Bibliogr. Index
Langues
- Français
Description matérielle
- 192 p. : ill. ; 24 x 16 cm
Collections
- Programmation par contraintes
Sujet(s)
- Optimisation combinatoire
ISBN
- 978-2-7462-1863-5
Indice
- 681.2 Programmation (généralités)
Quatrième de couverture
- L'optimisation par colonies de fourmis s'inspire du comportement collectif des fourmis dans la nature pour résoudre des problèmes d'optimisation combinatoires. Initialement proposée pour résoudre le problème du voyageur de commerce, elle a été appliquée avec succès à un grand nombre de problèmes NP-difficiles.
  La programmation par contraintes permet de décrire des problèmes combinatoires de façon déclarative, la résolution de ces problèmes étant prise en charge par des algorithmes intégrés au langage. Cette vision de la programmation par contraintes montre les bénéfices de l'optimisation par colonies de fourmis de manière large et novatrice ainsi que ses connections avec les principales approches existantes pour la résolution de problèmes combinatoires.
  Didactique, Optimisation par colonies de fourmis dresse tout d'abord un panorama des diverses méthodes pour la résolution de problèmes combinatoires et présente ensuite l'optimisation par colonies de fourmis. Des chapitres applicatifs permettent une compréhension en profondeur de ce sujet novateur.
Tables des matières
- - Optimisation par colonies de fourmis
  - Christine Solnon
  - Lavoisier
  - Préface de Pascal Van Hentenryck 13
  - Chapitre 1. Introduction 15
  - Chapitre 2. Notions de complexité 21
  - 2.1. Complexité algorithmique21
  - 2.2. Complexité théorique d'un problème22
  - 2.2.1. La classe P23
  - 2.2.2. La classe NP23
  - 2.2.3. Problèmes NP-complets24
  - 2.2.4. Problèmes NP-difficiles25
  - 2.2.5. Problèmes indécidables25
  - 2.2.6. Complexité des problèmes d'optimisation25
  - 2.3. Difficulté des instances d'un problème26
  - 2.3.1. Notion de transition de phases27
  - 2.3.2. Notion de paysage de recherche28
  - 2.4. ... et en pratique ?30
  - 2.4.1. Exploitation de cas particuliers32
  - 2.4.2. Algorithmes d'approximation32
  - 2.4.3. Approches heuristiques et méta-heuristiques33
  - 2.4.4. Structuration et réduction de l'espace de recherche34
  - Première partie. Programmation par contraintes 37
  - Introduction à la première partie 39
  - Chapitre 3. Problèmes de satisfaction de contraintes 41
  - 3.1. Qu'est-ce qu'une contrainte ?41
  - 3.1.1. Définition d'une contrainte en extension42
  - 3.1.2. Définition d'une contrainte en intention42
  - 3.1.3. Arité d'une contrainte et contraintes globales42
  - 3.2. Qu'est-ce qu'un problème de satisfaction de contraintes ?43
  - 3.2.1. Définition d'un problème de satisfaction de contraintes43
  - 3.2.2. Solution d'un problème de satisfaction de contraintes43
  - 3.2.3. Complexité d'un problème de satisfaction de contraintes44
  - 3.3. Exemple 1 : le problème des reines45
  - 3.3.1. Description du problème45
  - 3.3.2. Première modélisation45
  - 3.3.3. Deuxième modélisation46
  - 3.3.4. Troisième modélisation47
  - 3.3.5. De l'influence de la modélisation sur la résolution48
  - 3.4. Exemple 2 : les mariages stables49
  - 3.4.1. Description du problème49
  - 3.4.2. Modélisation du problème sous la forme d'un CSP51
  - 3.5. Exemple 3 : CSP binaires générés aléatoirement52
  - 3.6. Exemple 4 : problème d'ordonnancement de voitures53
  - 3.6.1. Description du problème53
  - 3.6.2. Modélisation sous la forme d'un CSP55
  - 3.7. Discussion56
  - Chapitre 4. Méthodes de résolution exactes 57
  - 4.1. Construction d'un arbre de recherche58
  - 4.2. Propagation de contraintes et consistances partielles59
  - 4.2.1. Filtrage par vérification en avant61
  - 4.2.2. Filtrage par consistance d'arc61
  - 4.3. Heuristiques d'ordre63
  - 4.3.1. Heuristiques pour le choix des variables64
  - 4.3.2. Heuristiques pour le choix des valeurs65
  - 4.3.3. Heuristiques aléatoires et redémarrage66
  - 4.4. Discussion66
  - Chapitre 5. Méthodes de résolution heuristiques 69
  - 5.1. Problèmes de satisfaction de contraintes et optimisation70
  - 5.1.1. Maximiser la satisfaction des contraintes70
  - 5.1.2. Problèmes sous-contraints et optimisation sous contraintes71
  - 5.2. Approches par voisinage72
  - 5.2.1. Algorithmes génétiques72
  - 5.2.2. Recherche locale75
  - 5.2.3. Optimisation par essaims de particules78
  - 5.3. Approches constructives80
  - 5.3.1. Algorithmes gloutons et gloutons aléatoires80
  - 5.3.2. Algorithmes par estimation de distributions82
  - 5.3.3. Optimisation par colonies de fourmis84
  - 5.4. Intensification versus diversification de la recherche84
  - 5.5. Discussion86
  - Chapitre 6. Langages de programmation par contraintes 87
  - 6.1. Langages basés sur des approches exactes88
  - 6.1.1. Prolog et la programmation par contraintes88
  - 6.1.2. Bibliothèques de programmation par contraintes90
  - 6.2. Langages basés sur des approches heuristiques91
  - 6.3. Discussion93
  - Deuxième partie. Optimisation par colonies de fourmis 95
  - Introduction à la deuxième partie 97
  - Chapitre 7. Des fourmis naturelles aux fourmis artificielles 99
  - 7.1. Systèmes complexes et intelligence collective99
  - 7.2. Recherche de plus courts chemins par une colonie de fourmis101
  - 7.3. Modélisation de l'expérience du double pont102
  - Chapitre 8. La méta-heuristique ACO 105
  - 8.1. Ant System et le voyageur de commerce106
  - 8.2. Principe général de la méta-heuristique ACO107
  - 8.2.1. Structure phéromonale et graphe de construction108
  - 8.2.2. Construction de combinaisons par les fourmis109
  - 8.2.3. Amélioration des combinaisons construites par recherche locale110
  - 8.2.4. Mise à jour de la phéromone111
  - 8.2.5. Paramètres d'un algorithme ACO112
  - 8.3. Intensification versus diversification112
  - 8.3.1. Intensification112
  - 8.3.2. Diversification115
  - 8.3.3. Indicateurs de diversification/intensification116
  - 8.4. Le coin du programmeur119
  - 8.4.1. Sélection d'un composant en fonction d'une probabilité119
  - 8.4.2. Indicateurs de diversification/intensification122
  - 8.5. Discussion123
  - Chapitre 9. Ordonnancement de voitures avec ACO 125
  - 9.1. Notations125
  - 9.2. Structure phéromonale pour identifier les «bonnes» séquences126
  - 9.2.1. Structure phéromonale127
  - 9.2.2. Construction d'une séquence par une fourmi128
  - 9.2.3. Dépôt de phéromone130
  - 9.3. Structure phéromonale pour identifier les voitures «critiques»130
  - 9.3.1. Structure phéromonale130
  - 9.3.2. Construction d'une séquence par une fourmi131
  - 9.3.3. Mise à jour de la phéromone131
  - 9.4. Combinaison des deux structures phéromonales132
  - 9.4.1. Première structure phéromonale132
  - 9.4.2. Seconde structure phéromonale132
  - 9.4.3. Construction d'une séquence par une fourmi133
  - 9.5. Evaluation expérimentale133
  - 9.5.1. Jeux d'essais133
  - 9.5.2. Comparaison des différents algorithmes ACO134
  - 9.5.3. Comparaison avec d'autres approches137
  - 9.5.4. Discussion141
  - Chapitre 10. Recherche de sous-ensembles avec ACO 143
  - 10.1. Problèmes de sélection de sous-ensembles144
  - 10.1.1. Recherche d'une clique maximum144
  - 10.1.2. Le sac à dos multidimensionnel144
  - 10.1.3. Maximisation de la satisfiabilité de formules booléennes (Max-SAT)145
  - 10.1.4. Satisfaction maximale de contraintes (MaxCSP)145
  - 10.1.5. Couverture minimale de sommets146
  - 10.1.6. Recherche du plus grand sous-graphe commun146
  - 10.2. Description d'Ant-SSP146
  - 10.2.1. Construction d'une combinaison par une fourmi147
  - 10.2.2. Dépôt de phéromone149
  - 10.3. Instanciations d'Ant-SSP par rapport à deux stratégies phéromonales149
  - 10.3.1. La stratégie phéromonale «Vertex»150
  - 10.3.2. La stratégie phéromonale «Clique»150
  - 10.3.3. Comparaison des deux stratégies151
  - 10.4. Application d'Ant-SSP à la résolution de CSP153
  - 10.4.1. Facteur heuristique153
  - 10.4.2. Recherche locale154
  - 10.5. Résultats expérimentaux154
  - 10.5.1. Instances binaires aléatoires154
  - 10.5.2. Résultats sur les instances de la compétition de solveurs 2006156
  - 10.6. Discussion159
  - Troisième partie. Programmation par contraintes avec des colonies de fourmis 161
  - Introduction à la troisième partie 163
  - Chapitre 11. Intégration d'ACO dans Ilog Solver 165
  - 11.1. La bibliothèque de programmation par contraintes Ilog Solver165
  - 11.2. Principe de l'intégration d'une recherche ACO dans Ilog Solver167
  - 11.2.1. Stratégie phéromonale169
  - 11.2.2. Choix d'une variable et d'une valeur170
  - 11.2.3. Propagation de contraintes171
  - 11.2.4. Mise à jour de la phéromone171
  - 11.3. Illustration sur le problème d'ordonnancement de voitures171
  - 11.3.1. Modélisation CSP du problème171
  - 11.3.2. Heuristique d'ordre de choix de variables172
  - 11.3.3. Stratégies phéromonales considérées172
  - 11.3.4. Facteur heuristique173
  - 11.4. Résultats expérimentaux174
  - 11.4.1. Instanciations d'Ant-CP comparées174
  - 11.4.2. Paramétrage et jeu d'essai174
  - 11.4.3. Résultats avec l'heuristique EtaDSU175
  - 11.4.4. Résultats avec l'heuristique EtaDSU+P176
  - 11.5. Discussion176
  - Chapitre 12. Conclusion 179
  - 12.1. Vers une recherche ACO basée sur les contraintes179
  - 12.2. Vers une recherche ACO réactive180
  - Bibliographie 183
  - Index 191
Origine de la notice:
- Electre