398 pages
Français

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

-

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

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.


Sujets

Informations

Publié par
Date de parution 22 mai 2014
Nombre de lectures 54
EAN13 9782746289277
Langue Français
Poids de l'ouvrage 4 Mo

Informations légales : prix de location à la page 0,0000€. Cette information est donnée uniquement à titre indicatif conformément à la législation en vigueur.

Exrait








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 ...................................... 277
4.5.1. Agrégation des étapes d’optimisation d’identification
et de conception de la commande d’un système dynamique........ 277
4.5.2. Agrégation des étapes d’identification et d’optimisation
pour la conduite des procédés ......................... 286
4.5.2.1. Approche par pondération paramétrique ............ 288
4.5.2.2. Approche par technique de partition .............. 289
4.5.2.3. Approche par l’algorithme du minimax289
4.6. Notes et commentaires ............................. 290
Chapitre 5. Méthodes et outils pour l’aide à la décision ............ 293
5.1. Introduction.................................... 293
5.2. Exemples introductifs.............................. 294
5.2.1. Choix d’un emploi, le cas probabiliste ................ 294
5.2.2. Démarrage d’une entreprise ....................... 294
5.2.3. Sélection d’un ingénieur informaticien ................ 295
























Table des matières 9
5.2.4. Quelques remarques ........................... 296
5.3. Décisions et activités de décision – Concepts de base........... 296
5.3.1. Définition.................................. 296
5.3.2. Approches ................................. 298
5.4. Analyse des décisions.............................. 299
5.4.1. Pré-analyse : préparation du choix ................... 299
5.4.1.1. Définition des objectifs ...................... 300
5.4.1.2. Evaluation de l’importance des objectifs ............ 303
5.4.1.3. Spécification des solutions possibles .............. 305
5.4.1.4. Tableau des conséquences .................... 307
5.4.1.5. Fonctions de valeur unidimensionnelles310
5.4.2. Faire le choix : méthodes de structuration et résolution ...... 312
5.4.2.1. Outils graphiques pour la structuration
des problèmes de décision ......................... 312
5.4.2.2. Méthode de pondération des objectifs – Cas probabiliste ... 317
5.4.2.3. Le cas d’interaction des critères ................. 320
5.5. Notes et commentaires ............................. 326
Chapitre 6. Simulations pour l’aide à la décision ................. 329
6.1. Problème de décision en environnement incertain ............. 329
6.2. Position du problème .............................. 330
6.3. Principe de la simulation ............................ 331
6.4. Etudes de cas ................................... 335
6.4.1. Gestion de stock.............................. 336
6.4.2. Appel d’offres ............................... 340
6.4.3. File d’attente ou ATM .......................... 343
Annexe 1. Générer des nombres pseudo-aléatoires
à distribution uniforme ................................. 349
Annexe 2. Générer des nombres pseudo-aléatoires
à distribution souhaitée355
Liste des algorithmes .................................. 369
























10 Optimisation en sciences de l’ingénieur
Liste des figures ..................................... 371
Liste des tableaux .................................... 375
Liste des acronymes ................................... 377
Bibliographie ....................................... 379
Index ............................................ 393

Avant-propos
Ce livre, conçu dans le cadre du projet européen ERRIC et réalisé en coopération
entre enseignants chercheurs de France et de Roumanie, complète la présentation
des techniques d’optimisation au service des ingénieurs et des décideurs du volume :
Optimisation en sciences de l’ingénieur – Méthodes exactes. Dans le premier
volume étaient présentées les méthodes d’optimisation exactes les plus utilisées.
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 en un temps acceptable.
Les méthodes présentées dans ce volume permettent de trouver, si ce n’est
la solution optimale d’un problème, du moins une bonne solution en un temps
raisonnable.
Les méthodes présentées ici sont :
– les métaheuristiques : approches locales (telles que le recuit simulé et la
méthode Tabou) et approches globales (telles que les algorithmes à stratégie
d’évolution, les colonies de fourmis, les essaims particulaires, etc.). Ces méthodes
sont principalement basées sur la nature ;
– les approches stochastiques, prenant en compte les incertitudes d’origines
diverses et incluant certains aspects de la théorie des jeux ;
– l’optimisation multicritères ;
12 Optimisation en sciences de l’ingénieur
– les méthodes et techniques d’aide à la décision, incluant également certains
aspects de la théorie des jeux et pour lesquelles de nombreuses références à des
logiciels existants sont proposées ;
 l’utilisation de la simulation pour l’aide à la décision.
Tout au long de l’ouvrage sont présentés divers exemples d’illustration des
méthodes proposées, et les champs d’applications possibles des algorithmes concernés
sont indiqués.
Cet ouvrage a été élaboré avec le support du projet européen FP7 ERRIC
(Empowering Romanian Research on Intelligent Information Technology), contrat
FP7-REGPOT-2010-1/264207.
Les auteurs
Bucarest et Lille
Mars 2014 Chapitre 1
Métaheuristiques – Méthodes locales
1.1. Contexte général
L’optimisation heuristique tire son nom de la langue grecque antique, où
heuriskein ( ευ ρισκειν) signifie « découvrir », « apprendre ». Le sens plus profond de
ce mot est bien illustré par l’exemple suivant. Supposons que les lecteurs de ce livre
soient invités à trouver et à indiquer (à l’aide d’un marqueur) la position de chacun
des mots métaheuristique ou métaheuristiques dans tout le texte. La manière dont on
fait la recherche dépend de la manière d’agir de chacun d’entre nous. Mais, en gros,
deux types de lecteurs peuvent être distingués : le lecteur qui lit tout le texte d’une
manière systématique, en tâchant ne pas sauter le moindre mot et le lecteur qui lit le
texte « en diagonale », avec l’appui des capacités visuelles humaines de
reconnaissances des formes, sans bien regarder tous les mots. Le premier lecteur effectue une
recherche exhaustive (en agissant plutôt d’une manière similaire à l’ordinateur),
alors que le deuxième applique une méthode heuristique de recherche (en agissant
plutôt d’une manière similaire à une entité vivante, pas nécessairement ayant une
conscience). Bien entendu, le temps alloué à la recherche est nettement plus long
pour le premier lecteur que pour le deuxième. Néanmoins, très probablement, le
premier lecteur aurait trouvé la plupart des mots (avec peu de ratés), tandis que
le deuxième pourrait manquer davantage d’occurrences. Mais, si l’on compare
les performances finales, on constate que la différence, en termes de nombre
d’occurrences trouvées, n’est pas si grande entre les deux lecteurs, bien que le temps
de la recherche soit sensiblement plus réduit pour le deuxième.
14 Optimisation en sciences de l’ingénieur

Les deux premiers chapitres de ce livre sont consacrés à la description d’une
collection de méthodes d’optimisation à la façon d’agir du deuxième type de lecteurs
et très proche du comportement des systèmes biologiques ou de l’évolution
de certains phénomènes naturels. Plus précisément, on va analyser une classe de
problèmes d’optimisation particulièrement importante pour les sciences de l’ingénieur,
de type granulaire. Ce terme est expliqué dans la suite.
Le problème d’optimisation concerné se pose dans le contexte d’une fonction
coût (ou critère) définie comme suit :
f :S→  [1.1]
nxoù l’espace de recherche S est, usuellement, un sous-ensemble borné de  . Ce
qui rend le critère f particulier est, d’une part, sa variation plutôt fractale, avec
beaucoup de ruptures (et donc d’extrema locaux) et, d’autre part, l’impossibilité de
lui calculer les dérivées d’une manière analytique (pourvuqu’elles existent). En
termes de régularité, en général, le critère f est localement continu ou dérivable par
portions. (Très rarement, il est lissé, mais ce cas peut être également considéré, il
n’est pas exclu.) Néanmoins, le critère f est calculable en n’importe quel point x
de l’espace de recherche S , selon une expression bien connue à l’avance. Alors,
pour résoudre le problème d’optimisation :
opt f [1.2]
x∈S
optqui signifie trouver l’optimum global de et le point d’optimum, on peutf x ∈S
s’appuyer seulement sur la comparaison entre différentes valeurs du critère,
calculées pour des points de l’espace de recherche. Puisque la stratégie de recherche
doit aboutir après une durée raisonnable, il est bien évident que seulement un
sousensemble discret et fini de S , soit D , peut être utilisé dans ce but. Afin de
minimiser la possibilité de rater l’optimum global, le sous-ensemble D possède,
usuellement, un nombre très grand de valeurs à tester.
Le problème [1.2] est alors relaxé, en le remplaçant par le problème suivant :
opt f [1.3]
x∈⊂DS
Métaheuristiques – Méthodes locales 15

