Les mouvements (ou transformations) sont au coeur de l'heuristique de Recherche Locale. Il n'y a pas de limite sur le nombre de mouvements pouvant intervenir dans un algorithme. Il faut cependant s'assurer de ne pas perdre trop de temps à s'intéresser à des mouvements qui se solde toujours par un échec et qui finalement pollue la recherche locale sans contribuer à son bon fonctionnement.

Plusieurs facteurs vont impacter la qualité de la solution finale obtenue :

• Leur modélisation
• Leur adaptabilité
• Leur complexité
• Leur diversité

L'objectif principal est de visiter un maximum de solutions différentes dans le temps imparti. Il est donc très important de créer une grande famille de mouvements plus ou moins spécialisés. Bien sûr, on retrouve toujours un socle commun composé de mouvements d'insertion, de suppression, d'échange. Pour illustrer ce propos quelque peu abstrait, voici un exemple :

Exemple 1 : Soit un problème d'optimisation où l'objectif est de placer tous les invités d'un séminaire à des tables en respectant un jeu de contraintes de placements.
Quelques mouvements possibles vont être :

• Supprimer un invité déjà affecté à une table, en le sélectionnant au hasard.
• Ajouter un invité non affecté à une table où il reste une place, en lasélectionnant au hasard.
• Echanger deux invités entre deux tables, en les sélectionnant au hasard.
• Etc...

On voit apparaître ici une notion importante qui est la notion de hasard. Bien évidement, certains mouvements font appel à des tirages au sort d'objets, d'autres peuvent faire appel à la sélection d'objets respectant certains critères (pour reprendre notre exemple, on pourrait imaginer d'aller choisir la table la plus vide et d'essayer d'y ajouter un nouvel invité, au lieu de choisir une table au hasard). Cette spécialisation des mouvements peut permettre d'améliorer la convergence, maître mot de la Recherche Locale. Cependant, il est important de conserver des mouvements génériques, pour garantir encore une fois une bonne diversification.

Helsgaun [1] et Estellon et al. [2] précisent dans leur article que l'utilisation de propriétés structurelles intrasèques au problème permet de définir des mouvements ayant un probabilité de succès plus élevée.

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 ] K. Helsgaun (2000). An effective implementation of the Lin-Kernighan traveling salesman heuristic. European Journal of Operational Research 126(1), pp. 106-130.

[ 2 ] B. Estellon, F. Gardi, K. Nouioua (2005). Two local search approaches for solving real-life car sequencing problems. (à paraître dans European Journal of Operational Research)