Algoritmo de colônia de formigas

Eu sou um estudante trabalhando em um simulador de colônia de formigas para um projeto de curso. O algoritmo para isso é (obviamente) um algoritmo de colônia de formigas. Eu sei que existem várias formas do algoritmo, mas todas eram muito matematicamente detalhadas para nós, por isso adotamos uma abordagem na qual temos:

• Uma formiga nasce em uma colônia e deve coletar alimentos de uma fonte para sustentar a colônia.
• Todas as formigas são semelhantes.
• A área na qual a formiga se move é uma grade de 1000 x 1000, portanto, cada ponto da grade serve como um ponto válido para uma formiga ocupar. Agora, todos os algoritmos que encontrei envolvem o tratamento de vértices e arestas separadamente, mas como restringimos o movimento das formigas a apenas quatro direções (cima, baixo, esquerda, direita), acho que não importa onde colocamos o feromônio.
• Os pontos de grade mencionados acima armazenam o feromônio.
• Uma formiga derruba o feromônio apenas se estiver carregando comida.
• Para uma formiga em uma posição (i, j), ela decide para onde se mover no próximo passo, levando em consideração as quantidades de feromônio em seus quatro nós adjacentes em uma fórmula probabilística simples, ou seja, a probabilidade de viajar para um nó é dada por (quantidade de feromônio em um nó adjacente específico) / (soma das quantidades de feromônio em 4 nós adjacentes).
• Uma formiga não pode voltar à posição de onde veio. Só pode fazê-lo se estiver em um local com comida ou em sua colônia.

Agora, minha preocupação é (e o que realmente está acontecendo em nosso programa) que, quando uma formiga FIRST chega a uma posição que tem comida e a pega, então pela maneira como nosso algoritmo funciona, ele pode se mover para qualquer lugar! Isso ocorre porque ele deixa apenas um rastro de feromônio, uma vez que ele tem a comida e não antes e, como é a primeira formiga, não existe um rastro.

Se a formiga puder se mover para qualquer lugar, as formigas que atingem a fonte de alimento depois tendem a segui-la. MESMO QUE NÃO esteja voltando para a colônia. Isso anula o objetivo de todo o algoritmo.

Então, minhas perguntas são

• A preocupação acima é válida? Se não, então por quê? Se sim, então como lidar com isso?
• Precisamos fazer algumas alterações em nossa compreensão básica do algoritmo para realmente fazê-lo funcionar?
• Quais são outras coisas sutis, mas importantes, que novatos como eu podem sentir falta neste caso?

Não é assim que o ACO funciona. O ACO só derruba feromônios após as formigas se moverem em todos os pontos da grade. Você avalia algo (talvez o tempo total de viagem), depois solta os feromônios para obter boas formigas e repete.

Eles não se movem para o mesmo vértice duas vezes, geralmente, embora você possa personalizá-lo para especificidade da implementação.

Os feromônios não são descartados a cada movimento, eles caem depois que se movem para qualquer lugar e algo é avaliado para determinar quais formigas são melhores. Formigas que são melhores do que soltam phereomones (talvez as melhores formigas com 25% de desempenho).

As implementações que vi de outras pessoas e as que escrevi para mim sempre fizeram com que as formigas liberassem os feromônios ao longo do caminho percorrido para chegar à comida, quando chegavam à comida. Ou seja, as formigas marcham da colônia para a comida após uma caminhada aleatória; os caminhos seguidos pelas formigas da colônia até a comida são marcados com feromônios somente depois que as formigas conseguiram chegar à comida. A viagem de volta não é explicitamente simulada. Em geral, várias formigas seguem seu curso antes que quaisquer feromônios sejam depositados para a iteração atual. Os feromônios são então implantados para os caminhos bem-sucedidos e uma nova rodada começa.

Geralmente, as chances de a formiga entrar em um determinado nó são ponderadas pela quantidade de feromônios vezes alguma medida de "bondade". Por exemplo, a medida da bondade pode ser algo como o inverso da distância entre a formiga e a comida - isso fará com que as formigas tentem se mover em direção à comida, independentemente dos depósitos de feromônios anteriores. A bondade pode ser ainda mais ponderada para explicar outros fatores, por exemplo, alguns nós podem ser mais fáceis de percorrer do que outros. E, como aponta enderland, normalmente existe alguma forma de "seleção" de caminho, uma vez que todas as formigas executam seus cursos com sucesso, onde apenas uma parte dos "melhores" caminhos é escolhida para o depósito de feromônios. No entanto, você ainda deve encontrar caminhos razoáveis, mesmo sem seleção,