où, soulignons-le encore une fois, D est discret et fini. Vu leur grand nombre,
les points de D à tester pour résoudre le problème [1.3] s’appellent granules.
Par conséquent, [1.3], lui-même, devient un problème granulaire d’optimisation.
(Parfois, le critère f est nommé fitness.) Résoudre le problème [1.3] revient alors à
localiser le granule le plus proche du point de l’optimum global de f .
Un autre exemple peut illustrer le principe de la granulation. Essayons de
traduire le dicton suivant, attribué à un célèbre physicien et mathématicien du
monde grec antique, Archimède : « E ν αρχεοσ ο αρητμοσ. » (/En arheos o
aritmos./) On cherche la traduction la plus fidèle que l’on puisse réaliser. Bien
entendu, cette fois-ci, la fonction de concordance est naturelle et concerne la
correspondance entre la langue grecque antique et la langue moderne dans laquelle
on souhaite faire comprendre le dicton (soit le français). L’espace de recherche S
est un dictionnaire avec beaucoup de mots (quelques dizaines de milliers). Il est,
donc, granulaire par nature (les granules étant les mots à traduire). Afin de résoudre
notre problème, il faut d’abord isoler le « sous-dictionnaire » D , formé par tous les
mots du dictionnaire S qui débutent avec α (/a/), ε (/e/) et ο (/o/). Ensuite, il faut
établir une stratégie de recherche efficace. Vérifier tous les mots de D est
impensable, car il a encore une taille assez grande. Mais, selon une stratégie de type
heuristique, la taille du sous-dictionnaire D peut être réduite au fur et à mesure
que l’on prend en compte les lettres successives des mots composant le dicton.
Finalement, D n’inclut que les mots à traduire et on retrouve une première
traduction brute des mots : dans, ancien/antique, est/était, nombre. Un raffinement
est nécessaire, afin de trouver le bon sens du dicton. Pour ce faire, un deuxième
problème d’optimisation peut se formuler, mais cette fois-ci, l’espace de recherche
est formé par des synonymes des mots déjà trouvés et des expressions usuelles
formées par des combinaisons de tous ces mots. Puisque l’espace de recherche est
assez petit, on peut maintenant faire appel à une stratégie exhaustive de recherche.
On arrive ainsi à la forme la plus concordante avec l’esprit du dicton : Au début était
le nombre.
Les méthodes pour résoudre les problèmes granulaires d’optimisation doivent
mener à des algorithmes numériques implantables sur ordinateur, sinon leur utilité
serait bien réduite pour les sciences de l’ingénieur. Les stratégies décrites dans
l’exemple précédent sont faciles à suivre par un être humain, mais l’ordinateur a
besoin de quelques astuces informatiques pour qu’il puisse « raisonner » d’une
manière similaire. Premièrement, les mots du dictionnaire initial S sont déposés à


16 Optimisation en sciences de l’ingénieur

des adresses de mémoire codifiées à partir des valeurs ASCII de leurs lettres (S
devenant ainsi un dictionnaire électronique). On évite ainsi la recherche exhaustive
(c’est-à-dire consistant à parcourir toutes les adresses du dictionnaire électronique
jusqu’à ce que le mot recherché soit trouvé). Deuxièmement, un système expert
d’expressions usuelles de la langue moderne doit être conçu et implémenté. Là,
aussi, les adresses mémoire doivent être générées de façon à éviter, si possible, la
recherche exhaustive. Troisièmement, pour augmenter la vitesse de recherche, une
statistique des mots les plus utilisés doit être prise en compte dans la création du
dictionnaire électronique. Les traducteurs linguistiques automatiques modernes sont
basés sur le principe des stratégies heuristiques que l’on vient d’énoncer.
En revenant au problème [1.3], l’objectif principal est de concevoir des méthodes
de résolution, de façon à ce que la recherche exhaustive soit évitée ou, tout au
plus, utilisée comme dernière étape sur un sous-ensemble de recherche restreint. En
même temps, on exige que ces méthodes mènent à des algorithmes implantables sur
ordinateur. Bien entendu, en renonçant à la recherche exhaustive, on ne peut plus
garantir que l’optimum global sera trouvé, mais on exige que la durée de la
recherche soit fortement réduite, pour une précision acceptable du résultat. Les
méthodes pour lesquelles le compromis durée-précision peut être contrôlé par
l’utilisateur sont préférées, bien que leur complexité soit assez élevée. (On va
en décrire quelques-unes dans ce volume.) Pour les autres méthodes (en général,
moins complexes), c’est à l’utilisateur de juger l’opportunité de les utiliser dans ses
applications.
Les méthodes heuristiques implantables sur ordinateur s’appellent métaheuristiques.
Leur principe de base est de rechercher la solution par simulation d’un certain
comportement de système biologique ou d’évolution de phénomène naturel, qui
inclut un mécanisme d’optimalité intrinsèque. Pour cette raison, une nouvelle
branche du domaine des optimisations s’est développée dans les vingt dernières
années : la programmation évolutionnaire. Elle concerne les algorithmes numériques
conçus à partir de métaheuristiques.
En général, les métaheuristiques sont basées sur un mécanisme de sélection
pseudo-aléatoire des valeurs de certains paramètres ou opérations qui contribuent à
l’estimation de la solution optimale. Pour cette raison, les algorithmes pour générer
des séquences (de nombres) pseudo-aléatoires (SPA) sont extrêmement importants
dans la conception des métaheuristiques. Quand on parle de nombres pseudo-aléatoires,


Métaheuristiques – Méthodes locales 17

il faut toujours les associer à une densité de probabilité. Pour les métaheuristiques,
en général, deux types de densités de probabilité sont utilisés : uniforme et normale
(gaussienne). On travaille donc avec :
– des générateurs de séquences pseudo-aléatoires uniformément distribuées
(GSPA-U) ;
− des générateurs de séquences pseudo-aléatoires à distribution de probabilité
souhaitée ou prescrite (GSPA-P).
Dans les annexes 1 et 2 de ce volume, des algorithmes pour chacun des deux
types de générateurs sont décrits. Ils sont à la fois simples et efficaces, bien que
d’autres algorithmes, encore plus sophistiqués, soient utilisés dans les applications.
L’intervention des nombres pseudo-aléatoires dans les métaheuristiques rend
impossible la formulation de tout résultat de convergence qui puisse être démontré
par des moyens mathématiques, rigoureux. Tout ce que l’on peut faire est d’énoncer
des conjectures de convergence pour les métaheuristiques qui semblent n’échouer
que dans peu de cas. Si le mécanisme d’optimalité naturel est bien simulé, alors
il existe une forte chance que la métaheuristique correspondante converge vers
l’optimum dans la plupart des applications.
Dans ce volume, deux catégories de métaheuristiques sont décrites : locales et
globales. Pour les méthodes locales, on présume que, soit le critère à optimiser
possède un optimum unique, soit la recherche est arrivée dans le voisinage de
l’optimum global et on doit juste l’approcher. Le but des méthodes globales est
plus large : on essaye de trouver l’optimum global (ou, au moins, une bonne
approximation de celui-ci) par une recherche dans plusieurs zones de l’espace S .
Usuellement, la recherche s’effectue selon un scénario qui peut changer soudainement
de zone (à l’aide des SPA), afin d’éviter l’attraction exercée par les optimums
locaux.
1.2. Principe de Monte-Carlo
Une des premières méthodes en lien avec la granularité des problèmes
numériques (non seulement d’optimisation) s’appelle méthode de Monte-Carlo. Elle a été
proposée par le physicien Stanislaw Ulam, à la fin des années 1940 [MET 49], après
avoir essayé, sans succès, de construire un modèle analytique viable du jeu de cartes
« Solitaire » (en lien avec un modèle analytique du noyau des atomes). Il a constaté

