I am doing ant colony optimization algorithm. I have got a few questions. I tried to search throw ant-colony, but found nothing.
1 — What is the result of the algorithm?
I have some graph and I need to find optimal path from start point to goal point, right? This algorithm is not working like dijkstra algorithm (which find one shortest path). There is a probability factor in it. After 10 cycles and 5000 ants worst path can be chosen, despite of that fact, that pheromone on better path will be 1000 times more. I mean 5000'th can chose path 1 -> 3 -> 5 (which has avg probability of 1%), despite of that fact, that 4999 ants had chosen 1 -> 2 -> 5 (99% probability). It is just an example ofc. So the question is how to detect most optimized (best, best on some parameter?) path and should I detect it or 1 -> 2 -> 5 in my example is correct outcome (happens...) and I have to output last chosen path?
2 — How results should be outputted
Well this answer depends on first answer maybe. Well how? I assume, that I have to output total summary of working algorithm and protocol of each cycle.
Summary data will be:
Path found: Yes/no
Path: path/message, that best path is not found
Iteration: N
Protocol will be:
Start data for iteration 3
Pheromone level for this iteration
Path found on this level or not (?)
Path on this iteration (?)
End data for iteration 3
Start data for iteration 2
Pheromone level for this iteration
Path found on this level or not (?)
Path on this iteration (?)
End data for iteration 2
Start data for iteration 1
Pheromone level for this iteration
Path found on this level or not (?)
Path on this iteration (?)
End data for iteration 1
Any suggestions? Help me with output data for each iteration please.
3 — Pheromone level stops growing when it reaches a certain value
Why it is so? For example (500 ants), pheromone level on best path is growing up up to ~10 step of search (cycle) and after that becomes stable. Is it good behaviour or it means some errors in my algorithm? If no errors, why this behaviour appears?
4 — Architecture of my program
I think that good way is to create onclick handler, which calls NEXT STEP (next cycle) of algorithm. I saw some examples, that it was on loop some time (don't remember link, can't show you :'( now). Is my method is acceptable or it is wrong at all?
1) You'd usually store the best-so-far path of all iterations (as in Elitist Ant System etc.), which is also the final result then.
2) With cycle you mean iteration? Anyway, as for "Path found on this level or not", I'd only allow successful (complete) paths in the first place, or let all ants run until every ant has found one and cut the loops. Otherwise placing pheromones and recording the path wouldn't make much sense here, I think. So I'd suggest to record the optimal path's length of each iteration (and thereby the pheromones to place) and the vertices of that path, of course.
3) Usually you'd break the algorithm if the pheromones stagnate and no better solution is being found for a certain number of iterations.
4) Certainly not wrong. I've seen an online implementation somewhere as well, and was a bit disappointed that you couldn't watch the ants step-by-step...