184
Recherche opérationnelle
où les deux principaux paramètres contrôlant le système (Ant System) sont
. Ils représentent l’importance relative de l’intensité de la piste,
, et
de visibilité,
.
Si = 0, seule la visibilité de la ville est prise en compte ; la ville la plus proche
est donc choisie à chaque pas. En revanche, si
, seules les pistes de
phéromone jouent (les fourmis sont aveugles).
- Règle (1) de distribution des phéromones. Après un tour complet, les fourmis
déposent, sur l’ensemble des arêtes parcourues, une quantité de phéromone
. Cette quantité est une fonction de la qualité de la solution trouvée :
où
est la chaîne parcourue par la fourmi
à l’itération ,
la
longueur de la chaîne, un paramètre de réglage (souvent du même ordre que
la longueur).
- La règle (2) de disparition des pistes de phéromone permet de ne pas tomber
dans des solutions optimales locales, les mauvaises solutions disparaissent
ainsi pendant l’exécution de l’algorithme. A la fin de chaque itération, la règle
de mise à jour des pistes de phéromone est la suivante :
où
un paramètre de réglage. La quantité initiale
de phéromone sur les arêtes est une distribution uniforme de petites quantités
.
Algorithme Ant System – Traveling Salesman Problem
Données :
: Nombre de sommets (villes) dans le graphe ;
, Ensemble d’arêtes (trajets) reliant les sommets (villes) ;
: (
le nombre de fourmis ;
: Quantité de phéromone initiale ;
Initialisation :
;
Placer arbitrairement chaque fourmi sur une ville
Pour chaque
Pour chaque
Construire un chemin
selon la règle de transition (1)
Calculer la longueur
de ce chemin
Soit
le meilleur chemin trouvé et
la longueur correspondante ;
Mettre à jour les traces de phéromones suivant la règle (2) ;
Retourner et