Algorithme de colonie de fourmis

Je suis un étudiant travaillant sur un simulateur de colonie de fourmis pour un projet de cours. L'algorithme est (évidemment) un algorithme de colonie de fourmis. Je sais qu'il existe différentes formes de l'algorithme, mais toutes étaient trop détaillées mathématiquement pour nous, nous avons donc adopté une approche dans laquelle nous avons:

• Une fourmi est née dans une colonie et doit recueillir de la nourriture à partir d'une source pour soutenir la colonie.
• Toutes les fourmis sont similaires.
• La zone dans laquelle la fourmi se déplace est une grille de 1000x1000, donc chaque point de la grille sert de point valide pour une fourmi à occuper. Maintenant, tous les algorithmes que j'ai rencontrés impliquent de traiter les sommets et les bords séparément, mais comme nous limitons le mouvement des fourmis à seulement quatre directions (haut, bas, gauche, droite), je suppose que peu importe où nous mettons la phéromone.
• Les points de grille mentionnés ci-dessus stockent la phéromone.
• Une fourmi ne laisse tomber la phéromone que si elle transporte de la nourriture.
• Pour une fourmi à une position (i, j), elle décide où se déplacer à l'étape suivante en tenant compte des quantités de phéromones sur ses quatre nœuds adjacents dans une formule probabiliste simple, c'est-à-dire que la probabilité de voyager vers un nœud est donnée par (quantité de phéromones à un nœud adjacent particulier) / (somme des quantités de phéromones dans 4 nœuds adjacents).
• Une fourmi ne peut pas revenir à sa position d'origine. Il ne peut le faire que s'il se trouve dans un site qui a de la nourriture ou s'il est dans sa colonie.

Maintenant, ma préoccupation est (et ce qui se passe réellement dans notre programme) que lorsqu'une fourmi PREMIÈRE atteint une position qui a de la nourriture et la ramasse, alors, par la façon dont notre algorithme fonctionne, elle peut se déplacer n'importe où! En effet, il ne laissera qu'une trace de phéromone, une fois qu'il a la nourriture et pas avant et comme c'est la première fourmi, il n'y a pas de trace existante.

Si la fourmi peut se déplacer n'importe où, les fourmis qui atteignent la source de nourriture après elle auront également tendance à la suivre. MÊME SI elle ne recule pas vers la colonie. Cela va à l'encontre du but de l'algorithme entier.

Donc mes questions sont

• La préoccupation ci-dessus est-elle valable? Si non, alors pourquoi? Si oui, comment y faire face?
• Avons-nous besoin de faire quelques changements dans notre compréhension de base de l'algorithme pour le faire fonctionner?
• Quelles sont les autres choses subtiles mais importantes que les débutants comme moi peuvent manquer dans ce cas?

Ce n'est pas ainsi que fonctionne ACO. ACO ne laisse tomber les phéromones qu'après que les fourmis se sont déplacées sur tous les points de la grille. Vous évaluez ensuite quelque chose (peut-être le temps de voyage total), puis vous laissez tomber les phéromones pour de bonnes fourmis et vous recommencez.

Ils ne se déplacent pas deux fois vers le même sommet, généralement, bien que vous puissiez personnaliser cela pour la spécificité de l'implémentation.

Les phéromones ne sont pas lâchées à chaque mouvement, elles tombent après s'être déplacées partout et quelque chose est évalué pour déterminer quelles fourmis sont meilleures. Les fourmis qui sont meilleures que les phéromones tombent (peut-être les meilleures fourmis performantes à 25%).

Les implémentations que j'ai vues des autres et celles que j'ai écrites pour moi-même ont toujours fait en sorte que les fourmis libèrent les phéromones le long du chemin parcouru pour se rendre à la nourriture, une fois qu'elles ont atteint la nourriture. C'est-à-dire que les fourmis marchent de leur colonie à la nourriture après une marche aléatoire; les chemins suivis par les fourmis de la colonie à la nourriture ne sont ensuite balisés à l'aide de phéromones qu'après que les fourmis ont réussi à atteindre la nourriture. Le voyage de retour n'est pas explicitement simulé. En général, plusieurs fourmis suivent leur cours avant que des phéromones ne soient déposées pour l'itération en cours. Les phéromones sont ensuite déployées pour les chemins réussis, et un nouveau cycle commence.

Habituellement, les chances de la fourmi d'entrer dans un nœud donné sont pondérées par la quantité de phéromones multipliée par une certaine mesure de «bonté». Par exemple, la mesure de la bonté pourrait être quelque chose comme l'inverse de la distance entre la fourmi et la nourriture - cela empêchera les fourmis de se déplacer vers la nourriture, indépendamment des dépôts de phéromones précédents. La qualité pourrait être davantage pondérée pour tenir compte d'autres facteurs, par exemple certains nœuds pourraient être plus faciles à parcourir que d'autres. Et comme le souligne Enderland, il existe généralement une certaine forme de "sélection" de chemin une fois que toutes les fourmis ont réussi leurs cours, où seule une partie des "meilleurs" chemins est choisie pour le dépôt de phéromones. Cependant, vous devriez toujours obtenir des chemins raisonnables même sans sélection,