18 Optimisation en sciences de l’ingénieur

qu’il vaut mieux observer les résultats du jeu pendant mille essais et construire une
statistique approximative associée, qu’écrire les équations de cette (extrêmement
compliquée) statistique. Son idée a été rapidement comprise par John von Neumann,
qui travaillait déjà à des projets secrets similaires pour l’armée. Pour cette raison, les
deux chercheurs ont choisi un nom de code pour la méthode, qui soit proche des
jeux de fortune et donc des casinos : Monte-Carlo [ECK 87]. (En fait, le nom a été
proposé par John von Neumann, après avoir appris la passion pour les casinos de
Monte-Carlo d’un oncle de Sanislaw Ulam.)
L’idée de cette méthode est à la fois simple et empirique. Si l’on souhaite avoir
une description numérique d’un système ou phénomène avec beaucoup d’entrées,
difficile à gérer (voire à déterminer), alors il vaut mieux stimuler cette entité avec un
nombre suffisamment grand de valeurs aléatoires et interpréter après les résultats
selon des règles assez simples. Le fait que le résultat est souvent très bien
approximé, dérive du théorème des grands nombres, combiné avec des hypothèses
ergodiques et le théorème « limite centrale de la statistique ». L’unique condition est
de formuler le problème à résoudre de telle manière que le principe de la méthode
puisse être mis en œuvre.
L’exemple suivant illustre assez bien comment la méthode fonctionne. Supposons
que l’on doive trouver une bonne approximation du nombre de Pythagore π. Alors,
au lieu d’utiliser une série de Taylor dans ce but (ce qui constituerait une manière
rigoureuse d’approximation), on va utiliser une propriété géométrique très simple.
Puisque le carré de côté unitaire inclut un quart de disque de rayon unitaire et le
rapport de leurs superficies est égal à 4/ π, il suffit d’approximer ce rapport, sans
mesurer effectivement les superficies. La méthode de Monte-Carlo propose d’abord
de remplir le carré avec N points aléatoirement générés, mais avec une distribution
uniforme et de compter ensuite combien de points se trouvent à l’intérieur du disque
n. (Les points sur le cercle unitaire peuvent être partagés en deux entre le carré et le
disque.) Il en résulte que :
n
π≅ 4 [1.4]
N
Plus N est grand, plus l’approximation est précise. Le résultat est illustré par les
images successives de la figure 1.1. On commence avec 3 000 points et on ajoute
successivement des points, jusqu’à l’obtention de la précision désirée de
l’approximation. Pour 30 000 points, π≅ 3,1436 . Métaheuristiques – Méthodes locales 19

π≅ 3,16667 π≅ 3,11467 π≅ 3,14633
3 000 6 000 12 000

π≅ 3,14756 π≅31, 445 π≅31, 436
18 000 24 000 30 000

Figure 1.1. Calcul empirique du nombre de Pythagore par la méthode Monte-Carlo
La réussite de la méthode est fortement influencée par la distribution de
probabilité des points générés. Si elle n’est pas uniforme, l’erreur s’accroît
rapidement. Les entrées constituent les points générés, qui, en fait, effectuent un
échantillonnage des deux surfaces. Non seulement le système possède ici une
infinité d’entrées, mais, en plus, il ne permet pas de compter ces entrées (car elles
sont continûment réparties sur la surface du carré).
La règle de calcul est tout simplement basée sur la décision d’appartenance ou
non au disque, ce qui implique un test numérique facile à implémenter (calculer la
distance de chaque point par rapport à l’origine et la comparer avec l’unité). En
général, les problèmes à résoudre par la méthode de Monte-Carlo doivent avoir des
expressions de calcul assez simples, sinon la précision souhaitée ne peut être atteinte
qu’après une durée très longue (car, pour chaque entrée stochastique, une quantité
doit être calculée). Même dans cet exemple simple, l’effort de calcul est important.
Mais, occuper beaucoup de ressources de calcul constitue une caractéristique
générale acceptée de la méthode de Monte-Carlo (qui est, en fait, une méthode
« gloutonne »).
20 Optimisation en sciences de l’ingénieur

En regardant les images de la figure 1.1, on voit bien le rapport avec le concept
de granularité (les points générés sont comme des granules d’une substance
quelconque versés sur la surface du carré). Donc, dans le contexte de la méthode de
Monte-Carlo, trouver une bonne approximation du nombre π constitue un problème
granulaire de calcul (pas forcément d’optimisation).
La méthode a été fréquemment utilisée pour calculer les superficies ou les
volumes de formes géométriques assez compliquées. Plus précisément, la méthode
est employée pour évaluer des intégrales multiples comme :
f()xxd [1.5] 
D
où la fonction f a, usuellement, une expression assez simple, tandis que la frontière
nxdu domaine d’intégration est décrite par des équations très compliquées, D⊂ 
voire implicites. Il est plus facile à vérifier si le système d’équations accepte ou non
un certain point comme solution que de trouver toutes ses solutions. Ceci est le cœur
du principe de la méthode de Monte-Carlo.
L’intégrale [1.5] se calcule en appliquant la technique des granules :
nx+11) on formule le problème de calcul dans l’espace  , où f génère une
hypersurface qui se dresse au-dessus du domaine D . L’intégrale est pratiquement le
volume du solide délimité par D et l’hyper-surface ; V f
2) ce solide peut être inclus dans un hyper-cylindre qui a pour base un
hyperdisque contenant D , mais d’une hauteur inconnue, pour l’instant ;
3) des granules uniformément distribués sont versés sur l’hyper-disque ;
4) pour chaque granule, l’appartenance au domaine D est vérifiée ;
5) pour les granules de D , on calcule les valeurs de f, et on détermine ainsi les
extrema de l’hyper-surface (les valeurs minimum et maximum de f) ;
6) on établit la hauteur de l’hyper-cylindre, telle que l’hyper-surface y soit
incluse et que le domaine D fasse partie sa base ;
7) on calcule le volume de l’hyper-cylindre V ;
hc
8) la couche de granules déjà formée est multipliée uniformément à différentes
hauteurs pour remplir tout l’hyper-cylindre. On connaît ainsi tous les granules

Métaheuristiques – Méthodes locales 21

