3

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:

enter image description here

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?

Sharikov Vladislav
  • 7,049
  • 9
  • 50
  • 87

3 Answers3

3

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.

Albinati
  • 31
  • 1
  • In other words, OP should be getting the optimal path (at least most of the time), and if not then he should adjust something somewhere. – Teepeemm May 28 '14 at 14:36
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.

stf
  • 591
  • 1
  • 4
  • 19
  • Thanks for your answer. About 1st point: first ant on first iteration select edge based on his own vision and on pheromones level. Probability of selecting one or another is calculated with [this formula](http://upload.wikimedia.org/math/6/e/8/6e8b12fe17df2a1006bece801e1df177.png) — it calculates probability based on own ant's vision and on pheromone level. About 2nd: I have pheromone levels in my programm, but the question is not about it. – Sharikov Vladislav May 28 '14 at 12:14
0

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

dfens
  • 5,413
  • 4
  • 35
  • 50
  • It's just a lab work. It's a task. A* had already done =) thank you for the answer. – Sharikov Vladislav May 29 '14 at 09:16
  • Oh ok :) So in short you will experience it when mostly when suboptimal paths are very close to optimal path (for example create example where optimal path is 100 and suboptimal 101), regards – dfens May 29 '14 at 09:20
  • It depends too. In my example, if I will build weights so, that edge 1-2 will have lesser weight than 1-6, then path 1-2-5 will be choosen in most cases, right? I have same example in my post, as you suggested. – Sharikov Vladislav May 29 '14 at 09:32