Discussion :

[mathchok]

Bonsoir!

je cherche à modéliser la phéromone sur un environnement de simulation, avec JAVA? avez vous une idée?

Merci pour votre aide

[Davidbrcz]

Le principe de la colonie de fourmis repose sur le fait que plus un chemin est court vers la nourriture plus celui ci est attractif.
Il va donc en un même temps être plus parcouru et donc plus attractif au détriment des autres qui vont devenir de moins en moins attractif car de moins en moins parcourus.

Pour implémenter ceci, je verrais bien un système A*-like où chaque case du monde mon aurait à la place de l'heuristique sur la distance le poids des phéromones. Ce poids diminuerais naturellement au cours du temps mais serai augmenté à chaque passage d'une fourmis sur la case. Ainsi, plus le poid des phéromones est élevé, plus la case a un poind faible vis à vis de de A*.

[ToTo13]

Bonjour,

je suis d'accord avec ce qui vient d'être marqué précédemment, mais je crois qu'il faut ajouter quelques précisions :
- si une fourmi trouve de la nourriture, elle retourne immédiatement à la fourmilière en laissant plus de féromones que d'habitude.

[Matthieu Brucher]

Sauf qu'on ne sait pas où est la nourriture, donc pas possible d'utiliser A*.

A chaque instant, la fourmi peut se déplacer dans une direction probabilisée par la densité de phéromones autour d'elle. A chaque instant, elle en dépose là où elle passe. Et comme le dit ToTo13, une fois qu'elle a trouvé de la nourriture, elle part en chemin inverse en déposant potentiellement plus de phéromones.

[Davidbrcz]

On peut utiliser A*, il suffit de rendre aléatoire la case d'arivée. Et si en chamin on trouve de la nourriture, on déplace la case d'arrivé sur la case actuelle.
Sinon, on peut parcourir de facon vraiment aléatoire le monde jusqu'a trouver de la nourriture.

[Matthieu Brucher]

Ce que tu proposes, c'est juste du sucre supplémentaire pour indiquer qu'on se balade dans la nature. Sauf que tu favorises une arrivée qui ne devrait pas l'être puisque ce n'est pas forcément de la nourriture et ce n'est pas donc pas optimal.
De plus, la colonie de fourmis n'a pas la possibilité de connaître un chemin d'arrivée. Ce n'est pas le principe des fourmis qui ont un horizon très très restreint. Dans les algos de fourmis plus complexes, tu ne verras jamais ce principe de connaître un point très loin vers lequel tu te diriges.

Ce que je propose :
- tu places tes fourmis à la sortie de la(les) fourmilière(s) dans des directions aléatoires
- la nouvelle direction de la fourmi est fonction de la direction de la fourmi actuelle (par exemple une loi de Laplace symétrique) + des phéromones (gaussienne) pour réorienter la fourmi vers les chemins avec phéromones.

L'intérêt, c'est que la direction principale sera tout droit, mais avec du bruit en plus. En revanche, une fois qu'un chemin existe, le lissage de la direction avec les phéromones permettra de créer au fur et à mesure un chemin optimal.