A multiple ant colonies optimization algorithm for finding different optimal tours in the Traveling Salesman Problem

A multiple ant colonies optimization algorithm for the TSP is presented. While each ant is attracted by the pheromone of its own colony, there exists repulsion in the colony-level interactions: the first colony is not affected by other colonies; the second colony is only repelled by the first colony; the third colony is only repelled by the first and the second colonies, etc. Inductively, the final colony is repelled by all the colonies before it. By introducing a time-dependent evaporation rate into the algorithm, it is shown that if there exist different optimal tours, each of the colonies is guaranteed with probability one to converge and find a different optimal tour.