Métaheuristiques

Auteur(s) :

Siarry, Patrick (1952-....) Découvrir l'auteur

Résumé

Présente les grandes techniques métaheuristiques, ainsi que leurs variantes : recuit simulé, recherche avec tabous, fourmis artificielles, essaims particulaires, etc. Il donne également des conseils pour modéliser ou choisir la méthode la plus adaptée à un problème donné. Avec 3 études de cas réels dans le domaine de la logistique et des transports.

Éditeur(s)
- Eyrolles
Date
- 2014
Notes
- Bibliogr. Index
Langues
- Français
Description matérielle
- 1 vol. : illustrations en noir et blanc
Collections
- Algorithmes
Sujet(s)
ISBN
- 978-2-212-13929-7
Indice
- 652.21 Programmation mathématique
Quatrième de couverture
- Métaheuristiques
  Les métaheuristiques et leurs applications
  Les ingénieurs, les économistes, les décideurs se heurtent quotidiennement, quel que soit leur secteur d'activité, à des problèmes d'optimisation. Il peut s'agir de minimiser un coût de production, d'optimiser le parcours d'un véhicule ou le rendement d'un portefeuille boursier, de rationaliser l'utilisation de ressources, d'améliorer les performances d'un circuit électronique, de fournir une aide à la décision à des managers, etc.
  Cet ouvrage présente une famille de techniques d'optimisation, appelées « métaheuristiques », adaptées à la résolution de problèmes pour lesquels il est difficile de trouver un optimum global ou de bons optimums locaux par des méthodes plus classiques.
  Un ouvrage de référence illustré d'études de cas
  La première partie de l'ouvrage présente les principales métaheuristiques : recuit simulé, recherche avec tabous, recherche à voisinages variables, méthode GRASP, algorithmes évolutionnaires, fourmis artificielles et essaims particulaires.
  La deuxième partie décrit différentes variantes et extensions de ces méthodes, ainsi que de nouvelles voies de recherche. Y sont également proposés des conseils méthodologiques : techniques de modélisation, comparaisons de méthodes et choix de la méthode la mieux adaptée à un problème donné.
  La troisième partie présente trois études de cas réels : optimisation de systèmes logistiques, optimisation de tournées de véhicules et gestion de trafic aérien.
  À qui s'adresse ce livre ?
  ¤ Aux élèves ingénieurs et étudiants en mathématiques appliquées, algorithmique, recherche opérationnelle, gestion de production, économie et finance, aide à la décision, etc.
  ¤ Aux ingénieurs, enseignants-chercheurs, informaticiens, industriels, économistes et décideurs ayant à résoudre des problèmes complexes d'optimisation et d'aide à la décision.