dont les projections tombent dans D . Ces granules font aussi partie du solide, à
condition que leur hauteur reste entre 0 et les valeurs de f (déjà calculées) ;
9) on compte les granules que le solide contient (par comparaison entre leurs
hauteurs et les valeurs de f), soit n ;
10) on compte les granules de tout l’hyper-cylindre, soit N ;
11) on calcule la valeur approximative du volume du solide :
n
VV≅ [1.6]
f hc
N
Malgré son esprit empirique, la méthode de Monte-Carlo est utilisée aujourd’hui
dans beaucoup d’applications provenant de la physique, l’ingénierie, la biologie,
l’infographie, la statistique, l’économie, les télécommunications, etc.
De nos jours, on ne parle plus d’une seule méthode de Monte-Carlo, mais d’une
famille de méthodes de type Monte-Carlo [FIS 95, KRO 11]. Elles offrent non
seulement les approximations exigées, mais des informations statistiques concernant
la confiance associée à ces approximations. De plus, les méthodes modernes de type
Monte-Carlo travaillent avec des distributions de probabilité non uniformes, afin
d’alléger l’effort de calcul.
En ce qui concerne le domaine de l’optimisation, l’emploi des méthodes de
Monte-Carlo est plutôt rude. Dans l’exemple précédent, on a vu que, pendant le
calcul de l’intégrale, les valeurs extrêmes de la fonction f ont été déterminées d’une
manière très empirique. Il est vrai, plus le nombre de granules est grand sur le
domaine D , plus les valeurs extrêmes de f sont précises. Mais il ne s’agit pas d’une
recherche de l’optimum au vrai sens de l’optimisation (c’est-à-dire consistant à
choisir une direction d’avancement et à la changer s’il le faut). La recherche est
brute, « à l’aveugle », sans prendre en compte les propriétés du critère à optimiser.
De plus, usuellement, dans l’optimisation, l’évaluation de ce critère est assez
compliquée, ou bien le calcul de la valeur pour un granule prend beaucoup de temps.
Les métaheuristiques ont adopté quand même le principe de la granularité
stochastique, car il peut beaucoup aider dans la recherche de l’optimum global.
Pour conclure cette section, l’algorithme 1.1 présente la procédure de type
Monte-Carlo utilisée dans l’optimisation heuristique.
22 Optimisation en sciences de l’ingénieur

1. Données d’entrée :
– Le voisinage de recherche V (les équations qui le délimitent, telle que
l’appartenance ou non d’un point à cet ensemble soit facile à décider).
– Le critère à optimiser f.
– Le nombre minimal de points stochastiques de la recherche, K .
– Le seuil de précision, ε> 0 .
2. Initialisation.
a. Choisir arbitrairement (mais à distribution uniforme) le point de départ
de la recherche x ∈V . Un GSPA-U de dimension doit être utilisé nx0
dans ce but (voir la section A2.4, de l’annexe 2). Si le point de départ ne
fait pas partie de V , alors il sera généré jusqu’à ce que cette propriété
soit vérifiée. (On tient compte, quand même, de la topologie de V .)
b. Calculer la performance de la position de départ : f x . () 0
optc. Choisir le point optimal initial : xx = .
0
d. Choisir le numéro d’itération de départ : . k= 0
3. Pour : kK∈−0, 1
k+13.1. Générer un point x à l’intérieur du voisinage V , en utilisant le k
GSPA-U bien calibré dans ce but.
k+13.2. Si , le point a été déjà généré auparavant et il faut le xx ∈{ }ki ik∈0,
remplacer par un autre, qui soit différent. Reprendre, donc, l’étape
précédente.
k+13.3. Sinon, enregistrer xx = .
kk+1
3.4. Evaluer la performance du nouveau point : . f x()k+1
opt3.5. Si la performance est meilleure que la performance , f x f x() ()k+1
optréactualiser le point optimal : xx = . k+1
3.6. Passer à l’itération suivante : kk←+ 1 .
4. Pour kK≥ :
k+14.1. Générer un point à l’intérieur du voisinage V , en utilisant le xk
GSPA-U.
k+14.2. Si xx ∈ , le point a été déjà généré auparavant et il faut le { }ki ik∈0,
remplacer par un autre, qui soit différent. Reprendre, donc, l’étape
précédente.
k+14.3. Sinon, évaluer la performance du nouveau point : f x . ()k
k+1opt4.4. Si ffxx−<ε , arrêter la recherche, car aucune amélioration () ( )k
k+1réelle n’est réalisée. Si, malgré cela, la performance f x est ()kMétaheuristiques – Méthodes locales 23

optmeilleure que la performance , réactualiser le point optimal : f x()
opt k+1xx = . Passer directement à l’étape finale.
k
k+14.5. Sinon, enregistrer xx = .
kk+1
opt4.6. Si la performance est meilleure que la performance , f x f x() ()k+1
optréactualiser le point optimal : xx = . k+1
4.7. Passer à l’itération suivante : kk←+ 1 .
5. Retourner :
opt– Le point optimal : x .
opt– La performance optimale : f x . ()
Algorithme 1.1. Procédure de type Monte-Carlo
pour l’optimisation heuristique locale
Usuellement, la procédure de l’algorithme 1.1 prend du temps, c’est-à-dire
qu’elle est « gloutonne ». A partir d’une certaine itération, la vérification parmi les
points déjà générés (pour éviter les doublons) peut s’avérer beaucoup plus lente que
le calcul effectif de la performance du point généré (même si ce calcul a été déjà
effectué auparavant), mais elle est nécessaire pour l’étape 3 de l’algorithme, afin
d’assurer le degré de granularité minimum prescrit (sinon les résultats de la
procédure sont inconsistants). En revanche, cette vérification peut éventuellement
être supprimée de l’étape 4, surtout si le calcul de la performance dure moins que la
recherche des doublons. (On peut donc supprimer le pas 4.2 de l’algorithme pour
augmenter sa vitesse.)
On va retrouver cette procédure intégrée dans quelques-unes des métaheuristiques
décrites dans le cadre de ce chapitre.
1.3. Ascension de la montagne
On débute avec une métaheuristique d’une grande simplicité, mais qui relève,
d’une part, du principe de base dans l’utilisation des générateurs pseudo-aléatoires
pour faire avancer la recherche vers l’optimum et, d’autre part, du lien avec
l’intelligence artificielle (IA) [RUS 95]. Similairement à cette méthode, beaucoup
de métaheuristiques sont liées d’une manière directe ou indirecte à l’IA. De plus,
cette méthode constitue un exemple d’intégration du principe Monte-Carlo dans
l’optimisation heuristique. 24 Optimisation en sciences de l’ingénieur

On part de la présomption que le critère f doit être maximisé dans un voisinage
V inclus dans S . Puisque S est borné, V hérite la même propriété. Il a donc des
nxlimites bien précisées sur chaque axe de l’espace cartésien  . Il n’est pas
nécessaire que le voisinage soit un hyper-cube ou que le critère soit lissé (on peut
donc rencontrer plusieurs extrema locaux), mais on sait que, dans ce voisinage, le
critère atteint son maximum global.
Soit x ∈V le point initial pour démarrer la recherche. Ce point correspond au
0
point de départ d’un touriste qui envisage d’escalader une montagne et d’arriver à
son sommet. On présume d’abord que le touriste n’est pas bien informé sur le trajet
et qu’il doit avancer « à l’aveugle » vers le pic. Sa stratégie est simple. Dès qu’il est
arrivé dans une position d’altitude supérieure par rapport à celle qu’il occupait avant
(l’altitude étant mesurée par le critère f), il tâche de la préserver, sans jamais
descendre. Il doit quand même ne pas quitter la zone où on l’a informé que le pic
existe (c’est-à-dire, le voisinage V ). A partir d’une position quelconque x ∈V , le k
touriste essaye de trouver le chemin vers la position suivante, tout en choisissant
aléatoirement une direction. Plus précisément, sa position suivante sera :
xx=+Δx , ∀∈k  [1.7] kk++11k
où Δx est un écart choisi au hasard, à la Monte-Carlo, tel que : k+1
x ∈V et ffxx>.8]() ()k+1 kk+1
Le touriste s’arrête quand une ou plusieurs des conditions ci-dessus se vérifient :
– il n’arrive pas à bouger, après avoir effectué un certain nombre de tentatives
∗pour trouver le bon chemin, soit ; N∈ 
– la différence d’altitude entre deux positions successives est trop petite, en
dessous d’un certain seuil, soit , après quelques tentatives successives, par δ> 0
∗exemple, au nombre de (le touriste se maintient sur la courbe de niveau, M∈ 
sans pouvoir s’en détacher) ;
− le gradient estimé de son déplacement, c’est-à-dire le vecteur :
T
 ffxx−−ffxx ffx−x() () () () () ()kk++11kk kk+1
