WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

Techniques hybrides de recherche exacte et approchée: application à  des problèmes de transport

( Télécharger le fichier original )
par Boris BONTOUX
Université d'Avignon et des pays de Vaucluse - Doctorat spécialité informatique 2008
  

précédent sommaire suivant

Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy

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.

précédent sommaire suivant






Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy








"Piètre disciple, qui ne surpasse pas son maitre !"   Léonard de Vinci