Should ant colony algorithm show best path in 100% cases?

Question

I developed ant colony algorithm. It is working quite good at the moment.

In some moot points it can show not best path, but close to best one.

For example, I have this graph:

Matrix is:

    1   2   3   4   5   6   7
1   0   6   5   0   0   2   0
2   6   0   3   2   1   5   0
3   5   3   0   2   5   0   0
4   0   2   2   0   3   0   0
5   0   1   5   3   0   6   0
6   2   5   0   0   6   0   2
7   0   0   0   0   0   2   0

First col and first row are vertex names.

So possible paths are (path - length of the path):

1. 1-2-5 with length 7
2. 1-6-2-5 with length 8
3. 1-6-5 with length 8

My programm is choosing 1st path in 1/10 starts, 2nd path in 7/10 starts and 3rd path in 2/10 start of the programm.

Is it working correct?

Explanation for this is ants has their own eyes (vision, they look at edge length) and also they can detect pheromone level. Own eyes shows for them, that 1-2 edge is rather long and longer then edge 1-6, so in generally they will choose edge 1-6 instead of choosing 1-2. Same for 6-5 and 6-2: 6-2 is more attractive, because it is shorter.

Am I right with my assumption?

Answer 1

In ant colony optimization algorithms, the ants have probabilities for each possible step while walking through the graph. Tipically, this probability is based on two factors: a local and a global measure of quality.

The global measure is usually associated with the pheromone deposit in an edge, since pheromone is added to each edge used in the path followed by an ant and the amount added is somehow related to the quality of the solution created by such ant.

The local measure is usually related to the quality of a particular step: the cost of an edge, in the example provided.

Therefore, if your ants are taking only greedy actions, it is possible that the probability function you are using is giving too much weight to local quality. Finding a probability function that exhibit a good compromise between local and global search is a fundamental aspect of a successfully applied ACO strategy.

Answer 2

According to this: http://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms#Summary , I can see 2 problems in your approach:

1. ants (initially) wander randomly; it has nothing to do with vision or the adjacent edge length
2. do you model those pheromone trails at all?

Answering the question: Should ant colony algorithm show best path in 100% cases? No, it doesn't need to show the best path at all.

Answer 3

Why are you using ant colony for shortest path? If you are searching shortest path you don't need optimization algorithm, best solution can be achieved with polynomial time with A* algorithm (with optimal heuristic function). Ant colony is better when you are using it for TSP problem.

And the answer is: no - keep in mind that algorithm is probabilistic so it may not lead to best solution but to local minimum