f =  [1.9]  k+1 x x x−x1,1 ,1 k 1,2 k ,2 k+1,nx k ,nx  
∗a eu, pendant ses dernières tentatives (en nombre de M∈  ), une norme trop petite,
en dessous d’un seuil, . ε> 0Métaheuristiques – Méthodes locales 25

Les deux dernières conditions sont, pratiquement, équivalentes, concernant
le maintien du touriste sur la courbe de niveau. (Le gradient peut être nul au
sommet.)
La procédure primaire d’ascension de la montagne est résumée dans
l’algorithme 1.2.
1. Données d’entrée :
– Le voisinage de recherche V (les équations qui le délimitent, telles que
l’appartenance ou non d’un point à cet ensemble soit facile à décider).
– L’indicateur d’altitude f (le critère à maximiser).
– Le nombre maximum N de tentatives effectuées pour s’échapper de la
position courante.
– Le nombre maximum M de tentatives effectuées pour trouver la position
maximale suivante sur la montagne, à partir de la position courante.
– Le seuil de maintien sur la courbe de niveau, δ> 0 .
2. Initialisation.
a. Choisir arbitrairement (mais à distribution uniforme) le point de départ
du touriste x ∈V . Un GSPA-U de dimension doit être utilisé dans ce nx0
but. Si le point de départ ne fait pas partie de V , alors il sera généré
jusqu’à ce que cette propriété soit vérifiée.
b. Calculer l’altitude de la position de départ : . f x() 0
c. Choisir un compteur pour mesurer le nombre de tentatives de s’échapper
de la position courante : . n= 0
d. Choisir un compteur pour le maintien sur la courbe de niveau : m= 0 .
e. Choisir le numéro d’itération de départ : k= 0 .
3. Approcher le sommet. Pour : k≥ 0
3.1. Effectuer des tentatives d’échapper de la position courante. Pour ce
faire :
3.1.1. Utiliser le GSPA-U pour générer un écart sur une direction de
k+1recherche : Δx . Le générateur doit opérer dans un
hyperk
cube qui inclut le voisinage, mais aussi étroit que possible.
k+13.1.2. Tant que xx+Δ ∉V , calibrer le GSPA-U pour générer un
kk
k+1k+1 nouvel écart, mais dans l’hyper-cube 0x,Δ , où Δx est k k 
le plus récent des écarts générés. 26 Optimisation en sciences de l’ingénieur

k+13.1.3. Fixer l’écart : . (Maintenant, on se trouve dans le Δ=xxΔkk+1
voisinage indiqué : xx+Δ ∈V .)
kk+1
3.2. Tester si l’on monte quand on prend la nouvelle position :
3.2.1. Calculer l’altitude de la position proposée : . f()xx+Δkk+1
3.2.2. Si ffxx+Δ > x , alors : ()()kk+1 k
3.2.2.1. Etablir la nouvelle position du touriste : xx=+Δx .
nn++11n
(Son altitude est déjà calculée :ff()xx=+( Δx) ) kk++11k
3.2.2.2. Remettre à zéro le compteur de blocage sur une même
position : . n← 0
3.2.2.3. Si ffxx−<δ , alors le touriste se maintient, () ()kk+1
pratiquement, sur la courbe de niveau et l’indicateur
correspondant augmente : . mm←+ 1
3.2.2.4. Sinon, remettre à zéro le compteur de maintien sur la
courbe de niveau : m← 0 .
3.2.3. Sinon, le touriste doit rester dans la même position (xx = )
kk+1
et l’indicateur de blocage augmente : nn←+1 .
3.3. Si nN> ou mM> arrêter l’approche du sommet et passer à l’étape
finale.
3.4. Sinon, passer à l’itération suivante : kk←+1 .
4. Retourner :
– La position courante du touriste : x . k+1
– L’altitude courante du touriste, f x , présumée être l’altitude du ()k+1
sommet de la montagne.
Algorithme 1.2. Procédure primaire d’ascension de la montagne
L’algorithme 1.2 a été décrit dans une perspective informatique. Pour cette
raison, il peut s’avérer différent des algorithmes d’ascension de la montagne que
l’on trouve dans la littérature de l’IA. Les paramètres de configuration (N, M, δ) ont
des valeurs implicites, afin d’aider l’utilisateur. Usuellement, on permet au touriste
de chercher plus longtemps sa route, à partir de la position courante qu’il occupe,
que d’avancer vers le sommet à pas de fourmi. Par conséquent, N∈10,100 , alors
que . En ce qui concerne le seuil δ, il constitue la partie la moins M∈ 5,10
significative de l’indicateur d’altitude f (la partie fractionnaire de ses valeurs ou les

Métaheuristiques – Méthodes locales 27

derniers chiffres). Normalement, il doit être choisi en fonction du type de variation
de cet indicateur. Usuellement, si les 3-7 derniers chiffres de f ne changent plus, on
peut arrêter la recherche de l’optimum. Par exemple, si les amplitudes de f couvrent
−3la plage de 0 à 1 000, alors on peut établir . Mais, si les amplitudes couvrent δ= 10
une plage 1 000 fois plus large, peut-être que serait un choix plus sage. δ= 1
En général, la performance de l’algorithme 1.2 est assez modeste, concernant
la précision et la vitesse de convergence. Une première étape critique est 1.a
(l’initialisation du point de départ). Si le voisinage V est peu connu, alors il existe
la possibilité de passer beaucoup de temps avant de trouver le bon endroit duquel on
peut démarrer la recherche. Il est souhaitable que le voisinage V, ainsi que
l’indicateur d’altitude f, soient analysés avec attention, bien avant de configurer
l’algorithme. Une autre étape critique (plus difficile à gérer) est 3.2. Là, aussi, il
existe le risque de passer beaucoup de temps pour retourner à l’intérieur du
voisinage de l’optimum. Une mesure pour éviter les boucles infinies a été prise
pourtant : le GSPA-U est forcé de générer des nombres avec des amplitudes de plus
en plus petites, car l’hyper-cube se restreint pour chaque écart généré. Pendant la
recherche, l’algorithme peut assez facilement se bloquer sur un maximum local
assez bien isolé du maximum global (par des vallées larges et profondes). En plus, la
recherche peut osciller. En gros, l’algorithme primaire de l’ascension de la montagne
est facile à implémenter, mais assez lent comme performance.
Une version améliorée consiste à donner au touriste plus de moyens pour
« deviner » sa route, sans essayer trop de possibilités. Bien entendu, il existe une
caractéristique que l’on pourrait prendre en compte : les directions à suivre (qui
montent sur la montagne) sont assez bien marquées par le gradient de l’indicateur
d’altitude f . Si l’on trouve un moyen d’approximer ce gradient pour la position x
courante, alors il est possible d’utiliser la méthode du gradient, combinée avec la
métaheuristique d’ascension. Cette combinaison pourrait non seulement augmenter
la précision de la recherche, mais aussi rendre la procédure plus rapide.
Le gradient peut très facilement être estimé, à partir de deux positions
successives du touriste, x et x , comme dans [1.9]. Par convention, chaque fois
k k+1
que la différence du dénominateur est nulle, la composante correspondante du
gradient est nulle aussi. Ce gradient est conventionnellement attribué à la position
x du touriste. Une fois le gradient courant estimé, l’algorithme de Cauchy à pas
k+1
variable [BOR 12] peut être utilisé, afin d’augmenter la vitesse de recherche de


28 Optimisation en sciences de l’ingénieur

