Optimisation en sciences de l’ingénieur : Métaheuristiques, méthodes stochastiques et aide à la décision , livre ebook

Optimisation en sciences de l’ingénieur











































© 2014, Lavoisier, Paris
www.editions.lavoisier.fr

ISBN 978-2-7462-3927-2
ISSN 2261-1088


Le Code de la propriété intellectuelle n’autorisant, aux termes de l’article L. 122-5, d’une
part, que les "copies ou reproductions strictement réservées à l’usage privé du copiste et non
destinées à une utilisation collective" et, d’autre part, que les analyses et les courtes citations
dans un but d’exemple et d’illustration, "toute représentation ou reproduction intégrale, ou
partielle, faite sans le consentement de l’auteur ou de ses ayants droit ou ayants cause, est
illicite" (article L. 122-4). Cette représentation ou reproduction, par quelque procédé que ce
soit, constituerait donc une contrefaçon sanctionnée par les articles L. 335-2 et suivants du
Code de la propriété intellectuelle.
Tous les noms de sociétés ou de produits cités dans cet ouvrage sont utilisés à des fins
d’identification et sont des marques de leurs détenteurs respectifs.





Optimisation en sciences

de l’ingénieur




métaheuristiques, méthodes stochastiques
et aide à la décision







Dan Stefanoiu
Pierre Borne

Dumitru Popescu
Florin-Gheorghe Filip

Abdelkader El Kamel





Série Systèmes automatisés
sous la direction de BERNARD DUBUISSON



Slim Hammadi et Mekki Ksouri, Gestion et optimisation des systèmes de transport
multimodaux, 2013
Pierre Borne et al., Optimisation en sciences de l’ingénieur, 2012
Slim Hammadi et Mekki Ksouri, Ingénierie du transport et des services de mobilité
avancés, 2012 Table des matières
Avant-propos ....................................... 11
Chapitre 1. Métaheuristiques – Méthodes locales ................ 13
1.1. Contexte général ................................. 13
1.2. Principe de Monte-Carlo ............................ 17
1.3. Ascension de la montagne ........................... 23
1.4. Recherche Tabou ................................ 30
1.4.1. Principe ................................... 30
1.4.2. Algorithme glouton31
1.4.3. Méthode de recherche Tabou ...................... 33
1.4.4. Liste Tabou ................................ 35
1.4.5. Algorithme de la recherche Tabou ................... 36
1.4.6. Intensification et diversification .................... 40
1.4.7. Exemples d’application ......................... 41
1.4.7.1. Recherche de la valeur la plus faible d’un tableau ...... 41
1.4.7.2. Problème des N reines ...................... 44
1.5. Recuit simulé48
1.5.1. Principe du recuit thermique48
1.5.2. Modèle de Kirkpatrick du recuit thermique.............. 49
1.5.3. Algorithme du recuit simulé....................... 51
1.6. Tunneling ..................................... 54
1.6.1. Principe du Tunneling .......................... 54
1.6.2. Types de Tunneling............................ 55
1.6.2.1. Tunneling stochastique ...................... 55
1.6.2.2. Tunneling par ajout des pénalités ................ 56
1.6.3. Algorithme de Tunneling ........................ 56
1.7. Méthode GRASP ................................ 58






















6 Optimisation en sciences de l’ingénieur
Chapitre 2. Métaheuristiques – Méthodes globales ............... 61
2.1. Principe des métaheuristiques évolutionnaires
(à stratégie d’évolution) ............................... 61
2.2. Algorithmes génétiques............................. 62
2.2.1. Bréviaire biologique ........................... 62
2.2.2. Caractéristiques des algorithmes génétiques ............. 64
2.2.2.1. Opérations génétiques ....................... 65
2.2.2.2. Viabilisation des héritiers ..................... 69
2.2.2.3. Sélection pour la reproduction .................. 70
2.2.2.4. Sélection pour la survie ...................... 78
2.2.3. Structure générale d’un algorithme génétique ............ 79
2.2.4. Sur la convergence des algorithmes génétiques ........... 82
2.2.5. Comment implémenter un algorithme génétique .......... 88
2.3. Ascension de la montagne par stratégies d’évolution103
2.3.1. Ascension en empruntant la rampe la plus accentuée ........ 104
2.3.2. Ascension en empruntant la rampe suivante ............. 106
2.3.3. Ascension en groupe ........................... 108
2.4. Optimisation par colonie de fourmis ..................... 109
2.4.1. Colonies de fourmis109
2.4.1.1. Fourmis réelles109
2.4.1.2. Aspects inspirés des fourmis réelles............... 110
2.4.1.3. Caractéristiques développées
chez les fourmis artificielles ........................ 111
2.4.2. Algorithme de base d’optimisation par colonie de fourmis .... 112
2.4.3. Mise à jour des traces de phéromone ................. 119
2.4.3.1. Mise à jour retardée adaptative.................. 120
2.4.3.2. Mise à jour en ligne121
2.4.3.3. Mise à jour par stratégie élitiste 121
2.4.3.4. Mise à jour selon le rang des fourmis .............. 122
2.4.4. Algorithme systémique de la colonie de fourmis .......... 123
2.4.5. Exemple du voyageur de commerce .................. 128
2.5. Optimisation par essaims particulaires .................... 132
2.5.1. Métaheuristique de base ......................... 132
2.5.1.1. Principe ............................... 132
2.5.1.2. Modèle dynamique des particules ................ 134
2.5.1.3. Choix des informatrices ...................... 139
2.5.2. Algorithme standard d’optimisation par essaims particulaires.... 140
2.5.3. Algorithme adaptatif d’optimisation par essaims particulaires,
à stratégie d’évolution .............................. 144
2.5.4. Algorithme des lucioles ......................... 159
2.5.4.1. Principe ............................... 159
































