Recherche locale

En informatique, la recherche locale est une métaheuristique utilisée pour résoudre des problèmes d'optimisation difficiles. La recherche locale peut être utilisée sur des problèmes de recherche d'une solution maximisant un critère parmi un ensemble de solutions candidates. Les algorithmes de recherche locale passent d'une solution à une autre dans l'espace des solutions candidates (l'espace de recherche) jusqu'à ce qu'une solution considérée comme optimale soit trouvée ou que le temps imparti soit dépassé. Les problèmes suivants se prêtent bien à l'utilisation de la recherche locale :

1. le problème de couverture de sommets dans lequel une solution est un arbre recouvrant un graphe simple et l'objectif est de trouver la solution avec le nombre de nœuds minimum ;
2. le problème du voyageur de commerce où une solution est un cycle contenant tous les nœuds du graphe et l'objectif est de minimiser la longueur totale du cycle ;
3. le problème SAT où une solution est une association et l'objectif est de maximiser le nombre de clauses vérifiées par l'association ; dans ce cas, la solution finale est celle qui satisfait toutes les clauses.

Beaucoup de problèmes peuvent être formulés de plusieurs manières en termes d'espace de recherche et d'objectif. Par exemple, pour le problème du voyageur de commerce une solution peut être un cycle et le critère à maximiser la combinaison du nombre de nœuds et de la longueur du cycle. Mais une solution peut aussi être un chemin, et le transformer en cycle peut faire partie de l'objectif.

Un algorithme de recherche locale part d'une solution candidate et la déplace de façon itérative vers une solution voisine. Cette méthode est applicable seulement si une notion de voisinage est définie sur l'espace de recherche. Par exemple, le voisinage d'un arbre recouvrant est un autre arbre recouvrant qui diffère seulement par un nœud. Pour le problème SAT, les voisins d'une bonne affectation sont habituellement les affectations qui diffèrent seulement par la valeur d'une variable. Le même problème peut avoir plusieurs définitions différentes de voisinage ; l'optimisation locale avec des voisinages qui limitent les changements à k composantes de la solution est souvent appelée k-optimale

Habituellement, chaque solution candidate a plus d'une solution voisine ; le choix de celle vers laquelle se déplacer est pris en utilisant seulement l'information sur les solutions voisines de la solution courante, d'où le terme de recherche locale. Quand le choix de la solution voisine est fait uniquement en prenant celle qui maximise le critère, la métaheuristique prend le nom de hill climbing (escalade de colline).

Le critère d'arrêt de la recherche locale peut être une limite en durée. Une autre possibilité est de s'arrêter quand la meilleure solution trouvée par l'algorithme n'a pas été améliorée depuis un nombre donné d'itérations. Les algorithmes de recherche locale sont des algorithmes sous-optimaux puisque la recherche peut s'arrêter alors que la meilleure solution trouvée par l'algorithme n'est pas la meilleure de l'espace de recherche. Cette situation peut se produire même si l'arrêt est provoqué par l'impossibilité d'améliorer la solution courante car la solution optimale peut se trouver loin du voisinage des solutions parcourues par l'algorithme.

Les algorithmes de recherche locale sont largement utilisés dans les problèmes d'optimisation difficiles, tels que les problèmes informatiques (en particulier l'intelligence artificielle), mathématiques, de recherche opérationnelle, d'ingénierie et de bio-informatique.

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Local search » (voir la liste des auteurs)
• Hoos, H.H. and Stutzle, T. (2005) Stochastic Local Search: Foundations and Applications, Morgan Kaufmann.

Liens externes

• Comet Optimization Language dedicated to Constraint-Based Local Search, Constraint-Programming and Mathematical Programming (free for academic use).
• ParadisEO
• Metaheuristics/Stochastic Local Search Forum
• SINTEF Optimization

• Portail de l'informatique théorique