蚁群系统文献翻译.doc

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