2.1.3 Recherche locale à voisinage variable
La recherche à voisinage variable a été
introduite par Mladenovi'c et Hansen (1997). Cette recherche utilise à
la place d'une seule structure de voisinage, plusieurs structures
appliquées dans un ordre prédéfini. Depuis son
introduction, la recherche à voisinage variable a vu le
développement d'un nombre important de variantes de diverses
complexités. La plus simple d'entre elles, la descente à
voisinage variable (Variable Neighborhood Descent) (voir Hansen et
al. (2006b) pour plus de détails), est la version multivoisinage de
la recherche locale simple. La procédure de la descente à
voisinage variable est la suivante : on applique sur une solution initiale un
opérateur de recherche locale en utilisant la première structure
de voisinage, jusqu'à ce qu'un optimum local soit atteint; la recherche
locale continue alors, en utilisant une deuxième structure de voisinage
jusqu'à ce qu'un optimum local (par rapport à cette structure)
soit atteint. Une fois que cet optimum local est atteint, on utilise une autre
structure de voisinage, et ainsi de suite, de manière
répétitive. Au bout d'un certain nombre d'itérations, la
descente à voisinage variable s'arrête, une fois qu'elle a atteint
une solution qui est un optimum local pour chacune des structures de voisinages
considérées. On peut cependant remarquer que l'ordre dans lequel
sont appliquées les structures de voisinage peut avoir un impact sur la
qualité de la solution finale.
2.1.4 Algorithmes utilisant de la recherche locale
L'utilisation de la recherche locale en conjonction avec
d'autres méthodes est une procédure très efficace. On peut
citer un certain nombre d'hybridations de méthodes avec de la recherche
locale.
Algorithmes de branchement et
séparation
La recherche locale peut être couplée avec une
procédure de branchement et séparation (Toth et Vigo, 2001;
Haouari et Ladhari, 2003; Danna, 2003; Prescott-Gagnon et al., 2007;
Baptiste et al., 2008). Danna (2003) utilise la recherche locale dans
une procédure de résolution par génération de
colonnes. Lorsqu'une solution entière est trouvée, la recherche
locale est utilisée pour améliorer la solution et ainsi
générer de nouvelles colonnes. Danna et al. (2005)
proposent aussi une méthode appelée RINS (Relaxation
Induced Neighborhood Search), qui utilise la recherche locale pour explorer un
sousespace qui est à la fois le voisinage de la solution entière
et le voisinage de la solution de la relaxation continue. Toth et Vigo (2001)
utilisent la recherche locale pour le calcul de bornes inférieures, en
résolvant de manière heuristique le dual de la relaxation
linaire. Baptiste et al. (2008) utilisent une procédure de
recherche locale afin d'améliorer la borne supérieure.
Prescott-Gagnon et al. (2007) proposent une méthode hybride
entre recherche locale et résolution par génération de
colonnes, dans laquelle une version heuristique de génération de
colonnes est utilisée pour la résolution du problème
restreint.
Métaheuristiques
La recherche tabou (Tabu Search ou TS) est une
métaheuristique présentée par Glover (1989). L'idée
de la recherche tabou consiste à explorer le voisinage d'une solution
par un opérateur de recherche locale et à choisir la solution
dans ce voisinage qui minimise la fonction objectif (dans le cas d'un
problème de minimisation). On autorise cependant à choisir une
solution qui augmente la valeur de la fonction objectif afin de sortir d'un
minimum local. Pour ne pas retomber dans ce minimum local, on garde en
mémoire dans une liste tabou les dernières positions
explorées dont on interdit la visite. Pour plus de détails sur la
recherche tabou, nous conseillons au lecteur l'ouvrage de Glover et Laguna
(1997).
Le recuit simulé (simulated annealing ou SA)
est une métaheuristique probabiliste, inspirée d'un processus
utilisé en métallurgie, proposée par Kirkpatrick et
al. (1983). Par analogie avec le processus physique, la fonction à
minimiser est l'énergie du système. On introduit également
un paramètre fictif, la température du système. À
chaque itération de l'algorithme, on applique un opérateur de
recherche locale sur une solution. Cette modification entraîne une
variation de l'énergie du système. Si cette variation fait
baisser l'énergie du système, elle est appliquée à
la solution courante. Sinon, elle est acceptée avec une certaine
probabilité dépendant de la température. En diminuant
progressivement la température (et ainsi la probabilité
d'accepter des solutions détériorantes), on tend à
minimiser l'énergie du système.
2.2. Recherche à grand voisinage
Algorithmes évolutionnaires
Les métaheuristiques basées sur des algorithmes
évolutionnaires sont souvent couplées avec de la recherche
locale. Pour les algorithmes génétiques (voir le chapitre 4 pour
plus de détails), la recherche locale est souvent utilisée pour
l'amélioration des solutions et l'intensification de la recherche (Tsai
et al., 2004; Snyder et Daskin, 2006; Hart et al., 2005;
Silberholz et Golden, 2007). On trouve aussi de nombreux algorithmes couplant
des algorithmes d'optimisation par Colonie de Fourmis (voir le chapitre 3 pour
plus de détails) et de la recherche locale (Dorigo et al.,
1996; Dorigo et Stutzle, 2004; Bell et McMullen, 2004; Bontoux et Feillet,
2008; Donati et al., 2008). La recherche locale est alors
utilisée pour améliorer les solutions trouvées par les
fourmis. Les algorithmes mémétiques ont été
proposés par Moscato et Norman (1992) et (Moscato et Cotta, 2005) et
peuvent être décrits comme une stratégie de recherche dans
laquelle une population d'agents coopèrent, couplée avec de la
recherche locale (voir la section 4.3 pour plus de détails sur ces
algorithmes).
Algorithmes basés sur de la programmation par
contraintes
Plusieurs méthodes proposent une coopération
entre la programmation par contraintes et la recherche locale (Prestwich, 2008;
Pisinger et Ropke, 2007; Benoist et al., 2007; Hansen et al.,
2006a; Shaw, 1998). Shaw (1998) propose une technique, appelée LNS
(Large Neighborhood Search) qui emploie des opérateurs de recherche
locale et utilise une recherche arborescente à base de propagation de
contraintes afin d'évaluer le coût et la
réalisabilité des mouvements des opérateurs de recherches
locales. Prestwich (2008) utilise le même principe en proposant la
méthode FCNS (Forward checking Colouration Neihbourhood Search)
pour un problème de coloration de graphes. Benoist et al.
(2007) propose une méthode, appelée Branch & Move
qui applique de la recherche locale sur des contraintes maîtresses
d'un problème.
Actuellement, l'hybridation de la recherche locale avec d'autres
méthodes semble proposer les algorithmes les plus performants pour de
nombreux problèmes.
| 
