计算机研究与发展
ＪｏｕｒｎａｌｏｆＣｏｍｐｕｔｅｒＲｅｓｅａｒｃｈａｎｄＤｅｖｅｌｏｐｍｅｎｔ
ＩＳＳＮ
１０００—１２３９／ＣＮ１１—１７７７／ＴＰ
４７（３）：４３４—４４４．２０１０
基于多粒度的旅行商问题描述及其蚁群优化算法
冀俊忠
黄振刘椿年代启国
１００１２４）
（北京工业大学计算机学院多媒体与智能软件技术北京市重点实验室北京
（ｊｊｚ０１＠ｂｉｕｔ．ｅｄｕ．ｃｎ）
Ａｎ
Ａｎｔ
ＣｏｌｏｎｙＡｌｇｏｒｉｔｈｍＢａｓｅｄ
ｏｎ
Ｍｕｌｔｉｐｌｅ－ＧｒａｉｎＲｅｐｒｅｓｅｎｔａｔｉｏｎｆｏｒｔｈｅＴｒａｖｅｌｉｎｇ
ＳａｌｅｓｍａｎＰｒｏｂｌｅｍｓ
ＪｉＪｕｎｚｈｏｎｇ，ＨｕａｎｇＺｈｅｎ，ＬｉｕＣｈｕｎｎｉａｎ。ａｎｄＤａｉＱｉｇｕｏ
（ＢｅｉｊｉｎｇＭｕｎｉｃｉｐａｌＫｅｙＬａｂｏｒａｔｏｒｙｏｆＭｕｌｔｉｍｅｄｉａａｎｄＩｎｔｅｌｌｉｇｅｎｔＳｏｆｔｗａｒｅＴｅｃｈｎｏｌｏｇｙ，ＣｏｌｌｅｇｅｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＢｅｉｊｉｎｇＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｂｅｉｊｉｎｇ１００１２４）
Ａｂｓｔｒａｃｔ
Ａｎｔｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎ（ＡＣＯ）ｉｓ
ａ
ｐｏｐｕｌａｔｉｏｎ—ｂａｓｅｄｍｅｔａｈｅｕｒｉｓｔｉｃｔｅｃｈｎｉｑｕｅ
ａｎ
ｔＯ
ｅｆｆｅｃｔｉｖｅｌｙ
ｔＯ
ｓｏｌｖｅｃｏｍｂｉｎａｔｉｏｎｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓ．Ｈｏｗｅｖｅｒ，ｉｔｉｓｓｔｉｌｌｔｈｅｐｅｒｆｏｒｍａｎｃｅｏｆＡＣＯａｌｇｏｒｉｔｈｍｓ．Ｔｈｏｕｇｈｔｈｅｒｅｓａｌｅｓｍａｎｐｒｏｂｌｅｍｓ（ＴＳＰｓ），ｔｈｅｒｅｉｓｔｉｍｅｉｎｏｒｄｅｒｔｏｇｅｔ
ａｎ
ａｎ
ａｒｅ
ａｃｔｉｖｅｒｅｓｅａｒｃｈｔｏｐｉｃｈｏｗ
ｉｍｐｒｏｖｅ
ｍａｎｙａｌｇｏｒｉｔｈｍｓｔｏｅｆｆｅｃｔｉｖｅｌｙｓｏｌｖｅｔｒａｖｅｌｉｎｇ
ｔｏｏ
ａｐｐｌｉｃａｔｉｏｎｂｏｔｔｌｅｎｅｃｋｔｈａｔｔｈｅＡＣＯａｌｇｏｒｉｔｈｍｃｏｓｔｓ
ｍｕｃｈ
ｏｐｔｉｍａｌｓｏｌｕｔｉｏｎ．ＴｏｉｍｐｒｏｖｅｔｈｅｔｉｍｅｐｅｒｆｏｒｍａｎｃｅｏｆＡＣＯｉｎｓｏｌｖｉｎｇｌａｒｇｅ
ｓｃａｌｅＴＳＰｓ，ａｆａｓｔａｌｇｏｒｉｔｈｍｉｓｐｒｅｓｅｎｔｅｄｉｎｔｈｉｓｐａｐｅｒ．Ｆｉｒｓｔｌｙ，ａｎｏｖｅｌｍｕｌｔｉｐｌｅ－ｇｒａｉｎｒｅｐｒｅｓｅｎｔａｔｉｏｎｍｏｄｅｌｏｆＴＳＰｓｉｓｐｒｏｐｏｓｅｄ．Ｂａｓｅｄｃｏｎｔａｉｎｓｓｉｘ
ｏｎ
ｔｈｅｍｏｄｅｌ，ｆｌｎｅｗａｌｇｏｒｉｔｈｍｆｏｒＴＳＰｓｉｓｐｒｅｓｅｎｔｅｄ，ｗｈｉｃｈｍａｉｎｌｙ
ｐａｒｔｉｔｉｏｎ
ａｌｇｏｒｉｔｈｍ
ｂａｓｅｄ
ｏｎ
ｐｈａｓｅｓ，ｉ．ｅ．ａｇｒａｎｕｌａｒｉｔｙ
ｏｎ
ｄｅｎｓｉｔｙ
ｃｌｕｓｔｅｒｉｎｇ，ａｎＡＣＯ
ＡＣＯ
ａｌｇｏｒｉｔｈｍｂａｓｅｄａｌｇｏｒｉｔｈｍ
ｉｎ
ｔｈｅ
ｔｈｅ
ｃｏａｒｓｅ
ｇｒａｉｎ，ａ
ｃｏｎｎｅｃｔｉｏｎｆｕｓｉｏｎ
ａｌｇｏｒｉｔｈｍ
ｂｅｔｗｅｅｎｔＷＯｇｒａｎｕｌａｒｉｔｉｅｓ，ａｎ
ｇｒａｎｕｌａｒｉｔｉｅｓ，ａｎｄ
ａ
ｓａｍｅ
ｇｒａｎｕｌａｒｉｔｙ，ａａｌｇｏｒｉｔｈｍａｍｏｎｇ
ｓｕｂｓｅｃｔｉｏｎ
ｔｈｅ
ｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｒｅｇａｒｄｌｅｓｓｏｆｇｒａｎｕｌａｒｉｔｉｅｓ．Ｔｈｅａｎａｌｙｓｉｓｏｆｃｏｍｐｕｔａｔｉｏｎｃｏｍｐｌｅｘｉｔｙａｎｄ
ｃａｎ
ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｆｏｒｌａｒｇｅｎｕｍｂｅｒｏｆＴＳＰｓｄｅｍｏｎｓｔｒａｔｅｔｈａｔｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｉｍｐｒｏｖｅｔｈｅｓｐｅｅｄｏｆｃｏｎｖｅｒｇｅｎｃｅｉｎ
ｃｏｎｔｒａｓｔ
ｔｏ
ｇｒｅａｔｌｙ
ｔｈｅｃｌａｓｓｉｃａｌＡＣＯａｌｇｏｒｉｔｈｍ，ａｎｄｉｓｈｉｇｈｌｙｃｏｍｐｅｔｉｔｉｖｅ
ｉｎｔｉｍｅｐｅｒｆｏｒｍａｎｃｅｃｏｍｐａｒｅｄｗｉｔｈｓｏｍｅｌａｔｅｓｔｅｌｉｔｉｓｔＡＣ０ａｌｇｏｒｉｔｈｍｓ．Ｋｅｙｗｏｒｄｓｏｐｔｉｍｉｚａｔｉｏｎ
ＴＳＰ；ｍｕｌｔｉｐｌｅ－ｇｒａｉｎ
ｃｉｔｙｍｏｄｅｌ；ＡＣＯ
ａｌｇｏｒｉｔｈｍ；ｃｌｕｓｔｅｒｉｎｇ
ａｌｇｏｒｉｔｈｍ；ｓｕｂｓｅｃｔｉｏｎ
摘要针对蚁群算法在求解大规模旅行商问题（Ｔｒａｖｅｌｉｎｇ
ＳａｌｅｓｍａｎＰｒｏｂｌｅｍｓ，ＴＳＰ）中时间性能方面
的不足，提出了一种快速的求解算法．首先，从ＴＳＰ问题描述入手，给出了一种新的多粒度的问题描述模型；然后，基于该模型，设计了包括基于密度聚类的粒度划分、粗粒度的蚁群寻优、粒度间的连接、细粒度的蚁群寻优、粒度问可行解的合成以及循环分段优化６个阶段在内的求解算法．算法的复杂度分析及在中、大规模ＴＳＰ问题上的实验表明：本算法的时间性能不仅比经典的蚁群算法有显著的提高，而且与近年来的一些同类算法相比也具有一定的优势，显示了快速求解大规模ＴＳＰ问题的能力．关键词旅行商问题；多粒度城市模型；蚁群算法；聚类算法；分段优化
中图法分类号ＴＰｌ８
收祷日期：２００９—０３一】】；修回日期：２００９—０９一０１
基金项目：国家自然科学基金重大基金项目（６０４９６３２２）；北京市自然科学基金项目（４０８３０３４，４１０２０１０）
冀俊忠等：基于多粒度的旅行商问题描述及其蚁群优化算法
旅行商问题ＴＳＰ是一个经典的组合优化问题．挖个城市的ＴＳＰ问题求解可描述为：给定一个城市集合Ｖ＿－－｛∥，，耽，…，％｝，求遍历ｙ中所有城市各一次且最后回到出发城市（求解约束）的一个最短旅行的连通图ｇ∈Ｇ（Ｖ，Ａ），其中Ｇ（Ｖ，Ａ）为所有满足上述求解约束的连通图集合，Ａ一｛ａｄ一（ｖｉ，口ｆ）ＩＯ＜ｉ，歹≤７ｚ，睁！－『）是城市间两两相连的一组边．如果把任意一条边的距离记为ｄ；，＝ＩａｉＩ，则一个解图的数学形式可表示为ｇ＝ａｒｇ
ｍｉｎ≥：ｄ口．
譬ｔ‘’（Ｐ’＾，ａ
∈譬７
ＴＳＰ问题的求解是一个典型的ＮＰ难问题，由于该问题的求解模型可广泛应用于多种复杂优化问题，故该问题的求解算法一直以来是国内外学者们关注的一个研究热点．然而，在求解ＴＳＰ问题的过程中，当城市规模ｎ大到一定程度后就会面临“组合爆炸”问题，这时传统的一些启发式搜索就会陷入困境．于是人们结合物理学、生物遗传学、仿生学等领域的研究成果，相继提出了多种元启发式的ＴＳＰ问题的求解方法，如模拟退火（ｓｉｍｕｌａｔｅｄ
ａｎｎｅａｌｉｎｇ）、
禁忌搜索（ｔａｂｕｓｅａｒｃｈ）、遗传演化（ｇｅｎｅｔｉｃｅｖｏｌｕｔｉｏｎａｒｙ）、蚁群优化（ａｎｔ
ｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎ）
等算法．其中，蚁群优化算法是２０世纪９０年代初才被提出的一种新的元启发搜索算法ｎ。２ｊ，其实现机理是通过模拟人工蚂蚁群体在觅食过程中所体现出的智能行为来完成对ＴＳＰ问题的求解．由于蚁群算法具有良好的鲁棒性、正反馈、分布式及并行计算等特点，所以受到学者们的广泛关注，蚁群算法的理论框架也日渐成熟［３．５］．尽管如此，当城市规模竹达到数百后，蚁群算法仍暴露出运行时间过长、难以满足实际应用需求的不足．为此，本文提出了一种新的基于多粒度的ＴＳＰ问题描述模型的蚁群求解算法．该算法的基本思想是通过对ＴＳＰ问题进行多粒度的描述。将难解的大规模ＴＳＰ问题分解为易于求解的小规模ＴＳＰ问题来求解．首先在粗粒度上完成蚁群寻优以确定粗粒度间的连接，然后在每个粗粒度内进行细粒度的蚁群寻优，实现城市间的连接。最后利用循环分段优化策略来弥补粒度划分对求解精度的影响．由于多粒度的划分大大缩小了原来单粒度问题的规模，所以算法的计算复杂度能大大降低，有效地提高了蚁群算法求解大规模ＴＳＰ问题的能力．在一些中、大规模的ＴＳＰ问题上的实验表明：新算法在求解速度上不仅比经典的ＡＣＯ算法有显著的提
４３５
高，而且与近年来的一些算法相比也有优势，体现出良好的求解大规模ＴＳＰ问题的能力．
１
相关工作
迄今为止，针对基本蚁群算法［１］（ａｎｔ
ｓｙｓｔｅｍ，
ＡＳ）迭代次数多、运行时间长的缺点，国内外的学者们已经提出了许多种新的快速、高效的蚁群算法［６。１４。．概括起来，这些算法主要包括３类：１）基于信息素更新机制的改进．通过对信息素生成和更新策略的优化来提高蚁群算法的寻优能力，改善解的全局收敛性．由于信息素是蚁群进行相互交流、完成信息融合并实现群集智能（ｓｗａｒｍｉｎｔｅｌｌｉｇｅｎｃｅ）的重要媒介，因此，许多学者对蚁群算法的研究都是围绕信息素的产生和更新策略进行的¨书］．２）基于随机搜索机制的改进．由于蚁群算法有易于与其他方法相结合的优点［１］，所以不少工作都是对随机搜索过程的控制策略进行调整，提高局部的寻优能力，以减少迭代次数，加速收敛．如文献［９］提出了相遇和分段优化的策略加速了构造解的过程；文献［１０］通过变异策略以加快局部搜索；文献［１１］将遗传算法与蚁群算法相融合也加快了求解速度．而文献［１２］将这２种改进机制相结合，提出了一种基于变异和动态信息素更新的新算法，在时间性能上取得了较大的提高．３）基于启发信息函数的改进．文献［１３］利用最小生成树的结构信息来对通用的启发函数进行加权高；文献［１４］则采用基于插入准则的ＧＥＮＩ思想来代替常用的概率最近邻的启发思想，给出了能够改１６］通过对局部最优解进行简单的相交操作得到模寻优算法、粒度间融合算法、滑动循环的分段优化算修正，在求解质量和时间性能上都获得了较大的提善蚁群算法求解质量的ＧＡＣＳ算法．此外，文献［１５－式或部分解，来减少后期迭代中的城市规模，有效地缩小了原问题的搜索空间。这是蚁群算法求解大规模ＴＳＰ问题的一种新尝试．基于类似的问题归约思想，本文从问题的描述出发，提出了一种新的基于多粒度ＴＳＰ问题描述的蚁群优化算法．算法包括基于密度聚类的粒度划分算法、基于粗粒度蚁群寻优的顺序学习算法、粒度间的连接算法、同粒度内的蚁群法６个阶段．新算法的主要特点是：突破了经典的ＴＳＰ问题的描述模型，给出了一种多粒度的ＴＳＰ问题描述模型，力求从本质上解决蚁群算法在求解大规模ＴＳＰ问题时运行时间过长的问题．
计算机研究与发展２０１０，４７（３）
定义１．超城市．在ＴＳＰ问题二维坐标的平面
２
多粒度ＴＳＰ问题描述模型
面对复杂的、难以准确把握的问题，人们通常不
上，如果城市的地理位置分布呈现较明显的分簇现象，那么那些具有足够高密度的区域称为超城市
（ｓｕｐｅｒ
ｃｉｔｙ）或地区（ｄｉｓｔｒｉｃｔ）．一个超城市中包含若
是盲目地追求精确的最佳解，而是通过逐步尝试的办法达到满足一定精度的合理目标［１７｜．这是一种概略地、由粗到细、不断求精的多粒度分析法，利用它可以避免求解原问题计算复杂度高的困难．换句话说，问题的多粒度描述是降低复杂问题求解计算复杂度的一种有效手段．
蚁群算法的实现机理是利用蚂蚁在觅食途中所释放的信息素来完成个体之间相互的交流和合作，其过程主要包括信息素的更新及以其为基础的状态迁移（蚂蚁选路）２部分．目前，大多数蚁群算法都将信息素的更新视为提高算法性能的关键，却忽视了食物源的分布对蚂蚁选择路径的影响．而生物学家的观察发现，在自然界的真实蚁群的觅食行为中，大部分蚂蚁会优先选择离自己目前位置较近的食物源去觅食，所以如果存在较密集（彼此间距离较近）的几个食物源，那么蚂蚁会优先遍历这几个食物源，等它们枯竭后才去寻找其他食物源．结合蚂蚁觅食的这种现象，我们给出如下假设：
假设１．商人最近城市选择假设．在一个较复杂的、有若干城市的ＴＳＰ问题中的一条遍历所有城市的最短路径中，城市ｉ连接到城市．ｆ，＿『不可能是离城市ｉ最远的那些城市［１２．１７］．于是，行个城市的ＴＳＰ问题可以按地理位置分布划分为不同的地区（根据相互间的距离），商人下一城市的选择范围局限于离当前城市ｉ较近的某一邻域（地区）的部分城市，商人在访问完该地区的所有城市后才会访问其他地区的城市．
本文使用连接图作为ＴＳＰ问题可行解的基本数据结构．基于上述假设，下面给出ＴＳＰ问题可行解的多粒度描述模型的定义：
干彼此距离相近的城市．
定义２．孤立城市．在一个给定的距离（半径）内，与任意城市都不相邻的城市称为孤立城市
（ｉｓｌａｎｄ
ｃｉｔｙ）．孤立城市是指在平面上远离其他城市
的城市，它也可看作是仅含１个城市的超城市．
定义３．边缘城市．在一个超城市（地区）中，与其他地区或孤立城市发生连接的城市，称为边缘城市（ｍａｒｇｉｎｃｉｔｙ）．根据地区间的连接顺序，一个地区内的２个边缘城市分别称为入区城市（ｉｎ－ｄｉｓｔｒｉｃｔｃｉｔｙ）和出区城市（ｏｕｔ－ｄｉｓｔｒｉｃｔ
ｃｉｔｙ）．
定义４．ＴＳＰ问题的多粒度描述模型．基于上述定义，一个ＴＳＰ问题的可行解可以表示为一个连
接图ｇＤ＝ｇ（Ｄ，Ｂ），其中：Ｄ＝｛ｄ。，ｄ：，…，ｄＩ｝为地区节点的集合，历为地区间两两相连的弧集合，如弧ｅ（ｄｉ，ｄ，）∈匕表示地区ｄ。和ｄ，之间的一条连
接．任意一个地区ｄｉ∈Ｄ表示ＴＳＰ问题的可行解内的一个超城市，它可进一步表示为一个从入区城市出发遍历该地区内所有城市后到达出区城市的连接图，即ｄ；＝ｇｉ（ｙ，Ｅ。），其中Ｖ为超城市内的城市集合，Ｅ。为超城市内城市间连接弧的集合．因此，ＴＳＰ问题的可行解可进一步表示为一个多粒度的连接图ｇＭ—ｇ（｛ｇｉ（Ｖ，Ｅ。）），Ｅ），Ｅ为粒度间的连接弧集合，用来刻画超城市与城市间的连接关系．
图１为这种多粒度连接图的ＴＳＰ解结构描述模型．所求问题的解描述由ＴＳＰ问题可行解、超城市连接以及城市连接３种描述粒度构成，超城市之间以及超城市内城市间分别以地区级的连接图和城市间连接图描述其连接结构，并且通过入区城市和出区城市完成不同粒度间的连接，最后构成一个多粒度的连接图．
Ｆｉｇ．１
Ｒｅｐｒｅｓｅｎｔａｔｉｏｎｏｆｔｈｅ
ｓｔｒｕｃｔｕｒｅ
ｏｆＴＳＰｓｏｌｕｔｉｏｎｓｂａｓｅｄ
ｏｎａ
ｍｕｌｔｉ—ｇｒａｉｎｃｏｎｎｅｃｔｉｏｎｇｒａｐｈ．
图１基于多粒度连接图的ＴＳＰ解的结构描述
冀俊忠等：基于多粒度的旅行商问题描述及其蚁群优化算法
４３７
通过引人多粒度的ＴＳＰ描述模型，在ＴＳＰ问题的求解中，便可达到降低问题规模、减少算法的计算复杂度、进而增进蚁群算法求解能力的目的．
３
粒度ＴＳＰ问题求解的蚁群算法（ａｎｔ
ｂａｓｅｄ
ｏｎ
ｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎ
ｍｕｌｔｉｐｌｅｇｒａｉｎｒｅｐｒｅｓｅｎｔａｔｉｏｎ，ＡＣＯＭＧＲ），图
２为多粒度ＴＳＰ问题求解算法的过程图解．从图２可见，ＡＣｏＭＧＲ算法求得一个满意解需要经过粒度划分算法、粗粒度的寻优、粒度间的连接、粗粒度内的蚁群寻优算法、粒度间可行解的合成、循环分段优化算法等６个关键步骤，下面分别对其进行讨论．
多粒度ＴＳＰ问题求解的蚁群算法
基于多粒度的ＴＳＰ问题描述模型，本文给出多
Ｆｉｇ．２
Ｔｈｅｏｐｔｉｍｉｚａｔｉｏｎ
ａｎ
ｐｒｏｃｅｄｕｒｅｂａｓｅｄ
ｏｎ
ｍｕｌｔｉｐｌｅ
ｇｒａｉｎｒｅｐｒｅｓｅｎｔａｔｉｏｎｆｏｒＴＳＰｓ．（ａ）Ｇｒａｉｎ
ｐａｒｔｉｔｉｏｎｔ（ｂ）
ａ
Ｃｏａｒｓｅｇｒａｉｎｓｅａｒｃｈｆｏｒ
ｏｒｄｅｒ；（ｃ）Ｉｎｔｅｒ－ｇｒａｉｎｃｏｎｎｅｃｔｉｏｎ；（ｄ）Ｆｉｎｅｇｒａｉｎｃｏｎｎｅｃｔｉｏｎ；（ｅ，Ｃｏｎｓｔｒｕｃｔｉｎｇ
ｆｅａｓｉｂｌｅ
ｓｏｌｕｔｉｏｎ；ａｎｄ（ｆ）Ｃｉｒｃｕｌａｒｓｕｂｓｅｃｔｉｏｎｏｐｔｉｍｉｚａｔｉｏｎ．
图２多粒度ＴＳＰ问题求解算法过程图解．（ａ）粒度划分；（ｂ）粗粒度的寻优；（ｃ）粒度间的连接；（ｄ）细粒度内的
连接；（ｅ）可行解的合成；（ｆ）循环分段优化
３．１
基于密度聚类的粒度划分算法
粒度的划分是将给定的ＴＳＰ问题描述转化为
算法１．ＧＰＤＣ（ＳＰｆｏ厂Ｐｏｉ珂ｆＳ，Ｅｐｓ，ＭｉｎＰｔｓ）．／＊ＳｅｔｏｆＰｏｉｎｔＳ为ＴＳＰ中未分区的城市集，Ｅｐｓ和ＭｉｎＰｔｓ分别为地区半径和地区内最小城市数＊／
｛初始化城市的地区标记为ＵＮＣＬＡＳＳＦＩＥＤ；
ＦＯＲｉ＝１Ｔ０ＳｅｔＤ，Ｐｏｉｎｔｓ．ｓｉｚｅ
多粒度ＴＳＰ问题描述模型的基础．如图２（ａ）所示，该算法运行的目的是将原ＴＳＰ问题描述的粒度变粗以降低原问题的规模．结合城市地理分布的特征，本文根据ＤＢＳＣＡＮ聚类算法的思想【ｌ引，设计了基于密度聚类的粒度划分算法．采用ＤＢＳＣＡＮ算法的原因是：１）能将具有足够高密度的区域划分为簇；２）能将相对稀疏的点视为“噪声”，故能够在带有“噪声”的空间点数据中利用类的密度连通性发现任意形状的聚类．换句话讲，该算法能对不同分布的数据进行聚类，符合多粒度的ＴＳＰ问题描述模型中对超城市和孤立城市的定义．基于密度聚类的粒度划分算法（ｇｒａｉｎ
ｐａｒｔｉｔｉｏｎｂａｓｅｄ
ｏｎ
Ｐｏｉｎｔ＝Ｓｅｔ砖Ｐｏｉｎｔｓ．ｇｅｔ（ｉ）；
／＊返回城市集合的第ｉ个元素＊／
ＩＦＰｏｉｎｔ．Ｄ耐＝ＵＮＣＬＡＳＳＩＦＩＥＤＴＨＥＮ
ＩＦＥ：ｃｐａｎｄＤｉｓｔｒｉｃｔ（ＳｅｔｏｆＰｏｉｎｔｓ，Ｐｏｉｎｔ，
Ｄｉｄ。Ｅｐｓ，ＭｉｎＰｔｓ）ＴＨＥＮ
／＊ＥｘｐａｎｄＤｉｓｔｒｉｃｔ函数为一个核心城市构造一个密度相连的城市集合（地区）＊／
ＤｉｓｔｒｉｃｔＩｄ＝Ｄｉｓｔｒｉｃｔｌｄ＋１；／＊地区标记更新＊／
ＥＮＤＩＦＥＮＤＩＦ
ｄｅｎｓｉｔｙｃｌｕｓｔｅｒｉｎｇ，
ＧＰＤＣ）的基本思想是：对于一个地区中的每一个核心城市，在其给定距离（半径）的邻域内所包含的城市数不得小于某～个给定的最小数量，具体算法的描述如下：
４３８
ＥＮＤＦＯＲ
返回粒度划分结果（孤立城市和地区内城市的地区标记）．
）
ＧＰＤＣ算法为了发现一个地区，先从ＴＳＰ问题的城市集Ｖ中任取一个城市口ｉ，利用密度参数判断其是否为核心城市．如果职是核心城市，则在以ｖｉ为中心以Ｅｐｓ为半径的区域内所包含的城市数量不少于ＭｉｎＰｔｓ，于是算法可以找到一个关于参数Ｅｐｓ和ＭｉｎＰｔｓ的地区．如果职是边界点，则在以让为中心以Ｅｐｓ为半径的区域内包含的城市数量少于ＭｉｎＰｔｓ，于是可以把让暂时标注为噪声点，然后，继续处理ｙ中的下一个未标记的城市．被标记为噪声点的城市随着划分过程的进行，可能改变标记成为某一地区的元素．在划分完成后，不被任一核心城市密度可达的那些噪声点城市被确定为孤立城市．城市的地区归属与地区的发现和扩展连通都由函数ＥｘｐａｎｄＤｉｓｔｒｉｃｔ（）完成【ｌ
８１．
３．２粗粒度的寻优及粒度间的连接
经过粒度划分过程，原问题就被归约为规模数大大降低的地区级（粗粒度）和各地区内城市（细粒度）的寻优问题．为了合成问题的解，首先进行粗粒度的寻优以确定地区间的前后连接关系．具体方法是：以孤立城市和各地区的重心（该地区内所有城市坐标的平均）为代表点，通过基本的ＡＣＳ算法【２３求解代表点所构成的新ＴＳＰ问题的最优路径，从而确定粗粒度的旅行路线，得到各地区与孤立城市间的连接顺序，如图２（ｂ）所示．连接顺序确定后，我们就可以两两进行相邻地区间出区城市和人区城市的连接．具体可分为３种情况．
１）孤立城市与孤立城市相邻时，直接连接．２）孤立城市（ｑ）与某地区（Ｄ，）相邻时，利用最近邻原则确定该地区的入（或出）区城市：
。；＝ａｒｇｍｉｎｄ＊ｏｒ口｛）＝ａｒｇｍｉｎ巩，
（１）
％６ｑ
１∈Ｄ，、≠。；
其中，口｛为Ｄ，的入区城市（当连接顺序为ｖｉ—ｑ），。｛）为Ｄ』的出区城市（当连接顺序为ｑ一让）．
３）两地区Ｄ。，Ｄｉ相邻且Ｄｉ—Ｄ，时，利用式（２）确定地区Ｄｉ的出区城市以及地区Ｄ，的入区城市：
（喃，口｛）一ａｒｇ
ｍｉｎ矗。．
（２）
‰∈Ｄ。ｔ‰≠吒
％∈ＤＪ
至此，完成了粒度间的连接，如图２（ｃ）所示．
计算机研究与发展２０１０，４７（３）
３．３粗粒度内的蚁群寻优算法
粗粒度内的蚁群寻优算法以入区城市为始点，出区城市为终点，确定地区内城市间的连接顺序，并依此得到该地区中入区城市到出区城市最短的旅行．不同地区内的蚁群寻优过程可并行地进行．在该算法中，我们使用蚁恒模型¨副作为信息素的增量模型，算法描述如下：
算法２．ＡＣＡＣＯ（ｋ）／＊是为区的标识号＊／
｛
１）初始化阶段：
初始化参数，赋给各条路径相同的信息素浓度，并将ｍ。只蚂蚁放到入区域市上；为每只蚂蚁设置允许访问的城市列表；２）蚁群的一次周游过程（一次迭代）：
ＦＯＲｐ＝１
ＴＯ咒。／＊遍历该区所有城市，最后
到达出区城市＊／
ＦＯＲｑ＝１ＴＯ
ｍ。／＊蚁群的一步转移＊／
｛ＩＦｐ＜巩ＴＨＥＮ／＊没有遍历完该区所有
城市＊／
｛按ＡＣＳ中的转移概率公式Ⅲ选择下一个城市；
完成一步行走，并变更允许访问的城市
列表；｝
｝
３）本次迭代的信息素的更新：
ＦｏＲｑ＝１ＴＯｍｋ
｛计算Ｌｑ；）／＊计算每只蚂蚁的旅行长度＊／ＦＯＲ每条边ａｄ∈ｇｌＵ９２Ｕ…Ｕｇ槭｛计算路径巧上新产生的信息素浓度；ｑ（￡＋１）＝（１－－ｐ）ｑ（ｆ）＋ｌＤ・＂ｔｏ；／＊ＩＤ为挥发系数＊／
）／＊局部信息素的更新＊／
Ｌｂｅ。畸＝Ｍｉｎｉｍｕｍ（Ｌ裱）；／＊计算本次迭代的最优值＊／
ＦＯＲ每个ａｄ∈ｇｂｅ。仲。
｛彬”＝（１一ｙ）碍ｕ＋７・Ａｒ口；／＊ｙ为挥发系数＊／
ｆ１／（Ｌｂｅｓｔ－ｉｔｅｒ），当全局最优解包含
△句＝＜路径口ｄ时；
【０，否则；
）／＊全局信息素的更新＊／４）判断算法是否结束：ＩＦ（结束条件满足）ＴＨＥＮ
输出多次迭代后的最优解Ｌｋ。ｎ。，；
冀俊忠等：基于多粒度的旅行商问题描述及其蚁群优化算法
ＥＬＳＥ
｛迭代次数增ｌ初始化入区城市可访问的城市列表
ＧＯＴｏ
２）．）／＊继续进行下次迭代＊／
｝
粗粒度内的蚁群寻优算法完成后，便得到了各地区内城市的连接，如图２（ｄ）所示．３．４可行解的合成
按上述步骤依次完成粗粒度（地区）的寻优、粒度间的连接、粗粒度内细粒度（城市）的蚁群寻优后，就可以通过路径合成得到初始ＴＳＰ问题的一个可行解．如图２（ｅ）所示．该可行解表示本次周游所有城市后回到出发城市所经过的旅行长度，其计算公式如下：
Ｎ
ＬＩ＝∑Ｌｑ＋Ｌ地区何，
（３）
ｉ皇ｌ
其中Ｎ为粒度划分后得到的地区数（含孤立城市），ＬＤ为从某地区的入区城市出发遍历完所有该区的其他城市后到达出区城市的最短路径．对于孤立城市Ｌｎ＝Ｏ，Ｌ地区问为按照地区连接顺序，所有孤立城市、地区间边缘城市（入区、出区城市）连接的距
离和．
３．５循环分段优化算法
为了提高求解的时间性能，本文通过多粒度的描述模型，人为地将ＴＳＰ问题分解为较小规模的ＴＳＰ问题来进行求解．由于原始问题的最优解并不一定是所有小规模ＴＳＰ问题最优解的简单叠加。所以我们在获得原始问题的一个可行解后，摈弃粒度的划分，采用分段优化算法［９］对ＴＳＰ问题的可行解进行随机分段、分段始点移动和循环寻优的方法来优化所得到的解，提高可行解的质量．如图２（ｆ）所示，其具体的算法描述如下：
算法３．Ｓｕｂｓｅｃｔｉｏｎ－ｏｐｔｉｍｉｚａｔｉｏｎ（）．
｛
１）参数初始化：
Ｃ。ｌ。＝ｃ；／＊循环因子＊／
Ｓｕｂｓｅｃｔｉｏｎ—ｌｅｎｇｔｈ＝ｚ（ｎ／ｔ；）／＊分段长度，ｔ取大于２的整数＊／
ｃｏｕｎｔｅｒ＝Ｏ；
２）循环分段开始：
ＷＨＩＬ，Ｅ（ｃｏｕｎｔｅｒ≤，ｌ／Ｃ。ｌｅ）
｛ｓ￡口ｒ￡＝∞鲫据ｒ・Ｃ。心；／＊分段始点＊／
ＡＣＳ（ｓｔａｒｔ，Ｓｕｂｓｅｃｔｉｏｎ
ＩＦ（分段寻优结果优于原结果）更换该段的
４３９
解路径；｝
输出分段优化后的结果．
｝
算法中函数ＡＣＳ（ｓｔａｒｔ，Ｓｕｂｓｅｃｔｉｏｎ—ｌｅｎｇｔｈ）是由ＡＣＳ算法稍加修改后得到，其返回值是蚁群从分段始点出发，遍历该段所有其他城市后到达分段终点所得到的最短路径长度．３．６计算复杂度分析
假设ｎ为原始ＴＳＰ问题中城市的实际数量，ｍ为用ＡＣＳ蚁群算法求解时所需的蚂蚁数，ＡＣＳ算法经过Ｃ次迭代后得到最优的解，则ＡＣＳ算法求解ＴＳＰ问题的计算复杂度可近似为ｏ（Ｃ・ｎ２・优）Ｌ６］．
下面分析本文算法的计算复杂度：假设经过粒度划分将ｎ个城市分为Ｄ个地区，ｗ个孤立城市，
Ｄ
即咒＝铷＋＞：咒ｉ（啦为地区ｉ中的城市数量）．
葛
１）算法ｌ（粒度划分算法）的计算复杂度是
Ｏ（ｎｌｏｇ竹）［１引．
２）利用ＡＣＳ算法进行粗粒度寻优的计算复杂度为０（Ｇ・Ｎ２・ｍ。），Ｇ为粗粒度寻优的迭代次数，Ｎ＝ｗ＋Ｄ《，２，且所需的蚂蚁数为ｍ。≤Ｎ．由于ＴＳＰ规模大大降低，故Ｇ《Ｃ，ｍ。《ｍ，所以有０（Ｃｄ・Ｎ２・ｍＪ）《ｏ（Ｃ・竹２・优）．
’
假设第ｉ个地区为粒度划分后最大的地区（含有城市最多），且ｎ；一ｍａｘ｛ｎ。）（Ｏ＜最≤Ｄ）．由于地区内的寻优可并行进行，故算法２（细粒度寻优）的计算复杂度为ｏ（Ｇ・ｎ；・ｍｉ），Ｃｉ为迭代次数，ｍ，为所需的蚂蚁数，同样由于ＴＳＰ规模的大大降低，其值远小于ｏ（Ｃ・ｎ５２・仇）．
３）算法３（循环分段优化）的计算复杂度为Ｏ（Ｃ。。・（ｎｉｔ）２・仇。・惫），其中ｋ为分段循环次数，由于分段使问题规模下降，故Ｃ。＜Ｃ，优。＜ｍ，且合理选取参数后可使志／ｆ２＜１，故容易使ｏ（Ｃ。・（咒／￡）２・ｍ。。・志）＜０（Ｃ・ｎ２・ｍ）．
此外，粒度间连接的最大复杂度为０（Ｎ・ｎ；），而可行解合成的计算复杂度为０（以）．
综上所述，算法总的计算复杂度为：Ｏ（ｎｌｏｇｎ）＋０（Ｇ・Ｎ２・ｍｄ）＋ｏ（Ｎ・ｎ；）＋ｏ（Ｃｉ・ｎ；・ｍｆ）＋ｏ（以）＋０（Ｃ。・（ｎｉｔ）２・，，ｌ。・矗）≈惫・Ｏ（Ｃ。・（ｎ／
ｆ）２・ｍ。。），令ｃ／Ｃ。＝Ｐ，ｍ伽。＝ｑ，则算法计算复
杂度可表示为：（ｋ／ｐ・ｑ・ｔ２）・ｏ（Ｃ・ｎ２・，，１）．显然，与ＡＣＳ算法具有同级的计算复杂度．但是由于分段优化时至少分２段，故ｔ）－２，而分段后城市规模
４４０
计算机研究与发展２０１０，．４７（３）
的下降会使迭代次数、蚂蚁数都会减少，有Ｐ，ｑ＞ｌ，所以通常情况下惫伽・ｑ・ｔ２＜１总成立．可见，在ＴＳＰ问题城市规模较大、分段较多的情况下，合理选取参数后可使Ｏ（Ｃ・靠２・，，ｚ）成倍地减小．
４．１分段优化策略的作用
为测试分段优化策略对求解质量的作用，我们分别对不含分段优化过程的ＡＣＯＭＧＲ－１算法和含分段优化过程的本文算法ＡＣＯＭＧＲ的求解结果进行比较．表１给出了在各种事例最佳的参数配置下的实验结果．其中，最佳的解长度为２种算法各运行１０次所得到的最佳值，优化率为２种算法所得的最佳值的差与该问题标准最优解的比率．在相同的运行时间下，ＡＣＯＭＧＲ算法得到的最优解都明显好于ＡＣＯＭＧＲ－１算法，这说明分段优化策略能够提高本文所提出的算法的解质量，尤其是在大于４００的事例上效果明显．
图３给出了在Ｐｒｌ５２问题上２种算法的解图．比较图３中２个解图，正是由于一些局部连接的差异（虚线圆框内的连接部分），导致了２种算法所得到的最优解的不同．
４
实验结果
本部分对新算法的性能进行测试，并给出分段
优化策略对新算法求解质量的影响，本文算法在一些中大规模ＴＳＰ问题上的实验结果以及与一些最新蚁群算法在求解性能方面的实验比较．实验采用ＴＳＰＬＩＢ的标准库（来源于ｈｔｔｐ：／／ｅｌｉｂ．ｚｉｂ．ｄｅ／ｐｕｂ／ｍｐ—ｔｅｓｔｄａｔａ／ｔｓｐ／ｔｓｐｌｉｂ／ｔｓｐｌｉｂ．ｈｔｍｌ）．实验的运行环境为：操作系统ＷｉｎｄｏｗｓＸＰ，ＣＰＵ为Ｐ４１．８ＧＨｚ，内存为５１２ＭＢ，算法用ＶｉｓｕａｌＣ＋＋语言编程实现，实验的最佳参数组合均通过实验确定．
Ｔａｂｌｅｌ
ＰａｒａｍｅｔｅｒＳｅｔｓｏｆｔｈｅＰｒｏｐｏｓｅｄＡｌｇｏｒｉｔｈｍｆｏｒＤｉｆｆｅｒｅｎｔＩｎｓｔａｎｃｅｓａｎｄＳｕｂｓｅｃｔｉｏｎＯｐｔｉｍｉｚａｔｉｏｎＲｅｓｕｌｔｓ
表１本文算法在求解不同问题时的参数设置及分段优化的结果
Ｐａｒａｍｅｔｅｒ
Ｓｅｔｓ
ＯｐｔｉｍａｌＲｅｓｕｌｔｓ
Ｑ
１
ｃ
ＥＰＳＭｉｎＰｔｓ
口
８
ｐ
ＡＣＯＭＧＲ’１
ＡＣＯＭＧＲ
Ｏｐｔｉｍａｌ
Ｒａｔｅ］％
（ａ）
ｏｆ
ｔｗｏｓｏｌｕｔｉｏｎ
ｐｒｌ５２
ｆｏｒ
（ｂ）
ｇｒａｐｈｓ
ｏｎ
Ｆｉｇ．３Ｃｏｍｐａｒｉｓｏｎ
ｔＷＯｄｉｆｆｅｒｅｎｔａｌｇｏｒｉｔｈｍｓ．（ａ）Ｓｏｌｕｔｉｏｎｇｒａｐｈ
ｗｉｔｈｏｕｔｓｕｂｓｅｃｔｉｏｎｏｐｔｉｍｉｚａｔｉｏｎａｎｄ（ｂ）Ｓｏｌｕｔｉｏｎｇｒａｐｈｗｉｔｈｓｕｂｓｅｃｔｉｏｎｏｐｔｉｍｉｚａｔｉｏｎ．
图３在ｐｒｌ５２问题上的解图．（ａ）没有分段优化策略的解图；（ｂ）有分段优化策略的解图
４．２算法总体性能及分析
我们在许多较大规模的ＴＳＰ问题上进行了大量
的实验，并将本文算法与经典的ＡＣＳ算法、ＡＣＳ＋２０ｐｔ、ＧＡＣＳ…。和ＭＳＴ—Ａｎｔｓ［１３３等算法进行比较．实
冀俊忠等：基于多粒度的旅行商问题描述及其蚁群优化算法４４１
验所采用的参数如下：＂ｔｏ＝ｌ／ｎＬ。，ＡＣＳ算法的参数设置为口＝１，ｐ＝２，』Ｄ＝０．１，ｙ＝０．１，而本文算法运行时的参数设置见表１．
在上述参数配置下，我们经过多次实验得到本文算法与ＡＣＳ算法在各个ＴＳＰ问题上的求解结果，表２列出了实验的结果．其中，最佳的解长度为２种算法各运行１０次所得到的最佳值，运行时间为
Ｔａｂｌｅ２
ＣｏｍｐａｒｉｓｏｎｏｆＳｏｌｖｉｎｇＰｅｒｆｏｒｍａｎｃｅｆｏｒ
得到各自最佳值所需时间的平均值，误差为所得到的最佳值与数据库中该问题的标准最优解之间的相对偏差．从这些事例上的结果可见，本文算法在较短的时间内就能得到误差更小的解，这说明通过粒度划分思想降低ＴＳＰ问题的规模，大大缩短了寻优时间，提高了搜索效率，并在一些问题上获得更令人满意的解．
ＡＣｏＭＧＲａｎｄＡＣＳＡｌｇｏｒｉｔｈｍｓ
Ｏｎ
表２ＡＣＯＭＧＲ和经典的ＡＣＳ算法在不同ＴＳＰ问题上求解性能的比较
ＡＣＳＡｌｇｏｒｉｔｈｍ
ＩｎｓｔａｎｃｅｓｏｆＴＳＰ
ＯｐｔＬｍｕｍ
Ｓｏｌｕｔｉｏｎ————
ＤｉｆｆｅｒｅｎｔＩｎｓｔａｎｃｅｓＡＣＯＭＧＲ
Ｂｅｓｔｌｅｎｇｔｈ
Ｅｒｒｏｒ／
Ｒｕｎｔｉｍｅ／ｓ
Ｂｅｓｔ
ｌｅｎｇｔｈＥｒｒｏｒ／ＮＲｕｎｔｉｍｅ／ｓ
如前所述，针对经典的ＡＣＳ算法在时间性能方面的不足，国内外的许多研究都对它进行了改进，并在一些中小规模的ＴＳＰ问题上作了测试．其中，在求解Ｏｌｉｖｅｒ３０问题时，文献Ｅ８］给出的算法收敛速度可提高约６倍，文献［１１］提出的算法收敛速度可提高约１１倍；文献［１２］给出了一些更好的实验结果，该文所提出的算法在一些ＴＳＰ问题上的收敛速度可提高数十到数百倍，例如，在求解ｅｌｌ５１时提高
Ｔａｂｌｅ３
Ｃｏｍｐａｒｉｓｏｎｏｆ
率为２５００１７≈３５７倍，在求解Ｓｔ７０时提高率约为６０００／２０＝３００倍，在求解Ｐｒｌ０７时提高率为６７００／３３０≈２０倍，在求解Ｄ１１９８时提高率为１００００１８００＝１２．５，但不难发现，该算法收敛速度的提高随ＴＳＰ事例中城市数的增加逐渐降低；而国外新近的几篇文献则更系统、详细地给出了一些改进算法的结果，表３列出了本文算法与其中几个改进算法的实验比较：
ｏｎ
Ｓｏｌｖｉｎｇ
Ｐｅｒｆｏｒｍａｎｃｅｆｏｒ
ＡＣＯＭＧＲａｎｄＳｏｍｅＩｍｐｒｏｖｅｄＡｌｇｏｒｉｔｈｍｓ
ＤｉｆｆｅｒｅｎｔＩｎｓｔａｎｃｅｓ
表３ＡＣＯＭＧＲ和一些改进算法在不同ＴＳＰ问题上求解性能的比较
ＡＣＳ＋２－ｏｐｔＣｌ４］
ＧＡＣｓ［１４】
ＭＳＴ—Ａｎｔｓ［１３］
ＡＣＯＭＧＲ
Ｉｎｓｔａｎｃｅｓｏｆ
ＴＳＰ——
ＡＣＳ
ＲＰＤ／％
１Ｏ７１３６１２４１５２２２６州¨“７刍４ＨＫＫ
ＯＯＯＯＯ２Ｚ９
●
ＲＰＤ／％ＴＩＲ
０Ｏ０Ｏ０１２
●
ＲＰＤ／％ＴＩＲ
０Ｏ０ＯＯ１ＺＯ１５８Ｏ５
～
ＲＰＤ／％ＴＩＲ
ＯＯＯＯ０Ｏ１Ｏ７Ｏ７８８Ｏ５一
●
ＲＰＤ／％ＴＩＲ
ＯＯＯＯＯ０ｌ２
●
５８２１３ｌ８６６５８７６７
４５ｌＯ５Ｏ６３ｌ９９２６
一
１６２Ｏ１Ｚ１
●
６７１１５４９３２４２
１
２８
Ｏ１１Ｏ３１
●
３２Ｏ６ｌ６
１８４
●
９５７４７２４４ＺＯ７１５
Ｏ９７５１４９１Ｏ４７２７Ｏ９１３
４８１１ｌ２２２２９４８６２
●
６３６３８７４１８４４４３
●
●●●●
５ｌ５３３ｌ８１２５８２
一
●●●●
●
●●●●●●
●
●●●
●
ｌ３
１ｌ８８
●●●
●●
●●●●●
●●
●●
●●●●●
●
３
１５７９
●●
●●●●
●●
●
一
．
一
●●
．
●
●
●
婚一博一吒＿
Ｏ一
●
９一６－
—
■
一－－
一
■
一一
＿
一
■
一＿．
—
●
一＿－—
■
一一．－
．－一＿—
■３—
３一一—－
７—９—
■
６一１—
４４２
表３中ＲＰＤ（ｒｅｌａｔｉｖｅ
ｐｅｒｃｅｎｔａｇｅ
ｄｅｖｉａｔｉｏｎ
ｏｎ
ｔｈｅｏｐｔｉｍａｌ
ｓｏｌｕｔｉｏｎ）为算法各自求得的最优解与
标准最优解的相对偏差，ＴＩＲ（ｔｉｍｅ
ｉｍｐｒｏｖｅｄｒａｔｅ）
为ＡＣＳ算法运行时间与各种算法获得各自最优解时所需的运行时间的比率，ＡＣＳ＋２－ｏｐｔ和ＧＡＣＳ的实验结果源于文献［１３］，ＭＳＴ—Ａｎｔｓ的实验结果源于文献［１４］，“一”为没提供．从表３可见：１）本文算法在收敛时间性能的改进上具有较大优势。在大部分事例上都具有最高的改进率（ＴＩＲ的值最高）；２）本文算法在时间性能上改进率随ＴＳＰ事例中城市数的增加而增大，体现了算法求解大规模ＴＳＰ事例的能力，而其他算法没有这样的趋势．
对比ＡＣＳ算法，图４给出了本文算法在收敛时间上的改进率．尽管本文算法在时间性能方面的改进率只有数倍到数十倍，但却显现出～种非常有潜力的趋势：算法收敛时间的改进随城市规模的增大而增大．究其原因，主要是因为本文算法将多粒度思想引入到ＴＳＰ问题的描述中，从根本上将大规模ＴＳＰ问题归约为容易求解的小规模问题来求解，故有可能有效地克服或避免“组合爆炸”问题，快速地求解原问题．而且，本文给出的ＴＳＰ问题的多粒度描述模型能被方便地扩展，得到更多层粒度的描述模型，从而为解决更大更复杂的ＴＳＰ问题提供・个可行的思路．
Ｆｉｇ．４
Ｉｍｐｒｏｖｅｍｅｎｔ
ｒａｔｅｓｏｆｔｈｅ
ＡＣＯＭＧＲａｌｇｏｒｉｔｈｍ
ｏｎ
ｒｕｎｔｉｍｅｆｏｒｄｉｆｆｅｒｅｎｔＴＳＰｉｎｓｔａｎｃｅｓ．
图４本文算法在不同ＴＳＰ事例上时间性能的改进率
然而，尽管本文算法在提高蚁群算法时间性能方面效果显著，但正如表３所示：算法在一些事例上所得到的最优解不如一些改进算法好．主要原因是本文算法的设计较依赖于所求解的问题中城市分布的特征，即对于具有明显聚类特征的大规模ＴＳＰ问题求解时，往往能快速得到较好的结果，而在处理分布特征不明显的ＴＳＰ问题时，解的精度欠佳．
计算机研究与发展２０ｌＯ，４７（３）
５结论及进一步的工作
蚁群算法是一种元启发式的随机搜索技术，由于具有鲁棒性、正反馈以及可并行计算等特点，所以成为目前解决组合优化问题最成功的算法之一．然而，蚁群算法在求解大规模组合优化问题时，收敛时间过长仍是制约其广泛应用的瓶颈．为此，本文给出了一种ＴＳＰ问题的多粒度描述模型，并基于该模型提出了一种新的ＴＳＰ问题的蚁群求解算法．该算法利用ＴＳＰ问题的多粒度描述将难解的大规模ＴＳＰ问题分解为易于求解的小规模ＴＳＰ问题来求解．由于粒度的划分大大缩小了原问题的规模，所以算法的计算复杂度能成倍地降低．在一些中、大规模的ＴＳＰ问题上的实验表明：新算法在求解速度上不仅比经典的ＡＣＳ算法有显著的提高，而且比一些新近的算法具有更强的求解大规模ＴＳＰ问题的能力．
本文提出的蚁群算法，为快速求解大规模ＴＳＰ问题提供了一种新方法，也为解决其他大规模组合优化问题提供了一种新思路，是蚁群算法快速收敛问题研究的一个新成果．但如前所述，本文算法在提高解质量方面具有一定的局限性，如何克服这个局限，在快速求解的前提下提高求解精度将是我们下一步研究的重点．
参考文献
［１３Ｄｏｒｉｇｏ
Ｍ。Ｍａｎｉｅｚｚｏ
Ｖ，Ｃｏｌｏｒｎｉ
Ａ．Ｔｈｅ
ａｎｔ
ｓｙｓｔｅｍ：
Ｏｐｔｉｍｉｚａｔｉｏｎ
ｂｙ
ａ
ｃｏｌｏｎｙｏｆ
ｃｏｏｐｅｒａｔｉｎｇ
ａｇｅｎｔｓ口］．ＩＥＥＥ
Ｔｒａｎｓ
ｏｎ
Ｓｙｓｔｅｍｓ。Ｍａｎ，ａｎｄＣｙｂｅｒｎｅｔｉｃｓ。ＰａｒｔＢ．１９９６，２６
（１）：２９—４１
［２］Ｇａｍｂａｒｄｅｌｌａ
Ｌ
Ｍ，Ｄｏｒｉｇｏ￣ＬＳｏｌｖｉｎｇｓｙｍｍｅｔｒｉｃ
ａｎｄ
ａｓｙｍｍｅｔｒｉｃ
ＴＳＰｓ
ｂｙ
ａｎｔ
ｃｏｌｏｎｉｅｓ［ｃＪ／／Ｐｒｏｃｏｆｔｈｅ
Ｉｎｔ
Ｃｏｎｆ
ｏｎ
Ｅｖｏｌｕｔｉｏｎａｒｙ
Ｃｏｍｐｕｔａｔｉｏｎ．Ｐｉｓｃａｔａｗａｙ，ＮＪ：ＩＥＥＥ，
１９９６ｚ
６２２—６２７
［３３
ＢｌｕｍＣ。ＤｏｒｉｇｏＭ．Ｓｅａｒｃｈｂｉａｓｉｎ
ａｎｔ
ｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎ
ｌ
Ｏｎ
ｔｈｅ
ｒｏｌｅｏｆ
ｃｏｍｐｅｔｉｔｉｏｎ－ｂａｌａｎｃｅｄｓｙｓｔｅｍｓ［／Ｊ．ＩＥＥＥ
Ｔｒａｎｓ
ｏｎ
Ｅｖｏｌｕｔｉｏｎａｒｙ
Ｃｏｍｐｕｔａｔｉｏｎ，２００５，９（２）：１５９－１７４
［４］Ｂｌｕｍ
Ｃ，ＤｏｒｉｇｏＭ．Ｔｈｅｈｙｐｅｒ－ｃｕｂｅ
ｆｒａｍｅｗｏｒｋ
ｆｏｒ
ａｎｔ
ｃｏｌｏｎｙ
ｏｐｔｉｍｉｚａｔｉｏｎ口］．ＩＥＥＥ
Ｔｒａｎｓ
ｏｎ
Ｓｙｓｔｅｍｓ，Ｍａｎ，ａｎｄ
Ｃｙｂｅｒｎｅｔｉｃｓ，２００４，３４（２）ｌ１１６１－１１７２
［５］ＤｏｒｉｇｏＭ，ＢｉｒａｔｔａｒｉＭ，ＳｔｕｔｚｌｅＴ．Ａｎｔｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎ：
Ａｒｔｉｆｉｃｉａｌ
ａｎｔｓ
ａｓ
ａ
ｃｏｍｐｕｔａｔｉｏｎａｌｉｎｔｅｌｌｉｇｅｎｃｅｔｅｃｈｎｉｑｕｅ［Ｊ］．
ＩＥＥＥＣｏｍｐｕｔａｔｉｏｎａｌＩｎｔｅｌｌｉｇｅｎｃｅＭａｇａｚｉｎｅ，２００６，１（１１）ｌ
２８—３９
冀俊忠等：基于多粒度的旅行商问题描述及其蚁群优化算法４４３
Ｅ６－］Ｄｏｒｉｇｏ
Ｍ，Ｇａｍｂａｒｄｅｌｌａ
Ｌ
Ｍ．Ａｎｔ
ｃｏｌｏｎｙ
ｓｙｓｔｅｍ：Ａ
ｃｏｏｐｅｒａｔｉｖｅｌｅａｒｎｉｎｇ
ａｐｐｒｏａｃｈ
ｔｏ
ｔｈｅ
ｔｒａｖｅｌｉｎｇ
ｓａｌｅｓｍａｎ
ｐｒｏｂｌｅｍ【Ｊ］．ＩＥＥＥ
Ｔｒａｎｓ
０ｎ
ＥｖｏｌｕｔｉｏｎａｒｊｒＣｏｍｐｕｔａｔｉｏｎ，
１９９７，ｌ（Ｉ）：５３－６６
Ｅ７３ＳｔｕｔｚｌｅＴ，ＨｏｏｓＨＨ．ＭＡＸ－ＭＩＮ
ａｎｔ
ｓｙｓｔｅｍｉ－Ｊ１．Ｆｕｔｕｒｅ
ＧｅｎｅｒａｔｉｏｎＣｏｍｐｕｔｅｒＳｙｓｔｅｍ，２０００．１６（８）：８８９－９１４
Ｆ８ＪＨｕａｎｇ
Ｇｕｏｒｕｉ，Ｃａｏ
Ｘｉａｎｂｉｎ，Ｗａｎｇ
Ｘｕｆａ．Ａｎａｎｔ
ｃｏｌｏｎｙ
ｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎ
ｐｈｅｒｏｍｏｎｅｄｉｆｆｕｓｉｏｎ［Ｊ］．
Ａｅｔａ
Ｅｌｅｃｔｒｏｎｉｃｓ
Ｓｉｎｉｃａ，２００４．３２（５）：８６５－８６８（ｉｎＣｈｉｎｅｓｅ）
（黄国锐，曹先彬，王煦法．基于信息素扩散的蚁群算法［Ｊ３．电子学报，２００４，３２（５）：８６５—８６８）Ｅ９－１
ＷｕＢｉｎ，ＳｈｉＺｈｏｎｇｚｈｉ．Ａｎ
ａｎｔ
ｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍ
ｂａｓｅｄ
ｐａｒｔｉｔｉｏｎ
ａｌｇｏｒｉｔｈｍｆｏｒＴＳＰ［Ｊ］．ＣｈｉｎｅｓｅＪｏｕｒｎａｌｏｆ
Ｃｏｍｐｕｔｅｒｓ。２００１，２４（１３）：１３２８—１３３３（ｉｎＣｈｉｎｅｓｅ）
（吴斌，史忠植．一种基于蚁群算法的ＴＳＰ问题分段求解算法［Ｊ］．计算机学报，２００１，２４（１３）：１３２８—１３３３）
［１０］ＷｕＱｉｎｇｈｏｎｇ，ＺｈａｎｇＪｉｈｕｉ，ＸｕＸｉｎｈｅ．Ａｎ
ａｎｔ
ｃｏｌｏｎｙ
ａｌｇｏｒｉｔｈｍｗｉｔｈｍｕｔａｔｉｏｎ
ｆｅａｔｕｒｅｓ［Ｊ３．ＪｏｕｒｎａｌｏｆＣｏｍｐｕｔｅｒ
ＲｅｓｅａｒｃｈａｎｄＤｅｖｅｌｏｐｍｅｎｔ．１９９９，３６（１０）ｌ１２４０—１２４５（ｉｎ
Ｃｈｉｎｅｓｅ）
（吴庆洪，张纪会，徐心和．具有变异特征的蚁群算法［Ｊ３．计算机研究与发展，１９９９，３６（１０）：１２４０－１２４５）
［１１］Ｄｉｎｇ
Ｊｉａｎｌｉ，Ｃｈｅｎ
Ｚｅｎｇｑｉａｎｇ，Ｙｕａｎ
Ｚｈｕｚｈｉ．Ｏｎ
ｔｈｅ
ｃｏｍｂｉｎａｔｉｏｎｏｆ
ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍａｎｄ
ａｎｔ
ａｌｇｏｒｉｔｈｍＥＪ３．
ＪｏｕｒｎａｌｏｆＣｏｍｐｕｔｅｒＲｅｓｅａｒｃｈａｎｄＤｅｖｅｌｏｐｍｅｎｔ・２００３・４０
（９）：１３５１—１３５６（ｉｎＣｈｉｎｅｓｅ）
（丁建立，陈增强，褒著祉．遗传算法与蚂蚁算法的融合ＥＪ３．计算机研究与发展，２００３，４０（９）：１３５１—１３５６）
［１ｚ］Ｚｈｕ
Ｑｉｎｇｂａｏ，Ｙａｎｇ
Ｚｈｉｊｕｎ．Ａｎａｎｔ
ｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍ
ｂａｓｅｄ
ｏｎｍｕｔａｔｉｏｎ
ａｎｄ
ｄｙｎａｍｉｃ
ｐｈｅｒｏｍｏｎｅ
ｕｐｄａｔｉｎｇ口］．Ｊｏｕｒｎａｌ
ｏｆ
Ｓｏｆｔｗａｒｅ，２００４。１５（２）：１８５—１９２
（ｉｎ
Ｃｈｉｎｅｓｅ）
（朱庆保，杨志军．基于变异和动态信息素更新的蚁群优化算法［Ｊ］．软件学报，２００４，１５（２）；１８５—１９２）
［１３］ＲｅｉｍａｎｎＭ．Ｇｕｉｄｉｎｇ
ＡＣＯｂｙｐｒｏｂｌｅｍｒｅｌａｘａｔｉｏｎ：Ａ
ｃａｓｅ
ｓｔｕｄｙ
ｏｎ
ｔｈｅｓｙｍｍｅｔｒｉｃＴＳＰ［Ｇ］／ＩＬＮＣＳ４７７１．Ｂｅｒｌｉｎ
ｌ
Ｓｐｒｉｎｇｅｒ。２００７：４５－５６［１４］ＬｅＬｏｕａｍＦＸ，ＧｅｎｄｒｅａｕＭ，ＰｏｔｖｉｎＪＹ．ＧＥＮＩａｎｔｓｆｏｒｔｈｅ
ｔｒａｖｅｌｌｉｎｇ
ｓａｌｅｓｍａｎ
ｐｒｏｂｌｅｍ［刀．Ａｎｎａｌｓｏｆ
Ｏｐｅｒａｔｉｏｎｓ
Ｒｅｓｅａｒｃｈ。２００４。１３１（１０）：１８７—２０１
［１５３
Ｌｉ
Ｂｉｎｇｙｕ，Ｘｉａｏ
Ｙｕｎｓｈｉ．Ａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｂａｓｅｄ
ｏｎ
ｍｏｄｅｌａｌｇｏｒｉｔｈｍｆｏｒｔｒａｖｅｌｉｎｇｓａｌｅｓｍａｎｐｒｏｂｌｅｍ口］．Ｊｏｕｒｎａｌ
ｏｆＴｏｎｇｊｉＵｎｉｖｅｒｓｉｔｙ，２００３，３１（１１）：１３４８—１３５２（ｉｎＣｈｉｎｅｓｅ）
（李炳宇，萧蕴诗．基于模式求解旅行商问题的蚁群算法［Ｊ－Ｉ．同济大学学报，２００３，３１（１１）：１３４８—１３５２）
［１６３
ＺｏｕＰｅｎｇ。Ｚｈｏｕ
Ｚｈｉ，ＣｈｅｎＧｕｏｌｉａｎｇ，ｅｔａＬ
Ａ
ｍｕｌｔｉｌｅｖｅｌ
ｒｅｄｕｃｔｉｏｎ
ａｌｇｏｒｉｔｈｍ
ｔｏ
ＴｓＰ［刀．Ｊｏｕｒｎａｌｏｆ
Ｓｏｆｔｗａｒｅ，２００３，
１４（１）：３５－４２（ｉｎＣｈｉｎｅｓｅ）
（邹鹏，周智。陈国良，等．求解ＴＳＰ问题的多级归约算法［Ｊ］．软件学报，２００３，１４（１）：３５－４２）
［１７］ＺｈａｎｇＹａｎｐｉｎｇ，ＺｈａｎｇＬｉｎｇ，ＷｕＴａｏ．Ｔｈｅ
ｒｅｐｒｅｓｅｎｔａｔｉｏｎ
ｏｆ
ｄｉｆｆｅｒｅｎｔｇｒａｎｕｌａｒ
ｗｏｒｌｄｓ：Ａ
ｑｕｏｔｉｅｎｔ
ｓｐａｃｅ口］．Ｃｈｉｎｅｓｅ
ＪｏｕｒｎａｌｏｆＣｏｍｐｕｔｅｒｓ，２００４，２７（３）：３２８—３３３（ｉｎＣｈｉｎｅｓｅ）
（张燕平，张铃．吴涛．不同粒度世界的描述法——商空间法
［Ｊ］．计算机学报，２００４，２７（３）：３２８－３３３）
［１８］ＥａｓｔｅｒＭ，Ｋｒｉｅｇｅｌ
Ｈ
Ｐ，ＳａｎｄｅｒＪ，ｅｔａ１．Ａｄｅｎｓｉｔｙ－ｂａｓｅｄ
ａｌｇｏｒｉｔｈｍｆｏｒｄｉｓｃｏｖｅｒｉｎｇｃｌｕｓｔｅｒｓ
ｉｎｌａｒｇｅ
ｓｐａｔｉａｌ
ｄａｔａｂａｓｅｓｗｉｔｈ
ｎｏｉｓｅ［ｃ］／／Ｐｒｏｃｏｆ
ｔｈｅ
Ｉｎｔ
Ｃｏｎｆ
ｏｎ
Ｋｎｏｗｌｅｄｇｅ
Ｄｉｓｃｏｖｅｒｙ
ａｎｄ
Ｄａｔａ
Ｍｉｎｉｎｇ（ＫＤＤ－９６）．ＭｅｎｌｏＰａｒｋ，ＣＡ：
ＡＡＡＩ，１９９６：２２６－２３１
［１９３ｊｉＪｕｎｚｈｏｎｇ．ＨｕａｎｇＺｈｅｎ，Ｌｉｕ
Ｃｈｕｎｎｉａｎ．Ａｆａｓｔ
ａｎｔ
ｃｏｌｏｎｙ
ｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｆｏｒｔｒａｖｅｌｉｎｇｓａｌｅｓｍａｎｐｒｏｂｌｅｍｓ［Ｊ］．
Ｊｏｕｒｎａｌｏｆ
Ｃｏｍｐｕｔｅｒ
Ｒｅｓｅａｒｃｈａｎｄ
Ｄｅｖｅｌｏｐｍｅｎｔ，２００９，４６
（６）：９６８—９７８（ｉｎＣｈｉｎｅｓｅ）
（冀俊忠，黄振，刘椿年．一种快速求解旅行商问题的蚁群算法［Ｊ］．计算机研究与发展。２００９，４６（６）：９６８—９７８）
ＪｉＪｕｎｚｈｏｎｇ。ｂｏｒｎｉｎ１９６９．ＰｈＤｏｆ
Ｂｅｉｊｉｎｇ
Ｕｎｉｖｅｒｓｉｔｙｏｆ
Ｔｅｃｈｎｏｌｏｇｙ．Ｐｒｏｆｅｓｓｏｒ．
Ｓｅｎｉｏｒ
ｍｅｍｂｅｒ
ｏｆＣｈｉｎａＣｏｍｐｕｔｅｒＦｅｄｅｒａｔｉｏｎ．Ｈｉｓｍａｉｎ
ｒｅｓｅａｒｃｈ
ｉｎｔｅｒｅｓｔｓ
ｉｎｃｌｕｄｅｍａｃｈｉｎｅ
ｌｅａｒｎｉｎｇ，Ｗｅｂ
ｉｎｔｅｌｌｉｇｅｎｃｅ，
ａｎｄｃｏｍｐｕｔａｔｉｏｎｉｎｔｅｌｌｉｇｅｎｃｅ．
冀俊忠，１９６９年生，博士，教授，中国计算机学会高级会员，主要研究方向为机器学习、Ｗｅｂ智能、计算智能．
ＨｕａｎｇＺｈｅｎ，ｂｏｒｎ
ｉｎ
１９８１．Ｍａｓｔｅｒ．Ｈｉｓ
ｍａｉｎｒｅｓｅａｒｃｈｉｎｔｅｒｅｓｔｓｉｎｃｌｕｄｅｄａｔａｍｉｎｉｎｇ
ａｎｄ
Ｗｅｂｉｎｔｅｌｌｉｇｅｎｃｅ．
黄振。１９８１年生，硕士，主要研究方向为数据挖掘、ｗｅｂ智能．
ＬｉｕＣｈｕｎｎｉａｎ．ｂｏｒｎｉｎ１９４４．ＰｒｏｆｅｓｓｏｒａｎｄＰｈＤｓｕｐｅｒｖｉｓｏｒ．ＲｅｃｅｉｖｅｄｈｉｓＢＳｃｄｅｇｒｅｅ
ｉｎ
ｍａｔｈｅｍａｔｉｃｓｆｒｏｍＰｅｋｉｎｇＵｎｉｖｅｒｓｉｔｙ，
ｈｉｓ
ＭＳＣ
ｄｅｇｒｅｅ
ｉｎ
ｃｏｍｐｕｔｅｒ
ｓｃｉｅｎｃｅ
ｆｒｏｍ
ＢｅｉｊｉｎｇＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，ａｎｄｈｉｓ
ＰｈＤ
ｄｅｇｒｅｅ
ｉｎ
ｓｏｆｔｗａｒｅ
ｅｎｇｉｎｅｅｒ
ｆｒｏｍ
ＮｏｒｗｅｇｉａｎＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ．Ｈｉｓｍａｉｎｒｅｓｅａｒｃｈ
ｉｎｔｅｒｅｓｔｓ
ｉｎｃｌｕｄｅ
ｄａｔａ
ｍｉｎｉｎｇ，ｉｎｄｕｃｔｉｖｅ
ｌｏｇｉｃ
ｐｒｏｇｒａｍｍｉｎｇ，ｃｏｎｓｔｒａｉｎｔｐｒｏｇｒａｍｍｉｎｇ，ｍａｃｈｉｎｅｌｅａｒｎｉｎｇ
ａｎｄｓｏｆｔｃｏｍｐｕｔｉｎｇ．
刘椿年，１９４４年生，教授。博士生导师，主要研究方向为数据挖掘、人工智能、约束逻辑程序设计．
Ｄａｉ
Ｑｉｇｕｏ，ｂｏｒｎｉｎ１９８５．Ｍａｓｔｅｒｃａｎｄｉｄａｔｅ
ｏｆ
ＢｅｉｊｉｎｇＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ．Ｈｉｓ
ｍａｉｎｒｅｓｅａｒｃｈｉｎｔｅｒｅｓｔｓｉｎｃｌｕｄｅｄａｔａｍｉｎｉｎｇａｎｄｃｏｍｐｕｔａｔｉｏｎｉｎｔｅｌｌｉｇｅｎｃｅ．
代启国．１９８５年生，硕士研究生，主要研究
方向为数据挖掘、计算智能．
４４４
计算机研究与发展２０１０．４７（３）
ＲｅｓｅａｒｃｈＢａｃｋｇｒｏｕｎｄ
Ａｎｔｃｏｌｏｎｙ
ｏｐｔｉｍｉｚａｔｉｏｎ（ＡＣＯ）ａｌｇｏｒｉｔｈｍｉｓ
ａ
ｍｅｔａｈｅｕｒｉｓｔｉｃａｎｄｓｔｏｃｈａｓｔｉｃｓｅａｒｃｈｔｅｃｈｎｏｌｏｇｙ，ｗｈｉｃｈｈａｓｂｅｅｎ
ａ
ｏｎｅ
ｏｆｔｈｅ
ｅｆｆｅｃｔｉｖｅｔｏｏｌｓｆｏｒｓｏｌｖｉｎｇｄｉｓｃｒｅｔｅｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓ．Ｈｏｗｅｖｅｒ，ｔｈｅｒｅｉｓｍｕｃｈｔｉｍｅ
ｔＯ
ｂｏｔｔｌｅｎｅｃｋｔｈａｔ
ｐｒｏｐｏｓｅｓ
ａ
ｔｈｅＡＣＯａｌｇｏｒｉｔｈｍｎｏｖｅｌａｎｄｈｉｇｈ
ＣＯＳＴＳｔＯＯ
ｓｏｌｖｅｔｈｅｉａｒｇｅ－ｓｃａｌｅｄｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓ．Ｔｈｅｒｅｆｏｒｅ，ｔｈｉｓ
ｐａｐｅｒ
ｅｆｆｉｃｉｅｎｔＡＣＯ
ａｌｇｏｒｉｔｈｍｆｏｒｔｈｅｔｒａｖｅｌｉｎｇｓａｌｅｓｍａｎｐｒｏｂｌｅｍｓ（ＴＳＰｓ）．Ｆｉｒｓｔ，ａｎｏｖｅｌｍｕｌｔｉｐｌｅ－ｇｒａｉｎｒｅｐｒｅｓｅｎｔａｔｉｏｎｍｏｄｅｌｏｆＴＳＰｓｉｓｐｒｏｐｏｓｅｄ．Ｂａｓｅｄ
ｏｎ
ｔｈｅｍｏｄｅｌ，ｔｈｉｓｐａｐｅｒ
ｏｎ
ｐｒｅｓｅｎｔｓ
ａ
ｎｅｗ
ａｌｇｏｒｉｔｈｍｆｏｒＴＳＰｓ，ｗｈｉｃｈｍａｉｎｌｙｃｏｎｔａｉｎｓｓｉｘｐｈａｓｅｓ，ｉ．ｅ．ａｇｒａｎｕｌａｒｉｔｙ
ｏｎ
ｐａｒｔｉｔｉｏｎａｌｇｏｒｉｔｈｍｂａｓｅｄｄｅｎｓｉｔｙｃｌｕｓｔｅｒｉｎｇ，ａｎＡＣＯａｌｇｏｒｉｔｈｍｂａｓｅｄ
ｔｈｅ
ｓａｍｅ
ｔｈｅ
ｃｏａｒｓｅ
ｇｒａｉｎ，ａ
ｃｏｎｎｅｃｔｉｏｎａｌｇｏｒｉｔｈｍｂｅｔｗｅｅｎ
ａ
ｔｗｏｇｒａｎｕｌａｒｉｔｉｅｓ，ａｎＡＣＯａｌｇｏｒｉｔｈｍｉｎｇｒａｎｕｌａｒｉｔｙ，ａｆｕｓｉｏｎａｌｇｏｒｉｔｈｍ
ａｍｏｎｇｇｒａｎｕｌａｒｉｔｉｅｓ，ａｎｄ
ｏｆ
ＴＳＰｓ
ｓｕｂｓｅｃｔｉｏｎ
ｔｈｅ
ｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｒｅｇａｒｄｌｅｓｓｏｆｇｒａｎｕｌａｒｉｔｉｅｓ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｆｏｒｌａｒｇｅｎｕｍｂｅｒｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｃｏｍｐｅｔｉｔｉｖｅｉｎｒｅｓｅａｒｃｈ
ｔｉｍｅ
ｃａｎ
ｄｅｍｏｎｓｔｒａｔｅｔｈａｔ
ｉｓ
ｇｒｅａｔｌｙｉｍｐｒｏｖｅｔｈｅｓｐｅｅｄｏｆ
ｃｏｎｖｅｒｇｅｎｃｅ
ｉｎｃｏｎｔｒａｓｔｔｏ
ｔｈｅｃｌａｓｓｉｃａｌＡＣＳａｌｇｏｒｉｔｈｍ．ａｎｄ
ｈｉｇｈｌｙ
ｐｅｒｆｏｒｍａｎｃｅｃｏｍｐａｒｅｄｗｉｔｈｓｏｍｅｌａｔｅｓｔｅｌｉｔｉｓｔＡＣＯａｌｇｏｒｉｔｈｍｓ．Ｏｕｒｗｏｒｋｉｓｓｕｐｐｏｒｔｅｄｂｙｔｈｅｍａｊｏｒ
ｐｒｏｇｒａｍｏｆｔｈｅＮａｔｉｏｎｓｌＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＣｈｉｎａ（Ｎｏ．６０４９６３２２）。ｔｈｅＢａｓｉｃＴｈｅｏｒｙａｎｄＣｏｒｅＴｅｃｈｎｉｑｕｅｓ
ｏｆＮｏｎ－ＣａｎｏｎｉｃａｌＫｎｏｗｌｅｄｇｅ（Ｎｏｓ．６０４９６３２２，６０４９６３２７），ａｎｄｔｈｅ
ＢｅｉｊｉｎｇＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎ（Ｎｏ．４０８３０３４）．
第１７届全国网络与数据通信学术会议（ＮＤＣＣ２０１０）征文通知
２０１０年９月１６Ｅｌ一１７日
北戴河
由中国计算机学会网络与数据通信专业委员会主办，由东北大学秦皇岛分校和东北大学信息科学与工程学院联合承办的“第１７届全国网络与数据通信学术会议”将于２０１０年９月１６日到１７日在美丽的海滨城市北戴河举行．
本次大会将围绕“网络与通信新技术及应用”这一主题展开，为来自国内外高等院校、科研院所、企事单位的学者、教授、专家、工程师提供一个代表国内网络与数据通信产学研界高水平的高层信息交流平台，探讨本领域发展所面临的关键挑战问题和热点研究方向．
会议论文集将由《东北大学学报（自然科学版）》增刊出版（ＥＩ检索源）．论文参照《东北大学学报》格式，字数一般不超过６０００字，稿件通过投稿系统提交，具体参见会议网站ｈｔｔｐ：／／ｎｄｃｃ２０１０．ｎｅｕｑ．ｅｄｕ．ｃｎ．部分优秀论文将被推荐到《计算机学报》，《电子学报》、《计算机研究与发展》、《电子与信息学报》的正刊发表（均为ＥＩ检索源）．会议期间将评选会议优秀论文和优秀学
生论文．
本次会议的主要征文范围包括以下领域（但不限于）：
新一代网络技术：网络体系结构、路由／交换技术、协议丁程、网络虚拟化、认知网络、ＩＰｖ４／ＩＰｖ６过渡技术、ＮＧＮＩＮＧＩ平台应用；新一代计算技术：云计算／网格计算、并行／分布式计算、普适／效用计算、服务计算；无线通信技术：下一代移动通信技术、自适应信号处理、传感器网络、移动自组织网络、智能天线、卫星通信；其他；光通信技术、网络安全、网络管理、网络应用．
投稿须知
１）投稿内容突出作者的创新与成果，具有较重要的学术价值与应用推广价值，未在国内外公开发行的刊物或会议上发表
或宣读过．
２）论文语言要求中文，字数一般不超过６０００字，论文格式参照《东北大学学报》，投稿稿件用Ｗｏｒｄ文件形式．东北大学学报的网站地址如下：ｈｔｔｐ：／ｌｘｕｅｂａｏ．ｎｅｄ．ｅｄｕ．ｅｎ／ｎａｔｕｒａｌ／ｉｎｄｅｘ．ａｓｐ．
３）请在稿件最后附上第一作者姓名、性别、职务／职称，所属单位、通信地址、邮政编码、联系电话和Ｅ—ｍａｉｌ地址．并注明论文所属领域．
４）被录用的论文，至少要有一位作者参加会议并发盲，才有资格参与优秀论文的评选．
投稿方式
论文投稿通过投稿系统进行提交，详见会议网站：ｈｔｔｐ：／／ｎｄｃｃ２０１０．ｎｅｕｑ．ｅｄｕ．ｃｎ或者通过邮件地址ｎｄｅｃ２０１０＠ｍａｉｌ．ｎｅｕｑ．ｅｄｕ．ｃｎ联系．电子邮件请在邮件标题注明“ＮＤＣＣ２０１０投稿”．
重要日期
论文提交截止日期：２０１０年５月１５日；论文录用通知日期：２０１０年７月１日；会议注册截止日期：２０１０年８月１５日．联系方式
联系电话：０３３５—８０５２１５５
邮件地址：ｎｄｅｅ２０１０＠ｍａｉｌ．ｎｅｕｑ．ｅｄｕ．ｃｎ
联系人ｌ王翠荣韩来权
会议网站：ｈｔｔｐ：／／ｎｄｅｃ２０１０．ｎｅｕｑ．ｅｄｕ．ｅｆｔ
计算机研究与发展
ＪｏｕｒｎａｌｏｆＣｏｍｐｕｔｅｒＲｅｓｅａｒｃｈａｎｄＤｅｖｅｌｏｐｍｅｎｔ
ＩＳＳＮ
１０００—１２３９／ＣＮ１１—１７７７／ＴＰ
４７（３）：４３４—４４４．２０１０
基于多粒度的旅行商问题描述及其蚁群优化算法
冀俊忠
黄振刘椿年代启国
１００１２４）
（北京工业大学计算机学院多媒体与智能软件技术北京市重点实验室北京
（ｊｊｚ０１＠ｂｉｕｔ．ｅｄｕ．ｃｎ）
Ａｎ
Ａｎｔ
ＣｏｌｏｎｙＡｌｇｏｒｉｔｈｍＢａｓｅｄ
ｏｎ
Ｍｕｌｔｉｐｌｅ－ＧｒａｉｎＲｅｐｒｅｓｅｎｔａｔｉｏｎｆｏｒｔｈｅＴｒａｖｅｌｉｎｇ
ＳａｌｅｓｍａｎＰｒｏｂｌｅｍｓ
ＪｉＪｕｎｚｈｏｎｇ，ＨｕａｎｇＺｈｅｎ，ＬｉｕＣｈｕｎｎｉａｎ。ａｎｄＤａｉＱｉｇｕｏ
（ＢｅｉｊｉｎｇＭｕｎｉｃｉｐａｌＫｅｙＬａｂｏｒａｔｏｒｙｏｆＭｕｌｔｉｍｅｄｉａａｎｄＩｎｔｅｌｌｉｇｅｎｔＳｏｆｔｗａｒｅＴｅｃｈｎｏｌｏｇｙ，ＣｏｌｌｅｇｅｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＢｅｉｊｉｎｇＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｂｅｉｊｉｎｇ１００１２４）
Ａｂｓｔｒａｃｔ
Ａｎｔｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎ（ＡＣＯ）ｉｓ
ａ
ｐｏｐｕｌａｔｉｏｎ—ｂａｓｅｄｍｅｔａｈｅｕｒｉｓｔｉｃｔｅｃｈｎｉｑｕｅ
ａｎ
ｔＯ
ｅｆｆｅｃｔｉｖｅｌｙ
ｔＯ
ｓｏｌｖｅｃｏｍｂｉｎａｔｉｏｎｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓ．Ｈｏｗｅｖｅｒ，ｉｔｉｓｓｔｉｌｌｔｈｅｐｅｒｆｏｒｍａｎｃｅｏｆＡＣＯａｌｇｏｒｉｔｈｍｓ．Ｔｈｏｕｇｈｔｈｅｒｅｓａｌｅｓｍａｎｐｒｏｂｌｅｍｓ（ＴＳＰｓ），ｔｈｅｒｅｉｓｔｉｍｅｉｎｏｒｄｅｒｔｏｇｅｔ
ａｎ
ａｎ
ａｒｅ
ａｃｔｉｖｅｒｅｓｅａｒｃｈｔｏｐｉｃｈｏｗ
ｉｍｐｒｏｖｅ
ｍａｎｙａｌｇｏｒｉｔｈｍｓｔｏｅｆｆｅｃｔｉｖｅｌｙｓｏｌｖｅｔｒａｖｅｌｉｎｇ
ｔｏｏ
ａｐｐｌｉｃａｔｉｏｎｂｏｔｔｌｅｎｅｃｋｔｈａｔｔｈｅＡＣＯａｌｇｏｒｉｔｈｍｃｏｓｔｓ
ｍｕｃｈ
ｏｐｔｉｍａｌｓｏｌｕｔｉｏｎ．ＴｏｉｍｐｒｏｖｅｔｈｅｔｉｍｅｐｅｒｆｏｒｍａｎｃｅｏｆＡＣＯｉｎｓｏｌｖｉｎｇｌａｒｇｅ
ｓｃａｌｅＴＳＰｓ，ａｆａｓｔａｌｇｏｒｉｔｈｍｉｓｐｒｅｓｅｎｔｅｄｉｎｔｈｉｓｐａｐｅｒ．Ｆｉｒｓｔｌｙ，ａｎｏｖｅｌｍｕｌｔｉｐｌｅ－ｇｒａｉｎｒｅｐｒｅｓｅｎｔａｔｉｏｎｍｏｄｅｌｏｆＴＳＰｓｉｓｐｒｏｐｏｓｅｄ．Ｂａｓｅｄｃｏｎｔａｉｎｓｓｉｘ
ｏｎ
ｔｈｅｍｏｄｅｌ，ｆｌｎｅｗａｌｇｏｒｉｔｈｍｆｏｒＴＳＰｓｉｓｐｒｅｓｅｎｔｅｄ，ｗｈｉｃｈｍａｉｎｌｙ
ｐａｒｔｉｔｉｏｎ
ａｌｇｏｒｉｔｈｍ
ｂａｓｅｄ
ｏｎ
ｐｈａｓｅｓ，ｉ．ｅ．ａｇｒａｎｕｌａｒｉｔｙ
ｏｎ
ｄｅｎｓｉｔｙ
ｃｌｕｓｔｅｒｉｎｇ，ａｎＡＣＯ
ＡＣＯ
ａｌｇｏｒｉｔｈｍｂａｓｅｄａｌｇｏｒｉｔｈｍ
ｉｎ
ｔｈｅ
ｔｈｅ
ｃｏａｒｓｅ
ｇｒａｉｎ，ａ
ｃｏｎｎｅｃｔｉｏｎｆｕｓｉｏｎ
ａｌｇｏｒｉｔｈｍ
ｂｅｔｗｅｅｎｔＷＯｇｒａｎｕｌａｒｉｔｉｅｓ，ａｎ
ｇｒａｎｕｌａｒｉｔｉｅｓ，ａｎｄ
ａ
ｓａｍｅ
ｇｒａｎｕｌａｒｉｔｙ，ａａｌｇｏｒｉｔｈｍａｍｏｎｇ
ｓｕｂｓｅｃｔｉｏｎ
ｔｈｅ
ｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｒｅｇａｒｄｌｅｓｓｏｆｇｒａｎｕｌａｒｉｔｉｅｓ．Ｔｈｅａｎａｌｙｓｉｓｏｆｃｏｍｐｕｔａｔｉｏｎｃｏｍｐｌｅｘｉｔｙａｎｄ
ｃａｎ
ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｆｏｒｌａｒｇｅｎｕｍｂｅｒｏｆＴＳＰｓｄｅｍｏｎｓｔｒａｔｅｔｈａｔｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｉｍｐｒｏｖｅｔｈｅｓｐｅｅｄｏｆｃｏｎｖｅｒｇｅｎｃｅｉｎ
ｃｏｎｔｒａｓｔ
ｔｏ
ｇｒｅａｔｌｙ
ｔｈｅｃｌａｓｓｉｃａｌＡＣＯａｌｇｏｒｉｔｈｍ，ａｎｄｉｓｈｉｇｈｌｙｃｏｍｐｅｔｉｔｉｖｅ
ｉｎｔｉｍｅｐｅｒｆｏｒｍａｎｃｅｃｏｍｐａｒｅｄｗｉｔｈｓｏｍｅｌａｔｅｓｔｅｌｉｔｉｓｔＡＣ０ａｌｇｏｒｉｔｈｍｓ．Ｋｅｙｗｏｒｄｓｏｐｔｉｍｉｚａｔｉｏｎ
ＴＳＰ；ｍｕｌｔｉｐｌｅ－ｇｒａｉｎ
ｃｉｔｙｍｏｄｅｌ；ＡＣＯ
ａｌｇｏｒｉｔｈｍ；ｃｌｕｓｔｅｒｉｎｇ
ａｌｇｏｒｉｔｈｍ；ｓｕｂｓｅｃｔｉｏｎ
摘要针对蚁群算法在求解大规模旅行商问题（Ｔｒａｖｅｌｉｎｇ
ＳａｌｅｓｍａｎＰｒｏｂｌｅｍｓ，ＴＳＰ）中时间性能方面
的不足，提出了一种快速的求解算法．首先，从ＴＳＰ问题描述入手，给出了一种新的多粒度的问题描述模型；然后，基于该模型，设计了包括基于密度聚类的粒度划分、粗粒度的蚁群寻优、粒度间的连接、细粒度的蚁群寻优、粒度问可行解的合成以及循环分段优化６个阶段在内的求解算法．算法的复杂度分析及在中、大规模ＴＳＰ问题上的实验表明：本算法的时间性能不仅比经典的蚁群算法有显著的提高，而且与近年来的一些同类算法相比也具有一定的优势，显示了快速求解大规模ＴＳＰ问题的能力．关键词旅行商问题；多粒度城市模型；蚁群算法；聚类算法；分段优化
中图法分类号ＴＰｌ８
收祷日期：２００９—０３一】】；修回日期：２００９—０９一０１
基金项目：国家自然科学基金重大基金项目（６０４９６３２２）；北京市自然科学基金项目（４０８３０３４，４１０２０１０）
冀俊忠等：基于多粒度的旅行商问题描述及其蚁群优化算法
旅行商问题ＴＳＰ是一个经典的组合优化问题．挖个城市的ＴＳＰ问题求解可描述为：给定一个城市集合Ｖ＿－－｛∥，，耽，…，％｝，求遍历ｙ中所有城市各一次且最后回到出发城市（求解约束）的一个最短旅行的连通图ｇ∈Ｇ（Ｖ，Ａ），其中Ｇ（Ｖ，Ａ）为所有满足上述求解约束的连通图集合，Ａ一｛ａｄ一（ｖｉ，口ｆ）ＩＯ＜ｉ，歹≤７ｚ，睁！－『）是城市间两两相连的一组边．如果把任意一条边的距离记为ｄ；，＝ＩａｉＩ，则一个解图的数学形式可表示为ｇ＝ａｒｇ
ｍｉｎ≥：ｄ口．
譬ｔ‘’（Ｐ’＾，ａ
∈譬７
ＴＳＰ问题的求解是一个典型的ＮＰ难问题，由于该问题的求解模型可广泛应用于多种复杂优化问题，故该问题的求解算法一直以来是国内外学者们关注的一个研究热点．然而，在求解ＴＳＰ问题的过程中，当城市规模ｎ大到一定程度后就会面临“组合爆炸”问题，这时传统的一些启发式搜索就会陷入困境．于是人们结合物理学、生物遗传学、仿生学等领域的研究成果，相继提出了多种元启发式的ＴＳＰ问题的求解方法，如模拟退火（ｓｉｍｕｌａｔｅｄ
ａｎｎｅａｌｉｎｇ）、
禁忌搜索（ｔａｂｕｓｅａｒｃｈ）、遗传演化（ｇｅｎｅｔｉｃｅｖｏｌｕｔｉｏｎａｒｙ）、蚁群优化（ａｎｔ
ｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎ）
等算法．其中，蚁群优化算法是２０世纪９０年代初才被提出的一种新的元启发搜索算法ｎ。２ｊ，其实现机理是通过模拟人工蚂蚁群体在觅食过程中所体现出的智能行为来完成对ＴＳＰ问题的求解．由于蚁群算法具有良好的鲁棒性、正反馈、分布式及并行计算等特点，所以受到学者们的广泛关注，蚁群算法的理论框架也日渐成熟［３．５］．尽管如此，当城市规模竹达到数百后，蚁群算法仍暴露出运行时间过长、难以满足实际应用需求的不足．为此，本文提出了一种新的基于多粒度的ＴＳＰ问题描述模型的蚁群求解算法．该算法的基本思想是通过对ＴＳＰ问题进行多粒度的描述。将难解的大规模ＴＳＰ问题分解为易于求解的小规模ＴＳＰ问题来求解．首先在粗粒度上完成蚁群寻优以确定粗粒度间的连接，然后在每个粗粒度内进行细粒度的蚁群寻优，实现城市间的连接。最后利用循环分段优化策略来弥补粒度划分对求解精度的影响．由于多粒度的划分大大缩小了原来单粒度问题的规模，所以算法的计算复杂度能大大降低，有效地提高了蚁群算法求解大规模ＴＳＰ问题的能力．在一些中、大规模的ＴＳＰ问题上的实验表明：新算法在求解速度上不仅比经典的ＡＣＯ算法有显著的提
４３５
高，而且与近年来的一些算法相比也有优势，体现出良好的求解大规模ＴＳＰ问题的能力．
１
相关工作
迄今为止，针对基本蚁群算法［１］（ａｎｔ
ｓｙｓｔｅｍ，
ＡＳ）迭代次数多、运行时间长的缺点，国内外的学者们已经提出了许多种新的快速、高效的蚁群算法［６。１４。．概括起来，这些算法主要包括３类：１）基于信息素更新机制的改进．通过对信息素生成和更新策略的优化来提高蚁群算法的寻优能力，改善解的全局收敛性．由于信息素是蚁群进行相互交流、完成信息融合并实现群集智能（ｓｗａｒｍｉｎｔｅｌｌｉｇｅｎｃｅ）的重要媒介，因此，许多学者对蚁群算法的研究都是围绕信息素的产生和更新策略进行的¨书］．２）基于随机搜索机制的改进．由于蚁群算法有易于与其他方法相结合的优点［１］，所以不少工作都是对随机搜索过程的控制策略进行调整，提高局部的寻优能力，以减少迭代次数，加速收敛．如文献［９］提出了相遇和分段优化的策略加速了构造解的过程；文献［１０］通过变异策略以加快局部搜索；文献［１１］将遗传算法与蚁群算法相融合也加快了求解速度．而文献［１２］将这２种改进机制相结合，提出了一种基于变异和动态信息素更新的新算法，在时间性能上取得了较大的提高．３）基于启发信息函数的改进．文献［１３］利用最小生成树的结构信息来对通用的启发函数进行加权高；文献［１４］则采用基于插入准则的ＧＥＮＩ思想来代替常用的概率最近邻的启发思想，给出了能够改１６］通过对局部最优解进行简单的相交操作得到模寻优算法、粒度间融合算法、滑动循环的分段优化算修正，在求解质量和时间性能上都获得了较大的提善蚁群算法求解质量的ＧＡＣＳ算法．此外，文献［１５－式或部分解，来减少后期迭代中的城市规模，有效地缩小了原问题的搜索空间。这是蚁群算法求解大规模ＴＳＰ问题的一种新尝试．基于类似的问题归约思想，本文从问题的描述出发，提出了一种新的基于多粒度ＴＳＰ问题描述的蚁群优化算法．算法包括基于密度聚类的粒度划分算法、基于粗粒度蚁群寻优的顺序学习算法、粒度间的连接算法、同粒度内的蚁群法６个阶段．新算法的主要特点是：突破了经典的ＴＳＰ问题的描述模型，给出了一种多粒度的ＴＳＰ问题描述模型，力求从本质上解决蚁群算法在求解大规模ＴＳＰ问题时运行时间过长的问题．
计算机研究与发展２０１０，４７（３）
定义１．超城市．在ＴＳＰ问题二维坐标的平面
２
多粒度ＴＳＰ问题描述模型
面对复杂的、难以准确把握的问题，人们通常不
上，如果城市的地理位置分布呈现较明显的分簇现象，那么那些具有足够高密度的区域称为超城市
（ｓｕｐｅｒ
ｃｉｔｙ）或地区（ｄｉｓｔｒｉｃｔ）．一个超城市中包含若
是盲目地追求精确的最佳解，而是通过逐步尝试的办法达到满足一定精度的合理目标［１７｜．这是一种概略地、由粗到细、不断求精的多粒度分析法，利用它可以避免求解原问题计算复杂度高的困难．换句话说，问题的多粒度描述是降低复杂问题求解计算复杂度的一种有效手段．
蚁群算法的实现机理是利用蚂蚁在觅食途中所释放的信息素来完成个体之间相互的交流和合作，其过程主要包括信息素的更新及以其为基础的状态迁移（蚂蚁选路）２部分．目前，大多数蚁群算法都将信息素的更新视为提高算法性能的关键，却忽视了食物源的分布对蚂蚁选择路径的影响．而生物学家的观察发现，在自然界的真实蚁群的觅食行为中，大部分蚂蚁会优先选择离自己目前位置较近的食物源去觅食，所以如果存在较密集（彼此间距离较近）的几个食物源，那么蚂蚁会优先遍历这几个食物源，等它们枯竭后才去寻找其他食物源．结合蚂蚁觅食的这种现象，我们给出如下假设：
假设１．商人最近城市选择假设．在一个较复杂的、有若干城市的ＴＳＰ问题中的一条遍历所有城市的最短路径中，城市ｉ连接到城市．ｆ，＿『不可能是离城市ｉ最远的那些城市［１２．１７］．于是，行个城市的ＴＳＰ问题可以按地理位置分布划分为不同的地区（根据相互间的距离），商人下一城市的选择范围局限于离当前城市ｉ较近的某一邻域（地区）的部分城市，商人在访问完该地区的所有城市后才会访问其他地区的城市．
本文使用连接图作为ＴＳＰ问题可行解的基本数据结构．基于上述假设，下面给出ＴＳＰ问题可行解的多粒度描述模型的定义：
干彼此距离相近的城市．
定义２．孤立城市．在一个给定的距离（半径）内，与任意城市都不相邻的城市称为孤立城市
（ｉｓｌａｎｄ
ｃｉｔｙ）．孤立城市是指在平面上远离其他城市
的城市，它也可看作是仅含１个城市的超城市．
定义３．边缘城市．在一个超城市（地区）中，与其他地区或孤立城市发生连接的城市，称为边缘城市（ｍａｒｇｉｎｃｉｔｙ）．根据地区间的连接顺序，一个地区内的２个边缘城市分别称为入区城市（ｉｎ－ｄｉｓｔｒｉｃｔｃｉｔｙ）和出区城市（ｏｕｔ－ｄｉｓｔｒｉｃｔ
ｃｉｔｙ）．
定义４．ＴＳＰ问题的多粒度描述模型．基于上述定义，一个ＴＳＰ问题的可行解可以表示为一个连
接图ｇＤ＝ｇ（Ｄ，Ｂ），其中：Ｄ＝｛ｄ。，ｄ：，…，ｄＩ｝为地区节点的集合，历为地区间两两相连的弧集合，如弧ｅ（ｄｉ，ｄ，）∈匕表示地区ｄ。和ｄ，之间的一条连
接．任意一个地区ｄｉ∈Ｄ表示ＴＳＰ问题的可行解内的一个超城市，它可进一步表示为一个从入区城市出发遍历该地区内所有城市后到达出区城市的连接图，即ｄ；＝ｇｉ（ｙ，Ｅ。），其中Ｖ为超城市内的城市集合，Ｅ。为超城市内城市间连接弧的集合．因此，ＴＳＰ问题的可行解可进一步表示为一个多粒度的连接图ｇＭ—ｇ（｛ｇｉ（Ｖ，Ｅ。）），Ｅ），Ｅ为粒度间的连接弧集合，用来刻画超城市与城市间的连接关系．
图１为这种多粒度连接图的ＴＳＰ解结构描述模型．所求问题的解描述由ＴＳＰ问题可行解、超城市连接以及城市连接３种描述粒度构成，超城市之间以及超城市内城市间分别以地区级的连接图和城市间连接图描述其连接结构，并且通过入区城市和出区城市完成不同粒度间的连接，最后构成一个多粒度的连接图．
Ｆｉｇ．１
Ｒｅｐｒｅｓｅｎｔａｔｉｏｎｏｆｔｈｅ
ｓｔｒｕｃｔｕｒｅ
ｏｆＴＳＰｓｏｌｕｔｉｏｎｓｂａｓｅｄ
ｏｎａ
ｍｕｌｔｉ—ｇｒａｉｎｃｏｎｎｅｃｔｉｏｎｇｒａｐｈ．
图１基于多粒度连接图的ＴＳＰ解的结构描述
冀俊忠等：基于多粒度的旅行商问题描述及其蚁群优化算法
４３７
通过引人多粒度的ＴＳＰ描述模型，在ＴＳＰ问题的求解中，便可达到降低问题规模、减少算法的计算复杂度、进而增进蚁群算法求解能力的目的．
３
粒度ＴＳＰ问题求解的蚁群算法（ａｎｔ
ｂａｓｅｄ
ｏｎ
ｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎ
ｍｕｌｔｉｐｌｅｇｒａｉｎｒｅｐｒｅｓｅｎｔａｔｉｏｎ，ＡＣＯＭＧＲ），图
２为多粒度ＴＳＰ问题求解算法的过程图解．从图２可见，ＡＣｏＭＧＲ算法求得一个满意解需要经过粒度划分算法、粗粒度的寻优、粒度间的连接、粗粒度内的蚁群寻优算法、粒度间可行解的合成、循环分段优化算法等６个关键步骤，下面分别对其进行讨论．
多粒度ＴＳＰ问题求解的蚁群算法
基于多粒度的ＴＳＰ问题描述模型，本文给出多
Ｆｉｇ．２
Ｔｈｅｏｐｔｉｍｉｚａｔｉｏｎ
ａｎ
ｐｒｏｃｅｄｕｒｅｂａｓｅｄ
ｏｎ
ｍｕｌｔｉｐｌｅ
ｇｒａｉｎｒｅｐｒｅｓｅｎｔａｔｉｏｎｆｏｒＴＳＰｓ．（ａ）Ｇｒａｉｎ
ｐａｒｔｉｔｉｏｎｔ（ｂ）
ａ
Ｃｏａｒｓｅｇｒａｉｎｓｅａｒｃｈｆｏｒ
ｏｒｄｅｒ；（ｃ）Ｉｎｔｅｒ－ｇｒａｉｎｃｏｎｎｅｃｔｉｏｎ；（ｄ）Ｆｉｎｅｇｒａｉｎｃｏｎｎｅｃｔｉｏｎ；（ｅ，Ｃｏｎｓｔｒｕｃｔｉｎｇ
ｆｅａｓｉｂｌｅ
ｓｏｌｕｔｉｏｎ；ａｎｄ（ｆ）Ｃｉｒｃｕｌａｒｓｕｂｓｅｃｔｉｏｎｏｐｔｉｍｉｚａｔｉｏｎ．
图２多粒度ＴＳＰ问题求解算法过程图解．（ａ）粒度划分；（ｂ）粗粒度的寻优；（ｃ）粒度间的连接；（ｄ）细粒度内的
连接；（ｅ）可行解的合成；（ｆ）循环分段优化
３．１
基于密度聚类的粒度划分算法
粒度的划分是将给定的ＴＳＰ问题描述转化为
算法１．ＧＰＤＣ（ＳＰｆｏ厂Ｐｏｉ珂ｆＳ，Ｅｐｓ，ＭｉｎＰｔｓ）．／＊ＳｅｔｏｆＰｏｉｎｔＳ为ＴＳＰ中未分区的城市集，Ｅｐｓ和ＭｉｎＰｔｓ分别为地区半径和地区内最小城市数＊／
｛初始化城市的地区标记为ＵＮＣＬＡＳＳＦＩＥＤ；
ＦＯＲｉ＝１Ｔ０ＳｅｔＤ，Ｐｏｉｎｔｓ．ｓｉｚｅ
多粒度ＴＳＰ问题描述模型的基础．如图２（ａ）所示，该算法运行的目的是将原ＴＳＰ问题描述的粒度变粗以降低原问题的规模．结合城市地理分布的特征，本文根据ＤＢＳＣＡＮ聚类算法的思想【ｌ引，设计了基于密度聚类的粒度划分算法．采用ＤＢＳＣＡＮ算法的原因是：１）能将具有足够高密度的区域划分为簇；２）能将相对稀疏的点视为“噪声”，故能够在带有“噪声”的空间点数据中利用类的密度连通性发现任意形状的聚类．换句话讲，该算法能对不同分布的数据进行聚类，符合多粒度的ＴＳＰ问题描述模型中对超城市和孤立城市的定义．基于密度聚类的粒度划分算法（ｇｒａｉｎ
ｐａｒｔｉｔｉｏｎｂａｓｅｄ
ｏｎ
Ｐｏｉｎｔ＝Ｓｅｔ砖Ｐｏｉｎｔｓ．ｇｅｔ（ｉ）；
／＊返回城市集合的第ｉ个元素＊／
ＩＦＰｏｉｎｔ．Ｄ耐＝ＵＮＣＬＡＳＳＩＦＩＥＤＴＨＥＮ
ＩＦＥ：ｃｐａｎｄＤｉｓｔｒｉｃｔ（ＳｅｔｏｆＰｏｉｎｔｓ，Ｐｏｉｎｔ，
Ｄｉｄ。Ｅｐｓ，ＭｉｎＰｔｓ）ＴＨＥＮ
／＊ＥｘｐａｎｄＤｉｓｔｒｉｃｔ函数为一个核心城市构造一个密度相连的城市集合（地区）＊／
ＤｉｓｔｒｉｃｔＩｄ＝Ｄｉｓｔｒｉｃｔｌｄ＋１；／＊地区标记更新＊／
ＥＮＤＩＦＥＮＤＩＦ
ｄｅｎｓｉｔｙｃｌｕｓｔｅｒｉｎｇ，
ＧＰＤＣ）的基本思想是：对于一个地区中的每一个核心城市，在其给定距离（半径）的邻域内所包含的城市数不得小于某～个给定的最小数量，具体算法的描述如下：
４３８
ＥＮＤＦＯＲ
返回粒度划分结果（孤立城市和地区内城市的地区标记）．
）
ＧＰＤＣ算法为了发现一个地区，先从ＴＳＰ问题的城市集Ｖ中任取一个城市口ｉ，利用密度参数判断其是否为核心城市．如果职是核心城市，则在以ｖｉ为中心以Ｅｐｓ为半径的区域内所包含的城市数量不少于ＭｉｎＰｔｓ，于是算法可以找到一个关于参数Ｅｐｓ和ＭｉｎＰｔｓ的地区．如果职是边界点，则在以让为中心以Ｅｐｓ为半径的区域内包含的城市数量少于ＭｉｎＰｔｓ，于是可以把让暂时标注为噪声点，然后，继续处理ｙ中的下一个未标记的城市．被标记为噪声点的城市随着划分过程的进行，可能改变标记成为某一地区的元素．在划分完成后，不被任一核心城市密度可达的那些噪声点城市被确定为孤立城市．城市的地区归属与地区的发现和扩展连通都由函数ＥｘｐａｎｄＤｉｓｔｒｉｃｔ（）完成【ｌ
８１．
３．２粗粒度的寻优及粒度间的连接
经过粒度划分过程，原问题就被归约为规模数大大降低的地区级（粗粒度）和各地区内城市（细粒度）的寻优问题．为了合成问题的解，首先进行粗粒度的寻优以确定地区间的前后连接关系．具体方法是：以孤立城市和各地区的重心（该地区内所有城市坐标的平均）为代表点，通过基本的ＡＣＳ算法【２３求解代表点所构成的新ＴＳＰ问题的最优路径，从而确定粗粒度的旅行路线，得到各地区与孤立城市间的连接顺序，如图２（ｂ）所示．连接顺序确定后，我们就可以两两进行相邻地区间出区城市和人区城市的连接．具体可分为３种情况．
１）孤立城市与孤立城市相邻时，直接连接．２）孤立城市（ｑ）与某地区（Ｄ，）相邻时，利用最近邻原则确定该地区的入（或出）区城市：
。；＝ａｒｇｍｉｎｄ＊ｏｒ口｛）＝ａｒｇｍｉｎ巩，
（１）
％６ｑ
１∈Ｄ，、≠。；
其中，口｛为Ｄ，的入区城市（当连接顺序为ｖｉ—ｑ），。｛）为Ｄ』的出区城市（当连接顺序为ｑ一让）．
３）两地区Ｄ。，Ｄｉ相邻且Ｄｉ—Ｄ，时，利用式（２）确定地区Ｄｉ的出区城市以及地区Ｄ，的入区城市：
（喃，口｛）一ａｒｇ
ｍｉｎ矗。．
（２）
‰∈Ｄ。ｔ‰≠吒
％∈ＤＪ
至此，完成了粒度间的连接，如图２（ｃ）所示．
计算机研究与发展２０１０，４７（３）
３．３粗粒度内的蚁群寻优算法
粗粒度内的蚁群寻优算法以入区城市为始点，出区城市为终点，确定地区内城市间的连接顺序，并依此得到该地区中入区城市到出区城市最短的旅行．不同地区内的蚁群寻优过程可并行地进行．在该算法中，我们使用蚁恒模型¨副作为信息素的增量模型，算法描述如下：
算法２．ＡＣＡＣＯ（ｋ）／＊是为区的标识号＊／
｛
１）初始化阶段：
初始化参数，赋给各条路径相同的信息素浓度，并将ｍ。只蚂蚁放到入区域市上；为每只蚂蚁设置允许访问的城市列表；２）蚁群的一次周游过程（一次迭代）：
ＦＯＲｐ＝１
ＴＯ咒。／＊遍历该区所有城市，最后
到达出区城市＊／
ＦＯＲｑ＝１ＴＯ
ｍ。／＊蚁群的一步转移＊／
｛ＩＦｐ＜巩ＴＨＥＮ／＊没有遍历完该区所有
城市＊／
｛按ＡＣＳ中的转移概率公式Ⅲ选择下一个城市；
完成一步行走，并变更允许访问的城市
列表；｝
｝
３）本次迭代的信息素的更新：
ＦｏＲｑ＝１ＴＯｍｋ
｛计算Ｌｑ；）／＊计算每只蚂蚁的旅行长度＊／ＦＯＲ每条边ａｄ∈ｇｌＵ９２Ｕ…Ｕｇ槭｛计算路径巧上新产生的信息素浓度；ｑ（￡＋１）＝（１－－ｐ）ｑ（ｆ）＋ｌＤ・＂ｔｏ；／＊ＩＤ为挥发系数＊／
）／＊局部信息素的更新＊／
Ｌｂｅ。畸＝Ｍｉｎｉｍｕｍ（Ｌ裱）；／＊计算本次迭代的最优值＊／
ＦＯＲ每个ａｄ∈ｇｂｅ。仲。
｛彬”＝（１一ｙ）碍ｕ＋７・Ａｒ口；／＊ｙ为挥发系数＊／
ｆ１／（Ｌｂｅｓｔ－ｉｔｅｒ），当全局最优解包含
△句＝＜路径口ｄ时；
【０，否则；
）／＊全局信息素的更新＊／４）判断算法是否结束：ＩＦ（结束条件满足）ＴＨＥＮ
输出多次迭代后的最优解Ｌｋ。ｎ。，；
冀俊忠等：基于多粒度的旅行商问题描述及其蚁群优化算法
ＥＬＳＥ
｛迭代次数增ｌ初始化入区城市可访问的城市列表
ＧＯＴｏ
２）．）／＊继续进行下次迭代＊／
｝
粗粒度内的蚁群寻优算法完成后，便得到了各地区内城市的连接，如图２（ｄ）所示．３．４可行解的合成
按上述步骤依次完成粗粒度（地区）的寻优、粒度间的连接、粗粒度内细粒度（城市）的蚁群寻优后，就可以通过路径合成得到初始ＴＳＰ问题的一个可行解．如图２（ｅ）所示．该可行解表示本次周游所有城市后回到出发城市所经过的旅行长度，其计算公式如下：
Ｎ
ＬＩ＝∑Ｌｑ＋Ｌ地区何，
（３）
ｉ皇ｌ
其中Ｎ为粒度划分后得到的地区数（含孤立城市），ＬＤ为从某地区的入区城市出发遍历完所有该区的其他城市后到达出区城市的最短路径．对于孤立城市Ｌｎ＝Ｏ，Ｌ地区问为按照地区连接顺序，所有孤立城市、地区间边缘城市（入区、出区城市）连接的距
离和．
３．５循环分段优化算法
为了提高求解的时间性能，本文通过多粒度的描述模型，人为地将ＴＳＰ问题分解为较小规模的ＴＳＰ问题来进行求解．由于原始问题的最优解并不一定是所有小规模ＴＳＰ问题最优解的简单叠加。所以我们在获得原始问题的一个可行解后，摈弃粒度的划分，采用分段优化算法［９］对ＴＳＰ问题的可行解进行随机分段、分段始点移动和循环寻优的方法来优化所得到的解，提高可行解的质量．如图２（ｆ）所示，其具体的算法描述如下：
算法３．Ｓｕｂｓｅｃｔｉｏｎ－ｏｐｔｉｍｉｚａｔｉｏｎ（）．
｛
１）参数初始化：
Ｃ。ｌ。＝ｃ；／＊循环因子＊／
Ｓｕｂｓｅｃｔｉｏｎ—ｌｅｎｇｔｈ＝ｚ（ｎ／ｔ；）／＊分段长度，ｔ取大于２的整数＊／
ｃｏｕｎｔｅｒ＝Ｏ；
２）循环分段开始：
ＷＨＩＬ，Ｅ（ｃｏｕｎｔｅｒ≤，ｌ／Ｃ。ｌｅ）
｛ｓ￡口ｒ￡＝∞鲫据ｒ・Ｃ。心；／＊分段始点＊／
ＡＣＳ（ｓｔａｒｔ，Ｓｕｂｓｅｃｔｉｏｎ
ＩＦ（分段寻优结果优于原结果）更换该段的
４３９
解路径；｝
输出分段优化后的结果．
｝
算法中函数ＡＣＳ（ｓｔａｒｔ，Ｓｕｂｓｅｃｔｉｏｎ—ｌｅｎｇｔｈ）是由ＡＣＳ算法稍加修改后得到，其返回值是蚁群从分段始点出发，遍历该段所有其他城市后到达分段终点所得到的最短路径长度．３．６计算复杂度分析
假设ｎ为原始ＴＳＰ问题中城市的实际数量，ｍ为用ＡＣＳ蚁群算法求解时所需的蚂蚁数，ＡＣＳ算法经过Ｃ次迭代后得到最优的解，则ＡＣＳ算法求解ＴＳＰ问题的计算复杂度可近似为ｏ（Ｃ・ｎ２・优）Ｌ６］．
下面分析本文算法的计算复杂度：假设经过粒度划分将ｎ个城市分为Ｄ个地区，ｗ个孤立城市，
Ｄ
即咒＝铷＋＞：咒ｉ（啦为地区ｉ中的城市数量）．
葛
１）算法ｌ（粒度划分算法）的计算复杂度是
Ｏ（ｎｌｏｇ竹）［１引．
２）利用ＡＣＳ算法进行粗粒度寻优的计算复杂度为０（Ｇ・Ｎ２・ｍ。），Ｇ为粗粒度寻优的迭代次数，Ｎ＝ｗ＋Ｄ《，２，且所需的蚂蚁数为ｍ。≤Ｎ．由于ＴＳＰ规模大大降低，故Ｇ《Ｃ，ｍ。《ｍ，所以有０（Ｃｄ・Ｎ２・ｍＪ）《ｏ（Ｃ・竹２・优）．
’
假设第ｉ个地区为粒度划分后最大的地区（含有城市最多），且ｎ；一ｍａｘ｛ｎ。）（Ｏ＜最≤Ｄ）．由于地区内的寻优可并行进行，故算法２（细粒度寻优）的计算复杂度为ｏ（Ｇ・ｎ；・ｍｉ），Ｃｉ为迭代次数，ｍ，为所需的蚂蚁数，同样由于ＴＳＰ规模的大大降低，其值远小于ｏ（Ｃ・ｎ５２・仇）．
３）算法３（循环分段优化）的计算复杂度为Ｏ（Ｃ。。・（ｎｉｔ）２・仇。・惫），其中ｋ为分段循环次数，由于分段使问题规模下降，故Ｃ。＜Ｃ，优。＜ｍ，且合理选取参数后可使志／ｆ２＜１，故容易使ｏ（Ｃ。・（咒／￡）２・ｍ。。・志）＜０（Ｃ・ｎ２・ｍ）．
此外，粒度间连接的最大复杂度为０（Ｎ・ｎ；），而可行解合成的计算复杂度为０（以）．
综上所述，算法总的计算复杂度为：Ｏ（ｎｌｏｇｎ）＋０（Ｇ・Ｎ２・ｍｄ）＋ｏ（Ｎ・ｎ；）＋ｏ（Ｃｉ・ｎ；・ｍｆ）＋ｏ（以）＋０（Ｃ。・（ｎｉｔ）２・，，ｌ。・矗）≈惫・Ｏ（Ｃ。・（ｎ／
ｆ）２・ｍ。。），令ｃ／Ｃ。＝Ｐ，ｍ伽。＝ｑ，则算法计算复
杂度可表示为：（ｋ／ｐ・ｑ・ｔ２）・ｏ（Ｃ・ｎ２・，，１）．显然，与ＡＣＳ算法具有同级的计算复杂度．但是由于分段优化时至少分２段，故ｔ）－２，而分段后城市规模
４４０
计算机研究与发展２０１０，．４７（３）
的下降会使迭代次数、蚂蚁数都会减少，有Ｐ，ｑ＞ｌ，所以通常情况下惫伽・ｑ・ｔ２＜１总成立．可见，在ＴＳＰ问题城市规模较大、分段较多的情况下，合理选取参数后可使Ｏ（Ｃ・靠２・，，ｚ）成倍地减小．
４．１分段优化策略的作用
为测试分段优化策略对求解质量的作用，我们分别对不含分段优化过程的ＡＣＯＭＧＲ－１算法和含分段优化过程的本文算法ＡＣＯＭＧＲ的求解结果进行比较．表１给出了在各种事例最佳的参数配置下的实验结果．其中，最佳的解长度为２种算法各运行１０次所得到的最佳值，优化率为２种算法所得的最佳值的差与该问题标准最优解的比率．在相同的运行时间下，ＡＣＯＭＧＲ算法得到的最优解都明显好于ＡＣＯＭＧＲ－１算法，这说明分段优化策略能够提高本文所提出的算法的解质量，尤其是在大于４００的事例上效果明显．
图３给出了在Ｐｒｌ５２问题上２种算法的解图．比较图３中２个解图，正是由于一些局部连接的差异（虚线圆框内的连接部分），导致了２种算法所得到的最优解的不同．
４
实验结果
本部分对新算法的性能进行测试，并给出分段
优化策略对新算法求解质量的影响，本文算法在一些中大规模ＴＳＰ问题上的实验结果以及与一些最新蚁群算法在求解性能方面的实验比较．实验采用ＴＳＰＬＩＢ的标准库（来源于ｈｔｔｐ：／／ｅｌｉｂ．ｚｉｂ．ｄｅ／ｐｕｂ／ｍｐ—ｔｅｓｔｄａｔａ／ｔｓｐ／ｔｓｐｌｉｂ／ｔｓｐｌｉｂ．ｈｔｍｌ）．实验的运行环境为：操作系统ＷｉｎｄｏｗｓＸＰ，ＣＰＵ为Ｐ４１．８ＧＨｚ，内存为５１２ＭＢ，算法用ＶｉｓｕａｌＣ＋＋语言编程实现，实验的最佳参数组合均通过实验确定．
Ｔａｂｌｅｌ
ＰａｒａｍｅｔｅｒＳｅｔｓｏｆｔｈｅＰｒｏｐｏｓｅｄＡｌｇｏｒｉｔｈｍｆｏｒＤｉｆｆｅｒｅｎｔＩｎｓｔａｎｃｅｓａｎｄＳｕｂｓｅｃｔｉｏｎＯｐｔｉｍｉｚａｔｉｏｎＲｅｓｕｌｔｓ
表１本文算法在求解不同问题时的参数设置及分段优化的结果
Ｐａｒａｍｅｔｅｒ
Ｓｅｔｓ
ＯｐｔｉｍａｌＲｅｓｕｌｔｓ
Ｑ
１
ｃ
ＥＰＳＭｉｎＰｔｓ
口
８
ｐ
ＡＣＯＭＧＲ’１
ＡＣＯＭＧＲ
Ｏｐｔｉｍａｌ
Ｒａｔｅ］％
（ａ）
ｏｆ
ｔｗｏｓｏｌｕｔｉｏｎ
ｐｒｌ５２
ｆｏｒ
（ｂ）
ｇｒａｐｈｓ
ｏｎ
Ｆｉｇ．３Ｃｏｍｐａｒｉｓｏｎ
ｔＷＯｄｉｆｆｅｒｅｎｔａｌｇｏｒｉｔｈｍｓ．（ａ）Ｓｏｌｕｔｉｏｎｇｒａｐｈ
ｗｉｔｈｏｕｔｓｕｂｓｅｃｔｉｏｎｏｐｔｉｍｉｚａｔｉｏｎａｎｄ（ｂ）Ｓｏｌｕｔｉｏｎｇｒａｐｈｗｉｔｈｓｕｂｓｅｃｔｉｏｎｏｐｔｉｍｉｚａｔｉｏｎ．
图３在ｐｒｌ５２问题上的解图．（ａ）没有分段优化策略的解图；（ｂ）有分段优化策略的解图
４．２算法总体性能及分析
我们在许多较大规模的ＴＳＰ问题上进行了大量
的实验，并将本文算法与经典的ＡＣＳ算法、ＡＣＳ＋２０ｐｔ、ＧＡＣＳ…。和ＭＳＴ—Ａｎｔｓ［１３３等算法进行比较．实
冀俊忠等：基于多粒度的旅行商问题描述及其蚁群优化算法４４１
验所采用的参数如下：＂ｔｏ＝ｌ／ｎＬ。，ＡＣＳ算法的参数设置为口＝１，ｐ＝２，』Ｄ＝０．１，ｙ＝０．１，而本文算法运行时的参数设置见表１．
在上述参数配置下，我们经过多次实验得到本文算法与ＡＣＳ算法在各个ＴＳＰ问题上的求解结果，表２列出了实验的结果．其中，最佳的解长度为２种算法各运行１０次所得到的最佳值，运行时间为
Ｔａｂｌｅ２
ＣｏｍｐａｒｉｓｏｎｏｆＳｏｌｖｉｎｇＰｅｒｆｏｒｍａｎｃｅｆｏｒ
得到各自最佳值所需时间的平均值，误差为所得到的最佳值与数据库中该问题的标准最优解之间的相对偏差．从这些事例上的结果可见，本文算法在较短的时间内就能得到误差更小的解，这说明通过粒度划分思想降低ＴＳＰ问题的规模，大大缩短了寻优时间，提高了搜索效率，并在一些问题上获得更令人满意的解．
ＡＣｏＭＧＲａｎｄＡＣＳＡｌｇｏｒｉｔｈｍｓ
Ｏｎ
表２ＡＣＯＭＧＲ和经典的ＡＣＳ算法在不同ＴＳＰ问题上求解性能的比较
ＡＣＳＡｌｇｏｒｉｔｈｍ
ＩｎｓｔａｎｃｅｓｏｆＴＳＰ
ＯｐｔＬｍｕｍ
Ｓｏｌｕｔｉｏｎ————
ＤｉｆｆｅｒｅｎｔＩｎｓｔａｎｃｅｓＡＣＯＭＧＲ
Ｂｅｓｔｌｅｎｇｔｈ
Ｅｒｒｏｒ／
Ｒｕｎｔｉｍｅ／ｓ
Ｂｅｓｔ
ｌｅｎｇｔｈＥｒｒｏｒ／ＮＲｕｎｔｉｍｅ／ｓ
如前所述，针对经典的ＡＣＳ算法在时间性能方面的不足，国内外的许多研究都对它进行了改进，并在一些中小规模的ＴＳＰ问题上作了测试．其中，在求解Ｏｌｉｖｅｒ３０问题时，文献Ｅ８］给出的算法收敛速度可提高约６倍，文献［１１］提出的算法收敛速度可提高约１１倍；文献［１２］给出了一些更好的实验结果，该文所提出的算法在一些ＴＳＰ问题上的收敛速度可提高数十到数百倍，例如，在求解ｅｌｌ５１时提高
Ｔａｂｌｅ３
Ｃｏｍｐａｒｉｓｏｎｏｆ
率为２５００１７≈３５７倍，在求解Ｓｔ７０时提高率约为６０００／２０＝３００倍，在求解Ｐｒｌ０７时提高率为６７００／３３０≈２０倍，在求解Ｄ１１９８时提高率为１００００１８００＝１２．５，但不难发现，该算法收敛速度的提高随ＴＳＰ事例中城市数的增加逐渐降低；而国外新近的几篇文献则更系统、详细地给出了一些改进算法的结果，表３列出了本文算法与其中几个改进算法的实验比较：
ｏｎ
Ｓｏｌｖｉｎｇ
Ｐｅｒｆｏｒｍａｎｃｅｆｏｒ
ＡＣＯＭＧＲａｎｄＳｏｍｅＩｍｐｒｏｖｅｄＡｌｇｏｒｉｔｈｍｓ
ＤｉｆｆｅｒｅｎｔＩｎｓｔａｎｃｅｓ
表３ＡＣＯＭＧＲ和一些改进算法在不同ＴＳＰ问题上求解性能的比较
ＡＣＳ＋２－ｏｐｔＣｌ４］
ＧＡＣｓ［１４】
ＭＳＴ—Ａｎｔｓ［１３］
ＡＣＯＭＧＲ
Ｉｎｓｔａｎｃｅｓｏｆ
ＴＳＰ——
ＡＣＳ
ＲＰＤ／％
１Ｏ７１３６１２４１５２２２６州¨“７刍４ＨＫＫ
ＯＯＯＯＯ２Ｚ９
●
ＲＰＤ／％ＴＩＲ
０Ｏ０Ｏ０１２
●
ＲＰＤ／％ＴＩＲ
０Ｏ０ＯＯ１ＺＯ１５８Ｏ５
～
ＲＰＤ／％ＴＩＲ
ＯＯＯＯ０Ｏ１Ｏ７Ｏ７８８Ｏ５一
●
ＲＰＤ／％ＴＩＲ
ＯＯＯＯＯ０ｌ２
●
５８２１３ｌ８６６５８７６７
４５ｌＯ５Ｏ６３ｌ９９２６
一
１６２Ｏ１Ｚ１
●
６７１１５４９３２４２
１
２８
Ｏ１１Ｏ３１
●
３２Ｏ６ｌ６
１８４
●
９５７４７２４４ＺＯ７１５
Ｏ９７５１４９１Ｏ４７２７Ｏ９１３
４８１１ｌ２２２２９４８６２
●
６３６３８７４１８４４４３
●
●●●●
５ｌ５３３ｌ８１２５８２
一
●●●●
●
●●●●●●
●
●●●
●
ｌ３
１ｌ８８
●●●
●●
●●●●●
●●
●●
●●●●●
●
３
１５７９
●●
●●●●
●●
●
一
．
一
●●
．
●
●
●
婚一博一吒＿
Ｏ一
●
９一６－
—
■
一－－
一
■
一一
＿
一
■
一＿．
—
●
一＿－—
■
一一．－
．－一＿—
■３—
３一一—－
７—９—
■
６一１—
４４２
表３中ＲＰＤ（ｒｅｌａｔｉｖｅ
ｐｅｒｃｅｎｔａｇｅ
ｄｅｖｉａｔｉｏｎ
ｏｎ
ｔｈｅｏｐｔｉｍａｌ
ｓｏｌｕｔｉｏｎ）为算法各自求得的最优解与
标准最优解的相对偏差，ＴＩＲ（ｔｉｍｅ
ｉｍｐｒｏｖｅｄｒａｔｅ）
为ＡＣＳ算法运行时间与各种算法获得各自最优解时所需的运行时间的比率，ＡＣＳ＋２－ｏｐｔ和ＧＡＣＳ的实验结果源于文献［１３］，ＭＳＴ—Ａｎｔｓ的实验结果源于文献［１４］，“一”为没提供．从表３可见：１）本文算法在收敛时间性能的改进上具有较大优势。在大部分事例上都具有最高的改进率（ＴＩＲ的值最高）；２）本文算法在时间性能上改进率随ＴＳＰ事例中城市数的增加而增大，体现了算法求解大规模ＴＳＰ事例的能力，而其他算法没有这样的趋势．
对比ＡＣＳ算法，图４给出了本文算法在收敛时间上的改进率．尽管本文算法在时间性能方面的改进率只有数倍到数十倍，但却显现出～种非常有潜力的趋势：算法收敛时间的改进随城市规模的增大而增大．究其原因，主要是因为本文算法将多粒度思想引入到ＴＳＰ问题的描述中，从根本上将大规模ＴＳＰ问题归约为容易求解的小规模问题来求解，故有可能有效地克服或避免“组合爆炸”问题，快速地求解原问题．而且，本文给出的ＴＳＰ问题的多粒度描述模型能被方便地扩展，得到更多层粒度的描述模型，从而为解决更大更复杂的ＴＳＰ问题提供・个可行的思路．
Ｆｉｇ．４
Ｉｍｐｒｏｖｅｍｅｎｔ
ｒａｔｅｓｏｆｔｈｅ
ＡＣＯＭＧＲａｌｇｏｒｉｔｈｍ
ｏｎ
ｒｕｎｔｉｍｅｆｏｒｄｉｆｆｅｒｅｎｔＴＳＰｉｎｓｔａｎｃｅｓ．
图４本文算法在不同ＴＳＰ事例上时间性能的改进率
然而，尽管本文算法在提高蚁群算法时间性能方面效果显著，但正如表３所示：算法在一些事例上所得到的最优解不如一些改进算法好．主要原因是本文算法的设计较依赖于所求解的问题中城市分布的特征，即对于具有明显聚类特征的大规模ＴＳＰ问题求解时，往往能快速得到较好的结果，而在处理分布特征不明显的ＴＳＰ问题时，解的精度欠佳．
计算机研究与发展２０ｌＯ，４７（３）
５结论及进一步的工作
蚁群算法是一种元启发式的随机搜索技术，由于具有鲁棒性、正反馈以及可并行计算等特点，所以成为目前解决组合优化问题最成功的算法之一．然而，蚁群算法在求解大规模组合优化问题时，收敛时间过长仍是制约其广泛应用的瓶颈．为此，本文给出了一种ＴＳＰ问题的多粒度描述模型，并基于该模型提出了一种新的ＴＳＰ问题的蚁群求解算法．该算法利用ＴＳＰ问题的多粒度描述将难解的大规模ＴＳＰ问题分解为易于求解的小规模ＴＳＰ问题来求解．由于粒度的划分大大缩小了原问题的规模，所以算法的计算复杂度能成倍地降低．在一些中、大规模的ＴＳＰ问题上的实验表明：新算法在求解速度上不仅比经典的ＡＣＳ算法有显著的提高，而且比一些新近的算法具有更强的求解大规模ＴＳＰ问题的能力．
本文提出的蚁群算法，为快速求解大规模ＴＳＰ问题提供了一种新方法，也为解决其他大规模组合优化问题提供了一种新思路，是蚁群算法快速收敛问题研究的一个新成果．但如前所述，本文算法在提高解质量方面具有一定的局限性，如何克服这个局限，在快速求解的前提下提高求解精度将是我们下一步研究的重点．
参考文献
［１３Ｄｏｒｉｇｏ
Ｍ。Ｍａｎｉｅｚｚｏ
Ｖ，Ｃｏｌｏｒｎｉ
Ａ．Ｔｈｅ
ａｎｔ
ｓｙｓｔｅｍ：
Ｏｐｔｉｍｉｚａｔｉｏｎ
ｂｙ
ａ
ｃｏｌｏｎｙｏｆ
ｃｏｏｐｅｒａｔｉｎｇ
ａｇｅｎｔｓ口］．ＩＥＥＥ
Ｔｒａｎｓ
ｏｎ
Ｓｙｓｔｅｍｓ。Ｍａｎ，ａｎｄＣｙｂｅｒｎｅｔｉｃｓ。ＰａｒｔＢ．１９９６，２６
（１）：２９—４１
［２］Ｇａｍｂａｒｄｅｌｌａ
Ｌ
Ｍ，Ｄｏｒｉｇｏ￣ＬＳｏｌｖｉｎｇｓｙｍｍｅｔｒｉｃ
ａｎｄ
ａｓｙｍｍｅｔｒｉｃ
ＴＳＰｓ
ｂｙ
ａｎｔ
ｃｏｌｏｎｉｅｓ［ｃＪ／／Ｐｒｏｃｏｆｔｈｅ
Ｉｎｔ
Ｃｏｎｆ
ｏｎ
Ｅｖｏｌｕｔｉｏｎａｒｙ
Ｃｏｍｐｕｔａｔｉｏｎ．Ｐｉｓｃａｔａｗａｙ，ＮＪ：ＩＥＥＥ，
１９９６ｚ
６２２—６２７
［３３
ＢｌｕｍＣ。ＤｏｒｉｇｏＭ．Ｓｅａｒｃｈｂｉａｓｉｎ
ａｎｔ
ｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎ
ｌ
Ｏｎ
ｔｈｅ
ｒｏｌｅｏｆ
ｃｏｍｐｅｔｉｔｉｏｎ－ｂａｌａｎｃｅｄｓｙｓｔｅｍｓ［／Ｊ．ＩＥＥＥ
Ｔｒａｎｓ
ｏｎ
Ｅｖｏｌｕｔｉｏｎａｒｙ
Ｃｏｍｐｕｔａｔｉｏｎ，２００５，９（２）：１５９－１７４
［４］Ｂｌｕｍ
Ｃ，ＤｏｒｉｇｏＭ．Ｔｈｅｈｙｐｅｒ－ｃｕｂｅ
ｆｒａｍｅｗｏｒｋ
ｆｏｒ
ａｎｔ
ｃｏｌｏｎｙ
ｏｐｔｉｍｉｚａｔｉｏｎ口］．ＩＥＥＥ
Ｔｒａｎｓ
ｏｎ
Ｓｙｓｔｅｍｓ，Ｍａｎ，ａｎｄ
Ｃｙｂｅｒｎｅｔｉｃｓ，２００４，３４（２）ｌ１１６１－１１７２
［５］ＤｏｒｉｇｏＭ，ＢｉｒａｔｔａｒｉＭ，ＳｔｕｔｚｌｅＴ．Ａｎｔｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎ：
Ａｒｔｉｆｉｃｉａｌ
ａｎｔｓ
ａｓ
ａ
ｃｏｍｐｕｔａｔｉｏｎａｌｉｎｔｅｌｌｉｇｅｎｃｅｔｅｃｈｎｉｑｕｅ［Ｊ］．
ＩＥＥＥＣｏｍｐｕｔａｔｉｏｎａｌＩｎｔｅｌｌｉｇｅｎｃｅＭａｇａｚｉｎｅ，２００６，１（１１）ｌ
２８—３９
冀俊忠等：基于多粒度的旅行商问题描述及其蚁群优化算法４４３
Ｅ６－］Ｄｏｒｉｇｏ
Ｍ，Ｇａｍｂａｒｄｅｌｌａ
Ｌ
Ｍ．Ａｎｔ
ｃｏｌｏｎｙ
ｓｙｓｔｅｍ：Ａ
ｃｏｏｐｅｒａｔｉｖｅｌｅａｒｎｉｎｇ
ａｐｐｒｏａｃｈ
ｔｏ
ｔｈｅ
ｔｒａｖｅｌｉｎｇ
ｓａｌｅｓｍａｎ
ｐｒｏｂｌｅｍ【Ｊ］．ＩＥＥＥ
Ｔｒａｎｓ
０ｎ
ＥｖｏｌｕｔｉｏｎａｒｊｒＣｏｍｐｕｔａｔｉｏｎ，
１９９７，ｌ（Ｉ）：５３－６６
Ｅ７３ＳｔｕｔｚｌｅＴ，ＨｏｏｓＨＨ．ＭＡＸ－ＭＩＮ
ａｎｔ
ｓｙｓｔｅｍｉ－Ｊ１．Ｆｕｔｕｒｅ
ＧｅｎｅｒａｔｉｏｎＣｏｍｐｕｔｅｒＳｙｓｔｅｍ，２０００．１６（８）：８８９－９１４
Ｆ８ＪＨｕａｎｇ
Ｇｕｏｒｕｉ，Ｃａｏ
Ｘｉａｎｂｉｎ，Ｗａｎｇ
Ｘｕｆａ．Ａｎａｎｔ
ｃｏｌｏｎｙ
ｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎ
ｐｈｅｒｏｍｏｎｅｄｉｆｆｕｓｉｏｎ［Ｊ］．
Ａｅｔａ
Ｅｌｅｃｔｒｏｎｉｃｓ
Ｓｉｎｉｃａ，２００４．３２（５）：８６５－８６８（ｉｎＣｈｉｎｅｓｅ）
（黄国锐，曹先彬，王煦法．基于信息素扩散的蚁群算法［Ｊ３．电子学报，２００４，３２（５）：８６５—８６８）Ｅ９－１
ＷｕＢｉｎ，ＳｈｉＺｈｏｎｇｚｈｉ．Ａｎ
ａｎｔ
ｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍ
ｂａｓｅｄ
ｐａｒｔｉｔｉｏｎ
ａｌｇｏｒｉｔｈｍｆｏｒＴＳＰ［Ｊ］．ＣｈｉｎｅｓｅＪｏｕｒｎａｌｏｆ
Ｃｏｍｐｕｔｅｒｓ。２００１，２４（１３）：１３２８—１３３３（ｉｎＣｈｉｎｅｓｅ）
（吴斌，史忠植．一种基于蚁群算法的ＴＳＰ问题分段求解算法［Ｊ］．计算机学报，２００１，２４（１３）：１３２８—１３３３）
［１０］ＷｕＱｉｎｇｈｏｎｇ，ＺｈａｎｇＪｉｈｕｉ，ＸｕＸｉｎｈｅ．Ａｎ
ａｎｔ
ｃｏｌｏｎｙ
ａｌｇｏｒｉｔｈｍｗｉｔｈｍｕｔａｔｉｏｎ
ｆｅａｔｕｒｅｓ［Ｊ３．ＪｏｕｒｎａｌｏｆＣｏｍｐｕｔｅｒ
ＲｅｓｅａｒｃｈａｎｄＤｅｖｅｌｏｐｍｅｎｔ．１９９９，３６（１０）ｌ１２４０—１２４５（ｉｎ
Ｃｈｉｎｅｓｅ）
（吴庆洪，张纪会，徐心和．具有变异特征的蚁群算法［Ｊ３．计算机研究与发展，１９９９，３６（１０）：１２４０－１２４５）
［１１］Ｄｉｎｇ
Ｊｉａｎｌｉ，Ｃｈｅｎ
Ｚｅｎｇｑｉａｎｇ，Ｙｕａｎ
Ｚｈｕｚｈｉ．Ｏｎ
ｔｈｅ
ｃｏｍｂｉｎａｔｉｏｎｏｆ
ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍａｎｄ
ａｎｔ
ａｌｇｏｒｉｔｈｍＥＪ３．
ＪｏｕｒｎａｌｏｆＣｏｍｐｕｔｅｒＲｅｓｅａｒｃｈａｎｄＤｅｖｅｌｏｐｍｅｎｔ・２００３・４０
（９）：１３５１—１３５６（ｉｎＣｈｉｎｅｓｅ）
（丁建立，陈增强，褒著祉．遗传算法与蚂蚁算法的融合ＥＪ３．计算机研究与发展，２００３，４０（９）：１３５１—１３５６）
［１ｚ］Ｚｈｕ
Ｑｉｎｇｂａｏ，Ｙａｎｇ
Ｚｈｉｊｕｎ．Ａｎａｎｔ
ｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍ
ｂａｓｅｄ
ｏｎｍｕｔａｔｉｏｎ
ａｎｄ
ｄｙｎａｍｉｃ
ｐｈｅｒｏｍｏｎｅ
ｕｐｄａｔｉｎｇ口］．Ｊｏｕｒｎａｌ
ｏｆ
Ｓｏｆｔｗａｒｅ，２００４。１５（２）：１８５—１９２
（ｉｎ
Ｃｈｉｎｅｓｅ）
（朱庆保，杨志军．基于变异和动态信息素更新的蚁群优化算法［Ｊ］．软件学报，２００４，１５（２）；１８５—１９２）
［１３］ＲｅｉｍａｎｎＭ．Ｇｕｉｄｉｎｇ
ＡＣＯｂｙｐｒｏｂｌｅｍｒｅｌａｘａｔｉｏｎ：Ａ
ｃａｓｅ
ｓｔｕｄｙ
ｏｎ
ｔｈｅｓｙｍｍｅｔｒｉｃＴＳＰ［Ｇ］／ＩＬＮＣＳ４７７１．Ｂｅｒｌｉｎ
ｌ
Ｓｐｒｉｎｇｅｒ。２００７：４５－５６［１４］ＬｅＬｏｕａｍＦＸ，ＧｅｎｄｒｅａｕＭ，ＰｏｔｖｉｎＪＹ．ＧＥＮＩａｎｔｓｆｏｒｔｈｅ
ｔｒａｖｅｌｌｉｎｇ
ｓａｌｅｓｍａｎ
ｐｒｏｂｌｅｍ［刀．Ａｎｎａｌｓｏｆ
Ｏｐｅｒａｔｉｏｎｓ
Ｒｅｓｅａｒｃｈ。２００４。１３１（１０）：１８７—２０１
［１５３
Ｌｉ
Ｂｉｎｇｙｕ，Ｘｉａｏ
Ｙｕｎｓｈｉ．Ａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｂａｓｅｄ
ｏｎ
ｍｏｄｅｌａｌｇｏｒｉｔｈｍｆｏｒｔｒａｖｅｌｉｎｇｓａｌｅｓｍａｎｐｒｏｂｌｅｍ口］．Ｊｏｕｒｎａｌ
ｏｆＴｏｎｇｊｉＵｎｉｖｅｒｓｉｔｙ，２００３，３１（１１）：１３４８—１３５２（ｉｎＣｈｉｎｅｓｅ）
（李炳宇，萧蕴诗．基于模式求解旅行商问题的蚁群算法［Ｊ－Ｉ．同济大学学报，２００３，３１（１１）：１３４８—１３５２）
［１６３
ＺｏｕＰｅｎｇ。Ｚｈｏｕ
Ｚｈｉ，ＣｈｅｎＧｕｏｌｉａｎｇ，ｅｔａＬ
Ａ
ｍｕｌｔｉｌｅｖｅｌ
ｒｅｄｕｃｔｉｏｎ
ａｌｇｏｒｉｔｈｍ
ｔｏ
ＴｓＰ［刀．Ｊｏｕｒｎａｌｏｆ
Ｓｏｆｔｗａｒｅ，２００３，
１４（１）：３５－４２（ｉｎＣｈｉｎｅｓｅ）
（邹鹏，周智。陈国良，等．求解ＴＳＰ问题的多级归约算法［Ｊ］．软件学报，２００３，１４（１）：３５－４２）
［１７］ＺｈａｎｇＹａｎｐｉｎｇ，ＺｈａｎｇＬｉｎｇ，ＷｕＴａｏ．Ｔｈｅ
ｒｅｐｒｅｓｅｎｔａｔｉｏｎ
ｏｆ
ｄｉｆｆｅｒｅｎｔｇｒａｎｕｌａｒ
ｗｏｒｌｄｓ：Ａ
ｑｕｏｔｉｅｎｔ
ｓｐａｃｅ口］．Ｃｈｉｎｅｓｅ
ＪｏｕｒｎａｌｏｆＣｏｍｐｕｔｅｒｓ，２００４，２７（３）：３２８—３３３（ｉｎＣｈｉｎｅｓｅ）
（张燕平，张铃．吴涛．不同粒度世界的描述法——商空间法
［Ｊ］．计算机学报，２００４，２７（３）：３２８－３３３）
［１８］ＥａｓｔｅｒＭ，Ｋｒｉｅｇｅｌ
Ｈ
Ｐ，ＳａｎｄｅｒＪ，ｅｔａ１．Ａｄｅｎｓｉｔｙ－ｂａｓｅｄ
ａｌｇｏｒｉｔｈｍｆｏｒｄｉｓｃｏｖｅｒｉｎｇｃｌｕｓｔｅｒｓ
ｉｎｌａｒｇｅ
ｓｐａｔｉａｌ
ｄａｔａｂａｓｅｓｗｉｔｈ
ｎｏｉｓｅ［ｃ］／／Ｐｒｏｃｏｆ
ｔｈｅ
Ｉｎｔ
Ｃｏｎｆ
ｏｎ
Ｋｎｏｗｌｅｄｇｅ
Ｄｉｓｃｏｖｅｒｙ
ａｎｄ
Ｄａｔａ
Ｍｉｎｉｎｇ（ＫＤＤ－９６）．ＭｅｎｌｏＰａｒｋ，ＣＡ：
ＡＡＡＩ，１９９６：２２６－２３１
［１９３ｊｉＪｕｎｚｈｏｎｇ．ＨｕａｎｇＺｈｅｎ，Ｌｉｕ
Ｃｈｕｎｎｉａｎ．Ａｆａｓｔ
ａｎｔ
ｃｏｌｏｎｙ
ｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｆｏｒｔｒａｖｅｌｉｎｇｓａｌｅｓｍａｎｐｒｏｂｌｅｍｓ［Ｊ］．
Ｊｏｕｒｎａｌｏｆ
Ｃｏｍｐｕｔｅｒ
Ｒｅｓｅａｒｃｈａｎｄ
Ｄｅｖｅｌｏｐｍｅｎｔ，２００９，４６
（６）：９６８—９７８（ｉｎＣｈｉｎｅｓｅ）
（冀俊忠，黄振，刘椿年．一种快速求解旅行商问题的蚁群算法［Ｊ］．计算机研究与发展。２００９，４６（６）：９６８—９７８）
ＪｉＪｕｎｚｈｏｎｇ。ｂｏｒｎｉｎ１９６９．ＰｈＤｏｆ
Ｂｅｉｊｉｎｇ
Ｕｎｉｖｅｒｓｉｔｙｏｆ
Ｔｅｃｈｎｏｌｏｇｙ．Ｐｒｏｆｅｓｓｏｒ．
Ｓｅｎｉｏｒ
ｍｅｍｂｅｒ
ｏｆＣｈｉｎａＣｏｍｐｕｔｅｒＦｅｄｅｒａｔｉｏｎ．Ｈｉｓｍａｉｎ
ｒｅｓｅａｒｃｈ
ｉｎｔｅｒｅｓｔｓ
ｉｎｃｌｕｄｅｍａｃｈｉｎｅ
ｌｅａｒｎｉｎｇ，Ｗｅｂ
ｉｎｔｅｌｌｉｇｅｎｃｅ，
ａｎｄｃｏｍｐｕｔａｔｉｏｎｉｎｔｅｌｌｉｇｅｎｃｅ．
冀俊忠，１９６９年生，博士，教授，中国计算机学会高级会员，主要研究方向为机器学习、Ｗｅｂ智能、计算智能．
ＨｕａｎｇＺｈｅｎ，ｂｏｒｎ
ｉｎ
１９８１．Ｍａｓｔｅｒ．Ｈｉｓ
ｍａｉｎｒｅｓｅａｒｃｈｉｎｔｅｒｅｓｔｓｉｎｃｌｕｄｅｄａｔａｍｉｎｉｎｇ
ａｎｄ
Ｗｅｂｉｎｔｅｌｌｉｇｅｎｃｅ．
黄振。１９８１年生，硕士，主要研究方向为数据挖掘、ｗｅｂ智能．
ＬｉｕＣｈｕｎｎｉａｎ．ｂｏｒｎｉｎ１９４４．ＰｒｏｆｅｓｓｏｒａｎｄＰｈＤｓｕｐｅｒｖｉｓｏｒ．ＲｅｃｅｉｖｅｄｈｉｓＢＳｃｄｅｇｒｅｅ
ｉｎ
ｍａｔｈｅｍａｔｉｃｓｆｒｏｍＰｅｋｉｎｇＵｎｉｖｅｒｓｉｔｙ，
ｈｉｓ
ＭＳＣ
ｄｅｇｒｅｅ
ｉｎ
ｃｏｍｐｕｔｅｒ
ｓｃｉｅｎｃｅ
ｆｒｏｍ
ＢｅｉｊｉｎｇＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，ａｎｄｈｉｓ
ＰｈＤ
ｄｅｇｒｅｅ
ｉｎ
ｓｏｆｔｗａｒｅ
ｅｎｇｉｎｅｅｒ
ｆｒｏｍ
ＮｏｒｗｅｇｉａｎＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ．Ｈｉｓｍａｉｎｒｅｓｅａｒｃｈ
ｉｎｔｅｒｅｓｔｓ
ｉｎｃｌｕｄｅ
ｄａｔａ
ｍｉｎｉｎｇ，ｉｎｄｕｃｔｉｖｅ
ｌｏｇｉｃ
ｐｒｏｇｒａｍｍｉｎｇ，ｃｏｎｓｔｒａｉｎｔｐｒｏｇｒａｍｍｉｎｇ，ｍａｃｈｉｎｅｌｅａｒｎｉｎｇ
ａｎｄｓｏｆｔｃｏｍｐｕｔｉｎｇ．
刘椿年，１９４４年生，教授。博士生导师，主要研究方向为数据挖掘、人工智能、约束逻辑程序设计．
Ｄａｉ
Ｑｉｇｕｏ，ｂｏｒｎｉｎ１９８５．Ｍａｓｔｅｒｃａｎｄｉｄａｔｅ
ｏｆ
ＢｅｉｊｉｎｇＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ．Ｈｉｓ
ｍａｉｎｒｅｓｅａｒｃｈｉｎｔｅｒｅｓｔｓｉｎｃｌｕｄｅｄａｔａｍｉｎｉｎｇａｎｄｃｏｍｐｕｔａｔｉｏｎｉｎｔｅｌｌｉｇｅｎｃｅ．
代启国．１９８５年生，硕士研究生，主要研究
方向为数据挖掘、计算智能．
４４４
计算机研究与发展２０１０．４７（３）
ＲｅｓｅａｒｃｈＢａｃｋｇｒｏｕｎｄ
Ａｎｔｃｏｌｏｎｙ
ｏｐｔｉｍｉｚａｔｉｏｎ（ＡＣＯ）ａｌｇｏｒｉｔｈｍｉｓ
ａ
ｍｅｔａｈｅｕｒｉｓｔｉｃａｎｄｓｔｏｃｈａｓｔｉｃｓｅａｒｃｈｔｅｃｈｎｏｌｏｇｙ，ｗｈｉｃｈｈａｓｂｅｅｎ
ａ
ｏｎｅ
ｏｆｔｈｅ
ｅｆｆｅｃｔｉｖｅｔｏｏｌｓｆｏｒｓｏｌｖｉｎｇｄｉｓｃｒｅｔｅｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓ．Ｈｏｗｅｖｅｒ，ｔｈｅｒｅｉｓｍｕｃｈｔｉｍｅ
ｔＯ
ｂｏｔｔｌｅｎｅｃｋｔｈａｔ
ｐｒｏｐｏｓｅｓ
ａ
ｔｈｅＡＣＯａｌｇｏｒｉｔｈｍｎｏｖｅｌａｎｄｈｉｇｈ
ＣＯＳＴＳｔＯＯ
ｓｏｌｖｅｔｈｅｉａｒｇｅ－ｓｃａｌｅｄｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓ．Ｔｈｅｒｅｆｏｒｅ，ｔｈｉｓ
ｐａｐｅｒ
ｅｆｆｉｃｉｅｎｔＡＣＯ
ａｌｇｏｒｉｔｈｍｆｏｒｔｈｅｔｒａｖｅｌｉｎｇｓａｌｅｓｍａｎｐｒｏｂｌｅｍｓ（ＴＳＰｓ）．Ｆｉｒｓｔ，ａｎｏｖｅｌｍｕｌｔｉｐｌｅ－ｇｒａｉｎｒｅｐｒｅｓｅｎｔａｔｉｏｎｍｏｄｅｌｏｆＴＳＰｓｉｓｐｒｏｐｏｓｅｄ．Ｂａｓｅｄ
ｏｎ
ｔｈｅｍｏｄｅｌ，ｔｈｉｓｐａｐｅｒ
ｏｎ
ｐｒｅｓｅｎｔｓ
ａ
ｎｅｗ
ａｌｇｏｒｉｔｈｍｆｏｒＴＳＰｓ，ｗｈｉｃｈｍａｉｎｌｙｃｏｎｔａｉｎｓｓｉｘｐｈａｓｅｓ，ｉ．ｅ．ａｇｒａｎｕｌａｒｉｔｙ
ｏｎ
ｐａｒｔｉｔｉｏｎａｌｇｏｒｉｔｈｍｂａｓｅｄｄｅｎｓｉｔｙｃｌｕｓｔｅｒｉｎｇ，ａｎＡＣＯａｌｇｏｒｉｔｈｍｂａｓｅｄ
ｔｈｅ
ｓａｍｅ
ｔｈｅ
ｃｏａｒｓｅ
ｇｒａｉｎ，ａ
ｃｏｎｎｅｃｔｉｏｎａｌｇｏｒｉｔｈｍｂｅｔｗｅｅｎ
ａ
ｔｗｏｇｒａｎｕｌａｒｉｔｉｅｓ，ａｎＡＣＯａｌｇｏｒｉｔｈｍｉｎｇｒａｎｕｌａｒｉｔｙ，ａｆｕｓｉｏｎａｌｇｏｒｉｔｈｍ
ａｍｏｎｇｇｒａｎｕｌａｒｉｔｉｅｓ，ａｎｄ
ｏｆ
ＴＳＰｓ
ｓｕｂｓｅｃｔｉｏｎ
ｔｈｅ
ｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｒｅｇａｒｄｌｅｓｓｏｆｇｒａｎｕｌａｒｉｔｉｅｓ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｆｏｒｌａｒｇｅｎｕｍｂｅｒｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｃｏｍｐｅｔｉｔｉｖｅｉｎｒｅｓｅａｒｃｈ
ｔｉｍｅ
ｃａｎ
ｄｅｍｏｎｓｔｒａｔｅｔｈａｔ
ｉｓ
ｇｒｅａｔｌｙｉｍｐｒｏｖｅｔｈｅｓｐｅｅｄｏｆ
ｃｏｎｖｅｒｇｅｎｃｅ
ｉｎｃｏｎｔｒａｓｔｔｏ
ｔｈｅｃｌａｓｓｉｃａｌＡＣＳａｌｇｏｒｉｔｈｍ．ａｎｄ
ｈｉｇｈｌｙ
ｐｅｒｆｏｒｍａｎｃｅｃｏｍｐａｒｅｄｗｉｔｈｓｏｍｅｌａｔｅｓｔｅｌｉｔｉｓｔＡＣＯａｌｇｏｒｉｔｈｍｓ．Ｏｕｒｗｏｒｋｉｓｓｕｐｐｏｒｔｅｄｂｙｔｈｅｍａｊｏｒ
ｐｒｏｇｒａｍｏｆｔｈｅＮａｔｉｏｎｓｌＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＣｈｉｎａ（Ｎｏ．６０４９６３２２）。ｔｈｅＢａｓｉｃＴｈｅｏｒｙａｎｄＣｏｒｅＴｅｃｈｎｉｑｕｅｓ
ｏｆＮｏｎ－ＣａｎｏｎｉｃａｌＫｎｏｗｌｅｄｇｅ（Ｎｏｓ．６０４９６３２２，６０４９６３２７），ａｎｄｔｈｅ
ＢｅｉｊｉｎｇＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎ（Ｎｏ．４０８３０３４）．
第１７届全国网络与数据通信学术会议（ＮＤＣＣ２０１０）征文通知
２０１０年９月１６Ｅｌ一１７日
北戴河
由中国计算机学会网络与数据通信专业委员会主办，由东北大学秦皇岛分校和东北大学信息科学与工程学院联合承办的“第１７届全国网络与数据通信学术会议”将于２０１０年９月１６日到１７日在美丽的海滨城市北戴河举行．
本次大会将围绕“网络与通信新技术及应用”这一主题展开，为来自国内外高等院校、科研院所、企事单位的学者、教授、专家、工程师提供一个代表国内网络与数据通信产学研界高水平的高层信息交流平台，探讨本领域发展所面临的关键挑战问题和热点研究方向．
会议论文集将由《东北大学学报（自然科学版）》增刊出版（ＥＩ检索源）．论文参照《东北大学学报》格式，字数一般不超过６０００字，稿件通过投稿系统提交，具体参见会议网站ｈｔｔｐ：／／ｎｄｃｃ２０１０．ｎｅｕｑ．ｅｄｕ．ｃｎ．部分优秀论文将被推荐到《计算机学报》，《电子学报》、《计算机研究与发展》、《电子与信息学报》的正刊发表（均为ＥＩ检索源）．会议期间将评选会议优秀论文和优秀学
生论文．
本次会议的主要征文范围包括以下领域（但不限于）：
新一代网络技术：网络体系结构、路由／交换技术、协议丁程、网络虚拟化、认知网络、ＩＰｖ４／ＩＰｖ６过渡技术、ＮＧＮＩＮＧＩ平台应用；新一代计算技术：云计算／网格计算、并行／分布式计算、普适／效用计算、服务计算；无线通信技术：下一代移动通信技术、自适应信号处理、传感器网络、移动自组织网络、智能天线、卫星通信；其他；光通信技术、网络安全、网络管理、网络应用．
投稿须知
１）投稿内容突出作者的创新与成果，具有较重要的学术价值与应用推广价值，未在国内外公开发行的刊物或会议上发表
或宣读过．
２）论文语言要求中文，字数一般不超过６０００字，论文格式参照《东北大学学报》，投稿稿件用Ｗｏｒｄ文件形式．东北大学学报的网站地址如下：ｈｔｔｐ：／ｌｘｕｅｂａｏ．ｎｅｄ．ｅｄｕ．ｅｎ／ｎａｔｕｒａｌ／ｉｎｄｅｘ．ａｓｐ．
３）请在稿件最后附上第一作者姓名、性别、职务／职称，所属单位、通信地址、邮政编码、联系电话和Ｅ—ｍａｉｌ地址．并注明论文所属领域．
４）被录用的论文，至少要有一位作者参加会议并发盲，才有资格参与优秀论文的评选．
投稿方式
论文投稿通过投稿系统进行提交，详见会议网站：ｈｔｔｐ：／／ｎｄｃｃ２０１０．ｎｅｕｑ．ｅｄｕ．ｃｎ或者通过邮件地址ｎｄｅｃ２０１０＠ｍａｉｌ．ｎｅｕｑ．ｅｄｕ．ｃｎ联系．电子邮件请在邮件标题注明“ＮＤＣＣ２０１０投稿”．
重要日期
论文提交截止日期：２０１０年５月１５日；论文录用通知日期：２０１０年７月１日；会议注册截止日期：２０１０年８月１５日．联系方式
联系电话：０３３５—８０５２１５５
邮件地址：ｎｄｅｅ２０１０＠ｍａｉｌ．ｎｅｕｑ．ｅｄｕ．ｃｎ
联系人ｌ王翠荣韩来权
会议网站：ｈｔｔｐ：／／ｎｄｅｃ２０１０．ｎｅｕｑ．ｅｄｕ．ｅｆｔ