Méthode du 2-opt optimisé

Présentation

Dans l'introduction, j'ai déjà présenté le sujet proposé à Rallye Sciences et vous avez du remarquer la propriété principale que les élèves devaient justifier : un parcours optimal ne peut être croisé.

N'ayant trouvé aucune référence directe à cette propriété sur Internet ni aucune méthode l'utilisant explicitement, par simple curiosité j'ai écrit un petit algorithme pour décroiser un parcours quelconque et me suis aperçu qu'il permettait d'atteindre rapidement des valeurs proches de celles du parcours idéal dans le cas du défi des 250 villes. La piste étant prometteuse, j'ai pris la peine d'approfondir un peu le sujet et d'appliquer des algorithmes d'optimisation aux résultats trouvés ce qui m'a conduit à mettre au point la méthode présentée.

Pour donner une idée de ses performances, avec un ordinateur familial acheté il y a un an (Pentium 4 à 3 GHz) et en utilisant un programme Delphi affichant en mode graphique les meilleurs parcours obtenus :

Le défi des 250 villes est résolu en moyenne en 4 minutes avec un temps record inférieur à la seconde,
Le problème classique A280 de Ludwig est en moyenne résolu en moins de 2 minutes.

Défi des 250 villes : 2-opt optimisé

Je ne me suis aperçu que j'utilisais la technique 2-opt que très récemment en rédigeant cet article mais il me semble que je procède différemment de la manière traditionnelle.

Dans les articles portant sur le sujet, le 2-opt est surtout utilisé pour améliorer un parcours obtenu par une autre méthode d'approximation.
Pour ma part, j'applique le 2-opt sur un parcours quelconque pour ensuite améliorer le résultat par d'autres techniques, c'est pourquoi je parle de 2-opt optimisé qui est un pléonasme, le "opt" signifiant "optimisé" mais qui se justifie dans la mesure où il y a des optimisations postérieures à son utilisation.

La méthode

Elle comporte trois grandes étapes. Voici leur déroulement et, dans le cas du défi des 250 villes, la longueur moyenne du tracé obtenu (le minimum est 11,8093) :

Un parcours quelconque calculé de manière aléatoire est choisi (longueur moyenne 130),
Le parcours est optimisé par la technique de décroisement (longueur moyenne 13),
Des altérations du tracé sont effectuées par permutations de segments (flips). Après décroisement et améliorations locales, le nouveau tracé est conservé à la place du précédent s'il est meilleur que celui-ci et de nouvelles tentatives d'optimisation par altérations du tracé sont effectuées.

Dans ce qui suit, j'utiliserais les notations I₁, I₂, I₃, ... pour indiquer les successeurs d'un point I dans le parcours.

Technique de décroisement

Rechercher une condition précise sur les points qui prouverait un croisement de deux segments serait une opération délicate et très coûteuse en temps, par contre, si un parcours est croisé, une propriété est facile à vérifier.

Si II₁ et JJ₁ sont croisés, d'après l'inégalité triangulaire : IJ + I₁J₁ < II₁ + JJ₁

En prenant le problème dans l'autre sens, si IJ + I₁J₁ < II₁ + JJ ₁on obtient un trajet plus court en reliant directement IàJet I₁ à J₁.

Si les points sont numérotés de 0 à n-1 et si I est inférieur à J, le parcours :

0 - 1 ... I - I₁ - ... - J - J₁ - ... - n-1 est transformé en

0 - 1 ... I - J - ... - I₁ - J₁ - ... - n-1 c'est à dire que l'on a retourné la suite des points situés entre I₁etJ. Le trajet est optimisé en intervertissant deux points, d'où la dénomination de 2-opt.

On peut remarquer que la formule utilisée s'applique également à des cas pour lesquels il n'y a pas de véritable croisement (figure 2). Dans cette situation, l'optimisation croise le parcours tout en réduisant sa longueur (tracé en rouge). Un nouveau décroisement (tracé en bleu) améliore encore le parcours.

