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

摘要：

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

关键词：旅行商问题、多粒度城市模型、蚁群算法、聚类算法、分段优化

所属期刊栏目：47

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金重大基金项目60496322;北京市自然科学基金项目4083034,4102010

在线出版日期：2010-04-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：434-444