A Max-Min Ant System with two colonies and its application to Traveling Salesman Problem

Based on the good performance of Max-Min Ant System (MMAS) in solving the Traveling Salesman Problem (TSP), a Max-Min Ant System with Two Colonies is proposed for the combinatorial optimization problems in this paper. This method is motivated by the fact that there are many colonies of ants in the natural world. In the proposed method, ants search solutions by cooperating with each other in the same colony until no better solution is found after a certain time period. Then, new pheromone distributions are built by communication between the two colonies. Basing on the new pheromone distribution, ants start their search procedure again in each separate colony. The proposed method is tested by simulating some TSP instances and simulation results show that the proposed algorithm performs better than the traditional ACO algorithms.