2-opt

En optimisation, 2-opt est un algorithme de recherche locale proposé par Georges A. Croes en 1958 pour résoudre le problème du voyageur de commerce en améliorant une solution initiale.

Définition formelle du problème du voyageur de commerce

Soit un graphe complet $G=(V,A,\omega )$ avec $V$ un ensemble de sommets, $A$ un ensemble d'arêtes et $\omega$ une fonction de coût sur les arcs. Le problème est de trouver le plus court cycle hamiltonien dans le graphe.

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 $a_{1},a_{2}\in H$ par deux arêtes $a_{3},a_{4}\in E$ tel que le tour résultant est toujours hamiltonien dans $G$.

Dans le cas du problème du voyageur de commerce géométrique, i.e. quand l'inégalité triangulaire des poids est respectée, 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 :

• 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 x_i de H faire

Pour tout sommet x_j de H, avec j différent de i-1, de i et de i+1 faire

Si distance(x_i, x_i+1) + distance(x_j, x_j+1) > distance(x_i, x_j) + distance(x_i+1, x_j+1) alors

Remplacer les arêtes (x_i, x_i+1) et (x_j, x_j+1) par (x_i, x_j) et (x_i+1, x_j+1) dans H

amélioration := vrai;

retourner H

Terminaison et complexité

Une permutation n’est admissible que si elle réduit strictement le coût total du cycle hamiltonien. En particulier, cela implique que chaque cycle hamiltonien est visité au plus une fois, garantissant la terminaison de l’algorithme en au plus $n!$ permutations. Il existe des instances où 2-opt prend un temps exponentiel, même dans le cas euclidien. En pratique cependant, on observe que l’heuristique se comporte en $O(n^{2})$. 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 a observé une complexité très légèrement supérieure à $O(n^{2})$. 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 (donc m ≤ n) ; une complexité de $O(mn)$ peut ainsi être obtenue.

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.

La principale limite de 2-opt réside 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 peut influer grandement sur les résultats.

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
• Algorithme de Christofides, un algorithme d'approximation pour le cas métrique du voyageur de commerce

Liens externes

• Implantation pratique dans le cadre de la coupe de france de robotique 2004
• Exemple interactif via une applet