Voir la source de 2-opt

En [[Optimisation (mathématiques)|optimisation]], '''2-opt''' est un algorithme de [[Recherche locale (optimisation)|recherche locale]] proposé par Georges A. Croes en [[1958]]<ref>G. A. Croes, ''A method for solving traveling salesman problems'', Operations Res. 6, 1958, pp. 791-812.</ref> 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 ==
{{article détaillé|Problème du voyageur de commerce}}
Soit un [[graphe complet]] <math>G = (V,A,\omega)</math> avec <math>V</math> un ensemble de sommets, <math>A</math> un ensemble d'arêtes et <math>\omega</math> 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 ===
[[Image:2-opt_wiki.svg|thumb|right|Exemple de permutation]]
2-opt est un [[méthode itérative|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 (mathématiques)|heuristique]]. Soit un [[Théorie des graphes|graphe]] <math>G = (V,E)</math> et <math>H</math> un [[cycle hamiltonien]] dans <math>G</math> muni d’une fonction ''coût'' renvoyant la somme des poids des arêtes composant le cycle. 

{{Théorème
|Définition
|On définit une ''2-permutation'' dans le cycle hamiltonien <math>H</math> comme le remplacement de deux arêtes <math>a_1, a_2 \in H</math> par deux arêtes <math>a_3, a_4 \in E</math> tel que le tour résultant est toujours hamiltonien dans <math>G</math>. }}

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<ref>aussi appelée, problème du voyageur de commerce métrique (''metric TSP'')</ref>, 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<ref name="Fournier07">{{Ouvrage |langue=fr |prénom1=Jean-Claude |nom1=Fournier |titre=Graphes et applications |tome=2 |éditeur=Hermes Science Publications |année=2007 |passage=54-63 |isbn=978-2-7462-1657-0}}</ref> :
* trouver une 2-permutation de <math>H</math> produisant le cycle <math>H'</math> tel que coût(H') < coût(H) ;
* remplacer <math>H</math> par <math>H'</math> ;
* 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 :

<div style="padding: 0.5em; border: 1px solid #ccc">
'''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{{ind|i}} de H '''faire'''
:::      '''Pour tout''' sommet x{{ind|j}} de H, avec j différent de i-1, de i et de i+1 '''faire'''
::::        '''Si''' distance(x{{ind|i}}, x{{ind|i+1}}) + distance(x{{ind|j}}, x{{ind|j+1}}) > distance(x{{ind|i}}, x{{ind|j}}) + distance(x{{ind|i+1}}, x{{ind|j+1}}) '''alors'''
:::::          Remplacer les arêtes (x{{ind|i}}, x{{ind|i+1}}) et (x{{ind|j}}, x{{ind|j+1}}) par (x{{ind|i}}, x{{ind|j}}) et (x{{ind|i+1}}, x{{ind|j+1}}) dans H
:::::	       amélioration := vrai;
:  '''retourner''' H
</div>

=== 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 d'un algorithme|terminaison de l’algorithme]] en au plus <math>n!</math> permutations. Il existe des instances où 2-opt prend un temps exponentiel, même dans le cas euclidien<ref>
{{chapitre
 |titre chapitre=Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
 |auteur1= Matthias Englert
 |auteur2=Heiko Röglin
 |auteur3= Berthold Vöcking
 |titre ouvrage=Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms
 |passage=1295-1304
 |année=2007
}}</ref>. En pratique cependant, on observe que l’heuristique se comporte en <math>O(n^2)</math><ref name="Cook97">{{Ouvrage|langue=en|prénom1=William J.|nom1=Cook|prénom2=William H.|nom2=Cunningham|prénom3=William R.|nom3=Pulleyblank|prénom4=Alexander|nom4=Schrijver|titre=Combinatorial Optimization|éditeur=[[Wiley-VCH|Wiley-Interscience]]|année=1997|passage=242-251|isbn=978-0-471-55894-1}}</ref>. 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 <math>O(1)</math>, Taillard<ref name="Taillard05">{{article|langue=en|auteur1=|prénom1=Éric|nom1=Taillard|titre=Few guidelines for analyzing methods|périodique=Metaheuristic International Conference|lien périodique=|année=2005|date=25.08.2005|issn=|url texte=http://mistic.heig-vd.ch/taillard/articles.dir/Taillard2005.pdf|consulté le=|pages=}}</ref> a observé une complexité très légèrement supérieure à <math>O(n^2)</math>. 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 <math>O(mn)</math> peut ainsi être obtenue<ref name="Nilsson03">{{en}} {{Lien web|url=http://www.ida.liu.se/~TDDB19/reports_2003/htsp.pdf |titre=Heuristics for the Traveling Salesman Problem |auteur=Christian Nilsson |année=2003 |éditeur=Linköping University |consulté le= }}</ref>.

=== 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<ref name="Aarts03">{{Ouvrage |langue=en |prénom1=Emile |nom1=Aarts |prénom2=J. K. |nom2=Lenstra |titre=Local search in combinatorial optimization |éditeur=[[Princeton University Press]] |année=2003 |pages totales=512 |passage=234-238 |isbn=978-0-691-11522-1 |lire en ligne=https://books.google.com/books?id=NWghN9G7q9MC&printsec=frontcover}}</ref>.

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<ref name="Aarts03" />.

== 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<ref>{{chapitre|titre chapitre= History of TSP computation|numéro chapitre=3|titre ouvrage = The traveling Salesman Problem: A Computational Study|auteur1=David L. Applegate|auteur2=Robert E. Bixby|auteur3=[[Václav Chvátal]]|auteur4=[[William J. Cook]]|année = 2006|éditeur = [[Princeton University Press]]}}</ref>. 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 (optimisation)|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 ===
* [http://labo.algo.free.fr/robotique2004/coconut.html Implantation pratique] dans le cadre de la [[coupe de france de robotique]] 2004
* [http://www-e.uni-magdeburg.de/mertens/TSP/node3.html Exemple interactif] via une ''[[applet]]''

=== Références et notes ===
{{Références|colonnes=2}}


{{Portail|informatique théorique}}

[[Catégorie:Algorithme d'optimisation]]
[[Catégorie:Heuristique]]
[[Catégorie:Algorithme de la théorie des graphes]]