la métaheuristique. Le gradient estimé agit alors comme une boussole pour le
touriste, en lui indiquant chaque fois la direction à suivre, même avec une certaine
imprécision.
La nouvelle procédure d’ascension de la montagne est présentée dans
l’algorithme 1.3.
1. Données d’entrée :
– Le voisinage de recherche V (les équations qui le délimitent, telles que
l’appartenance ou non d’un point à cet ensemble soit facile à décider).
– L’indicateur d’altitude f (le critère à maximiser).
– Le nombre maximum N de tentatives effectuées pour s’échapper de la
position courante.
– Le nombre maximum M de tentatives effectuées pour trouver la position
maximale suivante sur la montagne, à partir de la position courante.
– Le seuil de maintien sur la courbe de niveau, ε> 0 .
2. Initialisation.
a. Choisir arbitrairement (mais à distribution uniforme) le point de départ
du touriste x ∈V . Un GSPA-U de dimension nx doit être utilisé dans ce 0
but. Si le point de départ ne fait pas partie de V , alors il sera généré
jusqu’à ce que cette propriété soit vérifiée. (On tient compte de la
topologie de V .)
b. Calculer l’altitude de la position de départ : f x . () 0
nxc. Choisir le gradient associé au point du départ (usuellement, f ∈ 0
f0= ). 0
d. Choisir un pas d’avancement initial, α∈  (usuellement, α= 1 ). 0 0
e. Choisir un compteur pour mesurer le nombre de tentatives d’échapper de
la position courante : n= 0 .
f. Choisir un compteur pour le maintien sur la courbe de niveau : m= 0 .
g. Choisir le numéro d’itération de départ : k= 0 .
3. Approcher le sommet. Pour k≥ 0 :
3.1. Effectuer des tentatives d’échapper de la position courante. Pour ce
faire :
3.1.1. Utiliser le GSPA-U pour générer un écart sur une direction de
k+1
recherche : Δx . kMétaheuristiques – Méthodes locales 29

kk++113.1.2. Tant que , calibrer le GSPA-U pour générer xx=+Δx∉Vkk k
k+1k+1 un nouvel écart, mais dans l’hyper-cube 0x,Δ , où Δx k k 
est le dernier écart généré.
k+13.1.3. Calculer l’altitude de la position proposée : f x . ()k
3.1.4. Estimer le gradient indiqué par les positions x (courante) et
k
k+1x (pseudo-aléatoire), à l’aide de la définition [1.9] (mais avec
k
k+1 à la place de x ). On obtient ainsi f (avec des compo-xk k+1 k+1
santes nulles correspondant aux divisions par zéro, là où c’est le
cas). On mémorise ce gradient.
T3.1.5. Estimer le pas optimal d’avancement : α=α−ff (le
kk++11kk
gradient antérieur, f , étant déjà mémorisé).
k
3.1.6. Tant que xf+α ∉V , calibrer le GSPA-U pour générer un
kk++11k
nouveau pas d’avancement, mais dans l’intervalle 0,α , où [ ]k+1
α est le plus récent des pas générés (à partir du pas optimal
k+1
de l’étape précédente).
3.1.7. Fixer l’écart : Δ=xfα .
kk++11k+1
3.2. Tester si l’on monte quand on prend la nouvelle position :
3.2.1. Calculer l’altitude de la position proposée : fxx+Δ . ()kk+1
3.2.2. Si ffxx+Δ > x , alors : ()()kk+1 k
3.2.2.1. Etablir la nouvelle position du touriste : xx=+Δx .
kk++11k
(Son altitude est déjà calculée : ffxx=+Δx ) () ( )kk++11k
3.2.2.2. Remettre à zéro le compteur de blocage sur une même
position : n← 0 .
3.2.2.3. Si f <ε , alors le touriste se maintient, pratiquement, k
sur la courbe de niveau et l’indicateur correspondant
augmente : mm←+1 .
3.2.2.4. Sinon, remettre à zéro le compteur de maintien sur la
courbe de niveau : m← 0 .
3.2.3. Sinon, le touriste doit rester dans la même position (xx = ) kk+1
et l’indicateur de blocage augmente : nn←+1 .
3.3. Si nN> ou mM> arrêter l’approche du sommet et passer à l’étape
finale.
3.4. Sinon, passer à l’itération suivante : kk←+1 . 30 Optimisation en sciences de l’ingénieur

4. Retourner :
– La position courante du touriste : x . k+1
– L’altitude courante du touriste, f x , présumée être l’altitude du ()k+1
sommet de la montagne.
Algorithme 1.3. Procédure améliorée d’ascension de la montagne,
avec la boussole de Cauchy
L’algorithme 1.3 est seulement légèrement plus compliqué que l’algorithme
précédent. Pour mieux le comprendre, le lecteur est invité à analyser d’abord
l’algorithme 2.8 de [BOR 12] (l’algorithme de Cauchy à pas variable). Pour
configurer l’algorithme amélioré, on peut utiliser les mêmes recommandations
qu’auparavant. Néanmoins, le paramètre M peut descendre jusqu’à 0, car le gradient
estimé est plus sensible à la détection des extrêmes. De plus, les petites valeurs du
gradient favorisent le phénomène d’oscillation de l’algorithme. Dans ce cas, la
recherche est arrêtée dès que la norme du gradient estimé tombe pour la première
fois en dessous du seuil prescrit, ε . Par différence avec le seuil δ de l’algorithme
précédent, le seuil ε doit être calibré en fonction du rapport entre les variations de
l’indicateur d’altitude et les variations des positions le long des axes du repère
cartésien (revoir la définition [1.9]).
La performance de l’algorithme 1.3 est meilleure, concernant la précision et
surtout la vitesse de convergence, par rapport à l’algorithme précédent. Grâce à
l’utilisation du gradient estimé, on obtient une diminution du nombre total d’itérations
pour trouver le point maximal, bien que cette estimation soit assez grossière pour
certains points. Même si la boussole indique le maximum seulement d’une manière
approximative, le touriste possède pourtant un moyen d’orientation dont il peut se
servir. Dans l’algorithme précédent, le touriste était obligé d’effectuer la recherche
pratiquement « à l’aveugle ». L’algorithme amélioré reste malgré tout inférieur à
d’autres algorithmes issus des métaheuristiques, son atout principal étant la simplicité.
A noter que les algorithmes d’ascension de la montagne peuvent être adaptés
assez facilement pour un problème de descente d’une vallée, jusqu’au point le plus
profond.
1.4. Recherche Tabou
1.4.1. Principe
Il s’agit d’une méthode de recherche locale, issue de la méthode de descente
x« gloutonne ». Partant d’une solution de l’espace de recherche S , elle consiste à iMétaheuristiques – Méthodes locales 31

chercher, dans le voisinage , une solution améliorant un critère à optimiser, V x x() i j
correspondant à l’optimisation d’une fonction objectif f.
Le voisinage d’une solution x correspond à l’ensemble des solutions V()x i i
accessibles à partir de cette solution, en effectuant un seul mouvement, déplacement
ou transition admissible. Usuellement, cet ensemble prend la forme d’un hyper-cube
ou d’une hyper-sphère contenant la solution x .
i
1.4.2. Algorithme glouton
Le but étant la recherche d’un minimum de f, la meilleure solution x recherchée
j
dans le voisinage de la solution x est retenue si . Pour V x ffxx< ()() ()i i ji
délimiter ce voisinage, il suffit de générer d’une manière pseudo-aléatoire des
petits écarts par rapport à la solution x , tels que reste inclus dans l’espace V()xi i
de recherche S . Par exemple, si V x doit prendre la forme d’un hyper-cube, () i
alors :
V x =xx−γ,,+δ ×x −γx +δ× ×x −γ,x +δ ()ii,1 i,1i,1 i,1 i,2 i,2i,2 i,2 i,nx i,nxi,nx i,nx  
[1.10]
où les limites γ et δ font partie d’une SPA uniformément générée { } { }in, in,nn∈1,x nn∈1,x
(SPA-U). Les limites de variation de la SPA-U peuvent être établies comme
fractions du diamètre de l’espace de recherche D S . Un autre exemple, pour le ()
cas d’un voisinage sphérique, est le suivant :
VS()xx=∈ x−x<ρ [1.11] { }iii
où le rayon ρ est obtenu avec un GSPA-U, calibré de même par le diamètre i
D S . ()
Dans ce contexte, la procédure de descente gloutonne est décrite dans
l’algorithme 1.4.

