La recherche locale est une technique de résolution mathématique consistant à partir d'une solution initiale appartenant à l'espace des solutions et à l'améliorer de façon itérative en explorant un voisinage de celle-ci.

On obtient une solution dite voisine en appliquant des transformations (ou mouvements) sur la solution courante. Ces transformations peuvent être plus ou moins locales (c'est à dire des mouvements qui s'éloignent plus ou moins de la solution courante).

On distingue deux sous-fonctions très importantes dans cet algorithme : la fonction d'évaluation des transformations (qui consiste à mesurer l'impact d'une transformation sur la solution courante) et la fonction de validation de la transformation (qui consiste à passer de l'état courant en ce nouvel état).

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.

Lin et Kernighan [1] dans les années 1970 ont publié de nombreux travaux de Recherche Locale sur le problème du voyageur de commerce et ont démocratisé la notion de Recherche Locale. La technique a connu un regain d'intérêt dans les années 90 [2] avec l'avènement de la notion de Métaheuristique.

On ne compte plus le nombre de publications faisant référence à cette notion de Métaheuristique. Elles font souvent appel à des algorithmes sous-jacents de Recherche Locale, c'est-à-dire qu'elles décrivent les stratégies (coupes, voisinages, descente, ...) utilisées pour trouver rapidement et efficacement une solution de qualité en un temps raisonnable. C'est le cas des algorithmes à base de fourmis [3], le recuit simule [4], les algorithmes génétiques [5], etc.

Voici le plan de cette introduction à la recherche locale :

• Les notions de base :
  • La Recherche Locale
  • Algorithmie
    
    
• Méthodologie :
• Heuristique de Recherche
• Les Mouvements
• Implémentation
  

Plus d'infos sur le sujet de la Recherche Locale, consultez la note suivante (Estellon B., Gardi F. et Nouioua K.) : Cliquez ici. Questions, commentaires, compléments d'informations : antoinejeanjean@gmail.com

Références :

[ 1 ] S. Lin, B.W. Kernighan (1973). An effective heuristic algorithm for the Traveling-Salesman Problem.
Operations Research 21, pp. 498-516.

[ 2 ] E. Aarts, J.K. Lenstra (1997). Local Search in Combinatorial Optimization. Wiley-Interscience Series
in Discrete Mathematics and Optimization, John Wiley & Sons, Chichester, England, UK.

[ 3 ] Marco Dorigo, Phd Thesis, 1992.

[ 4 ] S. Kirkpatrick, C.D. Gelatt et M.P. Vecchi en 1983.

[ 5 ] Nils Aall Barricelli, 1954 et Alex Fraser, 1957