聚类处理的蚁群算法在旅行商问题中的应用

第３３卷第ｌ期　２０１５年３月　湖北民族学院学报（自然科学版）　Ｊｏｕｒｎａｌ　ｏｆ　Ｈｕｂｅｉ　Ｕｎｉｖｅｒｓｉｔｙ　ｆｏｒ　Ｎａｔｉｏｎａｌｉｔｉｅｓ（Ｎａｔｕｒｌａ　Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ）　Ｖ０１．３３　Ｎｏ．１　Ｍａｒ．２０１５　文章编号：１００８—８４２３（２０１５）０１－００３１—０４　ＤＯＩ：１０．１３５０１／ｊ．ｃｎｋｉ．４２—１５６９／ｎ．２０１５．０３．００９　聚类处理的蚁群算法在旅行商问题中的应用　孟喜艳　，傅文灵　，马波　，方壮　（１．恩施职业技术学院人文科学系，湖北恩施４４５０００；　２．湖北民族学院理学院，湖北恩施４４５０００）　摘要：针对大规模旅行商问题具有区域分布的族类特征，采用最小方差法将城市样本点聚成ｋ个城市群，利用蚁群　算法，求出每个城市群内部城市的最短路径及城市群之间的最短路径．提出了一种新的城市群连接方式及标记方　法，使得从任一个城市出发，以该方式可对每个城市群的连接城市进行标记，同时，利用循环搜索的方法可得到每　个城市群的连接方式，最终得到全局最短路径的一个满意解．最后利用ＴＳＰＬＩＢ提供的实验数据，对算法的正确性　进行了验证．　关键词：蚁群优化算法；旅行商问题；聚类分析　中图分类号：ＴＰ３０１．６　文献标志码：Ａ　Ａｐｐｌｉｃａｔｉｏｎ　ｏｆ　Ａｎｔ　Ｃｏｌｏｎｇ　Ａｌｇｏｒｉｔｈｍ　Ｂａｓｅｄ　ｏｎ　Ｃｌｕｓｔｅｒｉｎｇ　ｔｏ　Ｔｒａｖｅｌｉｎｇ　Ｓａｌｅｓ　Ｐｒｏｂｌｅｍ　ＭＥＮＧ　Ｘｉｙａｎ　，ＦＵ　Ｗｅｎｌｉｎｇ　，ＭＡ　Ｂｏ　，ＦＡＮＧ　Ｚｈｕａｎｇ　（１．Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｈｕｍａｎ　Ｓｃｉｅｎｃｅ，Ｃｏｌｌｅｇｅ　ｏｆ　Ｅｎｓｈｉ　Ｔｅｃｈｎｉｃａｌ，Ｅｎｓｈｉ　４４５０００，Ｃｈｉｎａ；　２．Ｓｃｈｏｏｌ　ｏｆ　Ｓｃｉｅｎｃｅ，Ｈｕｂｅｉ　Ｕｎｉｖｅｔｓｉｔｙ　ｆｏｒ　Ｎａｔｉｏｎａｌｉｔｉｅｓ，Ｅｎｓｈｉ　４４５０００，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ａｓ　ａ　ｌａｒｇｅ　ｎｕｍｂｅｒ　ｏｆ　ｓａｍｐｌｅ　ｓｅｔｓ　ｏｆ　ＴＳＰ　ｆｅａｔｕｒｅ　ｒｅｇｉｏｎａｌ　ｄｉｓｔｒｉｂｕｔｅｄ　ｃｌｕｓｔｅｒｉｎｇ，ｔｈｅ　ｃｉｔｙ　ｓａｍｐｌｅ　ｐｏｉｎｔｓ　ａｒｅ　ｃｈａｎｇｅｄ　ｉｎｔｏ　ｋ　ｄｉｆｆｅｒｅｎｔ　ｃｉｔｙ　ｇｒｏｕｐｓ　ａｎｄ　ｔｈｅ　ｓｈｏｒｔｅｓｔ　ｒｏｕｔｅ　ａｍｏｎｇ　ｃｉｔｙ　ｇｒｏｕｐｓ　ａｎｄ　ｃｉｔｉｅｓ　ｉｎｓｉｄｅ　ｅａｃｈ　ｃｉｔｙ　ｇｒｏｕｐｓ　ａｒｅ　ｏｂｔａｉｎｅｄ　ｂｙ　ｕｓｉｎｇ　ａｎｔ　ｃｏｌｏｎｙ　ｏｐｔｉｍｉｚａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ．Ｉｎ　ｔｈｉｓ　ｐａｐｅｒ，ｗｅ　ｐｒｏｐｏｓｅｄ　ａ　ｎｅｗ　ｍｅｔｈｏｄ　ｔｏ　ｌｉｎｋ　ｔｈｅ　ｃｉｔｙ　ｇｒｏｕｐｓ　ａｎｄ　ｍａｒｋ　ｔｈｅ　ｌｉｎｋｉｎｇ　ｃｉｔｉｅｓ．Ｂｙ　ｕｓｉｎｇ　ｔｈｉｓ　ｍｅｔｈｏｄ，ｅｖｅｒｙ　ｌｉｎｋｉｎｇ　ｃｉｔｙ　ｃａｎ　ｂｅ　ｍａｒｋｅｄ　ａｎｄ　ｔｈｅ　ｗａｙ　ｏｆ　ｃｏｎｎｅｃｔｉｎｇ　ｔｏ　ｅａｃｈ　ｃｉｔｙ　ｇｒｏｕｐｓ　ｃａｎ　ｂｅ　ｄｅｔｅｒｍｉｎｅｄ，ｔｈｅｎ　ｔｈｅ　ｇｌｏｂａｌ　ｓｈｏｒｔｅｓｔ　ｒｏｕｔｅ　ｉｓ　ｄｅｒｉｖｅｄ．Ｆｉｎａｌｌｙ　ｔｈｅ　ｃｏｒｒｅｃｔ　ｒｅｓｕｌｔ　ｈａｓ　ｂｅｅｎ　ｐｒｏｖｅｎ　ｂｙ　ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔａｌ　ｄａｔａ　ｖｅｒｉｆｉｃａｔｉｏｎ　ｐｒｏｖｉｄｅｄ　ｂｙ　ｔｈｅ　ｉｎｔｅｒｎａｔｉｏｎａｌｌｙ　ｒｅｃｏｇｎｉｚｅｄ　ＴＳＰＬＩＢ　ｉｎ　ｔｈｅ　ｃａｓｅ　ｐｒ１５２．　Ｋｅｙ　ｗｏｒｄｓ：ａｎｔ　ｃｏｌｏｎｙ　ｏｐｔｉｍｉｚａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ；ｔｒａｖｅｌｉｎｇ　ｓａｌｅｓｍａｎ　ｐｒｏｂｌｅｍ；ｃｌｕｓｔｅｒｉｎｇ　ａｎａｌｙｓｉｓ　旅行商问题（Ｔｒａｖｅｌｉｎｇ　Ｓａｌｅｍａｎ　Ｐｒｏｂｌｅｍ，ＴＳＰ）是指已知ｎ个城市的两两距离，商人从自己所处的城市出　发，确定一条访遍各个城市顾客一次且仅一次的最短路径问题．若将城市记为顶点集　＝　，　，…，　｝，相连　接顶点　与　组成的边ｅ　胸成集合记为边集Ｅ，相连接顶点　与　之间的距离ｄ　胸成的距离矩阵记为Ｄ，　ＴＳＰ问题的图论描述即为：在图Ｇ＝（　，ｅ）中确定一条长度最短的Ｈａｍｉｌｔｏｎ回路．　ＴＳＰ是一个ＮＰ完全难题，很多典型的组合优化问题如芯片加工问题、电路板设计中的钻孔问题、航迹　规划等，最终都可归结为ＴＳＰ问题．因此快速、有效地解决ＴＳＰ有着重要的理论价值和极高的实际应用价值．　相对于传统算法，蚁群算法＿１　自１９９１年Ｄｏｒｉｇｏ提出后，就成功应用到ＴＳＰ问题，并吸引了很多学者对其进　行研究．黄翰等　分析了蚁群算法的收敛速度；徐红梅等　分析了参数的初始设置对蚁群算法的影响；冀俊　忠　ｊ、李成兵　Ｊ、吴华峰　ｊ、梁志茂等　通过修正信息素更新方式，对蚁群算法进行了改进；胡俊鹏ｌ９　研究　了双向选择相遇算法，提高了搜索速度；怀丽波等¨ｕ－讨论了蚁群算法在其他优化方面的应用．春花等¨　研究　了蚁群算法参数的设置；孙凯等¨　还将蚁群算法与其它优化算法相融合，提高了部分ＴＳＰ问题的求解精度．　对于大规模的ＴＳＰ，蚁群算法容易陷入局部最优．考虑到旅行商问题的实际背景，商人访问一个城市群　中的每一个城市后，再访问下一个城市群是合理的，为此，先将所有城市聚类成若干城市群后，在每一个城市　收稿日期：２０１４—１２－１６．　基金项目：湖北省教育厅科学技术研究项目（Ｂ２０１１１９０９）；恩施州科技局科学研究项目（２０１１１６０１）；２０１２年地方高校国家级大学生创新创业　练计划项目（２０１２１０５１７００２）．　作者简介：孟喜艳（１９７９－），女，硕士生，讲师，主要从事数学建模、生物数学的研究．　３２　湖北民族学院学报（自然科学版）　第３３卷　群内求解ＴＳＰ子问题，然后选择合适的城市群之间的连接线路，使总的的连接路线最短，这样可以降低算法　的复杂度，最终得到所有城市最佳巡游路线的一个满意解．依据这一思想，卢欣　对这一算法的复杂度进行　了分析；丁建立¨　以ｐｃｂ４４２问题为例，通过动态聚类结合蚁群优化算法得到了该问题的一个近似解，冀俊　忠　Ｊ、侯文静　、任志刚等＿１　通过不同的类与类之间连接方式结合蚁群算法，得到了大规模ＴＳＰ的近似解．　通过聚类的方法求解ＴＳＰ问题，其准确性依赖于各城市群建的连接顺序，这样，如何从已有的分类及连接顺　序中找到一个满意的巡游圈，就是一个值得研究的问题，本文通过蚁群算法确定了城市群的连接顺序，并在　此顺序下，通过标记城市群接入点的方式，以ＴＳＰ问题测试库中的Ｐｒ１５２数据为例，得到了一个最佳巡游圈　的满意解．　１算法基本思想　如图１示，将所有城市聚类，图１所示聚成４个城市群，在每一城市群中用蚁群算法求解其最佳巡游圈，　并求出城市群的连接顺序，图１中每一类的最佳巡游圈如黑色线条所示，城市群的连接顺序为Ｇ　Ｇ：一Ｇ，　一Ｇ　一Ｇ　．任给一点Ｐ　∈Ｇ　，在下一个城市群Ｇ　找到距Ｐ　离最短的点Ｐ：，将Ｐ：标记为Ｇ　的接入点，Ｐ　：，　Ｐ”：为Ｐ：在Ｇ　中巡游圈中的邻接点；在第三个城市群Ｇ，中找到　距Ｐ　，Ｐ　最短的点Ｐ　Ｐ”。　并分别求其距离ＤＰ　尸　Ｄｐ＂２Ｐ”Ｇ　，计算ＤＰ＇２Ｐ　Ｇ　一Ｗ　２，　＂２Ｐ　Ｇ　一Ｗ　２，比较两者中的最小　值，将最小值对应的在Ｇ　中的点记为Ｐ。，Ｐ，作为Ｇ，城市群的接　入点，Ｐ　，Ｐ，，　为Ｐ　在Ｇ　城市群中巡游圈中的邻接点；　按此方法依次经行下去，当同一个点有两次标记为接入点时，　输出一个巡游圈，更新Ｐ　．寻找下一个巡游圈，当Ｐ　遍历完第一个　城市群中的每一个点时，结束循环．将巡游圈距离最小者作为输出．　２聚类分析的蚁群算法　２．１聚类分析　擘　图１算法示意图　在上节中，首先要对所有城市进行聚类．本文采用的是谱系聚类以城市点问的欧氏距离来进行分类，谱　系聚类是对统计样本进行定量分析的一种多元统计分析法，该方法是对待处理样本进行依次归类，然后由聚　类的方法得到一个二叉树聚类图．观测点之间的距离能够用欧氏距离或欧氏距离的平方来计算，而类间聚类　的计算方法有多种，这里计算类间距离的方法是Ｗａｒｄ最小方差法：若现在有／７，个观测数，　个变量数，Ｇ为　分类的个数，　为ｉ个观测，ｃ　是当前水平Ｇ的第Ｋ类，Ｊ７ｖ　为ｃ　中的观测个数，均值向量为　，类ｃ　中的均　值向量（中心）为　，ｌＩ　ｌＩ为欧氏长度，　＝　Ｉ　一　ｌｌ　是总离差平方和，　＝　ｌ　ｉ－ＸＫ＿　是类Ｃ　的类　ｌ内离差平方和，Ｐ　＝∑Ｗｊ为聚类水平Ｇ对应的各类的类内离差平方和的总和．假设某一步聚类过程中把类　ｃ　和类ｃ　合并为下一水平的类　，那么定义Ｂ甩＝　一　一　为合并导致的类内离差平方和的增量．用　ａ（ｘ，Ｙ）来表示两个观测点之间的距离或非相似性测度，Ｄ舡是第Ｇ水平的类ｃ　和类Ｇ　之间的距离或非相　似性测度．采用Ｗａｒｄ最小方差法时，Ｄ皿＝ＢＫＬ＝ｌ　一　ｌＩ『　／（１／　＋１／　）．　当观测距离为ｄ（　，ｌ，）＝ｌ　ＩＸ－Ｙ　ｌ　／２时递推公式为：ｌ　／ＮＭ。　ＤｊＭ＝　ＮＫＤ　ＪＫ＋Ｎ　ＬＤ　ＪＬ　／ＮＭ—ＮＫＮＬＤｒＬ，１　２．２基本蚁群优化算法　设ｃ表示观测点的集合，ｂ　（ｔ）表示ｔ时刻位于城市点ｉ的蚂蚁数目，　（　）为ｔ时刻路径（ｉ，Ｊ．）上的信息　量，ｍ为蚁群中蚂蚁的总数目，　表示ＴＳＰ规模，则ｍ＝　６　（ｔ）；ｒ＝｛丁　ｆ　　ｆｃ　，ｃｆ　ｃ　ｃ）是ｔ时刻集合Ｃ中所有城市　点任意两个城市点间残留信息素量的集合，设定在最开始时刻每条路径上的存储信息量相等，设定　（０）＝　ｃｏｎｓｔ．因为任意蚂蚁ｋ在遍历过程中不能重复经过同一个城市，建立禁忌表ｔａｂｕ　（ｋ＝１，２，…，１１）来记录蚂蚁　已经过的城市，禁忌表随着蚂蚁的运动做动态变化．搜索过程中，每只蚂蚁根据每条路径上的信息量及路径　本身的启发信息来计算状态转移概率，建立蚂蚁ｋ由ｉ城市转移Ｎｊ城市的状态转移概率如下　：　第１期　孟喜艳等：聚类处理的蚁群算法在旅行商问题中的应用　ｒ　３３　［ｒ　ｆ（ｔ）］　［ｒ／　ｆ（ｔ）］　．　ｐ　（　）：｛【　ｊ　＝＝１　＿　－　６　（２）　ｏ　∈　ｎ６　其中：　表示从ｉ到　的期望程度，一般认为从　到　的距离的倒数即ｒｌ　ｆ＝１／ｄ¨成为启发函数；ｏｌ为信息启发　式因子，表示路径的相对重要性，反映了蚂蚁在搜索路径过程中所积累的信息量在蚂蚁运动中所起的作用，　其值越大，那么其它蚂蚁走过的路径就更容易被后续蚂蚁选择，蚂蚁之间的相互协作性也就越强；　为期望　启发式因子，反映了蚂蚁在搜索路径过程中启发信息在蚂蚁选择路径中所受到重视程度，其值越大，则该状　态转移概率就会越接近贪心规则，越倾向于最优路径；ｐ　（ｔ）表示信息素较多且距离较短的路径被选中的概　率越大．　引入信息素在算法中的全局更新规则：当全部蚂蚁完成一次游历后，在其走过的路径上留下一定量的信　息素，从而改变信息素，则ｔ＋ｎ时刻的信息素修改公式：　丁　（ｔ＋ｎ）＝（１一Ｐ）・７－　（ｔ）＋Ｐ・△　（ｔ）　（３）　其中：Ｐ表示信息素挥发系数，则１－ｐ表示信息素的持久性系数，Ｐ∈［０，１）；初始时刻△　（０）＝０，△　（ｔ）表示　第ｋ只蚂蚁在本次迭代中留在边ｅ０上信息素量，若蚂蚁ｋ没有经过ｅ　则△ｒ　ｋ，的值为零，所以将△ｒ　表示为：　△　：Ｊ【　若蚂蚁ｋ在本次周游中经过边　（４）　０　否则　其中：Ｑ表示信息素强度；Ｃ　表示第ｋ只蚂蚁在本次周游中所走过的路径长度．　信息素局部更新规则：在路径构建过程中，对每只蚂蚁，每当其经过一条ｅ　时，它将立刻对这条边进行信　息素的更新：　ｒ　（ｔ）＝（１一　）・ｒ　（　）＋　・ｒｏ　（５）　其中：　是信息素局部挥发速率，满足Ｏ＜ｓＣ＜１；　。是信息素的初始值．　在算法的构建过程中，信息启发式因子Ｏ／和期望值启发式因子　对算法性能的影响和作用是相互配合、　密切相关的，要得到好的优化结果必须适当的选择　和　的取值范围一般的选取范围为　＝０．５～５，　＝１～５．　研究表明信息素的持久性系数１－１９关系到蚁群算法的全局搜索能力及收敛速度，系数过大则以前搜索过的　路径被再次选择的可能性过大，也会影响到算法的随机性能和全局搜索能力，反之减少系数虽可以提高算法　的随机性能和全局搜索能力但又会使得算法的收敛速度降低，因此在信息素的持久性系数选择的时候要对　全局搜索能力和收敛速度两方面做出合理折中的选择．　在ＴＳＰ测试库中以Ｏｌｉｖｅｒ３０（问题规模３０）数据为例，设定参数：　＝１，　＝５，Ｐ＝０．１，Ｑ＝１００，最大迭代次　数为２００次，计算得到图２所示结果．　由图２可知蚁群优化算法在解决ＴＳＰ上能较快得到可行解，结果也较为理想，但随着问题规模的增加，　算法的计算复杂度也在增加，收敛速度变慢，极有可能陷入局部最优解，例如取测试库中的ｐｒｌ０７（问题规模　１０７）测试时，得到如图３所示的结果．　一０　……一一…一～…—　鹣　ｍ　“１晦８　鬻　锄　黪　哟　ｔｍ妒姆　。。∞蹲　一ｌ肇８哇　孵一一一…一一　・　—　——　—　—弋　—　■　ｒ１崎—拍ｒ—　图２　Ｏｌｉｖｅｒ３０的ＴＳＰ最短路径及收敛分析　图３　Ｐｒｌ０７的ＴＳＰ最短路径及收敛分析　Ｆｉｇ．２　Ｔｈｅ　ｓｈｏｒｔｅｓｔ　ｒｏｕｔｅ　ａｎｄ　ｔｈｅ　Ｆｉｇ．３　Ｔｈｅ　ｓｈｏｒｔｅｓｔ　ｒｏｕｔｅ　ａｎｄ　ｔｈｅ　ｃｏｎｖｅｒｇｅｎｃｅ　ａｎａｌｙｓｉｓ　ｏｆ　Ｏｌｉｖｅｒ　３０　ｃｏｎｖｅｒｇｅｎｃｅ　ａｎａｌｙｓｉｓ　ｏｆ　Ｐｒｏｌ０７　图３所示，按收敛分析显示最短路径已收敛到最优解，但从其结果明显可看出此结果并非最优．Ｐｒｌ０７问　题的最优解为４４３０３，而图３所示的路径的最优解为４５　８４５．大量的实验显示ＡＣＯ算法因为其本身的鲁棒　性、自学习能力强能特点能有效解决小规模ＴＳＰ问题，但随着问题的规模变大、复杂度增加，迭代次数也要　３４　湖北民族学院学报（自然科学版）　第３３卷　增加，时间花费变大且不能得到全局最优解．　２．３基于聚类处理蚁群算法的步骤　针对单纯的ＡＣＯ算法已不能完全解决大规模ＴＳＰ问题，为了能有效求得可行解并求解过程中提高求解　速度，因此在ＡＣＯ算法的基础上加入聚类处理，通过聚类分析，将相似性大的城市点聚为一类，相似性小的　分开，每个小类可做一次ＴＳＰ子问题求解，然后将每个类作为一个城市点，再进行一次求解，最后即可合成　所需问题的可行解．如此一来，既保留了算法的特点，同时也提高了算法的求解速度，可避免出现局部最优现　象．其基本步骤如下：　１）对所有城市进行聚类．得到若干个城市群Ｇ　，Ｇ　，…，Ｇ　；　２）利用蚁群算法，求每一个城市群的最佳巡游圈Ｃ　．，Ｃ　一，ＣＧｋ￣并求每一类城市的聚类中心；　３）确定聚类中心的连接顺序，并将其作为城市群的连接顺序，不妨设其顺序就为Ｇ　，Ｇ　，…，Ｇ　；　４）确定城市群的接入点．任给Ｐ　∈Ｇ　，在Ｇ　中确定到Ｐ　距离最短的点Ｐ…，将Ｐ川标记为Ｇ…的接入　点，Ｐ　川，Ｐ”　为Ｐ川在第二类中巡游圈中的邻接点；在Ｇｍ中确定到Ｐ　，Ｐｎｉ＋ｌ距离最短的点Ｐ　，Ｐ”。　，并　分别求其距离ＤＰ　川Ｐ　，ＤＰ”川Ｐ”。　，计算ＤＰ　川Ｐ　ｒ　，－－Ｗ　Ⅲ，Ｄ　川尸，，　一　川，比较两者中的最小值，将最　小值对应的在Ｇｍ中的点记为Ｐｍ，Ｐｍ作为Ｇｍ的接入点，Ｐ　ｍ，Ｐ＂ｉ＋２为Ｐｍ在Ｇｍ中巡游圈中的邻接点；按　此方法依次经行下去，当同一个点有两次标记为接人点时，输出一个巡游圈，更新Ｐ　及接入城市标志．寻找　下一个巡游圈，当　遍历完Ｇ　中的每一个点时，结束循环．将巡游圈距离最小者作为输出．　３实验结果及分析　同样的设定参数Ｏ／＝１，　＝５，Ｐ＝０．１，Ｑ＝１００，最大迭代次数为５００次，分成３０个城市群，以测试数据库中　的Ｐｒ１５２为例，计算得到如图４所示，其可行解为７３　６８３与其最优解７３　６８２的误差不超过０．００１　５％．　４结论　本文所提出的在ＡＣＯ蚁群优化算法的基础上加入聚类的处理，对　大规模的ＴＳＰ问题进行分解，大大降低了问题的难度系数，也减小了　问题的复杂度，同时也保留了算法的求解特点．在聚类的基础上，问题　被细化，算法求解速度得到提高，避免了算法本身易陷入停滞现象的局　限性，但此方法也会因聚类的方法不一样而得到不一样的结果，同时还　图４本文算法处理Ｐｒ１５２所得结果　ｇ．４　Ｔｈｅ　ｐｒｏｃｅｓｓｉｎｇ　ｒｅｓｕｌｔ　ｏｆ　ｐｒ１５２　会因城市点间的相似程度而影响聚类结果，所以对于这类的大规模　ＦｉＴＳＰ问题的求解还需具体考虑到实际问题，从实际出发才能更好的解决问题．　参考文献：　［１］Ｃｏｌｏｒｎｉ　Ａ，Ｄｏｒｉｇｏ　Ｍ，Ｍａｎｉｅｚｚｏ　Ｖ．Ｄｉｓｔｉｒｂｕｔｅｄ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｂｙ　ａｎｔ　ｃｏｌｏｎｉｅｓ．Ｐｒｏｃｅｅｄｉｎｇ　ｏｆｔｈｅ　１ｓｔ　Ｅｕｒｏｐｅａｎ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ａｒｉｉｆｃｉａｌ　Ｌｉｆｅ［Ｃ］／／Ｐａｒｉｓ，　Ｆｒａｎｃｅ：Ｅｌｓｅｖｉｅｒ　Ｐｕｂｌｉｓｈｉｎｇ，１９９１：１３４—１４２．　［２］黄翰，郝志峰，吴春国，等．蚁群算法的收敛速度分析［Ｊ］．计算机学报，２００７（８）：１３４４—１３５３．　［３］徐红梅，陈义保，刘加光，等．蚁群算法中参数设置的研究［Ｊ］．山东理工大学学报：自然科学版，２００８（１）：７—１１．　［４］　冀俊忠，黄振，刘椿年．基于聚类和分段优化的蚁群算法［Ｊ］．北京工业大学学报，２００８（４）：４３４—４４０．　［５］　冀俊忠，黄振，刘椿年．一种快速求解旅行商问题的蚁群算法［Ｊ］．计算机研究与发展，２００９（６）：９６８—９７８．　［６］李成兵，郭瑞雪，李敏．改进蚁群算法在旅行商问题中的应用［Ｊ］．计算机应用，２０１４（ＳＩ）：１３１—１３２．　［７］吴华锋，陈信强，毛奇凰，等．基于自然选择策略的蚁群算法求解ＴＳＰ问题［Ｊ］．通信学报，２０１３（４）：１６５—１７０．　［８］梁志茂，腾建华，何晋．基于改进蚁群算法的ＴＳＰ问题研究［Ｊ］．云南民族大学学报：自然科学版，２０１０，１９（３）：２２０—２２３．　［９］胡俊鹏．基于双向选择的蚁群相遇算法的优化［Ｊ］．湖北民族学院学报：自然科学版，２０１３，３１（１）：６０—６４．　［１０］　怀丽波，崔某一，赵在慧．基于改进的蚁群算法的教室管理的优化问题［Ｊ］．延边大学学报：自然科学版，２０１４，４０（４）：３３５—３３９．　［１１］春花，特１３格勒，任哲明．关于蚁群算法参数的设定［Ｊ］．内蒙古民族大学学报：自然科学版，２０１１，２６（４）：４０２—４０４．　［１２］’孙凯，吴红星，王浩，等．蚁群与粒子群　昆合算法求解ＴＳＰ问题［Ｊ］．计算机工程与应用，２０１２（３４）：６０—６３．　［１３］卢欣，李衍达．ＴＳＰ问题分层求解算法的复杂度研究［Ｊ］．自动化学报，１９９９（２）：１３９—１４２．　［１４］丁建立，陈增强，袁著祉．基于动态聚类邻域分区的并行蚁群优化算法［Ｊ］．系统工程理论与实践，２００３（９）：１０５—１１０．　［１５］　侯文静，马永杰，张燕，等．求解ＴＳＰ的改进蚁群算法［Ｊ］．计算机应用研究，２０１０（６）：２０８７—２０８９．　［１６］任志刚，冯祖仁，柯良军，等．基于聚类分析的增强型蚁群算法［Ｊ］．控制与决策，２０１０（８）：１２０１—１２０６．　责任编辑：高山