Professeur responsable : M Michel Van Caneghem

Le 28 avril 1998

Sommaire

Le projet ............................................................................................................................................................................ 2

Présentation de l’ACS............................................................................................................................................... 3

Les déplacements :................................................................................................................................................... 3

Les phéromones :........................................................................................................................................................ 4

Initialement :................................................................................................................................................................ 4

Localement :................................................................................................................................................................. 4

Globalement :............................................................................................................................................................... 4

L’algorithme............................................................................................................................................................... 5

Test de minimalité, distance et précision................................................................................................ 5

Les Résultats.................................................................................................................................................................. 6

Expérimentation Reflexion ................................................................................................................................. 7

Le code ............................................................................................................................................................................... 8

Le projet

A la fin de notre cours de programmation complexité, nous avons eu à faire un tp nous permettant de mettre en application les théories acquises. Ce projet consiste à faire parcourir l’ensemble des villes à un voyageur de commerce en utilisant les mœurs d’une colonie de fourmis.

Ce projet s’est fait en plusieurs étapes. Il nous à fallu dans un premier temps comprendre les mécanismes de l’algorithme ACS (ant colony system).

Présentation de l’ACS

La biocybernétique des fourmis est de minimiser le chemin lors de leurs quêtes de nourriture. Pour se faire-elles déposent une phéromone lors des déplacement :

Il y a deux types de phéromone : une phéromone locale qui sera déposée à chaque déplacement et une phéromone globale qu’une fourmi virtuelle déposera sur le chemin le plus court.

Les déplacements :

Les déplacements sont choisis suivant une probabilité q. Nous choisissons aléatoirement un nombre que nous comparons avec q0 où q0 est le résultat de l’accumulation d’expérimentation

Si q £ q0 nous maximisons la fonction rech(v_k,u) ou v_k est la ville où se trouve la

fourmi et u les villes où elle n’est pas encore allée.

Nous définissons rech() par :

Sinon Nous définissons les probabilités p_k(u)

comme suit :

En pratique le dénominateur étant constant nous calculons p1_k (u)

Nous choisissons aléatoirement un nombre q1 compris entre 0 et p1_k(max.) avec max. la dernière ville non visitée.

Les phéromones :

Les phéromones sont déposées localement et globalement . Localement une quantité de phéromone sera ajoutée à chaque déplacement c’est à dire entre la ville d’où nous venons et la ville où nous allons et inversement car nous avons choisi l’émission d’une phéromone bidirectionnelle. Globalement une fourmi virtuelle parcourra le chemin mémorisé le plus court afin d’y déposer une quantité de phéromone globale ( pour simplifier nous n’avons pas tenu compte de l’évaporation des phéromones au cours du temps )

v_k est la ville où se trouve la fourmi et u la ville où elle va.

t₀ est la phéromone de base définie plus loin

L_meilleur est le chemin le plus court trouvé

L_glouton est la distance calculée par l’algorithme du glouton

N est le nombre de ville

a est un coefficient de communication ... (!!)

r est une constante de persistance 1-r une constante d’évaporation de la phéromone par rapport au nombre de passage nous l’avons fixé à 0,1

Initialement :

Localement :

Globalement :

L’algorithme

Chargement des données tsp

Calcul des distances

Choix aléatoire d’une ville de départ pour le glouton

Calcul du glouton

Initialisation de la phéromone dans chacune des villes

Choix des villes de départ parmi N, pour les fourmis M fourmis, 1 fourmi par ville une redistribution à chaque itération pourrait être envisagé ...

For iter :=1 to NbIter

For u :=1 to N

For v_k :=1 to M

Choix de la prochaine ville pour la fourmi v_k

Dépôt de la trace locale

End

End

Choix de la fourmi ayant pacouru le plus court chemin dans cette itération

Test de minimalité avec cette fourmi et la turbofourmi

Dépôt de la trace globale avec la turbofourmi

End

Turbofourmi : fourmi virtuelle ayant courru le plus court chemin sur l’ensemble des iterations

NbIter est une constante à partir de laquelle nous estimons la solution trouvé satisfaisante.

Test de minimalité, distance et précision

Les résultats sont dans certains cas sensiblement différents selon la précision choisie.

Nous avons eu besoin de comparer nos résultats entre eux mais surtout avec ceux déjà trouvés sur ce type de problème.

Notre algorithme calcule dans un premier temps les distances entre chaque ville en entier et en réel. Nous avons choisi de calculer les distances suivant la norme euclidienne.

Dx=tabx[v]-tabx[u];

Dy=taby[v]-taby[u];

Dist(u,v)=sqrt(Dx*Dx+Dy*Dy);

Pour les distances entières nous avons pris comme convention :

Si ( Dist(u,v)-(long)Dist(u,v) > 0,5 )

Alors Dist(u,v)=(long)Dist(u,v)+1

Sinon Dist(u,v)=(long)Dist(u,v)

