Les méthodes de résolution du problème du voyageur de commerce

Algorithme de la colonie de fourmis (ant colony)

Cette méthode a été inventée en 1996 par Marco Dorigo de L'Université Libre de Bruxelles.
L'idée initiale provient de l'observation des fourmis. Celles-ci ont la capacité de trouver le chemin le plus court entre leur nid et une source de nourriture en contournant les obstacles qui jonchent leur chemin.

Vous pouvez faire l'expérience suivante : Vous avez remarqué que les fourmis se déplacent "en ligne", suivant le chemin des fourmis précédentes. Placez maintenant un obstacle sur cette ligne (une pierre ou une grosse brindille, par exemple), de manière à ce que le contournement de l'obnstacle par un côté soit nettement plus court que par l'autre. Au bout d'un certain temps vous verrez que toutes les fourmis contourneront l'obstacle par le côté le plus court.

Le phénomène s'explique de la manière suivante : les fourmis déposent en marchant des marqueurs chimiques appelés phéromones. Les autres fourmis suivent le chemin tracé par ces phéromones. Plus un chemin est marqué, plus elles ont tendance à le suivre. Lorsque l'on pose l'obstacle, le chemin de phéromones est coupé, et les fourmis choisissent au hasard l'un ou l'autre côté pour contourner l'obstacle.

Comme un chemin est plus court, plus de fourmis auront franchi l'obstacle en passant par ce côté. Par exemple, sur 6 fourmis, 3 fourmis pourront être passées par le côté court alors que les 3 fourmis ayant passé par le côté long n'auront pas encore fini de contourner l'obstacle. Une fourmi arrivant en sens inverse verra donc plus de phéromone sur le chemin qui passe par le côté court, et prendra donc ce chemin.

Les fourmis rouge ont pris un plus court chemin, plus ont franchi l'obstacles, donc plus de phéromones ont été déposées du côté rouge que du côté noir. La fourmi bleue venant de l'autre sens choisira donc le côté rouge.

En transposant informatiquement cette méthode et en l'adaptant au PVC, on obtient l'algorithme suivant (proposé par Marco Dorigo pour son logiciel ACS) :

• On crée un ensemble d'agents (les fourmis, à rapprocher aux "individus" des algorithmes génétiques), qui coopèrent par l'intermédiare des phéromones pour trouver les chemin le plus court du TSP.
• Les phéromones sont modélisées par un tableau de taille N x N (avec N le nombre de villes).
  Par exemple :

  float Phéromone[N*N];

  Phéromone[i, j] représente la quantité de phéromones déposées par les fourmis sur le trajet reliant la ville i à la ville j.
• Le comportement des fourmis est modélisée ainsi :
  • La fourmi se place initialement sur une ville choisie au hasard
  • Elle choisie la ville suivante parmi les villes non encore visitées en suivant le chemin le plus marqué par les phéromones

        max_phéromone = 0;
        Pour Ville_courante allant de 1 à N
          Si Ville_courante pas encore visitée
            Si Phéromone[Ville_précédente, Ville_courante] > max_phéromone
              Ville_suivante = Ville_courante
              max_phéromone = Phéromone[Ville_précédente, Ville_courante]
          FinSi
        FinPour
        

  • Elle dépose des phéromones sur le chemin qu'elle a emprunté (règle locale de mise à jour des phéromones). On prend en compte l'"évaporation", ce qui donne une loi du genre :

          Pheromone[i, j] = (1 - alpha) Pheromone[i, j] + alpha * K
        

    Avec K une constante. La valeur de K recommandée par Dorigo et Gambardella est de 1 / ( N * Lmv ) avec N le nombre de villes du problèmes et Lmv la longueur du trajet calculé par la méthode du meilleur voisin ou une approximation.

Il faut faire des essais pour déterminer les valeurs optimales des différentes constantes (nombre de fourmis, alpha, K...)

En termes de performances cet algorithme est comparable à un algorithme génetique.