Discussion :

[Yaya074]

Bonjour a tous.
Je suis en classe préparatoire BCPST et j'ai pris l'option informatique. Pour la fin de l'année, nous avons deux projets a monter, avec un thème et une trame imposée, mais une démarche libre.

Pour notre projet, nous devons simuler le comportement des fourmis. Je vous "donne" l’énoncé qui résume assez bien le phénomène.

Des fourmis ayant détecté une source de nourriture rapportent cette nourriture au nid en suivant au départ plusieurs chemins possibles, puis au bout d'un certain temps, l'un des chemins devient privilégié : c'est le plus court.
En fait les fourmis sont guidées pas la quantité de phéromones laissées par les précédentes. Sur le chemin le plus court, la fréquence de passage des fourmis est plus importante, ainsi le chemin le plus court est progressivement renforcé en phéromones et l'effet boule de neige assure la suprématie de ce chemin.

Simulation : les fourmis circulent sur un trajet rectiligne entre deux points lorsqu'un obstacle survient. Il y a alors deux chemins possibles pour contourner l'obstacle, l'un étant plus court que l'autre.

On cherche donc a faire un programme qui simule le comportement normal des fourmis.



Voila alors ce que j'ai fait :
J'ai modélisé les 2 chemins possibles par deux vecteurs a deux coordonnées : la longueur du chemin en premier, le nombre de phéromones sur le chemin. On peut ainsi obtenir le nombre de phéromones sur chaque "cases" du vecteur.

L=[l,pl] et C=[c,pc]
Avec l et c les longueurs des vecteurs L et C et pl et pc le nombre de phéromones.

J'ai aussi fixé qu'une fourmis faisais l'aller et le retour sur le même chemin.

Je pense mettre une part de hasard (avec la fonction random) pour les premières fourmis, jusqu'a ce que le nombre de phéromones atteigne un certain seuil (a ce moment là, les fourmis ne prendrais plus que le chemin court!)

Le problème, c'est qu'il faudrais une notion de temps, ou un compteur pour "montrer" que les fourmis sur le chemin court reviennent plus vite que celles du chemin long... Et là je ne vois pas comment faire!


Auriez vous des idées? Ma démarche est-elle bonne?

Merci!

[Bibistudio]

bonjour.
Mon niveau en IA n'est pas bon, mais une solution pourrait être
1 : au début tu a n fourmis qui parte de la fourmilière en mode recherche( une variable suffi genre 0 mode recherche 1 mode récupération de nourriture) chaque fourmi a une Phéromone différente( Constant : A,B, ect),elle se déplace de façon aléatoire , sauf qu'elle ne peuvent pas revenir sur leurs pas ou passer sur une zone ou il y a une Phéromone d'autre fourmi( sauf si le degré de phéromone et plus élever que 1, alors elle passe en mode récupération) .a chaque fois en mode recherche qu'une fourmi passe sur une case elle y met sa Phéromone et incrément le compteur de la case (genre intensité du Phéromone ) .
2: des qu'une fourmi voit de la nourriture(les case autour d'elle) elle vas dessus puis passe en mode 1 puis suit obligatoirement le chemin qui par de la nourriture qui a le degré de Phéromone le plus élever même si se n'est pas le sien( se qui peut permettre quand 2 fourmi trouve la même nourriture de revenir pas le plus cour chemin), car une fourmi ( en mode récupération )qui passe par un case qui contient son phéromone l’incrément (mais uniquement elle).
exemple:
une fourmi A arrive a de la nourriture, elle voit une case a A 1 elle repart sur son chemin donc une case autour de la nourriture vaut A 2.une autre fourmi B arrive a la même nourriture prend une portion puis regard autour de la nourriture et voit une case avec B 1 et une case avec A2 donc ça veut dire que a est aller plus vite donc elle choisi A2 . Mais incrément pas le degrés de phéromone du chemin A.

3: quand des fourmi en mode 1 arrive au nid elle font le même chois du chemin elle vont ver celui du degrés le plus élever car cela veut dire que la fourmi du chemin en question a trouver de la nourriture plus prêt.si il n'y a que des chemin de degrés 1 et qu'il n'y a plus de chemin de son propre phéromone elle repasse en mode 0 recherche

4: quand une fourmi en mode 1 ne trouve plus de nourriture ou de chemin elle reviens en arrière si ces son chemin elle enlève son phéromone( je c pas si cela est réaliste mais pour un programme ça colle ).

c'est une idée comme ça que j'ai us en voyant ton énoncer je pense qu'il y a plein d'erreur de raisonnement et je ne sait pas si ça colle avec de la vrai IA.

C'est peut être se que tu a dit mais comme moi et les vecteurs ça fait plusieurs (non pas 2 , plusieurs)ainsi que moi et le français beaucoup plus.

j'ai bien envi d'essayer aussi ,en C et SDL, je le montrerai au cas et j'aimerai bien voir le tient une fois fini aussi .

[250rgv]

Salut,

Je ne sais pas ce que tu est autorisé à faire ou non (algo. tout nouveau tout beau et inédit ou le droit de s'inspirer des prédécesseurs) mais au cas ou, cherche 'Ant colony optimization' sur wikipédia, tu trouvera quelque chose qui ressemble quand même un peu à ce que tu dois faire et dont tu peut peut-être t'inspirer.

Pour plus d'info : cette recherche te donne des liens sur des livres/articles s'y rapportant.

Pour info, tu clique sur les liens de la colonne de droite pour y accéder gratuitement (les liens de la colonne de gauche mènent souvent sur les mêmes articles/livres mais payants).
Si le résultat ne change pas, le 1er lien te mène à (le ?) livre de Dorigo, qui a conçu quelques uns de ces d'algorithmes. Le 4eme te mène sur un des 1er (ou le 1er) article de ce même Dorigo à ce sujet.

Pratiquement tout est en anglais (pour le français, je te laisse faire la recherche toi-même )

[Yaya074]

Merci d'avoir répondu!

Bibistudio, j'ai peur que ça soit plutôt compliqué a réaliser avec Matlab... Car oui nous somme sous matlab obligatoirement (mon sujet a été déplacé et je le précise donc maintenant ^^)

J'avoue être d'accord avec toi sur le principe, mais nous n'avons qu'un an de cours d'informatique (1h a peine par semaine!) et je ne vois pas comment écrire un tel programme! :s

250rgv, je vois ça ce soir, merci!


Donc si vous avez d'autres idées, je suis toujours preneuse!

[MoDDiB]

Si sur une case donnée la quantité de phéromones diminue avec le temps ( lors de chaque déplacement de fourmis ? )
Dans ce cas lors du retour ça sera forcément le chemin avec le plus de phéromones qui sera choisi et donc le plus court non ?