Autres méthodes de résolution

Les colonnies de fourmis

Introduction

Il existe un algorithme s'inspirant du comportement des fourmis inventé en 1996 par Marco Dorigo à l'Université Libre de Bruxelles. Il se base sur quelques observations :

• les fourmis déposent des phéromones sur leur chemin
• elles suivent le chemin marqué par cette substance
• le chemin le plus marqué est préféré
• les phéromones s'évaporent avec le temps
• si on pose un obstacle coupant un chemin de phéromones, les fourmis le contour-nent par un côté au hasard.

A un instant donné, une plus grande quantité de phéromones sera déposées sur le chemin le plus court. Ceci est dû au fait que les fourmis ayant choisi ce chemin auront déposé leur phéromone en premier. Celles qui traversent le passage dans l'autre sens y trouveront plus de phéromones à cet instant.

L'algorithme

L'algorithme peut être décris de la manière suivante :

• on créé un ensemble de fourmis
• la quantité de phéromones déposée est stockée dans un tableau de taille $n\times n$, chaque indice correspondant à une ville
• pour chaque fourmi :
  • on place la fourmi sur une ville au hasard
  • elle choisie une ville parmi celles qui n'ont pas encore été visitées
  • elle s'y rend en suivant le chemin le plus marqué par les phéromones
  • elle dépose des phéromones sur le chemin
• on fait évaporer une certaine quantité des phéromones sur l'ensemble des chemins

Conclusion

L'efficacité de cet algorithme dépend de la quantité de phéromones déposées par une fourmi et la vitesse à laquelle elles s'évaporent. Ces deux paramètres sont réglés arbitrairement.

Recherche tabou

Il s'agit de déterminer aléatoirement une solution initiale $I$, ensuite d'extraire la solution la meilleure dans le voisinage de $I$ (par un balayage exhaustif du voisinage) et ensuite de recommencer le procédé avec cette nouvelle solution possible[10].

Voisinage $\lambda$-opt

$\lambda$-opt est un échange de $\lambda$ paires d'arêtes. On enlève $\lambda$ arêtes de la tournée afin de les remplacer par $\lambda$ autres pour obtenir une tournée. Une tournée qui n'est pas améliorable par l'agorithme $\lambda$-opt est dite optimale. Pour un problème à $N$ villes, une tournée optimale est $N$-optimale. Rozenkratz, Stearns et Lewis ont prouvé en 1997 qu'une tournée $\lambda$-optimale pour une tournée à $n$ villes pouvait être $(2-2n)$ fois plus longue que l'optimum. Donc $\lambda$-opt peut converger vers un point qui est loin de l'optimum.

Lin et Kernighan

Lin et Kernighan ont proposé d'adapter la taille de l'échange à chaque pas de l'algorithme. La généralisation de ce principe sert de base à un algorithme approximatif très efficace. C'est l'algorithme de Lin Kernighan implanté en $1971$. Il semble suivre une complexité $O(n^{2,2})$.

L'idée générale de l'algorithme consiste à définir une chaine d'arêtes à partir d'une séquence de sommets. On échange les arêtes paires de cette chaîne par ses arêtes impaires de manière à obtenir une tournée réalisable. On agrandit de proche en proche la chaîne alternée jusqu'à atteindre un cycle. Un mouvement $\lambda$-opt peut se définir sous forme de cycles alternés. La recherche d'une amélioration locale est effectuée par la recherche arborescente dans l'arbre des chaînes alternées. Cela est fait par l'exploration de l'arbre des possibilités avec certaines restrictions et retour-arrière. Le choix des arêtes pour l'insertion est effectuée à partir de l'ensemble des arêtes candidates. Keld Helsgaun a implanté une amélioration de cette algorithme. Il a notamment proposé d'utiliser la mesure d'$\alpha$-sensibilité pour choisir les candidats.