Updating ants pheromone issue

Question

I've developed my ant colony algorithm with one ant, so it can find the shortest path between start point and goal point.

But the repeatability of answers are poor. I've red in Dorigo book that result of the algorithm with one ant is bad, so I'm trying to add some more ants. Now my main question is how should I update the trails ? Should all ants find the goal and then update the passed edges ? Or every ant that finds the goal, algorithm should update the trail instantly?

Answer 1

Why you should update your pheromone after the full path has been constructed:

When you are constructing a path, in each iteration you are adding an available vertex, which is a vertex that wasn't added to the path yet. the value of the path will be determined only after a full path has been constructed, and in some cases some partial paths that may seem very promising may lead you to a "trap" (when you'll have to add very long edges in later phases of the path construction), and eventually lead to a very bad result.

More so, I recommend you to update the pheromone only after an entire generation of ants have constructed their full path.

Why? because you are using a probabilistic model, and the path that is being constructed is being affected by 2 parameters: the pheromone, and a "heuristic" parameter (which is the length of the edges). when you start the algorithm, all edges have the same pheromone level, and the ants are acting in a "greedy" way, which means they tend to choose the shorter available edges (edges that may be discarded in later iterations as they lead to bad results). if each ant will update the pheromone right when it's done, you have a greater chance to reach early stagnation and find a local minimum, and you don't give the ants a good chance to explore a wider area of the search space and get smarter. save a list of all the ants in each iteration, let all of them construct a path, then let each of them deposit pheromone (this way you can also apply a "ranking" method, which means the amount of deposited pheromone will be determined by the rank of the ant in the iteration, instead of the solution value, which sometimes help distinguish between close to optimal solutions).

This is also the reason why you shouldn't use only one ant in each iteration. as you'll get a similar result. I suggest you divide your "computation power" more evenly between the number of ants in each generation, and the number of generations (e.g. 100 ants in an iteration, 100 iteration).

I believe that if you'll apply this logic you'll get the expected results.

Answer 2

The ant colony optimization is optimize for speed when you want repeatability you can optimize the result with a k2 or k3-opt algorithm. When you want faster speed look for the dynamic solution. I can recommend optimap javascript from gebweb. It has also an ant colony optimizer and k2 and k3-opt algorithm and a dynamic solution for the tsp problem or the open tsp problem. There is also webpage with a frontend available.