2.1°) Voyageur de commerce : Algorithm Ant System (AS)

La représentation d'une colonie de fourmie nécéssite de dissocier les éléments suivants:

• des noeuds disposant d'une posiion spacial
• des arcs reliant un niveaux de phéromone et une longuer (arriver/destination)
• des fourmis avec une mémoire (noeud parcourus, paramètre aléatoire, …)

Le voyageur de commerce est un problème NP-complet. La méthaphore de la colonisation de fourmis s’y applique particulièrement bien. Ces caractéristique forme un graph (non orienter) et permete la recherche de circuit ou de “plus court chemain” suivant les caractéristiques du graphe. Le domaine d'étude seras limiter au graphs disposant d'une des propiétées suivante:

• graphe complets (recherche de circuit hamiltonien le plus court : TSP)
• graphe connecter (recherche de chemin élémentaire le plus court : )

2.2°) Conventions

la quantiter de phéromones et la longeurs des arcs influent sur le comportement aléatoire des fourmis suivent la formule:

• $ω + \frac{phéromone^β}{length^α}$ (valeurs par défault : ω=0 ; α=1; β=3)
• les fourmis ce déplace en cycle et parcours toutes un arcs par itération
• le niveaux de phéromone est évaporé a la fin de chaque cycle
• chaque fourmis à la mémoire du cycle (liste des noeuds et des arcs parcourus)
• chaque fourmis vide ça mémoire à chaque nouveaux cycle

2.3°) Choix d'implémentation

• Contrainte:
  • les fourmis doivent être indépendante, et sans synchronisation
• Solution:
  • les fourmis ne ce déplace plus en terme de cycle mais en fonction du temps
  • les foumis déposes continuèlement une infime quantitées de phéromone
  • les phéromones s'évapores continuèlement en infime quantitées quand une fourmis passe
  • le premier parcourt suite une propagation homogène (répartition égale des fourmis)
  • les fourmis parte toutes du même noeud
• Choix: Les arcs sont considéré comme des ensembles, on peut alors considéré des opération de base tel-que l'union, la disjonction, et la division qui permetron de distinguer
  • les arcs parcourus d'une fourmis
  • les arcs à parcourir au prochain “pas” pour un fourmis
  • les arcs restant
  • si la fourmis rentre dans un chemin impossible

2.4°) Fonctionement de l'algorithme

Si une fourmis ce déplace alors

    fourmis.déplacer(min(1, arcs.reste()));
    arcs.ajouter_pheromone();
    
sinon si (cherche_chemin et dernier(fourmi.chemin) = fourmi.cible) ou
         (cherche_cycle et taille(fourmi.chemin) = taille(ville)) alors

    si longueur(fourmi.chemin) <longeur(meilleur) alors
        meuilleur = fourmi.chemin;
    fin si
    evaporer(fourmi.chemin);
    fourmi.reinitialiser();

sinon

    # exclusion des arcs donc une des deux ville a déjà été parcourus
    arcs_disponible = connecter(fourmis);
    
    si taille(arcs_disponible) = 0 alors
        # le graph n'est pas complet
        fourmis.chemin.evaporer();
        fourmis.reinitialiser(mutation);
        fourmis = fourmis.suivante;
    fin si;
    
    fourmis.arcs_courent := distribution_discrete(
        random(), arcs_disponible,
        fourmis.tendance
        # tendance : calcule le poid de distribution de chaque arcs
        # en fonction des parametres ω;  α;  β de la fourmis actuelle
    );
    
    ajouter(fourmis.visiter, fourmis.cible);
    fourmis.cible := fourmis.arcs_courent.desitnation;

fin si;

Fourmis.reinitialiser() is
begin
    si system.mutation alors
        alpha := random(1..10);
        beta := random(1..10);
    fin si;
    
    gamma := system.facteur_aléatoire;
    chemin := vide();
    visitre := vide();
end ;     

arc.ajouter_pheromone(F : fourmis) is
begin
    // EVAPORATION_RATE = 0.001f
    level += 1.f / longuer(fourmis.arcs);
end ;

arc.evaporer() is
begin
    // EVAPORATION_RATE = 0.001f
    level *= 1.f - EVAPORATION_RATE;
end ;