5.4. Optimisation par colonies de fourmis
Le problème du voyageur de commerce (Travelling
Salesman Problem, TSP) a fait l'objet de la première
implémentation d'un algorithme de colonies de fourmis : le [Ant Syste
(AS)] [34].
Le problème du voyageur de commerce consiste à
trouver le trajet le plus court (désigne par «tournée»
ou plus loin par «tour») reliant n villes données, chaque
ville ne devant être visitée qu'une seule fois. Le problème
est plus généralement défini comme un graphe
complètement connecte , ou les villes sont les noeuds N et les trajets entre ces
villes, les arêtes A.
5.4.1. Algorithme
de base
Dans l'algorithme AS, à chaque itération , chaque fourmi  parcourt le graphe et construit un trajet complet de  étapes (on note
 le cardinal de l'ensemble N). Pour chaque fourmi, le trajet entre une
ville i et une ville j dépend de :
La liste des villes déjà visitées, qui
définit les mouvements possibles à chaque pas, quand la fourmi k
est sur la ville i :  ;
L'inverse de la distance entre les villes :  , appelée visibilité. Cette information
«statique» est utilisée pour diriger le choix des fourmis vers
des villes proches, et éviter les villes trop lointaines ;
La quantité de phéromone déposée
sur l'arête reliant les deux villes, appelée l'intensité de
la piste. Ce paramètre définit l'attractivité d'une partie
du trajet global et change à chaque passage d'une fourmi. C'est, en
quelque sorte, une mémoire globale du système, qui évolue
par apprentissage.
La règle de déplacement (appelée
«règle aléatoire de transition proportionnelle» par les
auteurs) est la suivante :
 (5-1)
Ou  et  sont deux paramètres contrôlant l'importance relative de
l'intensité de la piste,
 , et de la visibilité . Avec , seule la visibilité de la ville est prise en compte; la ville
la plus proche est donc choisie à chaque pas. Au contraire, avec  , seules les pistes de phéromone jouent. Pour éviter une
sélection trop rapide d'un trajet, un compromis entre ces deux
paramètres, jouant sur les comportements de diversification et
d'intensification est nécessaire.
Après un tour complet, chaque fourmi laisse une
certaine quantité de phéromone
 sur l'ensemble de son parcours, quantité qui dépend de la
qualité de la solution trouvée :
 (5-2)
Où
 : est le trajet effectué par la fourmi  à l'itération
 : la longueur de la tournée et  un paramètre fixé.
L'algorithme ne serait pas complet sans le processus
d'évaporation des pistes de phéromone. En effet, pour
éviter d'être piégé dans des solutions sous
optimales, il est nécessaire de permettre au système
«d'oublier» les mauvaises solutions. On contrebalance donc
l'additivité des pistes par une décroissance constante des
valeurs des arêtes à chaque itération. La règle de
mise à jour des pistes est donc :
 (5-3)
Ou  et m est le nombre de fourmis. La quantité initiale de
phéromone sur les arêtes est une distribution uniforme d'une
petite quantité  .
La figure (5-3) présente un exemple simplifié de
problème du voyageur de commerce.
Fig. (5-3) : Le problème du voyageur du commerce,
les points représente les villes et l'épaisseur des arêtes
la quantité de phéromone déposée. (a) exemple de
trajet construit par une fourmi. (b) au début du calcul, tous les
chemins sont explorés. (c) le chemin le plus court est plus
renforcé que les autres. (d) l'évaporation permet
d'éliminer les moins bonne solutions.
| 