Tables des matières
- - Métaheuristiques
  - Recuit simulé, recherche avec tabous, recherche à voisinages variables, méthode GRASP, algorithmes évolutionnaires, fourmis artificielles, essaims particulaires et autres méthodes d'optimisation
  - Patrick Siarry
  - Eyrolles
  - Index des auteursXV
  - Avant-propos1
  - I Présentation des principales métaheuristiques19
  - 1 La méthode du recuit simulé21
  - P. Siarry
  - 1.1 Introduction21
  - 1.2 Présentation de la méthode22
  - 1.2.1 Analogie entre un problème d'optimisation et certains phénomènes physiques22
  - 1.2.2 Recuit réel et recuit simulé23
  - 1.2.3 Algorithme au recuit simulé23
  - 1.3 Approches théoriques24
  - 1.3.1 Convergence théorique du recuit simulé25
  - 1.3.2 Espace des configurations26
  - 1.3.3 Règles d'acceptation27
  - 1.3.4 Programme de recuit27
  - 1.4 Parallélisation de l'algorithme du recuit simulé29
  - 1.5 Quelques applications32
  - 1.5.1 Problèmes modèles d'optimisation combinatoire32
  - 1.5.2 Placement des circuits électroniques34
  - 1.5.3 Recherche d'un schéma équivalent en électronique37
  - 1.5.4 Applications pratiques dans des domaines divers38
  - 1.6 Avantages et inconvénients de la méthode40
  - 1.7 Suggestions pratiques simples pour démarrer40
  - 1.8 Annexe : modélisation du recuit simulé à l'aide du formalisme des chaînes de Markov41
  - 1.9 Bibliographie commentée48
  - 2 La recherche avec tabous51
  - É.D. Taillard
  - 2.1 Historique51
  - 2.2 Problème de l'affectation quadratique53
  - 2.3 Recherche avec tabous de base55
  - 2.3.1 Voisinage55
  - 2.3.2 Mouvements, voisinage57
  - 2.3.3 Évaluation du voisinage59
  - 2.3.4 Limitation du voisinage : liste de mouvements candidats61
  - 2.3.5 Extension d'un voisinage : chaîne d'éjections61
  - 2.4 Mémoire à court terme62
  - 2.4.1 Table de hachage63
  - 2.4.2 Liste d'attributs tabous65
  - 2.4.3 Durée des interdictions66
  - 2.4.4 Critères d'aspiration72
  - 2.5 Direction de la recherche à long terme72
  - 2.5.1 Fréquence72
  - 2.5.2 Obligation d'effectuer des mouvements74
  - 2.6 Convergence de la recherche avec tabous75
  - 2.7 Conclusion75
  - 2.8 Bibliographie commentée76
  - 3 La recherche à voisinages variables77
  - G. Caporossi, P. Hansen
  - 3.1 Introduction77
  - 3.2 Fonctionnement de l'algorithme78
  - 3.2.1 Recherche locale78
  - 3.2.2 Diversification de la recherche81
  - 3.2.3 La recherche à voisinages variables (RVV)84
  - 3.3 Illustration et extensions86
  - 3.3.1 Trouver des graphes extrêmes avec la RVV87
  - 3.3.2 Améliorer k-means94
  - 3.3.3 Adapter la RVV à des problèmes continus97
  - 3.4 Conclusion97
  - 3.5 Bibliographie commentée98
  - 4 Une procédure de recherche itérative en deux phases : la méthode GRASP99
  - M. Vasquez, M. Buljuba(...)i(...)
  - 4.1 Introduction99
  - 4.2 Principe général de la méthode100
  - 4.3 Problèmes de couverture minimale101
  - 4.4 Un premier algorithme102
  - 4.4.1 Phase constructive102
  - 4.4.2 Phase d'amélioration104
  - 4.5 Banc d'essai105
  - 4.6 Expérimentations greedy(alpha)+descente105
  - 4.7 Recherche locale tabou107
  - 4.7.1 Espace de recherche107
  - 4.7.2 Évaluation d'un configuration107
  - 4.7.3 Gestion de la liste tabou107
  - 4.7.4 Voisinage108
  - 4.7.5 Algorithme tabou108
  - 4.8 Expérimentations greedy(alpha)+descente+tabou109
  - 4.9 Expérimentations greedy(1)+tabou111
  - 4.10 Conclusion112
  - 4.11 Bibliographie commentée112
  - 5 Les algorithmes évolutionnaires115
  - A. Pétrowski, S. Ben Hamida
  - 5.1 De la génétique à l'ingénierie115
  - 5.2 L'algorithme évolutionnaire générique117
  - 5.2.1 Opérateurs de sélection117
  - 5.2.2 Opérateurs de variation118
  - 5.2.3 La boucle générationnelle118
  - 5.2.4 Résolution d'un problème simple119
  - 5.3 Opérateurs de sélection121
  - 5.3.1 Pression de sélection121
  - 5.3.2 Dérivé génétique122
  - 5.3.3 Sélection proportionnelle123
  - 5.3.4 Sélection par tournois128
  - 5.3.5 Sélection déterministe129
  - 5.3.6 Sélection environnementale130
  - 5.3.7 Fonction de performance132
  - 5.4 Opérateurs de variation et représentations133
  - 5.4.1 Généralités sur les opérateurs de variation133
  - 5.4.2 Le croisement134
  - 5.4.3 La mutation136
  - 5.5 Représentation binaire137
  - 5.5.1 Croisements137
  - 5.5.2 Mutations138
  - 5.6 Représentations réelle140
  - 5.6.1 Croisements140
  - 5.6.2 Mutations143
  - 5.7 Exemples de représentations discrètes pour les problèmes de permutation148
  - 5.7.1 Représentation ordinale149
  - 5.7.2 Représentation de chemins ou de séquences149
  - 5.8 La représentation arborescente pour la programmation génétique153
  - 5.8.1 Création de la population initiale154
  - 5.8.2 Croisement155
  - 5.8.3 Mutations156
  - 5.8.4 Application à la régression symbolique158
  - 5.9 Cas particulier des algorithmes génétiques160
  - 5.10 Stratégie d'évolution par adaptation de la matrice de covariance162
  - 5.10.1 Présentation de la méthode162
  - 5.10.2 L'algorithme CMA-ES166
  - 5.10.3 Quelques résultats de simulation168
  - 5.11 Conclusion171
  - 5.12 Glossaire172
  - 5.13 Bibliographie commentée173
  - 6 Les fourmis artificielles175
  - N. Monmarché
  - 6.1 Introduction175
  - 6.2 L'intelligence collective des fourmis176
  - 6.2.1 Quelques faits marquants176
  - 6.2.2 La communication chimique chez les fourmis177
  - 6.3 La modélisation du comportement des fourmis179
  - 6.3.1 Définition d'un fourmi artificielle179
  - 6.3.2 Les fourmis sur un graphe179
  - 6.4 L'optimisation combinatoire avec les fourmis181
  - 6.4.1 Le problème du voyageur de commerce181
  - 6.4.2 La métaheuristique ACO183
  - 6.4.3 Convergence des algorithmes du type ACO192
  - 6.4.4 Rapprochements avec les algorithmes évolutionnaires193
  - 6.5 Conclusion196
  - 6.6 Bibliographie commentée197
  - 7 Les essaims particulaires199
  - M. Clerc
  - 7.1 Parce que l'union fait la force199
  - 7.2 Les ingrédients de l'optimisation par essaim particulaire (OEP)200
  - 7.2.1 Les objets200
  - 7.2.2 Les relations201
  - 7.2.3 Les mécanismes203
  - 7.3 Quelques versions d'OEP206
  - 7.3.1 1998. Une version de base206
  - 7.3.2 Deux versions « standard » améliorées208
  - 7.4 Applications et variantes211
  - 7.5 Pour approfondir212
  - 7.6 Annexe213
  - 7.6.1 Un exemple simple213
  - 7.6.2 SPSO 2011 avec corrélations distance-valeur214
  - 7.6.3 Comparaison de trois variantes simples214
  - 7.6.4 De quelques pièges215
  - 7.6.5 De l'importance des générateurs de nombres219
  - 7.7 Glossaire220
  - 7.8 Bibliographie commentée220
  - II Variantes, extensions et conseils méthodologiques223
  - 8 Quelques autres métaheuristiques225
  - I. Boussaïd
  - 8.1 Introduction225
  - 8.2 Systèmes immunitaires artificiels226
  - 8.2.1 Algorithmes de sélection négative228
  - 8.2.2 La sélection clonale229
  - 8.2.3 Réseau immunitaire artificiel231
  - 8.2.4 Algorithmes inspirés de la théorie du danger232
  - 8.3 L'évolution différentielle233
  - 8.3.1 Les schémas de mutation234
  - 8.3.2 Le croisement237
  - 8.4 L'algorithme d'optimisation BFO238
  - 8.4.1 Chimiotaxie239
  - 8.4.2 Essaimage241
  - 8.4.3 Reproduction241
  - 8.4.4 Élimination et dispersion242
  - 8.5 L'algorithme à base de biogéographie242
  - 8.6 Les algorithmes culturels248
  - 8.7 Les algorithmes coévolutionnaires249
  - 8.8 Conclusion250
  - 8.9 Bibliographie commentée250
  - 9 Les autres algorithmes d'insectes sociaux253
  - S. Aupetit, M. Slimane
  - 9.1 Les abeilles253
  - 9.1.1 Le fourragement des abeilles mellifères dans la nature254
  - 9.1.2 Le modèle classique ABC et son implémentation256
  - 9.1.3 Paramétrage et évolution de l'algorithme classique259
  - 9.2 À la recherche de l'harmonie musicale parfaite260
  - 9.2.1 Initialisation de la mémoire261
  - 9.2.2 Improvisation d'un nouvel accord261
  - 9.2.3 Mise à jour de la mémoire avec le nouvel accord263
  - 9.2.4 Paramétrage et évolution de l'algorithme classique264
  - 9.3 L'écholocalisation des micro chauves-souris264
  - 9.3.1 Initialisation265
  - 9.3.2 Déplacement des chauves-souris266
  - 9.3.3 Mise à jour des propriétés d'émission des ultrasons267
  - 9.3.4 Mise à jour de la meilleure solution267
  - 9.3.5 Évolutions268
  - 9.4 La nature est source de beaucoup d'autres inspirations268
  - 9.4.1 Bacterial Foraging Optimization268
  - 9.4.2 Slim Mold Optimization269
  - 9.4.3 Les vers luisants et les lucioles269
  - 9.4.4 Les termites270
  - 9.4.5 Les cafards270
  - 9.4.6 Les moustiques270
  - 9.4.7 Les guêpes270
  - 9.4.8 Les araignées270
  - 9.4.9 Les coucous270
  - 9.5 Conclusion270
  - 9.6 Bibliographie commentée271
  - 10 Extensions des algorithmes évolutionnaires à l'optimisation multimodale et l'optimisation multi-objectif273
  - A. Pétrowski
  - 10.1 Introduction273
  - 10.2 Optimisation multimodale274
  - 10.2.1 Le problème274
  - 10.2.2 Nichage par la méthode du partage274
  - 10.2.3 Nichage par la méthode de surpeuplement déterministe277
  - 10.2.4 Procédure d'éclaircissement279
  - 10.2.5 Spéciation281
  - 10.3 Optimisation multi-objectif283
  - 10.3.1 Formalisation du problème283
  - 10.3.2 Les indicateurs de qualité285
  - 10.3.3 Algorithmes évolutionnaires multi-objectifs288
  - 10.3.4 Méthodes utilisant un « classement de Pareto »288
  - 10.3.5 Méthodes de scalarisation301
  - 10.4 Conclusion311
  - 10.5 Bibliographie commentée311
  - 11 Extensions des algorithmes évolutionnaires à l'optimisation sous contraintes313
  - S. Ben Hamida
  - 11.1 Introduction313
  - 11.2 La pénalisation315
  - 11.2.1 La méthode de la « peine de mort »317
  - 11.2.2 Pénalités statiques317
  - 11.2.3 Pénalités dynamiques318
  - 11.2.4 Pénalités adaptatives319
  - 11.2.5 Pénalités auto-adaptatives322
  - 11.2.6 Segregated Genetic Algorithm (SGGA)324
  - 11.3 Supériorité des individus réalisables325
  - 11.3.1 Méthode de Powell et Skolnick, 1993325
  - 11.3.2 Méthode de Deb, 2000325
  - 11.3.3 Stochastic Ranking326
  - 11.4 Recherche des solutions réalisables327
  - 11.4.1 Réparation des individus irréalisables : Genocop III327
  - 11.4.2 Méthode de la mémoire comportementale329
  - 11.5 Préservation de la faisabilité des solutions329
  - 11.5.1 Le système Genocop329
  - 11.5.2 Recherche sur la frontière de la région réalisable330
  - 11.5.3 Homomorphous mapping331
  - 11.6 Méthodes multi-objectifs332
  - 11.6.1 Méthode de Surry et al.333
  - 11.6.2 Méthode de Kamponogara et Talukdar333
  - 11.6.3 La Méthode IDEA de Singh et al.334
  - 11.7 Méthodes hybrides334
  - 11.8 Conclusion335
  - 11.9 Bibliographie commentée336
  - 12 Techniques de modélisation et comparaisons de méthodes337
  - É.D. Taillard
  - 12.1 Introduction337
  - 12.2 Méthodes de décomposition339
  - 12.2.1 Décomposition en chaîne339
  - 12.2.2 Décomposition en sous-problèmes de petite taille341
  - 12.3 Modélisation du problème345
  - 12.4 Gestion de population et programmation à mémoire adaptative347
  - 12.4.1 Algorithmes évolutionnaires ou mimétiques347
  - 12.4.2 Recherche par dispersion348
  - 12.4.3 Colonies de fourmis349
  - 12.4.4 Construction de vocabulaire349
  - 12.4.5 Chemin de liaison350
  - 12.5 Comparaison d'heuristiques352
  - 12.5.1 Comparaison de taux de succès352
  - 12.5.2 Comparaison de méthodes d'optimisation itérative354
  - 12.6 Conclusions359
  - III Quelques domaines d'application361
  - 13 Techniques d'hybridation à base de métaheuristiques pour optimiser des systèmes logistiques363
  - L. Deroussi, N. Grangeon, S. Norre
  - 13.1 Les systèmes logistiques364
  - 13.1.1 Définitions, généralités364
  - 13.1.2 Importance d'une vision intégrée d'une chaîne logistique365
  - 13.1.3 Difficultés liées à l'optimisation de la performance d'une chaîne logistique366
  - 13.1.4 Système d'information et système d'aide à la décision (Décision Support System)368
  - 13.1.5 Intérêt des métaheuristiques369
  - 13.2 Les techniques hybrides369
  - 13.2.1 Généralités370
  - 13.2.2 L'hybridation Métaheuristiques/Méthode d'optimisation372
  - 13.2.3 L'hybridation Métaheuristique/Méthode d'évaluation des performances374
  - 13.3 Application pour le pilotage de la chaîne logistique376
  - 13.3.1 Préambule376
  - 13.3.2 Planification de la production378
  - 13.3.3 Location routing problem380
  - 13.3.4 Le Multi-Plant Multi-Product Capacitated Lot-Sizing Problem382
  - 13.3.5 Les systèmes flexibles de production384
  - 13.4 Conclusion386
  - 14 Métaheuristiques pour les problèmes de tournées de véhicules387
  - C. Prodhon, C. Prins
  - 14.1 Introduction387
  - 14.2 Les problèmes de tournées de véhicules388
  - 14.2.1 Le problème de base388
  - 14.2.2 Variantes du problème de base390
  - 14.3 Heuristiques simples et recherches locales391
  - 14.3.1 Heuristiques simples391
  - 14.3.2 Recherches locales392
  - 14.4 Métaheuristiques398
  - 14.4.1 Méthodes à parcours398
  - 14.4.2 Méthodes à population ou à agents400
  - 14.4.3 Évolution et tendances402
  - 14.5 Approche Split403
  - 14.5.1 Principe et intérêt403
  - 14.5.2 Algorithme Split405
  - 14.5.3 Intégration dans des heuristiques et métaheuristiques407
  - 14.6 Exemple de métaheuristique avec l'approche Split408
  - 14.6.1 Principe général d'un GRASPxELS408
  - 14.6.2 Application au problème de tournées de véhicules409
  - 14.7 Conclusion411
  - 14.8 Bibliographie commentée411
  - 15 Applications en gestion du trafic aérien413
  - N. Durand, D. Gianazza, J.B. Gotteland, C. Vanaret, J.M. Alliot
  - 15.1 Introduction413
  - 15.2 Optimisation des routes aériennes415
  - 15.2.1 Placement des noeuds et des arêtes par algorithmes géométriques416
  - 15.2.2 Placement des noeuds, à topologie fixée, par recuit simulé ou essaim particulaire419
  - 15.2.3 Placement en 2D de « tubes aériens », par clustering et algorithme génétique421
  - 15.2.4 Tubes-3D séparés, par algorithme évolutionnaire et A*422
  - 15.3 Optimisation de l'espace aérien426
  - 15.3.1 Sectorisation de l'espace427
  - 15.3.2 Définition de blocs fonctionnels d'espace429
  - 15.3.3 Prévision des regroupements de secteurs aériens433
  - 15.4 Optimisation des créneaux de décollage440
  - 15.5 Optimisation du trafic aéroportuaire441
  - 15.5.1 Optimisation des affectations de parking442
  - 15.5.2 Optimisation des séquences d'avions sur les pistes442
  - 15.5.3 Optimisation du roulage445
  - 15.5.4 Vers une planification globale des mouvements au sol447
  - 15.6 Résolution de conflits aériens449
  - 15.6.1 Résolution par colonies de fourmis451
  - 15.6.2 Des approches Free-Flight451
  - 15.6.3 Vers une comparaison des approches453
  - 15.7 Conclusion454
  - 15.8 Bibliographie commentée455
  - 15.8.1 Références générales455
  - 15.8.2 Optimisation de l'espace aérien455
  - 15.8.3 Optimisation des routes aériennes456
  - 15.8.4 Optimisation des créneaux de décollage457
  - 15.8.5 Optimisation du trafic aéroportuaire458
  - 15.8.6 Résolution de conflits aériens459
  - Conclusion461
  - Bibliographie463
  - Index511
Origine de la notice:
- Electre