Algorithme de colonies de fourmis
Dec 8, 2013
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:
- une fourmi choisit un trajet, et trace une piste de phéromone.
- l’ensemble des fourmis parcourt un certain nombre de trajets, chaque fourmis déposant une quantité de phéromone proportionnelle à la qualité du parcourts.
- chaque arête du meilleur chemin est plus renforcée que les autres.
- 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: