Stagnation in Ant Colony Optimization

[ozzy_85]

Greetings All :bg!!

I'v recently come across the ant colony optimization techniques. I'v applied the most trivial version of it, the Ant System to the symmetric travelling salesperson problem. One cannot get the most optimal solution using the Ant System. I however get reasonably optimal solutions. But, the problem is that my system converges to a particular solution in a very premature stage and all the parameters are stagnated.

I understand that stagnation occurs at the later stages of the algorithm. Any ideas on how i can aviod/overcome premature convergence??  :dazzled:

Regards,
Ozzy.

[Tedd]

If it's caused by a local maxima, then you could try adding a momentum term -- a weighted adjustment value proportional to the value of previous 'move' (it should start off large and will reduce as the solution converges.)
It might help if you give a little more details about how it works :wink

[PBrennick]

Tedd,

    Ant Colony Optimization

Paul

[Tedd]

Okay, so your 'momentum term' is the rate at which the trails fade over time (they don't just disappear at once, they should weaken gradually until their strength reaches zero.) Chances are that you've probably set this too high, or too low - try playing with it and see if you can get a better convergence.
The reason it would vary over time is due to the temperature of the day - as the sun rises the temperature increases and therefore so will the rate of evaporation; and falls after mid-day. I presume ants' foraging peaks at a specific time of day in phase with the sun, as an indirect consequence of this. It's a complex system with many hidden variables - an over-simplified version won't have the same performance.
Also, an ant follows a trail with a probability proportional to the trail's strength (i.e. weighted random) rather than simply following or not following - even a weak trail will have some ants follow, but more are likely to follow a strong one. This will help keep your search flexible and varied, and not always converge on the same solution every time (however, it will commonly fall onto similar solutions.)