一种新的TSP蚁群优化算法外文翻译资料

英语原文共 4 页，剩余内容已隐藏，支付完成后下载完整资料

外文翻译

题 目 一种新的TSP蚁群优化算法

一种新的TSP蚁群优化算法

Xiwu Wang

Information Engineering Department Ordnance Engineering College Shijiazhuang,

China 379342114@qq.com

摘要：传统的蚁群算法是基于正反馈机制的。本质上，这种正反馈机制有利于算法的收敛，但不利于搜索的多样性。为了缩短优化路径的长度，本文提出了一种改进的蚁群算法来提高搜索的多样性。该算法将正反馈和逆反馈同时进行，使得整个蚁群搜索时间大大缩短，并将大大增加蚁群搜索空间和搜索结果的多样性。TSP问题的仿真结果表明，该算法对求解复杂组合优化问题具有显著的效果。

关键词：蚁群算法；分集；正反馈；逆反馈

A New Ant Colony Optimization Algorithm for TSP

Xiwu Wang

Information Engineering Department Ordnance Engineering College Shijiazhuang, China 379342114@qq.com

Abstract:The traditional ant colony algorithm is based on the positive feedback mechanism. In essence, this guidance is conducive to the convergence of the algorithm but is not conducive to the diversity of the search. In order to shorten the length of the path of the optimization, this paper proposes an improved ant colony algorithm to improve search diversity. The algorithm, the positive feedback, the inverse feedback simultaneously makes the entire ant colony search time is greatly reduced, and will greatly increase the diversity of the ant colony search space and search results. Simulation results of the TSP problem show that, the new algorithm for solving complex combinatorial optimization problem has a significant effect.

Keywords:ant colony algorithm; diversity; positive feedback; inverse feedback

1介绍

自从Dorigo M.等人在1991年首次提出蚁群优化算法以来，它已经吸引了大量的研究人员对该算法进行了研究，并成功地应用于求解大型复杂组合优化问题，如TSP[1,2]（旅行商问题）、QAP[3]（二次分配问题）、JSP[4]（工作车间调度问题）等。蚁群算法只所以能高效率的找到最优解，是因为在一定程度上利用正反馈机制来加快计算过程。

最近关于组合优化问题的搜索空间的文章[6-8]表明，在迭代算法中，随着搜索的进行，蚂蚁路径选择的局限性越来越大，前路径选择明显优于后路径选择。极端发生在最后一步，正反馈在路径选择的后半部分非常不足，导致蚂蚁的路径选择由概率转移策略主导。为此，扩大搜索空间，提高搜索结果的多样性尤为重要。通过在由正反馈机制的多样性提出的蚁群算法中加入逆反馈机制，可以使得整个蚁群搜索空间和搜索结果大大增加，蚁群路径搜索时间大大缩短。

2蚁群系统

2.1 基础理论

蚂蚁系统[9,10]的概念源自自然界中蚂蚁的群体觅食行为。觅食蚂蚁将留在它们的路径上，通过一种叫做“信息素”的物质，可以像蚁群后来感觉到的那样，作为对物质作用的信号效应（在后者中表现为蚂蚁选择这些物质的可能路径，这些物质中没有一种路径比选择的可能性大），然后到对信息素感兴趣的原始信息素的残留增强了，而物质会随着时间的推移逐渐蒸发，所以路径的长度及其蚂蚁对信息素的强度有多大的影响。对于信息表现为正反馈的现象，蚂蚁个体通过信息交换将能够很快地在蚁群中找到食物的行为。

2.2 蚁群算法

利用TSP问题说明了该算法的实现过程。

假设m只蚂蚁随机分布到选定的n个城市，每只蚂蚁行为的每一步都是按照一定的规则（概率）选择一个它有访问权限的城市；在完成一次访问或一个周期后更新其路径中的信息素浓度。下一个城市的选则有两个关键点：T时刻连接城市i和j的路径上残留的信息素浓度，该浓度由算法本身提供，从城市I到城市J的距离得出的启发式，该启发式通过一定的算法实现，通常情况下，就是TSP中的城市I到城市J的距离的倒数（dij表示城市i和j之间的距离，在这里可以称为先验知识）。所以，位于城市i的蚂蚁k选择下一个目标城市j的概率如下公式。

式中，alpha;是剩余素浓度启发因数；beta;是期望启发因数；是蚂蚁K下次可能参观的城市。

，新的启发信息必须更新残留信息，旧信息必须消失（信息素挥发），每只蚂蚁完成N个城市的访问后，必须更新残留信息，弱化旧信息（信息素挥发），同时，它必须将新信息添加到中，这是最新的Ant访问路径信息。

式中，为剩余信息的残留系数；1-是剩余信息的挥发系数。提供信息素的挥发性指标；是从T到T N的时间段内，由蚂蚁K从I到J所经过路径的信息素残留浓度。为了防止旧信息素无限制积累，这里的必须小于1。

3改进的蚁群算法

在算法中，每次遍历的蚂蚁数是确定的，通过正反馈和逆反馈的蚂蚁数也是确定的。在执行过程中，为了表示负反馈策略，新算法在遇到的蚂蚁数不超过阈值的情况下，增加阈值。在一个特定的周期内，整个蚁群的搜索过程继续进行，直到所有的蚂蚁都完成了自己的路径，这一次信息素的更新过程与传统的蚁群算法相同；如果遇到的蚂蚁数量超过了某个周期的阈值，那么新路径上的信息素更新，新的信息素由所有蚂蚁产生。

