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

Dumitru Popescu, Pierre Borne, Dan Stefanoiu, Florin-Gheorghe Filip, Abdel El Kamel

Description

Optimisation en sciences de l’ingénieur présente les méthodes d’optimisation utilisées dans les domaines de la programmation évolutionnaire, des problèmes à critère stochastique et de la décision assistée par ordinateur. Dans le cas des problèmes incertains ou mal définis, éventuellement soumis à des perturbations aléatoires ou pour lesquels la recherche de solution risque de tomber sur l’explosion combinatoire, les méthodes exactes s’avèrent le plus souvent inexploitables dans un temps raisonnable. Les algorithmes décrits dans ce volume permettent de résoudre les problèmes rapidement. Illustré d’exemples sur les méthodes proposées, cet ouvrage précise également les champs d’applications possibles des algorithmes concernés.

Avant-propos

Chapitre 1. Métaheuristiques – Méthodes locales

1.1. Contexte général

1.2. Principe de Monte-Carlo

1.3. Ascension de la montagne

1.4. Recherche Tabou

1.5. Recuit simulé

1.6. Tunneling

1.7. Méthode GRASP

Chapitre 2. Métaheuristiques – Méthodes globales

2.1. Principe des métaheuristiques évolutionnaires (à stratégie d’évolution)

2.2. Algorithmes génétiques

2.3. Ascension de la montagne par stratégies d’évolution

2.4. Optimisation par colonie de fourmis

2.5. Optimisation par essaims particulaires

2.6. Optimisation par recherche harmonique

Chapitre 3. Optimisation stochastique

3.1. Introduction

3.2. Problème d’optimisation stochastique

3.3. Calcul de la fonction de répartition pour une variable aléatoire

3.4. Critères statistiques d’optimalité

3.5. Exemples de calcul

3.6. Optimisation stochastique par la théorie des jeux

Chapitre 4. Problèmes multicritères

4.1. Introduction

4.2. Trois problèmes

4.3. Deux sous-classes de problèmes

4.4. Méthodes de résolution

4.5. Optimisation simultanée pour le contrôle et la conduite des systèmes

4.6. Notes et commentaires

Chapitre 5. Méthodes et outils pour l’aide à la décision

5.1. Introduction

5.2. Exemples introductifs

5.3. Décisions et activités de décision – Concepts de base

5.4. Analyse des décisions

5.5. Notes et commentaires

Chapitre 6. Simulations pour l’aide à la décision

6.1. Problème de décision en environnement incertain

6.2. Position du problème

6.3. Principe de la simulation

6.4. Etudes de cas

Annexe 1. Générer des nombres pseudo-aléatoires

à distribution uniforme

Annexe 2. Générer des nombres pseudo-aléatoires à distribution souhaitée

Liste des algorithmes

Sujets

• Sciences & Techniques
• Mathématiques
• Sciences formelles
• Mathématiques générales
• Mathématiques générales
• Techniques
• Ingénieurie et sciences appliquées
• Ingénieurie et sciences appliquées
• Sciences appliquées
• Ingénierie
• Sciences appliquées
• Sciences appliquées
• Ingénierie
• Science
• Science formelle
• Statistiques
• Mathematics
• Statistics
• Sciences et techniques
• Sciences fondamentales
• Sciences
• Mathématiques pures
• Mathématiques fondamentales

Informations

• Publié par: lavoisier
• Date de parution: 23 mai 2014
• Nombre de lectures: 65
• EAN13: 9782746289277
• Licence : Tous droits réservés
• Langue: Français
• Poids de l'ouvrage: 4 Mo

Extrait

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 .................