- 2-opt
-
En optimisation, 2-opt est un algorithme de recherche locale proposé par Croes en 1958[1] pour résoudre le problème du voyageur de commerce en améliorant une solution initiale.
Sommaire
L'algorithme
Principe
Exemple de permutation
2-opt est un algorithme itératif : à chaque étape, on supprime deux arêtes de la solution courante et on reconnecte les deux tours ainsi formés. Cette méthode permet, entre autres, d'améliorer le coût des solutions en supprimant les arêtes sécantes lorsque l'inégalité triangulaire est respectée (voir figure ci-contre). Sur le schéma de droite, la route <a; b; e; d; c; f; g> est changée en <a; b; c; d; e; f; g> en inversant l'ordre de visite des villes e et c. Plus généralement, lorsqu'on inverse l'ordre de parcours de deux villes, il faut aussi inverser l'ordre de parcours de toutes les villes entre ces deux villes.
Formalisation
On peut donner une description plus formelle de l’heuristique. Soit un graphe G = (V,E) et H un cycle hamiltonien dans G muni d’une fonction coût renvoyant la somme des poids des arêtes composant le cycle.
Définition — On définit une 2-permutation dans le cycle hamiltonien H comme le remplacement de deux arêtes
par deux arêtes 
tel que le tour résultant est toujours hamiltonien dans G.Dans le cas du problème du voyageur de commerce géométrique, la permutation consiste généralement à remplacer les arêtes par leurs diagonales (cf. le schéma ci-contre).
L’algorithme s’énonce alors ainsi[2] :
- trouver une 2-permutation de H produisant le cycle H' tel que coût(H') < coût(H) ;
- remplacer H par H' ;
- recommencer tant qu’une telle 2-permutation est possible.
Pour des raisons de performance, la solution initiale H est souvent générée par une heuristique constructiviste ou gloutonne rapide, voire aléatoirement. On peut noter que diverses stratégies peuvent être appliquées lors du choix de la permutation : ce peut être la première trouvée, la meilleure ou la pire au regard de la tournée courante, ou encore un choix aléatoire parmi un ensemble de permutations admissibles.
Voici une transcription directe appliquée au cas du voyageur de commerce géométrique :
fonction 2-opt ( G : Graphe, H : CycleHamiltonien )
- amélioration : booléen := vrai
- Tant que amélioration = vrai faire
- amélioration := faux;
- Pour tout sommet xi de H faire
- Pour tout sommet xj de H, avec j différent de i-1 et i+1 faire
- Si distance(xi, xi+1) + distance(xj, xj+1) > distance(xi, xj) + distance(xi+1, xj+1) alors
- Remplacer les arêtes (xi, xi+1) et (xj, xj+1) par (xi, xj) et (xi+1, xj+1) dans H
- amélioration := vrai;
- Si distance(xi, xi+1) + distance(xj, xj+1) > distance(xi, xj) + distance(xi+1, xj+1) alors
- Pour tout sommet xj de H, avec j différent de i-1 et i+1 faire
- retourner H
Terminaison et complexité
Une permutation n’est admissible que si elle réduit strictement le coût total du cycle hamiltonien. Ce coût tend donc vers la solution optimale, garantissant la terminaison de l’algorithme. En revanche, aucune preuve ne donne la complexité au pire (si ce n'est l'exponentielle), le nombre de permutations possibles n’étant pas borné et pouvant s’exprimer en fonction du nombre de sommets n[3] ; en pratique cependant, on observe que l’heuristique se comporte en O(n2)[4]. Pour des problèmes euclidiens avec des villes uniformément distribuées dans le carré unité et en utilisant une structure de données permettant d'effectuer une modification 2-opt en O(1), Taillard[5] a observé une complexité très légèrement supérieure à O(n2). Diverses méthodes permettent d’optimiser ce résultat en calculant par exemple au préalable une liste des m sommets les plus proches de chaque ville ; une complexité de O(mn) peut ainsi être obtenue[6].
Estimation de performance et limites
Communément, on mesure l’efficacité des différentes heuristiques du voyageur de commerce en comparant la distance de la solution obtenue avec une borne inférieure de la solution optimale (par exemple, la borne de Held-Karp). Ce faisant, diverses études empiriques tendent à montrer que l’algorithme 2-opt donne de bons résultats par rapport aux heuristiques constructivistes, avec un écart par rapport à la borne allant de 4 à 7 % environ – c’est-à-dire au pire entre 4 et 7 % de la solution optimale[7].
La principale limite de 2-opt réside bien sûr dans le fait qu’il ne fournit pas de garantie satisfaisante quant à la qualité de la solution finale : l’algorithme est sujet à tomber dans des minima locaux assez rapidement. On note aussi que la nature de la solution initiale influe grandement sur les résultats[7].
Méthodes dérivées
L’algorithme 2-opt peut facilement être généralisé à k-opt, c’est-à-dire en cherchant à permuter k arêtes à chaque étape, bien qu’il soit en général rare de dépasser la 3-permutation (3-opt). Dans la même idée, l’algorithme de Lin-Kernighan est une heuristique très performante qui consiste à faire varier le nombre d’arêtes à permuter selon la solution courante. Enfin, des méthodes de recuit simulé peuvent être utilisées pour permettre à l’algorithme de sortir d’un minimum local.
Annexes
Articles connexes
- Algorithme de Lin-Kernighan
- Recherche locale
- Problème du voyageur de commerce
- Problème de tournées de véhicules
Liens externes
- Implantation pratique dans le cadre de la coupe de france de robotique 2004
- Exemple interactif via une applet
Références et notes
- G. A. Croes, A method for solving traveling salesman problems, Operations Res. 6, 1958, pp. 791-812.
- Jean-Claude Fournier, Graphes et applications, t. 2, Hermes Science Publications, 2007 (ISBN 978-2-7462-1657-0), p. 54-63
- (en) Prabha Sharma, « Local Search for Combinatorial Optimisation Problems », dans Indian Institute of Technology Kanpur, vol. 6, no 3, 2004 [texte intégral]
- (en) William J. Cook, William H. Cunningham, William R. Pulleyblank et Alexander Schrijver, Combinatorial Optimization, Wiley-Interscience, 1997 (ISBN 978-0-471-55894-1), p. 242-251
- (en) Éric Taillard, « Few guidelines for analyzing methods », dans Metaheuristic International Conference, 2005 [texte intégral]
- (en) Christian Nilsson, « Heuristics for the Traveling Salesman Problem », Linköping University, 2003
- (en) Emile Aarts et J. K. Lenstra, Local search in combinatorial optimization, Princeton University Press, 2003 (ISBN 978-0-691-11522-1) [lire en ligne], p. 234-238
Wikimedia Foundation. 2010.
