Discussion :

[momento85]

je suis entrain de faire une adaptation de l'algorithme colonie de fourmi, pour la recherche du plus court chemin dans une arborescence ( j'ai un point de départ , qui mène à plusieurs points d'arrivés )

voila mon problème :

Si je lance les fourmis une première fois à partir du point de départ , vu qu'il n'y a pas encore de phéromones , logiquement elles vont se diriger à chaque fois vers le voisin le plus proche (où visibilité est la plus faible ,d'après la formule des probabilité), "mais le chemin ou la sommes des visibilité de proche en proche est la plus faible , ne veux pas dire forcément que c'est le plus court chemin" . Une fois le premier chemin trouvé , il sera marqué par les phéromones.

A la prochaine itération , les fourmis auront tendances toujours à suivre ce chemin ,parce qu'il est doublement avantagé (d'une par parce que c'est le chemin où la visibilité de proche en proche est la plus petite, et d'autre part il est phéromoné ) .et donc mon réseau ne sera pas exploré totalement .

j'ai du mal à écrire un raisonnement , de tel manière à ce que la fourmi , ne soit pas influencé que par la visibilité, dans le cas ou le chemin n'a pas été encore exploré .

[benDelphic]

Je ne voix pas pourquoi tu fais appel à une méta heuristique sur un problème qui peut être résolu de manière très efficace et en un temps polynomial ?

[Clercq]

Bonjour,

J'avoue que je rejoins benDelphic, disons que je ne sois pas sur que la technique des fourmis soit la plus appropriée pour le problème du plus court chemin.

Mais si tu veux absolument utilisé cette technique qui est "jolie" à mon gout, je pense que tu doit faire abstraction des voisins les plus proches. Tu dois utiliser le principe, ou plutôt le compromis "Exploration / Exploitation". Chaque fourmis à une probabilité de choisir d'explorer l'environnement et une probabilité (complémentaire) d'exploiter les phéromones déposer par ses consoeurs. Le but étant de trouver le plus court chemins, mais mes connaissances dans cette technique étant lointaine, je dirais que le temps de conservation des phéromones devrait être proportionnel à la longueur du chemin connu après l'avoir exploré, quelque chose du genre.

Toujours est t'il que si tu as les connaissances à priori sur les voisins les plus proches, autant utiliser du bellman ou tout autres algorithmes de plus court chemin plus efficace que les fourmis.

Clercq.