PASCP在大规模TSP中的应用

蚂蚁系统是由M．Dorigo等人首先提出的一种新型的模拟进化算法，初步的研究表明该算法具有极强的鲁棒性和发现较好解的能力，但同时也存在收敛速度慢等缺点。该文提出了一种带聚类处理的并行蚂蚁系统，该算法首先将大规模TSP问题通过聚类处理分解成一些小规模，ISP问题，然后对每一个小规模TSP问题分别使用蚂蚁系统并行求解，最后将所有小规模TSP问题的解合并成TSP问题的解。对带聚类特征的大规模TSP问题的仿真实验表明该算法极大地提高了蚂蚁系统的收敛速度。

Parallel Ant System with Clustering Processing Apply to Large-scale TSP Problem

Ant System is a novel simulated evolutionary algorithm which was proposed first by M. Dorigo. Preliminary study has shown that the algorithm is very robust and has great ability of searching better solution, but at the same time there are some shortcomings such as converging slowly. In this paper a new ant algorithm, Parallel Ant System with Clustering Processing (PASCP), is proposed. First of all, the large-scale TSP problem is divided into several small-scale TSP problems by clustering processing and then all the small-scale TSP problems will be solved in parallel by Ant System, respectively, At last the solutions of all small-scale TSP problems are merged into the solution of the large-scale TSP problem. Simulated experiments on large-scale TSP problem have show that the convergence rate of the new ant algorithm is greatly improved.