Colonie de fourmis
Les algorithmes à base de colonie de fourmis permettent de résoudre des problèmes statiques et offrent un haut degré de flexibilité et de robustesse dans des environnements dynamiques. La colonie s’adapte aux brusques changements d’environnement et continue de fonctionner lorsque certains individus échouent à accomplir leur tâche.
La principe de colonie de fourmis est simple. Les fourmis sont capables de sélectionner le plus court chemin pour aller du nid à une source de nourriture grâce au dépôts et au suivi de pistes de phéromone. Ces dernières sont déposées par les fourmis sur leur chemin. Une fourmis a tendance à suivre la piste ayant l’impact de phéromone le plus élevé. Les phéromones se dissipent dans le temps (pas dans toutes les versions de l’algorithme). On en conclut donc qu’après un temps, les fourmis choisiront toutes la pistes la plus courte entre le nid et la nourriture.
Optimisation de colonie de fourmis
L’algorithme fut introduit par M. Dorigo en 1991, initialement prévu pour le TSP (voyageur du commerce). On représente le problème à résoudre sous la forme de la recherche d’un plus court chemin dans un graphe.
La structure de l’algorithme de colonie de fourmis est la suivante :
- Initialiser
- Répéter jusqu’à max cycles
- Chaque fourmis construit une solution
- Améliorer les solutions par recherche locale
- Récompenser les meilleures solutions en ajoutant de la phéromone
- Évaporer les traces de phéromone
Les algorithmes de types ACO possède des preuves de convergence qui ne seront pas montrées dans ce cours.
Initialisation (cas du TSP)
Les m fourmis sont réparties aléatoirement sur les n villes. Pour chaque fourmis, une liste tabou lui est attribué, elle contient sa liste de départ. Les pistes de phéromones sont initialisées sur une valeur c positive non nulle. Chaque arête du graphe ij possède sa piste de phéromones noté Tij=c.
Construction de la solution et recherche locale
Une fourmis k placée sur une ville i à l’instant t choisit sa ville de destination j en fonction de :
- La visibilité de cette ville nij (la distance dans le cas du TSP)
- La quantité de phéromone Tij(t) déposée sur la piste.
Le choix est aléatoire selon une probabilité où deux paramètres a et b contrôlent l’importance relative à la visibilité et la quantité de phéromones. Si b=0, les villes les plus proches ont plus de chances d’être sélectionnées, il s’agit d’un algorithme glouton. Si a=0, seule l’amplification des phéromones agit, il a y convergence prématurée et non optimalité des résultats.La nouvelle ville est rajoutée à la liste tabou de la fourmis.
Chaque fourmis procède de cette façon jusqu’à parcourir toutes les villes.
Fin d’un cycle
Pour chaque fourmis k, on calcule la longueur de son tour Lk(t) puis on vide sa liste-tabou (sauf initialisation).
Puis les pistes de phéromones sont mises à jour :
Tij(t+1)=p*Tij(t)+pheromonesij(t) avec p entre 0 et 1 et pheromonesij(t) la quantité de phéromone déposée par les fourmis sur l’arête ij au cycle t.
L’évaporation de la piste est calculé directement dans la formule précédente. En effet p représente la persistance de la piste, c’est à dire la mémoire de la quantité de phéromones que l’on garde pour le cycle suivant. Si p=1, il n’y a pas d’évaporation donc pas de limitation du phénomène autocatalytique. Si p=0, le système est sans mémoire, on ne tient compte que du dernier cycle effectué.
Pour chaque fourmis k passant par l’arête ij, elle incrémente la quantité de phéromone déposée selon le calcul suivant :
pheromonesij(t) += Q/Lk(t) où Q représente un quota de phéromones attribué à chaque fourmis (souvent Q=100). L’idée est d’approvisionner tout le chemin parcouru par une fourmis de façon homogène en phéromones.
On garde en mémoire le plus petit tour s’il est meilleur que le dernier mémoriser. Les fourmis recommencent un cycle à partir de leur ville initiale (gardée dans leur liste-tabou).
Variantes de l’algorithme : MMAS
Le Max-min ant system (MMAS) est une variante efficace de l’algorithme. Seuls les meilleures fourmis tracent des pistes où le dépôt de phéromones est limité par une borne supérieure et une borne inférieure. Ainsi on empêche une piste d’être trop renforcée et on laisse la possibilité d’explorer n’importe qu’elle piste. Cela évite notamment une convergence prématurée.
FR 
EN 
ES