Recherche locale (optimisation)

En algorithmique, la recherche locale est une méthode générale utilisée pour résoudre des problèmes d'optimisation, c'est-à-dire des problèmes où l'on cherche la meilleure solution dans un ensemble de solutions candidates. La recherche locale consiste à passer d'une solution à une autre solution proche 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é.

Exemple introductif

On prend comme exemple le problème du voyageur de commerce, qui consiste, étant donné une liste de villes et les distances entre celles-ci, à trouver un circuit qui passe par toutes les villes, et qui est le plus court possible. Autrement dit, l'ensemble des solutions admissibles est l’ensemble des circuits qui passent par toutes les villes, et l'objectif est la minimisation de la longueur. On peut considérer que l'on se place sur un graphe non orienté dont les sommets sont les villes, et les arêtes sont des routes entre les villes.

Un algorithme de recherche locale simple, appelé 2-opt, est le suivant : partir d'un circuit quelconque, et itérer la recherche suivante. Prendre deux arêtes (A,B) et (C,D), et les remplacer par les arêtes par (A,D) et (B,C). Si ce nouveau circuit est plus court le conserver et continuer, sinon reprendre le circuit précédent et essayer une autre paire d'arêtes.

On peut arrêter l'algorithme lorsque toutes les paires d'arêtes ont été testées. La solution obtenue n'est pas garantie d'être optimale, mais peut tout de même être utile et de qualité.

Description

Notion de voisinage

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).

Critère d’arrêt

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.

Utilisations

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.

Exemples

Les problèmes suivants se prêtent bien à l'utilisation de la recherche locale^{[réf. souhaitée]} :

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.

Articles connexes

• Algorithme anytime, la plupart des recherches locales sont anytime, c'est-à-dire que l'on peut les arrêter avant la terminaison de l'algorithme et obtenir la solution courante.

Bibliographie

• (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.