维普资讯 http://www.cqvip.com Ｖｏ１．４０ ２ ０ ０ ２年１０月 吉林大学学报（理学版） ＪＯＵＲＮＡＬ ＯＦ ＪＩＬＩＮ ＵＮＩＶＥＲＳＩＴＹ（ＳＣＩＥＮＣＥ ＥＤＩＴＩＯＮ） Ｎｏ．４ ３６９～３７３ 基于蚂蚁算法的混合方法求解旅行商问题 黄 岚，王康平，周春光，原 媛，庞 巍 （吉林大学计算机科学与技术学院．长春１３００１２） 提要：通过介绍蚂蚁觅食过程中最短路径的搜索策略，给出蚂蚁算法在旅行商问题中的应 用，并加入３－ｏｐｔ方法和去交叉策略对问题求解进行局部优化．实验结果证明了其有效性． 关键词：蚂蚁算法；旅行商问题；组合优化 中图分类号：ＴＰ３１ 文献标识码：Ａ 文章编号：１６７１—５４８９（２００２）０４—０３６９—０５ 蚂蚁算法是模拟自然界蚂蚁觅食过程中的一种分布式、启发式搜索算法，最早是由Ｃｏｌｏｒｎｉ等人Ⅲ 提出的，用于求解复杂的组合优化问题，如旅行商问题（Ｔｒａｖｅｌｉｎｇ Ｓａｌｅｓｍａｎ Ｐｒｏｂｌｅｍ，ＴＳＰ）、加工调度 问题（Ｊｏｂ Ｓｈｏｐ Ｓｃｈｅｄｕｌｉｎｇ Ｐｒｏｂｌｅｍ，ＪＳＳＰ）、图着色问题（Ｇｒａｐｈ Ｃｏｌｏｕｒｉｎｇ Ｐｒｏｂｌｅｍ，ＧＣＰ）等． ＴＳＰ是典型的组合优化问题，是ＮＰ完全的．目前，ＴＳＰ问题得到较为深入的研究，其求解算法 包括最近邻域搜索、模拟退火、神经网络方法和遗传算法等［２］，而应用蚂蚁算法求解ＴＳＰ是近年来研 究的新方向［３“］，因为其并行性与分布性，特别适用于大规模启发式搜索，实验结果证明了其可行性和 有效性． １ 蚂蚁觅食过程中最短路径的搜索策略 自然界中蚂蚁在觅食过程中沿途散播一种化学物质，称为信息素（ｐｈｅｒｏｍｏｎｅ），信息素中记录了 食物源的远近与食物量的多少，而其它蚂蚁通过触角能够检测识别到这种信息素，并跟踪，从而找到 食物源．当大量蚂蚁不断地从蚁穴通往食物源，并在识别原有信息素的同时沿途不断地散播新的信息 素时，使得越短路线上的信息素浓度越来越高，从而最终找到一条最短的路线，此后所有的蚂蚁都将 沿这条路线到达食物源． 如图１（ａ）所示，假设从蚁穴到食物源有两条等长路线ＮＡＦ和ＮＢＦ（ＮＡＦ＝ＮＢＦ）．开始两条路 线上都没有信息素，每个蚂蚁是随机选择其中一条路线，并沿途散播信息素的；随着时间的推移，各 路线会挥发掉部分信息素，同时也不断地增加新蚂蚁带来的信息素，这是一个正反馈的过程；后来的 蚂蚁再选择路线时，浓度较高的路线被选择的概率较大；一段时间后，越来越多的蚂蚁会选择同一条 路线，而另一条路线上的蚂蚁数越来越少，且其上的信息素逐渐挥发殆尽． 如图１（ｂ）所示，对两条不等长的路线ＮＡＦ和ＮＢＦ（ＮＡＦ＞ＮＢＦ），如何找到较短路径．开始时， 两条路线上都没有信息素，每个蚂蚁随机选择其中一条路线，即一些走ＮＡＦ路线，另一些走ＮＢＦ路 线，并沿途散播信息素，两条路线上的蚂蚁数大致相等；假设蚂蚁的行走速度相同，则选择走ＮＢＦ路 线（较短路线）的蚂蚁比选择走ＮＡＦ路线（较长路线）的蚂蚁先到达食物源Ｆ；当走ＮＢＦ路线的蚂蚁返 回到蚁穴时，走ＮＡＦ路线的蚂蚁仍在途中Ｃ点处，即２ＮＢＦ＝ＮＡＦ＋ＦＡＣ，可以看出，线段ＮＣ上的 信息素要少于别处；下次蚂蚁再选择路线时，会以较高概率走较短路线，这使得较长路线上的信息素 浓度越来越低，较短路线上的信息素浓度越来越高；一段时间后，所有的蚂蚁都将选择较短的路线． 收稿日期：２００２．０４．１９． 作者简介：黄岚（１９７４￣），女，博士研究生．讲师，从事智能算法与应用的研究，Ｅ－ｍａｉｌ：ｈｕａｎｇｌａｎ＠￣ｐｕｂｌｉｃ．ＣＣ．ｊ１．ｃｎ．联系人：周 春光（１９４７￣），男，教授，博士生导师，从事人工神经网络、模糊系统和进化计算的研究，Ｅ－ｍａｉｌ：ｃｇｚｈｏｕ＠＿，ｍａｉｌ．ｊｌｕ．ｅｄｕ．ｃｎ． 基金项目；国家自然科学基金（批准号：６０１７５０２４）和教育部“符号计算与知识工程”重点实验室资助基金． 维普资讯 http://www.cqvip.com ３７０ 吉林大学学报（理学版） ／５ （ａ） （ｂ） Ｆｉｇ．１ Ｃｈｏｉｃｅ ｂｅｔｗｅｅｎ ｔｈｅ ｅｑｕａｌ ｐａｔｈｓ（ａ）ａｎｄ ｔｈｅ ｕｎｅｑｕａｌ ｐａｔｈｓ（ｂ） 人工蚂蚁算法就是从蚂蚁觅食时寻找最短路径的现象中得到启示而设计的，由计算机编程实现的 分布式并行搜索策略．蚂蚁通过别的蚂蚁留下来的信息素的强弱来作为自己选择路径的参数。信息素 越强的路径被选择的可能性越大．信息素的更新策略是越好的路径上获得的信息素越多，通过这个正 № ～ Ｓ 反馈来寻找更好的路径，这是蚂蚁算法工作的基本原理．单个蚂蚁的规则相当简单，但是通过蚂蚁群 体的协同工作，产生对复杂环境的认知，以实现对解空间进行有效的搜索． ２蚂蚁算法在旅行商问题中的应用 旅行商问题描述如下：给定 个城市及各城市间的距离，求一条经过各城市一次且仅一次的最短 路线．其图论描述为：给定图Ｇ：（ ，Ａ）。其中 为顶点集，Ａ为各顶点相互连接组成的弧集，已知各 顶点间连接距离，要求确定一条长度最短的Ｈａｍｉｌｔｏｎ回路，即遍历所有顶点一次且仅一次的最短回 路．设ｄ ，为城市ｉ与 间的距离，即弧（ ，．『）的长度．引入决策变量： ｆ１， 若旅行商访问城市ｉ后访问城市 ； …、 １０，否则， ・¨ 则ＴＳＰ的目标函数为 ｍｉｎ Ｚ：∑ｘｏｄ ． （２．２） ｔ ；１ ＴＳＰ问题描述非常简单，但最优化求解很困难，若用穷举法搜索，则要考虑所有可能情况。并两 两对比，找出最优．算法复杂性呈指数增长，即所谓的组合爆炸．所以，寻求和研究ＴＳＰ的有效启发 式算法，是问题的关键所在． 求解ＴＳＰ问题的蚂蚁算法中，每只蚂蚁是一个的用于构造路线的过程，若干蚂蚁过程之间通 过自适应的信息素值来交换信息，合作求解，并不断优化．这里的信息素值分布式存储在图中．与各 弧相关联．蚂蚁算法求解ＴＳＰ问题的过程如下： （１）初始化．初始时，设定最大代数ｍａｘＧＥＮ，蚂蚁数 ，ＧＥＮ＝０． （２）起始点．将 只蚂蚁分别随机地置于各顶点处，即每个蚂蚁过程随机地给予一个起始点． （３）构造解．每个蚂蚁按照状态变化规则一步一步地构造一个解，即生成一条线路． 蚂蚁过程相当于一个智能体（ａｇｅｎｔ），其任务是访问所有的城市后回到起点，生成一个回路．设蚂 蚁ｋ当前所在的顶点为ｒ，其待访问的点用集合。， （ｒ）表示，那么，蚂蚁ｋ由点ｒ向点 移动要遵循 ｆａｒｇ ｍａｘ（［－ｒ（ｒ，ｕ）３．［７（ｒ，“）］ ），ｑ≤ｑｏ（利用）； ：ｆ ’ （２．３） Ｓ， 否则（开发） 的状态变化规则而不断迁移，按不同概率来选择下一点．（２．３）式中ｒ（ｒ，“）相当于真实蚂蚁沿途散播 的信息素，是一个正实数，与图Ｇ中弧（ｒ，“）关联，其值在运行时不断改变，用于表示蚂蚁从点ｒ向点 “移动的动力； （ｒ，“）用于评价蚂蚁从点ｒ向点“移动的启发函数，其值通常用距离的倒数来求得，即 （ｒ，“）：１／ｄ ；参数 ＞０描述启发函数的重要性；参数ｑｏ（０≤ｇ。≤１）决定利用和开发的相对重要性， 利用是指走最好的路，开发是指按浓度高概率高的原则选路Ｓ；ｑ是在［０，１］上任取的随机数，当ｇ≤ ｏ 维普资讯 http://www.cqvip.com Ｎｏ．４ 黄岚等：基于蚂蚁算法的混合方法求解旅行商问题 时，按（２．３）式选最好的路，否则按下式的概率进行选路： ：』｛煮 。舞，，［ｒ（ｒ ）］ （ｒ ）］ 臼 ｒ）． （２．４ ） 否 （４）局部更新信息素值．应用局部信息素更新规则来改变信息素值． 在构造解时，蚂蚁七对其走过的每条弧用 ｒ（ｒ， ）一（１一ｐ）ｒ（ｒ， ）＋ｐｒｏ （２．５） 局部信息素更新规则来改变弧上关联的信息素值，其中Ｏ＜ｐ＜ｌ是信息素挥发参数；ｒｏ＝（ｎＬ ）～，Ｌ 是最近邻域启发算法产生的路线长度；一为城市数． （５）若所有的ｍ个蚂蚁都构造完解，则转（６）；否则转（３）． （６）全局更新信息素值．应用全局信息素更新规则来改变信息素值． 当所有，一个蚂蚁生成了棚个解，其中有一条最短路径是本代最优解，将属于这条路线上的所有弧 相关联的信息素值按下式更新： ｒ（ｒ， ）＝（１一口）ｒＯ ， ）＋ａＡｒ（ｒ，ｓ）， （２．６） 其中Ｏ＜ａ＜ｌ是挥发参数； ／ｘ．， 、 ｒ（，．，ｓ）＝ Ｉ ‘ 暑６ ，若弧（，．， ）在全局最优解中； 【０， 否则， Ｌ一是目前得到的全局最优解的路线长度． 全局信息素更新的目的是在最短路线上注入额外的信息素，即只有属于最短路线的弧上的信息素 才能得到加强，这是一个正反馈的过程，也是一个强化学习的过程．在图中各弧上，伴随着信息素的 挥发，全局最短路线上各弧的信息素值得到增加． （７）终止．若终止条件满足，则结束；否则ＧＥＮ＝ＧＥＮ＋１，转（２）进行下一代进化．终止条件可 指定进化的代数，也可限定运行时间，或设定最短路长的下限． ３用３．ｏｐｔ方法局部优化 对于我们用蚂蚁算法构造的ＴＳＰ解，若用于小规模问题，一般能快速找到最优解，但由于ＴＳＰ是 ＮＰ完全问题，其规模的扩展，即城市数的增加，使问题求解变得复杂化．蚂蚁算法尽管能够分布式并 行搜索，但在限定的时间或代数内找到最优解仍是困难的，可能找到的只是可行的近优解，这一点与 遗传算法相似．因此，我们在蚂蚁算法中混入局部优化算法，对每代构造的解进行改进，从而进一步 缩短解路线的长度，以加快蚂蚁算法的收敛速度． 用于启发式局部优化的方法很多，主要包括２－ｏｐｔ，３－ｏｐｔ，顶点重定位（ｒｅｌｏｃａｔｅ），交换（ｅｘｃｈａｎｇｅ） 和交叉（ｃｒｏｓｓ）等，其中最实用有效的是２－ｏｐｔ和３－ｏｐｔ算法． 将３－ｏｐｔ方法混入蚂蚁算法求解过程中，对每代最优解进行改进，这样，在上述求解过程（５）与（６） 之间加入（５ ）： （５ ）改进解．对本代最优解使用３－ｏｐｔ算法进行改进．当所有 个蚂蚁生成了ｍ个解，其中有一 条最短路线是本代最优解 ．设 为路线 经过顶点的有序排列， ｒ２，，．。是从 中随机地选择的 ３个顶点，Ⅳ为没有任何改进的最大循环次数，则３－ｏｐｔ算法的步骤如下： ． １）初始化．循环次数变量ｆ一１，当前最优解Ｓ。＝ ，其长度为Ｌ（Ｓ。）． ２）选择点．在 中随机选择３个顶点，． ，，．ｚ，ｒ３． ３）评价解．将这３个顶点排序得到 ’的６个相邻解 ， ，…， ，比较这６个相邻解的路线长度 Ｌ（Ｓ１），Ｌ（Ｓ２），…，Ｌ（Ｓ６），选Ｌ －￣ｍｉ－ｎ｛Ｌ（Ｓ１），Ｌ（Ｓ２），…，Ｌ（Ｓ６）），其对应的解为 ． ４）改进解．若Ｌ ＜Ｌ（ 。），则Ｓ‘＝ ，ｔ－－１，转２）；否则，ｆ—ｆ＋１，转５）． 维普资讯 http://www.cqvip.com 吉林大学学报（理学版） ５）终止．若 （ ）在最后Ⅳ个循环中没有减少，则结束， ＝ 。；否则转２）． ４去交叉策略改进解的可视效果 求解ＴＳＰ问题的方法很多，事实上，无论通过何种方法得到其最优解或可行的近优解，都希望它 不仅达到标准目标（如最短路长下限，时间或代数的限定），而且能够满足某些非标准的目标（如视觉 可行性）．这样，尽管已得到的解已经满足需求，仍要对之进行去交叉操作，以增强解的可视效果．经 进一步研究发现，对交叉的消除可以再次缩短路线长度． 去交叉策略描述如下：首先，遍历解回路，找到一交叉点（），如图２（ａ）所示，将相交两弧的端点按 解路线访问先后次序分别设为 ，Ｂ，ｃ，Ｄ．去交叉时，如图２（ｂ）所示，将解路线访问次序变为 ，ｃ，Ｂ， Ｄ，其中Ｂ和ｃ之间所有结点要颠倒次序． 上） 上） （ａ） （ｂ） Ｆｉｇ．２ Ｃｒｏｓｓ・ｒｅｍｏｖｉｎｇ ｓｔｒａｔｅｇｙ （ａ）Ｂｅｆｏｒｅ ＣｒＯ．￣・ｒｅｍｏｖｉｎｇ（ｂ）ａｆｔｅｒ ｅｒｏ，￣ｓ—ｒｅｍｏｖｉｎｇ． 下面证明去交叉操作能够缩短路线长度，即Ａ—ｃ—Ｂ—Ｄ—Ａ长度小于Ａ—Ｂ．ｃ—Ｄ—Ａ长度． 证明： Ｌ（Ａ—Ｂ—Ｃ—Ｄ—Ａ）＝ＡＢ＋ＢＣ＋ＣＤ＋ＤＡ一 （ＡＯ＋０Ｂ）＋ＢＣ＋（ＣＯ＋０Ｄ）＋ＤＡ＝ （ＡＯ＋Ｃ０）＋ＢＣ＋（ＯＢ＋（）Ｄ）＋ＤＡ， （４．１） Ｌ（ —Ｃ—Ｂ—Ｄ—Ａ）＝ＡＣ＋∞＋ＢＤ＋Ｄ ， （４．２） 据ＴＳＰ对称性，有ＢＣ＝ＣＢ；又据三角形不等式两边之和大于第三边，有ＡＯ＋ＣＯ＞ＡＣ， （）Ｂ＋（）Ｄ＞ＢＤ，比较（４．１）式和（４．２）式，得 （Ａ—Ｂ—Ｃ—Ｄ—Ａ）＞ （Ａ…Ｃ Ｂ Ｄ—Ａ）． ５ 实验结果 使用Ｐ３—１Ｇ的ＰＣ机进行测试，内存为２５６ Ｍ，操作系统为Ｗｉｎ２０００，开发软件为Ｖｃ＋＋６．０．程 序中用到参数设置为 ＝１０， ＝２，ａ＝ｐ＝０．１，ｑ０＝Ｏ．９． 测试数据来源于ＴｓＰ的标准问题库．表１分别列出用蚂蚁算法、蚂蚁算法与３一ｏｐｔ混合算法、带 去交叉策略的混合算法所求得的最短路线长度及相对偏差率．对于每个测试问题，每种方法测试５次， 结果取平均值． Ｔａｂｌｅ １ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ＢＡＡ，ＨＡＡ一３・Ｏｐｔ ａｎｄ Ｈａａ・３・Ｏｐｉ－ＣＲ ｏｎ ＴＳＰ ｐｒｏｂｌｅｍｓ 由表１可见，加入３－ｏｐｔ方法改进了蚂蚁算法的局部搜索能力，因而提高了算法的求解能力，同等 的运算时间内可得到更短的路线长度，如对Ｂｉｅｒ１２７（１２７个城市）问题，基本蚂蚁算法得到平均路线长 度为１２３ ９５８．４，而加入３－ｏｐｔ后的长度为１２２ ５６３．４．另外，同等的运算时间内交叉的消除对提高解的 维普资讯 http://www.cqvip.com Ｎｏ．４ 黄岚等：基于蚂蚁算法的混合方法求解旅行商问题 ３７３ 质量没有明显的效果，主要原因是交叉消除策略不能为蚂蚁算法提供好的指导信息，而且计算时间的 消耗可能会产生稍差的结果．总之，基于蚂蚁算法的混合方法获得的解接近目前已知最优解，与之相 对偏差率的平均值低于５％，计算速度较快，生成解时间可以接受，生成路线图的可视效果较好，说明 算法是有效的．图３和图４是Ｂｅｒｌｉｎ５２（５２个城市）问题的初始解和混合算法运行６０ ｓ时得到的解． Ｆｉｇ．３ Ｉｎｉｔｉａｌ ｓｏｌ ｕｔｉｏｎ（ｆ＝Ｏ） Ｆｉｇ．４ ＨＡＡ－３－ｏｐｔ－ＣＲ ｓｏｌ ｕｔｉｏｎ（ｆ一６０ ｓ） 实验证明，我们研究并提出的混合算法是有效的，同时为继续深入研究更复杂的带约束的组合优 化问题一车辆路线问题（Ｖｅｈｉｃｌｅ Ｒｏｕｔｉｎｇ Ｐｒｏｂｌｅｍ，ＶＲＰｆｌ 创造了条件． 参考文献 ［１］Ｃｏｌｏｒｎｉ Ａ・Ｄｏｒｉｇｏ Ｍ，Ｍａｎｉｅｚｚｏ Ｖ．Ｄｉｓｔｒｉｂｕｔｅｄ Ｏｐｔｉｍｉｚａｔｉｏｎ ｂｙ Ａｎｔ Ｃｏｌｏｎｉｅｓ［Ｃ］．Ｉｎ：Ｖａｒｅｌａ Ｆ，Ｂｏｕｒｇｉｎｅ Ｐ．Ｅｄｓ． Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ］ｓｔ Ｅｕｒｏｐｅａｎ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｒｔｉｆｉｃｉａｌ Ｌｉｆｅ（ＥＣＡＬ＇９１）．Ｐａｒｉｓ：Ｅｌｓｅｖｉｅｒ Ｐｕｂｌｉｓｈｉｎｇ，１９９１．１３４～ ｌ４２． ［２］周春光．梁艳春．计算智能［Ｍ］．长春：吉林大学出版社．２００１．１Ｏ２～１０４，２７７￣２８０． ［３］Ｄｏｒｉｇｏ Ｍ・Ｇａｍｂａｒｄｅｌｌａ Ｌ Ｍ．Ａｎｔ Ｃｏｌｏｎｙ Ｓｙｓｔｅｍ：Ａ Ｃｏｏｐｅｒａｔｉｖｅ Ｌｅａｒｎｉｎｇ Ａｐｐｒｏａｃｈ ｔｏ ｔｈｅ Ｔｒａｖｅｌｉｎｇ Ｓａｌｅｓｍａｎ Ｐｒｏｂｌｅｍ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｎ ｏＥｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ，１ ９９７．１（１）：５３￣６６． ［４］Ｇｕｔｊａｈｒ Ｗ Ｊ．Ａ Ｇｒａｐｈ—ｂａｓｅｄ Ａｎｔ Ｓｙｓｔｅｍ ａｎｄ Ｉｔｓ Ｃｏｎｖｅｒｇｅｎｃｅ［Ｊ］．Ｆｕｔｕｒｅ Ｇｅｎｅｒａｔｉｎ Ｃｏｍｐｕｔｏｉｎｇ Ｓｙｓｔｅｍｓ．２０００． １６：８７３～８８８． ［５］Ｂｕｌｌｎｈｅｉｍｅｒ Ｂ，Ｈａｒｔｌ Ｒ Ｆ。Ｓｔｒａｕｓｓ Ｃｈ．Ａｎ Ｉｍｐｒｏｖｅｄ Ａｎｔ Ｓｙｓｔｅｍ Ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ Ｖｅｈｉｃｌｅ Ｒｏｕｔｉｎｇ Ｐｒｏｂｌｅｍ［Ｊ］． Ａｎｎａｌｓ ｏｆ Ｏｐｅｒａｔｉｏｎｓ Ｒｅｓｅａｒｃｈ，１９９９．８９：３１９￣３２８． Ｈｙｂｒｉｄ Ａｐｐｒｏａｃｈ Ｂａｓｅｄ ｏｎ Ａｎｔ Ａｌ ｇｏｒｉｔｈｍ ｆｏｒ Ｓｏｌ ｖｉｎｇ Ｔｒａｖｅｌ ｉｎｇ Ｓａｌ ｅｓｍａｎ Ｐｒｏｂｌ ｅｍ ＨＵＡＮＧ Ｌａｎ，ＷＡＮＧ Ｋａｎｇ—ｐｉｎｇ，ＺＨＯＵ Ｃｈｕｎ—ｇｕａｎｇ，ＹＵＡＮ Ｙｕａｎ，ＰＡＮＧ Ｗｅｉ （Ｃｏｌｌｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ．Ｊｉｌｉｎ Ｕｎｉｖｅｒｓｉｔｙ．Ｃｈａｎｇｃｈｕｎ １３００１２．Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｎ ｔｈｅ ｐｒｅｓｅｎｔ ｐａｐｅｒ ｔｈｅ ａｕｔｈｏｒｓ ｉｎｔｒｏｄｕｃｅ ａｎ ａｎｔ ａｌｇｏｒｉｔｈｍ，ａ ｄｉｓｔｒｉｂｕｔｅｄ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ ｓｏｌｕｔｉｏｎ ｏｆ ｃｏｍｂｉｎａｔｏｒｉａｌ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍｓ ｗｈｉｃｈ ｈａｓ ｂｅｅｎ ｉｎｓｐｉｒｅｄ ｂｙ ｔｈｅ ｏｂｓｅｒｖａｔｉｏｎ ｏｆ ｒｅａｌ ｃｏｌｏｎｉｅｓ ｏｆ ａｎｔｓ．Ｔｈｅｎ ｔｈｅ ａｕｔｈｏｒｓ ａｐｐｌｙ ａ ｈｙｂｒｉｄ ａｐｐｒｏａｃｈ ｏｆ ａｎｔ ａｌｇｏｒｉｔｈｍ ｗｉｔｈ ３一ｏｐｔ ａｎｄ ｃｒｏｓｓ—ｒｅｍｏｖｉｎｇ ｔｏ ｔｈｅ ｔｒａｖｅｌｉｎｇ ｓａｌｅｓｍａｎ ｐｒｏｂｌｅｍ（ＴＳＰ）．Ｔｈｅ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｉｔ ｉｓ ａｂｌｅ ｔｏ ｆｉｎｄ ｇｏｏｄ ｓｏｌｕｔｉｏｎｓ ｑｕｉｃｋｌｙ． Ｋｅｙｗｏｒｄｓ：ａｎｔ ａｌｇｏｒｉｔｈｍ；ｔｒａｖｅｌｉｎｇ ｓａｌｅｓｍａｎ ｐｒｏｂｌｅｍ；ｃｏｍｂｉｎａｔｏｒｉａｌ ｏｐｔｉｍｉｚａｔｉｏｎ
