Ant Colony Algorithm – Optimization Techniques

algorithmsoptimization

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 1000×1000 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?

Best Answer

This isn't how ACO works. ACO only drops pheromones after ants have moved across all the points in the grid. You then evaluate something (perhaps total travel time) and then drop pheromones for good ants, and repeat.

They don't move to the same vertex twice, generally, though you can customize this for implementation specificness.

Pheromones aren't dropped each move, they drop after they move everywhere and something is evaluated to determine which ants are better. Ants which are better then drop phereomones (perhaps the best 25% performing ants).

Related Solutions

Find the min/max length of directed graph

For the shortest path, start at the well known Dijkstra's algorithm.

When you're on E, according to certain values and variable states, only G may be available...

A simple solution - which I want to encourage you to implement - is to implement dijkstra such that it calls a function to get the outgoing links from a given node. You can then do your checks there. When the conditions change, you would then invalidate the results of the search, and execute it again.

Note: It is even better if you can mark nodes as invalidated. That way the algorithm can cache the lists of links and only reevaluate for the invalidated nodes.

That a given link or node could be unavailable is not really a problem if the graph cannot change while it is being used. You simply compute it for the graph as you have it.

Since this is a concern, I suppose that there is something that will be traversing the graph and it could find that it changed from one moment to the other... when that happens, this something has advanced some distance on the graph, and it makes sense to compute the path from the current position to the target on the modified graph.

I am not sure how do you want to define longest path...

Perhaps, a good definition for longest path is: the shortest path that maximizes the number of visited nodes. Under that definition, walking an infinite loop is not beneficial.

We would searching for the shortest path... but we need a new metric to call "distance". My initial intuition is to use a metric that does not increase when we visit a new node.

If the distance does not increase nor decrease when visiting a new node, then the following paths are the same length:

A -> B
A -> C -> F -> G -> I -> B

However, we want the second path to be better (I mean, "shorter", I mean, to have a lower value in the metric, I mean, to be preferible).

A simple solution is to decrease the metric when visiting a new node.

Notes:

A negative metric can be problematic. For path finding, it is not safe to use Dijkstra with negatives. We can normalize it to only positive values by using a sigmoid function before comparing.
We also need to encode the rule that distance is different depending on whatever or not we have visited a node. You can solve this by similar means to what I described for having parts of the graph unavailable. Except, instead of passing the current node to evaluate the available links, you pass the current path.

With this metric we have:

A B - length: -1

A C D F G I B - length: -6

A C D E G I B - length: -6

A C D E B - length: -4

A C D E J - length: -4

A C D E C D F G I B - length: -5
        ¯ ¯
A C D E C D E G I B - length: -3
        ¯ ¯ ¯
A C D E C D E B - length: -1
        ¯ ¯ ¯
A C D E C D E J - length: -1
        ¯ ¯ ¯
A C D E C D E C D E F G I B - length: -1
        ¯ ¯ ¯ ¯ ¯ ¯

Then our "longest" path is one of the two longer paths that does not loop (A C D F G I B or A C D E G I B).

In case it is not evident, a path with a loop is always considered worse than its variant without loops because the loop traverses visited nodes, and thus increases the metric. And remeber that we are minizming the metric.

If you are using Dijkstra with a sigmoid of this metric - as I suggest - the loops will be discarded because - as explained above - they will always yield worst paths that those without loop.

Addendum: After posting the answer, I notice that I got some interesting results... for instance: A C D E C D F G I B manages to visit more nodes than A C D F G I B but scores worse (higher), that is not what I expected. I suppose we can tweak it to be more or less interested in going out of its way to reach more nodes before going to the target by applying factors to the added or decreased distance... for example, we could increase only half the value when traversing a visited node. What is the ideal proportion to increase? I have no idea. For practical purposes it can be tweaked to suit the design or problem domain.

Best Answer

Related Solutions

Find the min/max length of directed graph

Related Topic