32 Optimisation en sciences de l’ingénieur

1. Données d’entrée :
– L’espace de recherche S (les équations qui le délimitent, telles que
l’appartenance ou non d’un point à cet ensemble soit facile à décider).
– L’indicateur de profondeur f (le critère à minimiser).
– Les limites du GSPA-U, utilisées pour générer les voisinages successifs.
(Usuellement, ces limites sont exprimées comme fractions du diamètre
de l’espace de recherche.)
– Le nombre minimum N de granules pour la méthode de Monte-Carlo.
– Le seuil de précision ε> 0 , pour la méthode de Monte-Carlo.
2. Initialisation.
a. Choisir arbitrairement (mais à distribution uniforme) le point de départ
de la recherche x ∈S . Un GSPA-U de dimension nx doit être utilisé 0
dans ce but. Si le point de départ ne fait pas partie de S , alors il sera
généré jusqu’à ce que cette propriété soit vérifiée. (On tient compte,
quand même, de la topologie de S .)
b. Calculer la profondeur du point de départ : f x . () 0
c. Etablir le numéro d’itération de départ : . k= 0
3. Pour k≥ 0 :
3.1. Utiliser le GSPA-U, calibré conformément aux prescriptions spécifiées,
pour générer un voisinage . V()xk
3.2. Tant que V x ⊄S , générer un nouveau voisinage, mais en calibrant () k
chaque fois le GSPA-U avec la frontière du dernier voisinage généré.
3.3. Maintenant, V()x ⊂S . Ceci permet de trouver la meilleure solution k
optdu voisinage , soit . Pour ce faire, on emploie la méthode de V()x xk k
Monte-Carlo (l’algorithme 1.1), localement, dans le voisinage V x , () k
pour la granularité N et le seuil ε (spécifiés a priori).
opt3.4. Calculer la profondeur de la meilleure solution locale : . f x()k
opt3.5. Si ffxx≥ , arrêter la recherche et passer à l’étape finale. ()()kk
opt
3.6. Sinon, mettre à jour le point minimal : xx = . kk+1
3.7. Passer à l’itération suivante : kk←+1 .
4. Retourner :
– Le point minimal courant : x .
k
– La profondeur minimale : f x . () k
Algorithme 1.4. Procédure de descente gloutonne Métaheuristiques – Méthodes locales 33

Dans l’étape 3.3 de l’algorithme 1.4, la méthode de Monte-Carlo peut être
remplacée par une autre technique d’optimisation, voire exacte [BOR 12], si le
critère d’optimisation f le permet. En général, il est souhaitable de combiner
les métaheuristiques avec les méthodes exactes d’optimisation, si possible, afin
d’augmenter la précision du résultat. Par les métaheuristiques, on peut mieux
isoler le voisinage où l’optimum global semble être présent, tandis que par les
méthodes exactes, on peut trouver cet optimum avec une bonne précision.
Néanmoins, si le critère est trop fractal par nature, l’emploi des méthodes exactes
devient impossible.
L’approche ci-dessus est simple à réaliser, mais risque de tomber rapidement sur
un minimum local. Une façon de pallier à cet inconvénient consiste à recommencer
la recherche en partant de solutions initiales différentes. Diverses améliorations ont
été proposées à la descente gloutonne, qui ont conduit à la recherche Tabou.
1.4.3. Méthode de recherche Tabou
Tout en gardant le principe de la recherche locale, on se donne la possibilité de
sortir d’un minimum local. Dans la suite, on appelle mouvement toute modification
d’une solution permettant d’obtenir une solution voisine. Le critère ici encore
consiste à rechercher la solution minimisant la fonction objectif. Partant d’une
solution initiale x , on recherche la meilleure solution x de son voisinage V x , ()i j i
même s’il y a dégradation de la fonction objectif ffxx> et on recommence () ()ji
la recherche dans le voisinage de cette nouvelle solution. Toutefois, afin de ne pas
générer un cycle, le mouvement inverse (ou le retour à la solution précédente) est
exclu, il devient « tabou » (d’où le nom de la méthode) [ENN 04, GHE 07, GLO 89,
GLO 90].
Supposons que la solution x ait été visitée à la k-ème itération de la recherche.
i
Alors, les dernières solutions visitées (suite aux mouvements réalisés) sont Nki ,
taboues. On peut noter T la liste des dernières solutions taboues (la liste Tabou).
ki ,
La méthode exige que tout mouvement devant conduire à une solution de la liste
T soit interdit. ki ,
Le voisinage courant dans lequel est recherchée la solution est alors :
VVxx= \T [1.12] () ()ki i k ,i⎯




34 Optimisation en sciences de l’ingénieur

A partir d’une solution x , un ensemble de mouvements possibles M peut être i ki ,
construit, à l’itération k. Soit un tel mouvement. On va utiliser la notation m∈Mki ,
m
xx⎯⎯ → pour marquer la transition de la solution x à un nouveau point x , iij j
obtenu suite au mouvement m . Alors :
 mVVxx=∈ x ∃m∈MT,&x→∉x x [1.13] () ()ki j i k,,i i j j ki

Pratiquement, la définition [1.13] montre qu’il faut seulement générer de
nouvelles solutions, dans le voisinage de la solution courante.
Cette approche, bien qu’intéressante ne garantit pas d’éviter un bouclage et peut
donner un caractère tabou ou inaccessible à certaines solutions non testées.
Cet inconvénient peut être levé en acceptant de relaxer ce caractère tabou si le
mouvement envisagé permet d’atteindre une solution meilleure que celles déjà
visitées (critère d’aspiration) ou d’aller vers des solutions non encore envisagées.
Il convient de remarquer qu’il est souvent plus facile d’estimer la variation
Δ=ffxx−f de la fonction objectif, que de la calculer avec précision à () ()ji
chaque itération ce qui permet de limiter les calculs à réaliser.
Le choix des mouvements admissibles peut varier considérablement, suivant le
problème à traiter. Par exemple, dans le problème du voyageur de commerce, qui
doit visiter N villes une fois et une seule, en minimisant la distance parcourue,
plusieurs types de mouvements sont envisageables dans l’ordre de passage, comme
suit :
dep
– déplacement d’une ville : CDEGAFHHJKI →CDE GAFJKI ;
per
– permutation de deux villes : CDEJGAFH KI →CDJEHGAF KI ;
− inversion de l’ordre de passage d’un groupe de villes :
inv
CDEGAFHJKI →CDFAGEHJKI
Dans cet exemple, la solution x est CDEGAFHJKI, qui représente la suite des
i
villes à visiter dans un certain ordre. Les mouvements changent cet ordre d’une
façon ou d’une autre, pour arriver à des solutions x .
j
⎯⎯
⎯⎯
⎯⎯Métaheuristiques – Méthodes locales 35

