对一类带聚类特征TSP问题的蚁群算法求解

Solving TSP with Characteristic of Clustering by Ant Colony Algorithm

蚁群算法是近几年提出的一种新型的模拟进化算法,初步的研究表明该算法具有极强的鲁棒性和发现较好解的能力,但同时也存在收敛速度慢的缺点。针对带聚类特征的TSP问题,提出了一种新型的蚁群算法。该算法利用TSP问题本身所具有的聚类特征,从数据域上将其分解成多个子问题,对每个子问题分别采用蚁群算法并行求解,最后将所有子问题的解按一定规则合并成问题的解。对带聚类特征TSP问题的仿真实验表明该算法的收敛速度得到了极大的提高。

Ant colony algorithm (ACA) is a novel simulated evolutionary algorithm which was proposed in recent years. Preliminary study has shown that the algorithm is very robust and has great capabilities in searching better solution, but at the same time there are some shortcomings such as converging slowly in the algorithm. To tackle traveling salesman problem (TSP) with characteristic of clustering, a new ACA algorithm is proposed. First the TSP problem is divided into several sub-problems by clustering processing, and then all the sub-problems will be solved in parallelization by ACA algorithm, respectively. At last all the solutions of each sub-problem will be merged into the solution of the TSP problem by some rules. Simulated experiment on TSP with characteristic of clustering shows that the convergence rate of the new algorithm has been greatly improved.