A hierarchical parallel algorithm of ant system and local search for TSPs

Ant colony optimization algorithm is an important swarm intelligence algorithm. It has been applied to many fields of combinatorial optimization because of its parallel, distributed computing and running speed. But, ant colony optimization algorithm has some shortcomings. For example, searching process may stagnate. Local search is a good method when cooperate with other algorithms. But hybrid algorithm of local search and other methods will increase the running time. This paper devises a hierarchical parallel algorithm of ant colony optimization and local search for TSPs and computes the hierarchical parallel algorithm with 4 processors. Computation results show that the hierarchical parallel algorithm can improve the running time about 2.5 times.