Heuristique de Lin-Kernighan
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.
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.
Description
modifierL'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
modifierLe problème du voyageur de commerce est de trouver le plus court cycle hamiltonien dans un graphe complet avec un ensemble de sommets, un ensemble d'arêtes et une fonction de coût sur les arcs. L'heuristique 2-opt consiste à partir d'un cycle hamiltonien dans généré aléatoirement ou de façon gloutonne, puis à chercher deux arêtes de , (A, B) et (C, D), qui peuvent être remplacées par (A, C) et (B, D) en réduisant le coût global. Ce remplacement est appelé 2-permutation. La procédure est ensuite répétée tant qu'une telle 2-permutation est possible dans . Une généralisation naturelle est de prendre plus de deux arêtes, on parle alors de 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
modifierLe 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ées « 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 afin de gagner en efficacité, ou pour décider de l'ordre dans lequel ils doivent être considérés[3].
Histoire
modifierDans 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].
Extensions et variantes
modifierLin-Kernighan-Helsgaun (LKH)
modifierL’algorithme de Lin-Kernighan-Helsgaun (LKH) est proposé en 2000 par Keld Helsgaun[5], avec des résultats expérimentaux qui montrent des performances supérieures aux autres variantes. Là où l'algorithme Lin-Kernighan original recherche les arêtes candidates à échanger parmi les proches voisins de chaque nœud, LKH étend la recherche à d'autres arêtes sans compromettre l'efficacité de l'algorithme, en utilisant l'arbre couvrant de poids minimal pour sélectionner de arêtes candidates et calculer pour chacune une probabilité (valeurs alpha) d'appartenir à la solution optimale.
Une des améliorations possibles de LKH utilise la métaheuristique POPMUSIC (Partial OPtimization Metaheuristic Under Special Intensification Conditions) pour explorer simultanément différents ensembles d’arêtes candidates, puis ne garder que les meilleures arêtes apparaissant dans plusieurs de ces explorations. Les résultats expérimentaux montrent que cette approche est plus efficace que LKH[6].
Variantes avec réseaux de neurones
modifierPlusieurs travaux ont proposé à partir des années 2020 d'utiliser les réseaux de neurones pour améliorer et accélérer la phase de sélection des arêtes candidates, qui est l'étape critique dans l'heuristique. Parmi ces approches, qui sont basées sur LKH, VSR-LKH (Variable Strategy Reinforced LKH) utilise l'apprentissage par renforcement[7], et NeuroLKH encode un réseau creux pour optimiser le calcul des paramètres de LKH[8]. Dans les deux cas, le réseau de neurones est entraîné pour trouver les arêtes candidates de façon plus adaptée à la tournée courante que LKH. Les résultats expérimentaux de ces approches sont positifs tant en matière de performances que d'efficacité.
Voir aussi
modifierRéférences
modifier- G. A. Croes (1958), A method for solving traveling salesman problems, Operations Res. 6 (1958), p. 791-812.
- 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,
- 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,
- S. Lin and B. W. Kernighan (1973), An Effective Heuristic Algorithm for the Traveling-Salesman Problem,. Operations Res. 21, p. 498-516.
- (en) Keld Helsgaun, « An effective implementation of the Lin–Kernighan traveling salesman heuristic », European Journal of Operational Research, vol. 126, no 1, , p. 106–130 (ISSN 0377-2217, DOI 10.1016/S0377-2217(99)00284-2, lire en ligne, consulté le )
- (en) Éric D. Taillard, « A linearithmic heuristic for the travelling salesman problem », European Journal of Operational Research, vol. 297, no 2, , p. 442–450 (ISSN 0377-2217, DOI 10.1016/j.ejor.2021.05.034, lire en ligne, consulté le )
- (en) Jiongzhi Zheng, Kun He, Jianrong Zhou et Yan Jin, « Reinforced Lin–Kernighan–Helsgaun algorithms for the traveling salesman problems », Knowledge-Based Systems, vol. 260, , p. 110144 (ISSN 0950-7051, DOI 10.1016/j.knosys.2022.110144, lire en ligne, consulté le )
- (en) Xin, Liang, Song, Wen, Cao, Zhiguang et Zhang, Jie, « NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem », Advances in Neural Information Processing Systems, vol. 34, (lire en ligne, consulté le )
