英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料
通过使用蚁群优化算法用交互式仿真分析软件求解旅行商问题
- 介绍
在离散优化或组合优化和要求用最小的总成本往返给定的城市（节点）一次中，旅行商问题是一个非常著名并且研究广泛的问题。成本消耗可以是距离，时间，金钱。能量等。旅行商问题是一个非确定性多项式困难问题并且自从二十世纪五十年代以来，研究者尤其是数学家和科学家一直在不停的研究开拓有效地解决办法。因为，它是如此简单的可以描述，也如此困难的解决。图论定义这个问题对于给出完整的加权图找到有最小权重的哈密顿循环。
旅行商问题在工程应用中被广泛应用。它被应用到硬件装置和无线电装置的设计，通信，计算网络的构建等等。除此之外，像机器计划，蜂窝制造和频率分配问题一些工业问题可以用一个旅行商问题来进行表示。
一个直接的解决方法是挑选有N个城市的所有可能排列的最小总花费的路线。对于四十个城市来说排列的数字一定非常大。每个旅行用两个不同的路线来表现（对于对称旅行者问题）。因为这儿有n!种可能方法来排列数字n，搜索空间的范围是|S|=n!/(2n)=(n-1)!/2，而不是列举所有的可能性。很多近似算法基于基因算法，模拟退火处理，禁止搜索，蚁群优化和神经网络被开发出来，同时在一个合理的时间里产生良好的解决办法。一些基于分枝割法的精准算法也已经为旅行商问题的解决做好了准备。
蚁群优化是一种基于种群的算法，这种算法已经成功的被运用到了多种非确定性多项式困难问题的组合优化问题中，首先是旅行商问题。作为一个通常的优化工具，蚁群优化算法已经被应用问题到工程问题的各个领域中。一些已发表的关于使用蚁群优化算法解决工程的研究可以在文献[13-17]中找到。蚁群优化算法用虚拟蚂蚁作为代理，通过间接的方式进行通讯并且用随机传播规则来使算法和代理行为变得有难度的来理解。蚁群优化算法有很多对性能有很大影响的关键参数，并且在这之前它：的值是很难被研究者所估计出来的。
很多仿真和分析工具已经被发展用于遗传算法[18-20]，神经网络[21,22]，和其他元启发式[23-25]或人工智能方法[26,27]的文献中。但是，这儿没有一个具有动画和追踪能力，特别是为研究人员在蚁群领域的全面的模拟和分析软件。
在本文中，使用蚁群优化算法的交互式仿真模拟分析软件被发展为来解决旅行商问题。这个通过虚拟蚂蚁和二维交互式图形的软件来被用于生产旅行商问题的近似最优解，并且这个软件支持分析和算法可视化的教育培训。第二节描述了蚁群优化和它的变种。第三节提供了关于TSPAntSim模拟工具的详细信息，第四节通过TSPAntSim图解了获得的实验结果，第五节包括本文。
2蚁群优化
Dorigo等人最早在[5,28,6]文献中提出了基于蚂蚁觅食行为的蚁群优化算法并且被Dorigo和Di Caro在[29]文献中被形式化为一种新的元启发式算法。元启发式算法是一种可应用于不同优化问题的通用的算法框架，但相对较少的修订[30]。在近些年，几种蚁群优化在理论[7,31-37]和实际工业和工程应用，比如网络（英国电信公司的研究），运输，制造（AntOtima软件）被实现。
在蚁群优化中，许多人工蚂蚁创建解决办法和考虑优化问题为手头并且通过一种通信方案交换关于这些解决方案质量的信息，这个方案使人想起真实的蚂蚁所采用的方案[30]。蚁群优化算法的骨架如下所示：
过程蚁群算法元启发式
设置参数，初始化信息素轨迹
while (不满足终止条件) do
施工方案
ApplyLocalSearch % 可选
更新邮件
结束
结束蚁群算法元启发式
算法表明，在问题搜索空间上对参数和信息素（真实蚂蚁为局部和间接通信而储存的物质，Grass[38]称之为stigmergy）进行初始化之后，每个蚂蚁可以通过概率选择的方式来构建它的解决办法，并且根据它们的解决办法在图上来更新信息素的水平。除此之外，蚂蚁可以应用局部搜索的方法来提高每个解的性能。这些三步算法的详细描述如下：
建设解决方案：对于给出的问题实例，每个蚂蚁都开启一个状态，然后一个接一个的来遍历这些状态，每个蚂蚁计算一个概率分布函数来选择这些可能中的一个状态。这个随机选择被叫做随机比例转换规则[30]（也被叫做伪随机比例规则）并且依靠两个值的组合：
·移动的吸引力，这是一个表示该移动的先验期望的一个启发式函数（取决于问题）。
·人工信息素的追踪水平表现了移动的期望值的后验，因为它表示在当前状态下选择下一可能状态的学习期望值。
正因为这样，每一个蚂蚁都逐渐的为实例的解决来构建一个解决方案。
应用本地搜索：在更新追踪水平之前，当地搜索方法例如2-opt.3-opt[39]和Lin-Kernighan[40]可以应用到当前迭代的每个解决方法构建中。虽然这根过程是可选择的并且只针对特定的问题，但是它提高了蚂蚁获得的解决办法，并且已经被最新的蚁群优化算法所使用。
更新路径：在构造和计算解决方法后，在好的解决办法和坏的解决办法的相关路径中，信心素水平分别增加（被叫做信息素沉积）和减少（被叫做信息素蒸发）。
应用在旅行商问题中的蚁群优化算法有：蚂蚁系统（AS），精英蚂蚁系统（AS）[6],蚁群系统（ACS）[41]，基于排列的蚂蚁系统（RBAS）[42]，最好最差蚂蚁系统（MMAS）[44]。蚁群优化算法因为它们不同的信息素的更新和随机转换规则的实现从而实现分离。所以，信息素的更新和随机比例转换规则是蚁群优化的关键之机制之一。
2.1随机比例转换规则（RPT 规则）
根据第一个蚁群优化算法，对旅行商问题的蚂蚁系统，在城市i之后城市j被挑选来被被访问的概率可以写成如下公式：
在城市i和城市j之间的追踪强度tau;ij在哪里，eta;ij是从城市i（eta;i=1/dij）城市j的可见距离，Omega;是未访问的城市，dij是城市i到城市j的距离追踪的强度可以解释为自适应记忆并且被变化的参数alpha;所调节。后一个标准可以被解释作为期望的衡量并且也被叫做可见性。它代表着上面的启发式功能并且被常参beta;调节。alpha;和beta;是很重要的常数自适应参数，它们明显的改变了算法的性能。“Ifalpha;=0最近的城市最有可能被挑选”：这个符合经典的随机贪婪算法。如果，在另一方面，beta;=0仅仅信息素放大处于有效：这个方法将会导致快速选择不是最好的旅游路线”[30]。所以是有必要在旅游路线长度和旅游路线强度间进行权衡的，但是如果没有实验的话是很难建立参数的有效值的。通过从这些经验观测中收集的先验知识来确定参数的最佳值。所有的算法除了蚁群算法都是使用相同的RPT规则。它们不同于其它得由于信息素更新策略的不同实现。RPT规则被明确的来修订以便允许在ACS中探索。如下所示：
q是一个随机数字，q0是一个参数（0lt;=q0lt;=1)并且J根据之前在Eq.(1).给出的概率分布函数的随机变量选择。在每一步中，自在城市i中的一个蚂蚁必须选择城市j去访问，它为q生成一个均匀分布的随机值。如果qlt;=q0，就选择（选择）最好边，否则按照Eq(1)（偏差探测）选择一个边缘。
2.2信息素更新
在群体中信息素更新通过间接多重交流来提供正反馈和负反馈。正反馈通过信息素在良好路径中的加固来实现，但是增加的信息素水平没有蒸发导致算法停止停滞状态。为了避免这种情况，负反馈机制在所有甚至有时在坏的路径上信息素蒸发被引用。在每次迭代结束后，每个蚂蚁k独立沉积1/Lk(Lk是它旅行的长度)的信息素并且根据tau;ij（t 1）=(1-rho;)tau;ij(t)公式在所有路径上蒸发掉一些信息素。其中rho;（0lt;=rho;lt;=1）是衰减系数。在所有蚂蚁走过的路径中信息素下降并且导致比当前旅行商问题更差的解决办法，这鼓励着研究者制作新的变体来对AS的性能进行改进。
精英策略是在每个循环中，位于最好的路径的边缘上的轨迹都比精英算法的AS算法增强的多[36]的AS算法的第一个改进版本。在每次循环后，额外的e=L 信息素被添加到最近最好的旅游线路的每一条弧线当中，e表示精英蚂蚁的数量，L表示从小径的起点。在另一种改进的RBAS算法中，蚂蚁的信息素沉积的加权是根据其等级进行的。迄今为止最好的旅行团的重量是w，通常设置的群体大小为平方米。RBAS只允许信息素被（w-1）排名最佳的蚂蚁和到目前为止最好的蚂蚁储存。正式的，到现在为止最好的蚂蚁在其路径上的沉积量等于w=L并且其他排名的蚂蚁增加的信息素水平可以按照公式进行计算， T*r（t）是在迭代中排名为r的蚂蚁的旅行，（t）是蚂蚁排名为r的信息素。
（3）
这两种算法为算法的增强提供了良好的搜索性能，是其他蚂蚁解决附近的最好的旅游的解决办法。
ACS使用两种类型的信息素更新策略：当地的和全球的。在全局更新过程中中，每一次迭代后，通过增加信息素水平rho;=L *是信息素到目前为止最好的旅行，其中rho;是上述提及的衰减参数。本地信息素更新是在旅游建设的每一步之后执行的所有蚂蚁的公式如下：
其中0lt;phi;lt;1是局部信息素衰减系数，tau;0是
信息素的初值，特别是最近邻信息素旅行长度。
在MMAS中，信息素只在迄今为止最好的一次旅行中沉积像ACS和重新初始化信息素水平时已找到旅游路线。但是除此之外，它使用了两个新规则来避免停滞。
· 限制边缘信息素水平的范[tau;min,tau;max]。
· 初始化信息素值为tau;max。
除BWAS算法外，所有算法都使用相同的蒸发规则。但是在BWAS，最差旅行时间的信息素基于算法tau;ij(t 1)=(1-p)tau;ij(t) 其中（i,j）notin;T*-并且（i,j）notin;T*。除此之外，边缘（i-j）的信息素追踪被当做概率Pmut基因算法的突变： （5）
当i,j=1,...,n,ine;j，△tau;mut是一个随机数字，它的取值范围依赖迭代的数目和在边缘路线T*的平均信息素，并且alpha;isin;{1,1}是一个随机数字[45].
3交互式蚁群算法仿真分析软件解决旅行商问题
作为独立的Java小应用程序实现，TSPAntSim采用Java2D技术，是一种利用蚂蚁求解TSP的交互式仿真环境。TSPAntSim的网址是:http://yzgr-afik.ege.edu.tr /projects/TSPAntSim/amp;gt;所有的蚁群算法都能演示，并且支持分析不同参数值和蚂蚁行为的算法。图1为算法运行时TSPAntSim的快照。如图1所示，在右侧面板中输入仿真设置。TSP实例可以通过使用顶部面板和中间的选项卡式面板进行仿真和分析。仿真速度可以通过底部面板来进行控制，同时还包括了一个进度条。在模拟面板中当前实例中定义数字的城市以圆圈表示。所有的城市都代表了最近发现的最好的旅游线路，信息素水平来显示为城市之间的线。
3.1。TSPAntSim的能力
为了强调环境的能力，系统的特点如下所示:
- Web可访问:用户可以使用支持java的浏览器可以通过internet访问软件。不需要安装。
- 蚁群算法和局部搜索算法支持:TSPAntSim支持蚂蚁系统、精英蚂蚁系统、基于排序的蚂蚁系统、最优最劣蚂蚁系统、蚁群系统和最大最小蚂蚁系统算法，它们就可以很容易地与局部搜索算法相结合。TSPAntSim使用2-opt和2.5-opt[46]本地搜索启发式来改进旅游。在2-opt启发式算法中，每次迭代后，移除每个蚁群中的一对边，将它们的端点重新连接，这是唯一的另一种方式，从而可以实现一个关联的遍历。只要蚂蚁旅行的长度变得减少了，就可以来做到这一点。2.5 opt算法类似地进行切割和重新连接 但切边的数量是3条。它看起来像简单的3-opt移动，但是在2.5-Opt移动中，一个人将一个城市从它当前的位置移动到旅行[47]中两个相邻的当前旅游城市之间的位置。
- 轻松设置TSP实例:用户可以选择他们喜欢的TSP实例生成方法之一。可以加载TSPAntSim提供的TSPLIB实例，或者用户可以通过使用鼠标在任何一个地方添加点来定义一组城市。也可以随机位置生成一组点。是很重要的在不同类型的TSP实例上测试蚁群算法，因为这类问题具有结构上的差异，这使得对于特定的算法来说是很困难的，同时对另一个[41]很容易。
- 参数设置灵活:使用参数窗口和面板可以轻松设置在算法中的所有参数值。
- 交互式和动画仿真:可以对测试实例进行计算，可以通过鼠标交互观察算法的执行情况，在执行过程中，化算法的步骤和迭代可以被环境动画。
-
不同类型的执行:由于多线程的优势，TSPAntSim提供了四种类型的执行:nor- mal, step - by - step, with ants和zoom to ant。在正常执行过程中，所选算法运行速度较快，但算法仿真效果比较差，只有进度条显示算法的进度。它有助于解决旅行商问题实例，并尽可能快地分析参数设置和算法比较。顾名思义，分步执行在视觉上反映了每次迭代后解决方案和信息素水平的变化。在每次迭代中分析解决方案、最佳旅行和信息素水平的机会是很有用的。图2显示了在寻找100个城市的最佳之旅的逐步执行过程中，从过程图中截取的一些关键截图。蚁群如何解决这个问题可以用蚂蚁的执行来说明。如图1a所示，所有蚂蚁的踪迹和信息素水平都由虚拟蚂蚁进行匹配，所以执行速度较慢。它使得计算真实蚂蚁和虚拟蚂蚁的跟踪行为变得更加简单。在蚂蚁从一个城市迁移到另一个城市的过程中，全局信息素和局部信息素的边缘更新以及信息素水平的变化都可以被直观地观察到。仿真速度可以通过底部的滑块组件来控制。在缩放到蚂蚁的方法(如图3所示)，蚂蚁被索引，并要求用户在执行之前选择一个索引蚂蚁。显示了选择概率和可用/不可用城市。另外，虚拟
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[241491]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
