Préface

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

pic

Algorithme

Description générale

pic

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:

pic

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:

pic

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:

pic

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:

pic

Code

The implementation of algorithme can be found here:

ant