Improving MAX-MIN ant system performance with the aid of ART2-based Twin Removal method

A nondeterministic algorithm that mimics the foraging behavior of ants to solve difficult optimization problems is known as Ant Colony Optimization (ACO). One of the most important problems in ACO is stagnation. Early convergence to a small region of the search space leaves its large sections unexplored. On the other hand, very slow convergence cannot sufficiently concentrate the search in the vicinity of good solutions and therefore render the search inefficiently. Recent studies have shown that similarity growth in th e population leads to these problems. Twin Removal (TR) has been already investigated to reduce the similarity in Genetic Algorithm population but not for any of ACO algorithms. In this paper, TR technique is extended to MAX-MIN Ant System (MMAS) and a novel and effective TR method is proposed b y which not only the negative impact of similarity and run-time are reduced, but al so better results than M MAS without TR ar e obtained in most cases. Experiments conducted on TSP benchmarks showed the robustness of the proposed TR method. Results s how that, removal of ants of initial population having certain percentage of solution similarity would strengthen MMAS to perform better, accelerating convergence to best solution.