I have a standard ACO implementation for the TSP problem, with local hill climbing using a full 2-opt (exchanging edges until no further improve can be achieved). The algorithm does fairly well to find pretty good solutions, however, it converges very quickly. After a few hundred iterations all ants are sampling more or less the same path, and the pheromone trails have only a few edges with pheromones > 1, exactly those edges that lie in the best path found.
At this point I'm doing a restart, since the algorithm has lost all ability to search for new paths. I've toyed around adding some tabu-like mechanism to increase diversity after this restart. I've tried with "tabuing" all edges in the best path or some of them (the best n, the worst n, etc.) but in all cases the algorithm fails to find solutions as good as in the first iterations. I basically think that edges are way too general features, and "tabuing" them is too strong. Instead, I would like to tabu parts of the specific best paths found so far.
Is anyone aware of results in this direction?
Using edges as attributes of a move in Tabu Search is correct (see Glover’s paper on Tabu Search). Perhaps you need to use an Aspiration Criteria to override tabu moves. Aspiration Criteria allows making a move even if it is tabu… as long as you don’t fall in cycle.
in Ant Colony System(ACS) version there are a mechanism to avoid selected paths by decreasing their pheromone level. and it works well in face of large scale problems.
Also, we developed a new version of ACO named NLAS(non-linear ant system) which employs the concept of non linearity from Learning Automata field to prevent the algorithm from early convergence.
https://www.researchgate.net/publication/258227549_An_Improved_Model_of_Ant_Colony_Optimization_using_a_Novel_Pheromone_Update_Strategy?ev=prf_pub
Article An Improved Model of Ant Colony Optimization Using a Novel P...
A way to increase diversity is to use more than a group of ants/pheromone trails and allow for them to communicate periodically. Even using a single trail having ants with different search strategies (for instance, varying the parameters) can improve the diversity.
That is one of the focus of my research, so feel free to look at it:
https://www.researchgate.net/profile/Leonor_Melo/publications
If using tabu search, you might employ search reversion or make the tabu state random (within a reasonable range) to avoid cycling. Here's a paper on reversion....http://www.silvafennica.fi/article/1232/author/3751
- Badges
- Science method
- Similar topics
- Biological Science
- Ecology