Algorithme de colonies de fourmis

Préface

C’est mes reponses pour le cours Info-521:

Algorithme

Description générale

L’algorithme “Système formique” optimisant le problème du voyageur de commerce:

1. une fourmi choisit un trajet, et trace une piste de phéromone.
2. l’ensemble des fourmis parcourt un certain nombre de trajets, chaque fourmis déposant une quantité de phéromone proportionnelle à la qualité du parcourts.
3. chaque arête du meilleur chemin est plus renforcée que les autres.
4. l’évaporation fait disparaître les mauvaises solutions.

Description formelle

La régle de déplacement, appelée “règle aléatoire de transition proportionnelle”, est écrite mathématiquement sous la forme suivante:

Une fois la tournée des villes éffectuée, une fourmi k dépose une quantité de phéromone sur chaque arête de son parcours:

A la fin de chaque itération de l’algorithme, les phéromones déposées aux itérations précédentes par les fourmis s’évaporent de:

Et à la fin de l’itération, on a la somme des phéromones qui ne se sont pas évaporées et de celles qui viennent d’être déposées:

Code

The implementation of algorithme can be found here:

ant