La formule n'utilise pas l'inégalité triangulaire et fonctionne très bien dans l'espace, situation où les croisements effectifs sont très rares. Elle est également valable dans un espace non euclidien où l'inégalité triangulaire n'est pas forcément vérifiée.

En appliquant la méthode à tous les couples de segments II₁ et JJ₁ vérifiant l'inégalité, le trajet est considérablement optimisé mais les "décroisements" peuvent provoquer d'autres croisements. Il faut donc répéter l'opération tant que l'on trouve des couples pour lesquels l'inégalité est vérifiée.

Tentatives d'améliorations par altération des tracés

Le parcours obtenu après un décroisement étant déjà assez bon, pour l'optimiser il est nécessaire d'employer des techniques n'agissant que sur une partie du parcours.

La méthode choisie a été d'intervertir deux points quelconques du tracé. Cette technique, utilisée dans d'autres algorithmes s'appelle un flip.

Sur les figures ci-contre, nous voyons l'effet du flip des deux points A et B lors d'une tentative dans le défi des 250 villes. On peut constater que le flip conserve une bonne partie du tracé mais provoque un nombre de croisements suffisant pour qu'il soit peu probable que le décroisement de la nouvelle figure ramène à la situation initiale

Améliorations des parcours obtenus par des méthodes locales

Les flips suivis de décroisements sont assez efficaces et permettent d'obtenir de bons résultats facilement mais le parcours optimal est rarement atteint.

Les résultats étant très proches de l'optimum dans le cas des 250 villes, il est légitime d'analyser les parcours obtenus un peu plus finement afin d'en corriger certains défauts.

Voici trois techniques que j'ai pu repérer mais il y en a probablement beaucoup d'autres.

Réordonner les villes proches

Une première approche consiste à calculer les longueurs obtenues en permutant plusieurs points consécutifs, par exemple pour 7 points I, I₁, I₂ I₃, I₄, I₅, I₆, il est possible de calculer les longueurs pour tous les tronçons I - I₆ obtenus en permutant les points I ₁ à I₅ (120 possibilités). Pour analyser l'ensemble d'un parcours de 250 villes, nous avons 250x120 calculs à effectuer ce qui n'est pas énorme. Le gain obtenu est de l'ordre de 0,5% pour le premier parcours décroisé mais a tendance à diminuer et devient pratiquement nul après avoir effectué un certain nombre d'améliorations du parcours par des flips.

Capturer des points proches

Dès une centaine de points les trajets sont souvent tortueux et des points éloignés dans l'ordre du tracé peuvent être assez proches en réalité. Par exemple, dans une situation comme celle ci-contre, je point J₁ peut être capturé et placé entre I et I₁. D'une manière plus générale :

si IJ₁ + J₁I₁ + JJ₂ < IJ₁ + JJ₁ + J₁J₂, J₁ doit être placé entre I et I₁.

Cette capture peut faire gagner 3% sur un premier parcours et elle continue à être intéressante après plusieurs améliorations par des flips. On peut la généraliser en capturant 2, voire plus de points mais les temps de calcul deviennent assez vite longs et les gains moins importants.

Modifier les ponts

Sur un parcours, on peut visuellement constater des étranglements que l'on peut considérer comme des ponts reliant des îles et il peut être intéressant de déplacer ces liaisons.

D'une manière générale, si L est entre I et J, si J est entre L et K et si :

IJ₁ + I₁J + K₁L + L₁K < II₁ + JJ₁ + KK ₁ + LL₁, on peut remplacer la séquence

I - I₁ - ... - K - K₁ - ... - J - J₁ - ... - L - L₁ par
I - J₁ - ... - L - K₁ - ... - J - I₁ - ... - K - L₁ce qui revient à intervertir les deux séquences I₁ - ... - K et J ₁ - ... - L.

Le gain obtenu est proche de 3% pour le premier parcours décroisé mais l'intérêt est beaucoup moins important par la suite et les calculs un peu longs.

