1、 1 中文 1.2 万字 文献出处： Dorigo M, Gambardella L M. Ant colony system: a cooperative learning approach to the traveling salesman problemJ. IEEE Trans on Ec, 1997, 1(1):53-66. 毕 业 论 文（设 计） 英 文 翻 译 届 网络工程 专业 班级 翻译题目 姓 名 学号 指导教师 职称 讲师 年 月 日 2 蚁群系统 :一个合作学习模式解决旅行 商问题的方法 摘要 本文介绍了蚁群系统（ ACS），应用于解决旅行商问题（ TSP）的分布式算
2、法。ACS 就是一些合作代理所谓的蚂蚁合作找到 TSP 问题的良好解决方案。蚂蚁通过播撒一种信息素来间接合作，在生成解决方案的同时把信息素存放在 TSP 图形的边缘。我们研究 ACS 通过运行试验了解其操作。结果表明， ACS 优于其他自然灵感的算法，如模拟退火和进化的自然启发算法计算。我们得出结论与ACS-3-opt 比较 ，在本地搜索过程中，优化的 ACS 通过一些算法来表现最优的的 TSP 和 ATSP。 索引术语 适应行为、 旅行商问题的蚁群、紧急行为。 一、导论 蚂蚁算法是基于自然的比喻蚁群。真正的蚂蚁能够找到从食物源到自己的窝3的最短路径， 22不利用视觉线索 24而通过感知信息素
3、。在移动的时候，蚂蚁在地上洒下信息素，并趋向于 朝其他蚂蚁播撒的信息素方向移动。在图 .1我们展示了蚂蚁利用信息素找到两点之间的最短路径。 考虑图（ a）：蚂蚁到达一个抉择点，他们要决定向左还是向右。因为没有线索表明哪一个是最佳选择。他们随机选择。可以预期，一般情况下，是一半蚂蚁左转一半蚂蚁右转。两蚂蚁从左至右（名称开头为 L）和从右至左移动（名字开头为 R）。图（ b）和（ c）显示在紧随其后的瞬间发生了什么，假设所有的蚂蚁以大约相同的速度移动。虚线代表蚂蚁沉积在地面上的信息素。由于较低的路径比上面一个短，更多的蚂蚁将平均访问，因此信息素累积更快。经过短暂的过渡时 期，两个路径信息素量的差异
4、就足够大，从而影响进入系统的新蚂蚁的决定。 图 (d)显示，从现在开始，新进入的蚂蚁在概率上更倾向于选择较短的路径，因为在决定点时，他们感知到了短路径上的有较多的信息素。在正反馈的影响下，这又反过来增加了更多的蚂蚁去选择较短的路径。很快所有的蚂蚁将会使用较短的路径。真实蚂蚁的上述行为，激发了蚂蚁系统，一个算法，其中一组人工蚂蚁合作解决一个问题，通过沉积在图的边缘上的信息素来交换信息。蚂蚁系统已应用于组合优化问题，旅行商问题（ TSP） 7， 8， 10， 12和 二次分配问题 32， 42。 蚁群系统（ ACS），这篇文章提出的算法，是建立在以前的蚂蚁系统之上，应用于对称和非对称 TSP 问题
5、，来提高效率。其主要思想是，有一组代理商，所谓的蚂蚁，通过信息素的间接合作和全球通信，来并行的寻找 TSP 良好的解决方案。简单的说，每个蚂蚁构建解决 TSP 问题用一个迭代的方式：它增加了新的城市，从过去的经验和贪婪启发式获得通过利用双方信息的部分解决方案。通过记忆存放在 TSP 边缘上的信息素，而启发式信息仅仅决定于边缘的长度。被引入蚁群算法的新理念将在论文的其余部分讨论，是 协同使用相对简单了许多代理人之间的 3 合作它通过分布式内存实现信息素沉积在图的边缘。 本文的组织如下：第二节通过描述蚁群系统以及其起源来引出 ACS；第三节介绍 ACS；第四节致力于研究 ACS 的一些特点；我们研
6、究在运行时信息素是如何变化的，估计要使用蚂蚁的最佳数量，观察信息素在协同调解中的作用和评估信息素和贪婪式算法在 ACS 中的作用。第五节提供了一套标准测试的问题，比较知名的如通用算法，进化计算和模拟退火 ACS 结果的概述。在第六节中，我们添加到 ACS 的局部优化，获得一个新的算法，称为 ACS-3-OPT。该算 法相比，毫不逊色于第一次进化优化 5国际大赛的非对称旅行商问题（ ATSP）（见图 2），尽管它产生的 TSP 问题上的表现略差。第七节专门讨论了 ACS 的主要特点，并指出进一步研究的方向。如图 .1 蚂蚁如何找到最短路径 ： 图 .1 蚂蚁如何找到最短路径 （ a）蚂蚁到达决定点 （ b）蚂蚁随即的选择较高和较低的路径 （ c）因
