基于多粒度的旅行商问题描述及其蚁群优化算法

An Ant Colony Algorithm Based on Multiple-Grain Representation for the Traveling Salesman Problems

针对蚁群算法在求解大规模旅行商问题(Traveling Salesman Problems,TSP)中时间性能方面的不足,提出了一种快速的求解算法.首先,从TSP问题描述入手,给出了一种新的多粒度的问题描述模型;然后,基于该模型,设计了包括基于密度聚类的粒度划分、粗粒度的蚁群寻优、粒度间的连接、细粒度的蚁群寻优、粒度间可行解的合成以及循环分段优化6个阶段在内的求解算法.算法的复杂度分析及在中、大规模TSP问题上的实验表明:本算法的时间性能不仅比经典的蚁群算法有显著的提高,而且与近年来的一些同类算法相比也具有一定的优势,显示了快速求解大规模TSP问题的能力.

Ant colony optimization （ACO） is a population-based metaheuristic technique to effectively solve combination optimization problems. However, it is still an active research topic how to improve the performance of ACO algorithms. Though there are many algorithms to effectively solve traveling salesman problems （TSPs）, there is an application bottleneck that the ACO algorithm costs too much time in order to get an optimal solution. To improve the time performance of ACO in solving large scale TSPs, a fast algorithm is presented in this paper. Firstly, a novel multiple-grain representation model of TSPs is proposed. Based on the model, a new algorithm for TSPs is presented, which mainly contains six phases, i. e. a granularity partition algorithm based on density clustering, an ACO algorithm based on the coarse grain, a connection algorithm between two granularities, an ACO algorithm in the same granularity, a fusion algorithm among granularities, and a subsection optimization algorithm regardless of granularities. The analysis of computation complexity and the experimental results for large number of TSPs demonstrate that the proposed algorithm can greatly improve the speed of convergence in contrast to the classical ACO algorithm, and is highly competitive in time performance compared with some latest elitist ACO algorithms.