Remarque :

Toutes ces techniques peuvent provoquer de nouveaux croisements du parcours, il faut donc les faire suivre d'un décroisement ce qui en augmente le coût en temps de calcul.

Gestion des minimums locaux

Le parcours présenté ci contre est fréquemment atteint dans le problème des 250 villes, plus fréquemment que le parcours optimum. La différence de longueur entre les deux parcours est négligeable ( inférieure à 1/1000^ème) et l'on peut facilement se convaincre qu'un simple flip suivi d'un décroisement ne peuvent permettre de passer du premier au second. Dans la mesure où seul un parcours meilleur que le précédent est accepté, nous sommes bloqués.

La situation présentée ici et un peu caricaturale car c'est un des meilleurs parcours possible mais dans le cas de notre problème il y a des centaines, voire des milliers de minimums locaux, certains étant assez éloignés de la bonne solution.

D'une manière générale, si en effectuant de nombreux flips un parcours ne peut être amélioré, la solution trouvée est un minimum local pour la technique utilisée.

Optimum local : 11.81308

Optimum : 11.80932

La présence de minimums locaux n'est pas particulière à cette méthode et se retrouve avec tous les algorithmes d'approximation. Lorsqu'un tel minimum est rencontré, il n'y a que deux solutions :

Effectuer une opération un peu plus traumatisante qu'un simple flip et accepter de continuer avec un parcours un peu moins bon que le précédent.
Abandonner et repartir sur d'autres bases,

Dans le cas qui nous concerne, j'ai trouvé deux solutions pour sortir d'un minimum local :

Effectuer plusieurs flips sur des points proches (par exemple permuter I et J, I₃ et J₃ ainsi que I₆ et J₆).
Casser un pont.

Pour comprendre cette deuxième technique, il suffit de regarder le parcours mesurant 11.81308 affiché ci-dessus. On constate que sa différence principale par rapport au parcours idéal est lié à la présence du pont placé vers le milieu de la figure. Casser ce pont permet de repartir sur d'autres bases et permet d'espérer arriver au parcours optimal.

Pour ma part, la sortie d'un minimum local pouvant être assez longue et ne garantissant pas un résultat rapide, je préfère abandonner et passer à un autre parcours initial.

Programmes et algorithmes

Vous trouverez ci-joint, sous forme compressée, les sources et les programmes écrits en Delphi et en Java que j'ai réalisé pour tester et préparer cet article :

L'applet Java présentée ci-dessus

Le programme correspondant en Delphi

Les deux programmes sont écrits selon le même principe et sont paramétrables, ils sont accompagnés de plusieurs ensembles de villes, ce qui permet de les utiliser aussi bien avec le défi des 250 villes qu'avec d'autres circuits plus classiques.

Cas d'un nombre de villes important

Les programmes présentés ci-dessus utilisent des nombres réels (sur 10 octets) afin de pouvoir traiter le défi des 250 villes mais ils ne peuvent convenir pour un nombre de villes vraiment important. A titre d'exemple, pour essayer de traiter le problème des 13 509 communes de plus de 500 habitants des Etats-Unis, j'ai non seulement du arrondir les valeurs aux entiers les plus proches mais également diviser le distances obtenues par 1 000 pour cantonner les résultats à des valeurs sur 2 octets. En effet, avec ce nombre de villes et 2 octets par distance, le tableau des distances occupe 13 509² x 2 octets soit environ 360 Mo ce qui est pratiquement le maximum que je peux placer en mémoire vive dans mon ordinateur personnel.

Je n'ai aucun élément pour apprécier la qualité des résultats obtenus mais voici ci-dessous le premier parcours obtenu (21 082 000 après 14 minutes de calcul). Au bout de 2 h 30, j'atteins 20 899 000 alors que le meilleur parcours possible mesure 19 947 008.

Jean-Luc Juveneton : Ingénierie Educative - CRDP - Grenoble (38) / imel@ac-grenoble.fr / 12 avril 2005