Définir une heuristique de recherche consiste tout d'abord à mettre en place une fonction objectif du problème.

Ensuite, il s'agit pour compléter l'heuristique d'établir une stratégie d'acceptation / de refus des transformations. Différentes possibilités sont envisageables :

• Dès qu'une transformation améliore la valeur de la fonction objectif de la solution courante, on l'accepte : on parle de First-Improvement Algorithm. L'intérêt de cette stratégie est qu'elle permet une grande diversification des solutions par les mouvements en premier lieu.
  
  
• On évalue plusieurs mouvements à la fois, c'est-à-dire qu'on calcule la distance entre la valeur de la fonction objectif avant et après transformation. Parmi toutes les transformations améliorant, on va choisir celle qui améliore le plus l'objectif : on parle ici de Best-Improvement Algorithm.
  
  
• On accepte généralement les transformations améliorantes mais on peut se permettre de temps en temps d'accepter une transformation dégradant la qualité de la solution. C'est le principe de l'algorithme de Recuit Simule [1] inspiré d'un processus utilisé en métallurgie. Ce processus alterne des cycles de refroidissement lent et de réchauffage (recuit) qui tendent à minimiser l'énergie du matériau.

Dans ces trois stratégies, on peut décider ou non d'accepter les transformations qui n'ont pas d'impact sur la fonction objectif mais qui ne sont pas les mêmes solutions que la solution courante. L'avantage est de garatir une meilleure diversification de la solution courante et d'éviter de rester bloquer dans un optimum local.

De nombreuses études ont comparé les méthodes [2], nous choisissons généralement d'utiliser plutôt le First Improvement Algorithm avec acceptation des transformations sans impact sur la fonction objectif. Ainsi, on assure une diversification permanente de la solution et on change en permanence d'état courant.

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. Kirkpatrick, C.D. Gelatt et M.P. Vecchi,1983.

[ 2 ] Pierre Hansen , Nenad Mladenovic', First vs. best improvement: an empirical study, Discrete Applied Mathematics, v.154 n.5, p.802-817, 1 April 2006

[ 3 ]

[ 4 ]