Heuristique de Lin-Kernighan

En optimisation combinatoire, l'heuristique de Lin-Kernighan est une heuristique pour le problème du voyageur de commerce. L'algorithme consiste à échanger itérativement un certain nombre d'arêtes à partir d'une solution donnée pour trouver une solution de meilleur coût.

Cet article concerne l'heuristique de résolution du problème du voyageur de commerce. Pour l'heuristique de partitionnement d'un graphe, voir Algorithme de Kernighan-Lin.

Description

L'heuristique de Lin-Kernighan est une méthode itérative, qui consiste à améliorer peu à peu une solution. Au départ on choisit arbitrairement une solution, puis on l'améliore par des changements simples. C'est une généralisation de l'heuristique 2-opt[1].

Idée de base : 2-OPT

L'heuristique 2-opt consiste à chercher deux arêtes du tour courant, (A, B) et (C, D), qui peuvent être remplacées par (A, C) et (B, D) en réduisant le coût global, et à reproduire la procédure. Ce remplacement est appelé permutation. Une généralisation naturelle est de prendre plus de deux arêtes, on parle alors k-opt, mais le temps de calcul devient rapidement grand pour un grand nombre d'arêtes considérées[2].

La méthode 2-opt peut être vue de la manière suivante (en notant s(v) le sommet qui suit v dans le tour) :

  • Choisir un sommet v (appelé la base),
  • Choisir un sommet p,
  • Si le coût de (v,s(v))+(p,s(p)) est plus grand que le coût de (v,p)+(s(v),s(p)), alors effectuer la permutation.

Le principe

Le principe de l'heuristique de Lin-Kernighan est de faire un k-opt adaptatif (variable k-opt) qui consiste à améliorer une solution en faisant un certain nombre de permutations successives. La différence avec 2-opt est que l'on ne demande pas que les étapes intermédiaires réduisent le coût de la solution, seul le coût final est pris en compte. La différence avec k-opt est que l'on ne considère pas toutes les suites de permutations possibles, on se restreint à celles qui sont jugés « prometteuses », dans le sens suivant[3].

Une permutation est « prometteuse » si (en suivant les notations de la partie précédente) le coût de (v, s(v)) est supérieur au coût de (s(v), s(p)). D'une certaine manière, cela revient à dire que l'on s’intéresse seulement à l'amélioration d'une arête sur les deux.

Une étape consiste à épuiser la réserve de permutations prometteuses à partir d'un sommet v, en enregistrant après chaque permutation la valeur du tour créé. Puis à faire la suite de permutations jusqu'à atteindre le minimum correspondant à cette série.

Il existe ensuite plusieurs variantes, pour restreindre les sommets prometteurs, ou pour décider de l'ordre dans lequel ils doivent être considérés[3].

Histoire

Dans les années 1950 et 1960, le problème du voyageur de commerce est devenu relativement populaire, et de nombreux chercheurs ont défini des heuristiques pour obtenir des solutions de faible coût[2]. L'heuristique de Lin et Kernighan a été publiée en 1973[4], et est encore l'une des plus populaires. Elle est utilisée comme sous-routine de la plupart des heuristiques rapides actuelles[2].

Voir aussi

Références
  1. G. A. Croes (1958), A method for solving traveling salesman problems, Operations Res. 6 (1958), p. 791-812.
  2. David L. Applegate, Robert E. Bixby, Václav Chvátal et William J. Cook, chap. 3 « History of TSP computation », dans The traveling Salesman Problem: A Computational Study, Princeton University Press,
  3. David L. Applegate, Robert E. Bixby, Václav Chvátal et William J. Cook, chap. 15 « Tour finding : Lin-Kernighan », dans The traveling Salesman Problem: A Computational Study, Princeton University Press,
  4. S. Lin and B. W. Kernighan (1973), An Effective Heuristic Algorithm for the Traveling-Salesman Problem,. Operations Res. 21, p. 498-516.
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.