| 基于多粒度的旅行商问题描述及其蚁群优化算法 |
| |
| 引用本文： | 冀俊忠,黄振,刘椿年,代启国.基于多粒度的旅行商问题描述及其蚁群优化算法[J].计算机研究与发展,2010,47(3). |
| |
| 作者姓名： | 冀俊忠 黄振 刘椿年 代启国 |
| |
| 作者单位： | 北京工业大学计算机学院多媒体与智能软件技术北京市重点实验室,北京,100124 |
| |
| 基金项目： | 国家自然科学基金重大基金项目(60496322);;北京市自然科学基金项目(4083034,4102010) |
| |
| 摘 要： | 针对蚁群算法在求解大规模旅行商问题(Traveling Salesman Problems,TSP)中时间性能方面的不足,提出了一种快速的求解算法.首先,从TSP问题描述入手,给出了一种新的多粒度的问题描述模型;然后,基于该模型,设计了包括基于密度聚类的粒度划分、粗粒度的蚁群寻优、粒度间的连接、细粒度的蚁群寻优、粒度间可行解的合成以及循环分段优化6个阶段在内的求解算法.算法的复杂度分析及在中、大规模TSP问题上的实验表明:本算法的时间性能不仅比经典的蚁群算法有显著的提高,而且与近年来的一些同类算法相比也具有一定的优势,显示了快速求解大规模TSP问题的能力.
|
| 关 键 词： | 旅行商问题 多粒度城市模型 蚁群算法 聚类算法 分段优化 |
An Ant Colony Algorithm Based on Multiple-Grain Representation for the Traveling Salesman Problems |
| |
| Ji Junzhong,Huang Zhen,Liu Chunnian,Dai Qiguo.An Ant Colony Algorithm Based on Multiple-Grain Representation for the Traveling Salesman Problems[J].Journal of Computer Research and Development,2010,47(3). |
| |
| Authors: | Ji Junzhong Huang Zhen Liu Chunnian Dai Qiguo |
| |
| Affiliation: | Beijing Municipal Key Laboratory of Multimedia and Intelligent Software Technology;College of Computer Science and Technology;Beijing University of Technology;Beijing 100124 |
| |
| 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 algo... |
| |
| Keywords: | TSP multiple-grain city model ACO algorithm clustering algorithm subsection optimization |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
