Chapitre 2
La recherche à grand voisinage : un
nouvel opérateur
2.1 Introduction à la recherche locale
Un nombre important de problèmes d'optimisation
d'intérêts pratiquessont difficilement résolus de
manière exacte dans des temps de calcul raisonnables. Ainsi, une
approche pratique pour résoudre de tels problèmes est d'employer
des algorithmes heuristiques (ou d'approximation) qui peuvent être
capables de trouver des solutions quasi optimales dans des temps de calcul
raisonnables. La littérature dédiée aux algorithmes
heuristiques distingue fréquemment deux classes d'algorithmes : les
algorithmes constructifs et les algorithmes d'amélioration. Un
algorithme de construction construit une solution à partir de rien en
assignant des valeurs à une ou plusieurs variables de décisions
itérativement. Un algorithme d'amélioration démarre
généralement à partir d'une solution réalisable et
essaie itérativement d'obtenir de meilleures solutions. Les algorithmes
de recherche à voisinage (appelés aussi algorithmes de recherche
locale) sont une vaste classe d'algorithmes d'amélioration pour lesquels
à chaque itération une meilleure solution est trouvée en
explorant le voisinage de la solution courante.
2.1.1 Bases de la recherche locale
Le principe de la recherche locale est le suivant :
l'algorithme débute avec une solution initiale réalisable. Sur
cette solution initiale, on applique une série de modifications locales
(définissant un voisinage de la solution courante), tant que celles-ci
améliorent la qualité de l'objectif. Malheureusement, en
appliquant ce principe, rien ne garantit d'atteindre la ou les solutions
optimales. La recherche peut se retrouver bloquée dans un optimum local
relativement au voisinage considéré et s'arrêter, faute
d'amélioration possible. On voit donc que la qualité des
solutions finales dépend en grande partie de
la complexité et de la diversité des
transformations permises par les opérateurs de recherche locale. Un des
principaux problèmes est donc de faire un compromis entre le temps de
calcul nécessaire pour explorer l'intégralité d'un espace
de recherche défini par le voisinage et sa taille.
On définit l'espace de recherche comme l'espace dans
lequel la recherche locale s'effectue. Cet espace peut correspondre à
l'espace des solutions réalisables du problème
étudié. Chaque point de l'espace correspond ainsi à une
solution satisfaisant l'ensemble des contraintes associées au
problème.
À chaque itération, l'ensemble des modifications
que l'on se permet d'effectuer sur la solution courante S
définit un nouvel ensemble de solutions. Ce nouvel ensemble de
solutions est appelé le voisinage de S ou
N(S). Pour un même problème, il existe un grand
nombre d'opérateurs de voisinages possibles et intéressants.
Les bases de la recherche locale peuvent être
définies ainsi. Soient : - f() la fonction qu'on l'on souhaite
maximiser,
- S la solution courante,
- S* la meilleure solution connue,
- f* la valeur de la meilleure solution
connue,
- N(S) le voisinage de S.
La procédure de recherche locale est la suivante :
7
8
9
Algorithme 2 : Algorithme d'une recherche locale
simple de plus grande pente
1 Initialisation: Construire une solution de
départ S0;
2 S* = S0;
3 S = S0;
4 f* =
f(S0);
5 tant que l'optimum local n'a pas
été atteint faire
6 S =
argmaxSI?N(S)(f(S0));
si f(S) >
f* alors
f* = f(S); S* =
S;
2.1.2 Principales classes de recherches locales Recherche
locale simple ou méthode de descente
La plus simple de toutes les approches de recherches locales
consiste à construire une unique solution initiale et à
l'améliorer en utilisant une unique structure de voisinage
jusqu'à ce qu'un optimum local soit atteint, arrêtant ainsi la
recherche. Il y a cependant deux variantes de cette approche :
- meilleure amélioration : on parcourt
l'intégralité de l'espace de recherche défini
par la
structure de voisinage et on choisit S* tel que
S* =
argmaxSl?N(S)(f(S')),
2.1. Introduction à la recherche locale
- première amélioration: on parcourt l'espace de
recherche et on met à jour la solu-
tion courante dès qu'une solution S' est
trouvée, définie telle que f(S') >
f(S).
Hansen et Mladenovi'c (2006) ont étudié l'impact
de ces variantes pour le problème de Voyageur de Commerce. Ils ont
montré que l'efficacité de ces différentes versions
dépendait en grande partie du choix dans les solutions initiales. La
version de la meilleure amélioration, qui semble la plus attirante car
plus prometteuse dans l'amélioration des solutions, donnait dans leurs
résultats expérimentaux des résultats significativement
plus mauvais que la version de la première amélioration.
Recherche locale à départs
multiples
La recherche locale à départs multiples est une
simple extension du schéma de la recherche locale simple. Plusieurs
solutions générées (par exemple aléatoirement) sont
utilisées comme solutions initiales de la recherche locale.
L'exploration des voisinages à partir de ces solutions initiales permet
d'obtenir plusieurs optima locaux. Parmi ces optima locaux, le meilleur est
sélectionné puis retenu comme solution de la résolution
heuristique.
| 
