2-opt

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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.

Définition formelle du problème du voyageur de commerce[modifier | modifier le code]

Article détaillé : 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[modifier | modifier le code]

Principe[modifier | modifier le code]

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[modifier | modifier le code]

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[2], 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[3] :

  • 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;
retourner H

Terminaison et complexité[modifier | modifier le code]

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[4] ; en pratique cependant, on observe que l’heuristique se comporte en O(n^2)[5]. 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[6] 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[7].

Estimation de performance et limites[modifier | modifier le code]

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[8].

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[8].

Méthodes dérivées[modifier | modifier le code]

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[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Références et notes[modifier | modifier le code]

  1. G. A. Croes, A method for solving traveling salesman problems, Operations Res. 6, 1958, pp. 791-812.
  2. aussi appelée, problème du voyageur de commerce métrique (metric TSP)
  3. Jean-Claude Fournier, Graphes et applications, t. 2, Hermes Science Publications,‎ 2007 (ISBN 978-2-7462-1657-0), p. 54-63
  4. (en) Prabha Sharma, « Local Search for Combinatorial Optimisation Problems », Indian Institute of Technology Kanpur, vol. 6, no 3,‎ 2004 (lire en ligne)
  5. (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
  6. (en) Éric Taillard, « Few guidelines for analyzing methods », Metaheuristic International Conference,‎ 2005 (lire en ligne)
  7. (en) Christian Nilsson, « Heuristics for the Traveling Salesman Problem », Linköping University,‎ 2003
  8. a et b (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