Maintenant que nous avons clairement défini l'importance d'une bonne heuristique de descente et d'une famille de mouvements adaptée, il paraît important de rappeler les points clés de l'algorithmique de la Recherche Locale.

Toute la puissance de cette technique de résolution de problèmes combinatoires va dépendre de l'implémentation d'une bonne algorithmique incrémentale sous jacente. L'idée est d'exploiter au mieux les invariants dans les différentes structures de données, afin de faire diminuer le temps de convergence et d'améliorer ainsi la qualité de la solution.

A chaque sélection de mouvements, on va devoir faire appel à une première fonction Eval(), qui calcule le gain résultant d'une transformation appliquée à la solution courante. Un mouvement perturbe généralement l'état courant et entraine une modification d'un certain nombre d'objets. On peut :

• soit choisir de modifier la valeur des objets puis de calculer la nouvelle valeur de la fonction objectif, puis en fonction de sa valeur, effacer ou valider cette modification ;
  
  
• soit choisir de travailler sur des structures temporaires mises à jour lors de l'évaluation et recopiées uniquement si le mouvement est accepté.

On note aussi l'importance des deux autres fonctions Commit() et Rollback() qui respectivement valide une transformation en mettant à jour la solution courante ou la rejette en réinitialisant les structures de données modifiées.

Différents champs temporaires peuvent être mises en place sur les objets (utiles pour modifiés les objets impactés par une transformation), des indexeurs de données (utiles pour accéder en O(1) à des objets dans des listes), des listes chaînées (utiles pour gérer les précédences et supprimer des éléments dans des listes en O(1)), des tags d'objets modifiés (afin de savoir quel objet et modifiés et de ne pas perdre du temps à mettre à jour des objets non impactés).

Pour certains problèmes, les taux d'acception d'un mouvement ne dépasse pas les 1 pour 1000. C'est à dire qu'on va tenter de faire 1000 modifications de notre état courant, appeler 1000 fois la fonctione Eval() pour déduire la nouvelle valeur de la fonction objectif, appeler 999 fois la fonction Rollback() pour revenir dans l'état précédent et appeler 1 seul fois la fonction Commit() pour valider la modification. Il est donc très important d'optimiser les 2 premiers fonctions. La fonction Commit() peut être plus coûteuse que les autres et elle doit intégrer les fonctions d'enregistrements des statistiques, de mise à jour de la fonction objectif et de toutes les structures.

Toute cette 'implémentation de l'algorithme se doit d'être soucieuse du principe de localité présidant la gestion de la mémoire cache et optimisée par profiling du code, afin d'accélérer grandement le temps de convergence de la Recherche Locale. Moret [ 1 ] a publié un très bon article en 2002 sur ces sujets d'efficacité algorithmique.

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 ] B.M.E. Moret (2002). Towards a discipline of experimental algorithmics. In Data Structures, Near Neighbor Searches, and Methodology : 5th and 6th DIMACS Implementation Challenges (sous la direction de M.H. Goldwasser, D.S. Johnson et C.C. McGeoch), DIMACS Monographs, Vol. 59, pp. 197-213. American Mathematical Society, Providence, RI.