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

被引：16

作者：

冀俊忠

黄振

刘椿年

代启国

机构：

[1] 北京工业大学计算机学院多媒体与智能软件技术北京市重点实验室

来源：

计算机研究与发展 | 2010年 / 47卷 / 03期

基金：

北京市自然科学基金;

关键词：

旅行商问题; 多粒度城市模型; 蚁群算法; 聚类算法; 分段优化;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

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

引用

页码：434 / 444

页数：11

共 10 条

[1] 一种快速求解旅行商问题的蚁群算法 [J].