基于上述改进策略，改进后的蚁群算法流程图如图1所示：

第一步参数初始化：所有参数在每个周期前都要初始化。

第二步蚂蚁分配：根据随机选择的规则，将蚁群中的m个蚂蚁在这个循环中初始化为n个城市。

第三步路径建立：根据随机选择的规则，蚂蚁选择一定概率的城市进行访问，建立自己的搜索路径（同时进行正反馈和负反馈搜索）。

第四步统计蚂蚁选择的城市：在每个周期中，当搜索过程执行到路径的一半时，检查所有蚂蚁通过搜索路径的路径。我们认为，在搜索路径中遇到的两只蚂蚁，如果有大于或等于任意两只的蚂蚁已经访问过城市总数的城市。这两个蚂蚁被记录为遭遇蚂蚁，它正在形成一个新的搜索路径，这两个遭遇蚂蚁已经访问。

第五步阈值判断：如果循环中遇到的蚂蚁数量不超过阈值，算法中的蚂蚁将继续搜索，直到所有蚂蚁都建立了自己的路径。信息素更新策略与传统的蚁群算法相同，如果循环中遇到的蚂蚁数量超过阈值，则信息素将在新的路径上更新，搜索过程将结束。

第六步信息素更新：根据阈值判断结果并更新相应的信息素。

本文在算法的每一个循环中，所有路径上的信息素浓度都被限制在最小最大的范围内，如果信息素浓度超过这个范围，将被设置为最小或最小，并且有效地避免了算法过早收敛到非最优解，因此，

步骤7输出最佳路径和最佳结果。

4仿真

为了验证改进后的蚁群算法的结果，我们选取了一些TSP进行检测，这些问题都来自于TSP标准数据库。由经验和电子表格设置的算法参数的初始值，所以，

将最优路径的平均长度与TSP问题的最优结果进行了比较，验证了改进的蚁群算法的性能，具体结果见表一。

由表中的结果可以看出，新算法在特定参数上优于已知的最优结果。

改进的蚁群算法有两个重要参数，即阈值和蚂蚁数m，这两个参数对算法的性能有很大的影响。下面我们将讨论算法的影响。

改进的蚁群算法中的阈值会影响遭遇蚂蚁的数量和信息素更新策略。如果0，由于反反馈不足，改进后的算法将毫无意义，其信息素更新策略将与传统的蚁群算法相同。相反，如果0，蚂蚁的反反馈效应就会出现。为了找出反映搜索空间变化和搜索结果多样性的特点，将evil51tsp问题应用到改进的蚁群算法中。我们将分析变化导致搜索结果标准差变化的原因。具体结果如图2所示。

由图2的结果可以看出，算法搜索结果的标准差随着阈值的减小而增大，证明了算法的搜索空间和搜索结果的多样性在增大。因此，通常将阈值设置为1，以便改进的蚁群算法获得最佳结果。

蚂蚁数m是算法中的第二个重要参数。同样，为了研究其对算法性能的影响，我们通过计算图3所示的实例得到了计算结果。

从图3的结果可以看出，随着搜索蚂蚁数量的增加，平均最优解派生算法的运行效果更好。因此，我们将回路中的蚂蚁数M设置为与城市n相同的数目，这样改进的蚁群算法就可以获得最佳的结果。

5结论

针对传统的基于正反馈策略的蚁群算法。这有利于算法的收敛性，但对提高搜索的多样性没有帮助。本文改进了遭遇蚁群算法，提高了搜索的多样性。该算法将正反馈、逆反馈同时进行，使得整个蚁群搜索时间大大缩短，将大大增加蚁群搜索空间的多样性和搜索结果的多样性，从而减少了路径长度的优化。最后，讨论了阈值和蚂蚁数m这两个参数对算法性能的影响。TSP问题的仿真结果表明，该算法对求解复杂组合优化问题具有显著的效果。

参考文献：

[1] H. B. Duan, The Principles and Applications of Ant Colony Optimization. Beijing: Science publisher, 2005.

[2] C. Bulm, “Ant colony optimization: introduction and recent trends,” Physics of life reviews, vol. 2, no. 4, pp. 353-373, 2005.

[3] L. M. Gambardella, E. D. Taillard, and M. Dorigo, “Ant colonies for the QAP,” Technical report IDSIA-4-97, 1997.

[4] T. Teich, M. Fischer, and A. Vogel, “A new ant colony algorithm for the job shop scheduling problem,” In Proceedings of the 2001 Genetic and Evolutionary Computation, pp. 803-808, 2001.

[5] M. Dorigo and T. Stutzle, Ant Colony Optimization. Cambridge MA: MIT Press, 2004.

[6] Z. Y. Sun and W. Wei, “A study on improvement of ant colony algorithm strategies combinational optimization,” Computer Simulation, vol. 27, no. 8, pp. 194-197, 2010.

[7] Z. Y. Sun and X. F. Xing, “Research on solution to adaptive ant colony algorithm of combinational optimization,” Computer Engineering and Application, vol. 45, no. 35, pp. 31-33, 2009.

[8] Y. M. Li, W. J. Wang, and Z. B. Xu, “About ACO algorit

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[20565]，资料为PDF文档或Word文档，PDF文档可免费转换为Word