Algorithme d'optimisation par colonie de fourmis

Version imprimable

Bonjour

Je souhaite coder un algorithme d'optimisation par colonie de fourmis, le plus simple possible, mais surtout, plutot que de recopier betement des sources, bien le comprendre.
J'ai donc chercher dans google, et trouvé sur http://web.archive.org/web/200208121...gorithmes.html
un début d'algorithme, que voici :
Code:

1 2 3 4 5 6 7 8 max_phéromone = 0; Pour Ville_courante allant de 1 à N Si Ville_courante pas encore visitée Si Phéromone[Ville_précédente, Ville_courante] > max_phéromone Ville_suivante = Ville_courante max_phéromone = Phéromone[Ville_précédente, Ville_courante] FinSi FinPour
et

Code:

Pheromone[i, j] = (1 - alpha) Pheromone[i, j] + alpha * K

Néanmoins je me pose toujours quelques petites questions:
- Lors de la première itération, les pheromones ne seront présentes nulle part. Comment les fourmis choisiront elles leurs villes de destination ? Au hasard ? Ou en fonction de la distance de cette ville par rapport à celle de départ ?
- Une fois que les fourmis ont visité chacune toutes les villes, que se passe t'il ? Le résultat est il trouvé, ou faut il réinitialiser les fourmis encore et encore ?
- Comment le plus court chemin est trouvé ? S'agit t'il des x chemins comportant le plus de phéromones ? Ou alors, au bout d'un certains nombre d'itérations, le chemin que les fourmis suivent ( en supposant qu'elles stockent en mémoire l'ordre des villes qu'elles visitent )

Merci
Floopy

07/11/2006, 19h07
borisd

Bonjour,

- lors de la première itération, si on veut appliquer le concept de l'algo tel quel, les fourmis se dirigent au pur hasard (cf remarque de fin)
- il faut attendre un nombre "suffisant" d'itérations avant d'avoir une bonne solution. Il est très probable que les fourmis atteindront toutes les villes, la première fois, par des chemins loins d'être bons. Ces chemins devraient s'affiner au fur et à mesure du temps
- le plus court chemin (en fait un bon chemin, pas forcément un des chemins optimaux) sera indifférement celui où les phéromones sont les plus présentes ou celui que les fourmis suivront, puisque après un certain temps, les fourmis suivront quasiment exclusivement un bon chemin, qui sera le plus balisé, les autres "mourant"

Je trouve plus joli de faire choisir par une fourmi la destination suivante selon une probabilité croissante avec le nombre de phéromones : ainsi, une destination avec peu de phéromones a quand même une chance d'être visitée, cela peut être important dans les premières itérations et pour la convergence à (très) long terme.

merci pour cette réponse. Donc si j'ai bien compris, l'algorithme pourrait ressembler à ça :

(je ne sais pas trop comment écrire un algorithme, donc j'espère que celui qui suit sera compréhensible )

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
Pour Iteration allant de i à N //N : nombre d'itérations voulu
    Pour Chaque Fourmi
        Remise A zero du chemin en mémoire
         Ville de depart : derniere ville visitée
    Fin Pour
 
    Pour Chaque Fourmi
        Tant que Toutes les villes ne sont pas visitee
            Ville_Choisie = -1; //Numero de la ville choisie
            Pour Ville_Testee allant de 1 à Nv //Nv : nombres de villes
                Si Ville_Testee pas encore visité par cette fourmi
                    K = Probalite;
                    Hasard(0,1) //Un nombre entre 0 et 1
                    Si Hasard < K alors
                        Ville_Choisie = Ville_Testee
                    Fin Si
                Fin Si 
            Fin Pour
            Deplacement(ville_choisie) //la fourmi va dans la ville choisie
        Fin Tant que
        Placer Pheromones
    Fin Pour
Fin Iteration
 
Probalite:
P = (alpha*Pheromones(i,j) * beta*Distance(i,j)) / somme(alpha*Pheromones(i,g) * beta*Distance(i,g))
Avec G les villes non visitées
 
( inspiré de [IMG]http://www.codeproject.com/cpp/GeneticandAntAlgorithms/image003.gif[/IMG]
mais je ne sais pas si j'ai très bien retranscrit la formule )
 
Placer Pheromones:
P=evaporation*Pheromones(i,j) + alpha * K

Faut il mieux placer les pheromones après chaque deplacement ou quand la fourmi a fini de faire son tour entier ?

08/11/2006, 15h03
borisd

Ton algo est parfaitement compréhensible :applo:

Attention, quand tu choisis le déplacement de la fourmi, tu dois choisir la ville de destination dont la probabilité calculée est la plus forte. Ton algo choisit la première ville dont la proba dépasse le seuil, et privilégie donc les villes de petit numéro.

[Edit]Tu peux envisager deux méthodes de gestion des phéromones :
- une gestion "temps réel", où tu poses les phéromones après chaque déplacement, et tu traites plusieurs fourmis à la fois (un déplacement fourmi 1, un déplacement fourmi 2...)
- une gestion "par tour", ou tu envoies tes fourmis une par une. Une fois qu'elles ont toutes fait leur tour, tu mets à jour les phéromones. Attention à l'application de ta formule de mise-à-jour dans ce cas, car l'évaporation ne concernera que les phéromones présentes à l'itération précédente.