1.4.4. Liste Tabou
La définition et la taille de la liste Tabou constituent des paramètres importants
de la recherche. Une taille très élevée permet de restreindre la recherche mais
augmente le risque de rater le minimum global. En revanche, une liste de taille trop
faible augmente le risque d’apparition de cycles.
La solution la plus courante consiste à choisir une liste Tabou de taille constante.
Dans ce cas, la dernière solution visitée (suite au dernier mouvement réalisé) entre
dans la liste et la plus ancienne solution visitée (suite au plus ancien mouvement
réalisé) en est exclue, dès que la taille choisie est atteinte.
En pratique, il apparaît souvent plus intéressant d’avoir une taille N évolutive,
ki ,
susceptible d’être modifiée à chaque itération, en restant comprise entre deux valeurs
extrêmes :
NN≤≤N , ∀∈ki,  [1.14] min ki , max
De nombreuses règles d’évolution ont été proposées, dont nous ne citerons que
les deux principales :
– si la solution générée dans l’itération courante produit une amélioration de la
fonction objectif, alors la taille est diminuée d’une unité : NN←−max 1,N . { }ki,, k imin
Ainsi, les deux solutions les plus anciennes sont supprimées de la liste et la plus
récente y est insérée. Si, en supprimant les solutions, la taille de la liste Tabou
décroît en dessous de la taille minimum, alors soit on élimine la solution la plus
ancienne seulement, soit on renonce à cette opération ;
− si la solution générée dans l’itération courante ne produit pas une
amélioration de la fonction objectif, alors la taille est augmentée d’une unité :
NN←+min 1,N . Ainsi, la dernière solution est ajoutée à la liste, sans { }ki,, k imax
qu’aucune soit supprimée. Si, en ajoutant la nouvelle solution, la taille de la liste
Tabou dépasse la valeur maximum prévue, alors on peut éliminer la solution la plus
ancienne.
On peut remarquer que le caractère tabou des derniers mouvements peut
conduire à un blocage de l’itération, ainsi qu’il apparaît dans l’exemple présenté
plus loin. Dans ce cas, il convient de violer le caractère tabou pour aller vers des
solutions non encore visitées. 36 Optimisation en sciences de l’ingénieur

1.4.5. Algorithme de la recherche Tabou
La procédure de la recherche Tabou est décrite dans l’algorithme 1.5.
1. Données d’entrée :
– L’espace de recherche S (les équations qui le délimitent, telles que
l’appartenance ou non d’un point à cet ensemble soit facile à décider).
– Le critère d’optimisation f.
– Les types de mouvements possibles, à partir d’une solution (tenant
compte des restrictions possibles).
– Le nombre minimum de solutions pour un voisinage courant, N . V
– Les limites de la liste Tabou : N et N , avec NN < .
min max min max
– Le nombre maximum d’itérations, K .
– Le seuil de précision, ε> 0 .
– Le nombre maximum M des solutions trouvées, satisfaisant le seuil de
précision.
– Le nombre maximum N d’itérations suite auxquelles la solution optimale
trouvée ne change pas.
2. Initialisation.
a. Choisir arbitrairement (mais à distribution uniforme) le point de départ
de la recherche x ∈S . Un GSPA-U de dimension nx doit être utilisé
0,0
dans ce but. Si le point de départ ne fait pas partie de S , alors il sera
généré jusqu’à ce que cette propriété soit vérifiée. (On tient compte de
la topologie de S .)
b. Calculer la performance du point de départ : f x . ()0,0
optc. Initialiser la solution optimale : . xx = 0,0
d. Initialiser la liste Tabou : T = x . { }0,0 0,0
e. Choisir le compteur initial des solutions satisfaisant le seuil de précision :
m= 0 .
f. Choisir la position de la solution optimale initiale : i= 0 .
g. Choisir le numéro d’itération de départ : k= 0 .
3. Pour : kK∈−0, 1
3.1. Préciser les types de mouvements possibles (tout en considérant les
restrictions, si elles existent), à partir de la solution courante, x .
ki ,
L’ensemble de tous ces mouvements, même s’il possède un nombre fini
d’éléments, peut avoir une taille très grande. ⎯
Métaheuristiques – Méthodes locales 37

3.2. Initialiser le voisinage de la solution courante : V x =∅ . ()kk ,i
3.3. Tant que le nombre des éléments de V x est inférieur à N : ()kk ,i V
3.3.1. Utiliser le GSPA-U, pour sélectionner un mouvement possible
. (Si tous les mouvements possibles ont été épuisés, sortir de mp
la boucle et passer à l’étape 3.4.)
3.3.2. Effectuer le mouvement mp pour obtenir un nouveau point :
mp mp
xx⎯⎯ → ki,, k i
mp3.3.3. Si ce point fait partie de l’espace de recherche ( x ∈S ) et
ki ,
mpn’appartient pas à la liste Tabou ( x ∉T ), alors ajouter le ki,, ki
point au voisinage :
mpVVxx←∪x () () { }k k,,i k ki ki,
3.3.4. Sinon, conserver le voisinage.
3.4. Si le voisinage contient au moins un point ( ) : V x ≠∅()kk ,i
3.4.1. Prendre la nouvelle solution comme premier meilleur point,
, où indique sa position dans le cadre du voisinage. Il faut x jkj,
donc résoudre le problème :
xx= argopt f ( ) kj,
xx∈V()kk ,i
par une recherche exhaustive.
3.4.2. Définir la nouvelle solution : xx = .
kj+1, k ,j
3.4.3. Ajouter la nouvelle solution à la liste Tabou et mettre à jour
cette liste :
TT=∪ x { }kj++1, k ,i k 1,j
3.4.4. Réactualiser la position de la solution : ij= .
3.4.5. Si la performance de la nouvelle solution ( , déjà f x()ki+1,
calculée) est meilleure que la performance courante optimale
opt( f x , disponible) : ()
opt
3.4.5.1. Réactualiser la solution optimale : xx = . ki+1,
3.4.5.2. Remettre à zéro le compteur de blocage : n← 0 .
opt3.4.5.3. Si ffxx−<ε , incrémenter le compteur des () ()ki+1,
solutions satisfaisant le seuil de précision : . mm←+ 138 Optimisation en sciences de l’ingénieur

3.4.5.4. Si mM> , abandonner la recherche, car aucun progrès
réel n’est réalisé. Passer à l’étape finale (n° 4).
3.4.5.5. Si possible, éliminer une ou deux des solutions les plus
anciennes de la liste Tabou, pour que le nombre des
solutions taboues restantes soit au moins égal à N . min
(Si ce nombre est déjà inférieur à N , ne pas affecter min
la liste Tabou.)
3.4.6. Sinon, la solution optimale courante reste inchangée et alors :
3.4.6.1. Incrémenter le compteur de blocage : nn←+1 .
3.4.6.2. Si nN> , abandonner la recherche, car, probablement,
on est arrivé au meilleur point que l’on puisse obtenir
avec l’algorithme. Passer à l’étape finale (n° 4).
3.4.6.3. Sinon, vérifier si la liste Tabou réactualisée (T ) a ki+1,
un nombre trop grand de solutions (plus de N ). Dans max
ce cas, éliminer la solution la plus ancienne, pour
revenir à N solutions.
max
3.4.6.4. Remettre à zéro le compteur des solutions satisfaisant
le seuil de précision : . m= 0
3.4.7. Passer à l’itération suivante : kk←+1 .
3.5. Sinon, le voisinage courant étant vide, on est arrivé à un blocage et il
faut sortir de la boucle principale. Passer à l’étape finale (n° 4).
4. Retourner :
opt– Le point optimal courant : x .
opt– La performance : f x . ()
Algorithme 1.5. Procédure de la recherche Tabou
Comme pour les procédures précédentes, dans l’algorithme 1.5, plusieurs
conditions d’arrêt ont été intégrées. Premièrement, il existe un nombre maximum K
d’itérations à effectuer. Si la procédure s’arrête à cause de cette condition, il vaut
mieux continuer la recherche avec un nombre plus grand d’itérations, à partir de la
liste Tabou et de la solution optimale courantes. Deuxièmement, la recherche peut
être arrêtée soit quand les dernières M solutions optimales de la liste Tabou ne
produisent pas une amélioration effective du critère choisi, soit quand la solution
optimale ne change plus pour N itérations successives. Ces conditions d’arrêt