Le test de minimalité intervient lorsque nous cherchons la distance minimale nous avons choisi de faire ce test en réel pour favoriser les fourmis aventurières en effet il peut exister des chemins différents mais ayant la même distance entière que le chemin minimum.

Attention : Pour la distance du chemin en entier nous avons conservé le test de minimalité en réel. Le turbochemin est recalculé en entier à la fin.

Les Résultats

Ces résultats ont été obtenus avec un colonie proportionnelle à 50% du nombre de ville. Q₀=0.94 a=r=0.1

eil51.tsp

D :429.117931179311793 Dint : 426 Iter : 198

Chemin :

21 16 50 34 30 9 49 10 39 33 45 15 44 42 19 40 41 13 25 14 24 43 7 48 6 27 51 46 12 47 18 4 17 37 5 38 11 32 1 22 8 26 31 28 3 36 35 20 2

eil76.tsp

D : 544.369053690536905 Dint : 538 Iter :1569

Chemin :

46 34 67 26 76 75 4 68 6 51 17 40 12 58 72 39 9 32 44 3 16 63 33 1 73 62 22 64 42 43 41 56 23 49 24 18 50 25 55 31 10 38 65 66 11 59 14 53 7 35 8 19 54 13 57 15 5 37 20 70 60 71 69 36 47 21 61 28 74 2 30 48 29 45 27 52

kprA100.tsp

D : 21285.443184431844318 Dint : 21282 Iter :888

Chemin :

33 37 5 52 78 96 39 30 48 100 41 71 14 3 43 46 29 34 83 55 7 9 57 20 12 27 86 35 62 60 77 23 98 91 45 32 11 15 17 59 74 21 72 10 84 36 99 38 24 18 79 53 88 16 94 22 70 66 26 65 4 97 56 80 31 89 42 8 92 75 19 90 49 6 63 1 47 93 28 67 58 61 51 87 25 81 69 64 40 54 2 44 50 73 68 85 82 95 13 76

d198.tsp

D : 15894.937969379693796 Dint : 15864 Iter :1408

Chemin :

112 106 107 111 110 109 108 167 168 182 183 181 177 175 176 173 174 198 197 196 195 194 179 178 180 184 185 187 186 193 192 191 188 189 190 171 128 170 127 129 137 172 166 165 164 163 151 150 162 152 149 148 153 161 160 159 158 157 156 155 154 139 138 134 140 142 147 146 145 144 143 141 136 135 133 132 131 130 126 125 169 124 123 120 119 118 117 121 122 116 115 104 103 102 93 94 101 95 96 90 89 97 98 88 83 82 75 62 53 46 36 37 32 31 38 45 54 61 66 74 70 67 60 55 44 56 59 68 72 73 84 87 99 100 86 85 71 69 58 57 43 42 41 13 12 11 10 9 8 5 4 3 6 7 2 1 40 14 15 16 17 18 19 20 21 24 25 26 27 22 23 29 30 28 33 34 35 39 47 51 52 65 81 76 77 78 64 50 48 49 63 79 80 91 92 105 114 113

Expérimentation Reflexion

Détermination du nombre d’itérations est étroitement lié à la saturation en phéromone d’une ville. Nous avons constaté qu’un grand nombre d’itérations n’apportait pas toujours de meilleur résultat. En effet si nous prenons 1 fourmi et un nombre d’itération infinie il y a peu de chance d’obtenir de meilleurs résultats qu’avec N=M fourmis et un nombre fini d’itération ce dernier dépendant alors du nombre de villes.

Détermination du nombre de fourmis quand nous avons un nombre faible de fourmis la saturation en phéromone a lieu rapidement sur certaines portions du graphe tandis que d’autres sont à peine explorées Il faut trouver un équilibre entre le nombre de fourmis et le temps mis pour chaque itération. Une nouvelle colonie pourrait être envisagé à chaque itération. Pour trouver en peu d’itérations une solution optimale nous choisirons de prendre Nb fourmis = Nb villes.

Détermination du chemin minimum par le glouton est primordial dans l’évolution de trace de phéromone en effet il permet de déterminer les phéromones initiales plus la distance du glouton est proche de la distance minimale et plus la situation évolue rapidement.

Choix des coefficients a r b : nous n’avons pas fait varier ces valeurs car leurs implications sur la quantité de phéromone nous ont paru bien difficile à interpréter malgré les publications de Doringo, Gambardella traitant du sujet. L’évaporation des phéromones au cours du temps n’a pas été implanté; r peut pallier cette absence puisqu’il traduit la persistance au cours des passages .

Choix de q0 seuil de probabilité pour les déplacements. Il semble avoir une influence marginale lorsqu’il varie peu cela se traduit par un vagabondage plus ou moins important en effet si q0 diminue les fourmis ne choisiront pas forcément le chemin le plus emprunté ou la ville la plus proche.

Nous n’avons pas utilisé la librairie TSP car nous avions déjà fait un système de récupération de donnée.