I am a student working on an ant colony simulator for a course project. The algorithm for it is (obviously) an ant colony algorithm. I know there are various forms of the algorithm but all of those were too mathematically detailed for us so we took an approach in which we have :
- An ant is born at a colony and must gather food from a source to sustain the colony.
- All ants are similar.
- The area in which the ant moves is a 1000x1000 grid, so every grid point serves as a valid point for an ant to occupy. Now, all the algorithms which I have come across involve treating vertices and edges separately but as we are restricting the ants movement to only four directions (up, down, left, right) I guess it doesn't matter where we put the pheromone.
- The grid points mentioned above store the pheromone.
- An ant drops pheromone only if it is carrying food.
- For an ant at a position (i,j), it decides where to move in the next step by taking the pheromone amounts on its four adjacent nodes into account in a simple probabilistic formula,i.e. the probability of traveling to a node is given by (pheromone amount at particular adjacent node) / (sum of pheromone amounts in 4 adjacent nodes).
- An ant cannot travel back to the position it just came from. It can only do so if it is at a site which has food or it is at its colony.
Now my concern is ( and what is actually happening in our program ) that when an ant FIRST reaches a position which has food and picks it up, then by the way our algorithm works, it can move anywhere! This is because it will only leave a pheromone trail, once it has the food and not before and as it is the first ant, there is no existing trail.
If the ant can move anywhere, the ants that reach the food source after it will also mostly tend to follow it.. EVEN IF it is not moving back towards the colony. This defeats the purpose of the entire algorithm.
So my questions are
- Is the above concern valid? If no, then why? If yes, then how to deal with it?
- Do we need to make some changes in our basic understanding of the algorithm to actually make it work?
- What are some other subtle yet important things that newbies like me may miss in this case?