ISSN 1000-1239 CN 11-1777/TP

• 论文 •

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

1. (北京工业大学计算机学院多媒体与智能软件技术北京市重点实验室 北京 100124) (jjz01@bjut.edu.cn)
• 出版日期: 2010-03-15

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

Ji Junzhong, Huang Zhen, Liu Chunnian, and Dai Qiguo

1. (Beijing Municipal Key Laboratory of Multimedia and Intelligent Software Technology, College of Computer Science and Technology, Beijing University of Technology, Beijing 100124)
• Online: 2010-03-15

Abstract: 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.