Table des matières 7
2.5.4.2. Modèle dynamique des lucioles ................. 160
2.5.4.3. Algorithme standard des lucioles ................ 164
2.5.5. Algorithme des chauves-souris ..................... 168
2.5.5.1. Principe ............................... 168
2.5.5.2. Modèle dynamique des chauves-souris ............. 169
2.5.5.3. Algorithme standard des chauves-souris ............ 172
2.5.6. Algorithme des abeilles ......................... 177
2.5.6.1. Principe177
2.5.6.2. Modèle dynamique et coopératif des abeilles ......... 178
2.5.6.3. Algorithme standard des abeilles ................ 184
2.5.7. Prédiction optimale multivariable par essaims particulaires .... 189
2.6. Optimisation par recherche harmonique ................... 201
2.6.1. Composition musicale et optimisation................. 201
2.6.2. Modèle de la recherche harmonique .................. 202
2.6.3. Algorithme standard de la recherche harmonique .......... 205
2.6.4. Exemple d’application .......................... 208
Chapitre 3. Optimisation stochastique ....................... 211
3.1. Introduction.................................... 211
3.2. Problème d’optimisation stochastique .................... 213
3.3. Calcul de la fonction de répartition pour une variable aléatoire ..... 214
3.4. Critères statistiques d’optimalité ....................... 221
3.4.1. Cas des solutions totalement admissibles ............... 221
3.4.2. Cas des solutions partiellement admissibles ............. 225
3.5. Exemples de calcul ............................... 230
3.5.1. Exemple 1 ................................. 230
3.5.2. Exemple 2231
3.5.3. Exemple 3233
3.6. Optimisation stochastique par la théorie des jeux ............. 235
3.6.1. Principe ................................... 235
3.6.2. Stratégie de Wald (maximin) ...................... 237
3.6.3. Stratégie de Hurwicz ........................... 238
3.6.4. Stratégie de Laplace238
3.6.5. Stratégie de Bayes-Laplace ....................... 239
3.6.6. Stratégie de Savage ............................ 240
3.6.7. Exemple .................................. 240
Chapitre 4. Problèmes multicritères ......................... 243
4.1. Introduction.................................... 243
4.2. Trois problèmes ................................. 245































8 Optimisation en sciences de l’ingénieur
4.2.1. Choix du premier emploi ........................ 245
4.2.2. Sélection d’un outil informatique ................... 246
4.2.3. Planification d’une raffinerie ...................... 246
4.3. Deux sous-classes de problèmes ....................... 247
4.3.1. Deux sous-catégories de problèmes .................. 247
4.3.1.1. Sous-classe des problèmes multi-attributs (PMA) ...... 247
4.3.1.2. Souselèmes multi-objectifs (PMO) 249
4.3.2. Dominance et optimalité de Pareto................... 251
4.4. Méthodes de résolution ............................. 254
4.4.1. Classifications ............................... 255
4.4.2. Méthodes basées sur la substitution des fonctions-objectifs .... 256
4.4.2.1. Définition de la contrainte .................... 256
4.4.2.2. But programmé ........................... 256
4.4.2.3. Résolution progressive ...................... 258
4.4.3. Méthodes basées sur l’agrégation ................... 258
4.4.3.1. Définition .............................. 259
4.4.3.2. Méthode de la sommation pondérée............... 260
4.4.3.3. Méthodes basées sur la distance ................. 264
4.4.3.4. Agrégation des valeurs ordinales ; méthode de Borda .... 266
4.4.4. Autres méthodes269
4.4.4.1. Méthodes basées sur la théorie des jeux
pour les situations incertaines ....................... 269
4.4.4.2. Méthodes basées sur la comparaison de paires ........ 273
4.5. Optimisation simultanée pour le contrôle et la conduite
des systèmes .................