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