2022年蚁群算法的TSP问题求解策略分析研究.docx

《2022年蚁群算法的TSP问题求解策略分析研究.docx》由会员分享，可在线阅读，更多相关《2022年蚁群算法的TSP问题求解策略分析研究.docx（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 基于蚁群算法的TSP 问题求解策略讨论摘要 TSP 问题是运算机网络、路由规划中的经典问题；而蚁群优化算法作为高效的运算智能的方法,在离散优化领域有着非常广泛的应用,其中最为经典的是最优回路求解问题；因此,本文在分析蚁群算法进呈现状的基础上,针对TSP 问题的求解策略,来深化分析蚁群基数的设置对收敛效率的影响；最终通过 MATlAB 编程工具运行相关代码,并得到相应的TSP 问题解；试验结果说明：随着蚁群基数的增加,TSP 问题求解的时间也会线性增加；当蚁群基数大于等于 TSP 问题的结点个数的时候, TSP 问题的解才会保持稳固且趋近于蚁群基

2、数与节点个数相等时的 TSP 问题的解；关键字 蚁群算法 蚁群基数 TSPI / 24 名师归纳总结 - - - - - - -第 1 页,共 24 页精选学习资料 - - - - - - - - - Research on the TSP Solution based on Ant Colony OptimizationAbstract The TSP problem is a classic problem in computer network, route planning.And the ant colony optimization algorithm as an efficien

3、t method of computational intelligence, has the extremely widespread application in the field of discrete optimization, the most classic is the optimal circuit to solve the problem. Therefore, this article on the basis of analyzing the current situation of the development of ant colony algorithm, TS

4、P problem solving strategy, to analyze ant colony base Settings affect the convergence efficiency. Finally through MATlAB programming tools run the code, and get the corresponding TSP problem solution. The experimental results show that with the increase of base of ant colony, TSP problem solving li

5、near time will also grow ； when ant colony cardinality is greater than or equal to the node number of the TSP problem, the solution of the TSP problem will keep stable and tend to base of ant colony and TSP problem solution of node number is equal. Key Words Ant colony optimization Thebase of ant co

6、lony TSP II / 24 名师归纳总结 - - - - - - -第 2 页,共 24 页精选学习资料 - - - - - - - - - 目录1 引言 .1 1.1 TSP问题简述及其历史 .1 1.2 TSP问题的意义及求解方法 .1 1.3 蚁群算法的前景和意义 .2 1.4 蚁群算法的产生与进展 .2 1.5 蚁群算法的现状 .3 1.6 本文的讨论内容 .3 1.7 本文的组织结构 .4 2 蚁群算法 .5 2.1 蚁群算法的基本原理 .5 2.2 蚁群算法的基本流程 .6 2.3 蚁群优化算法的改进版本 .7 3 试验设计与分析 .11 3.1 试验假设 .11 3.2 试

7、验设计 .11 3.3 试验结果及结果分析 .12 结论 .19 致谢语 .20 参考文献 .21 III / 24 名师归纳总结 - - - - - - -第 3 页,共 24 页精选学习资料 - - - - - - - - - 1 引言1.1 TSP 问题简述及其历史旅行商问题 Traveling Salesman Problem, TSP）：假设一个旅行商人想要去 拜望如干个城市,每个城市只经过一次,并且最终要回到他动身时所在的那个 城市,为使整个拜望过程所走的路径最少,商人必需规划出一条最短的旅行路 线；TSP问题的历史悠久,最早的描述是1759 年欧拉讨论的骑士周游问题,即对于国际象

8、棋棋盘中的 64 个方格,如何做到每个方格都走访并只走访一次之后回到起点位置； TSP 问题最早由美国RAND 公司于 1948 年引入到运算机领域,目前已在网络路由、路径规划等有着非常广泛的应用；1.2TSP 问题的意义及其求解方法优化问题是信息领域的关注热点,其中组合优化问题是最常见的优化问题之一；目前很多工程上的问题都可以抽象为对应的组合优化问题,如：集成电路的布控、 GPS导航、网络路由、交通网等都需要用到优化学问；TSP 问题是组合优化问题的典范,对TSP 问题的大部分讨论成果可以胜利地应用到其他的组合优化问题上,TSP 问题已经成为测试新组合优化算法的标准问题；传统的 TSP问题的

9、解法只适用于小搜寻空间的 TSP 问题,并且有的算法仍表现出不错的精确性；这些方法主要有：迪杰斯特拉 伊德 floyd）算法以及一些其他的算法；, 以其分布式并发性、正反馈、鲁棒性强、收敛速度快、易获得全局最优解等特点引起越来越多国内外学者的关注,成为目前国内外启示式算法讨论的热点和前沿问题 用在 TSP问题的求解中；1.3 蚁群算法的前景和意义2；目前 蚁群算法已胜利将其应蚁群算法作为一种全局最优化的搜寻算法,同遗传算法一样来源于大自然 的启示,并且也同样拥有者良好的搜干脆能；不同的是,蚁群算法通过模拟蚂 蚁觅食的过程,是一种自然的解决离散组合优化问题的方法,在解决经典典型组合优化问题,如旅

10、行商问题 Traveling Salesman Problem, TSP、车辆路径问题 Vehicle Routing Problem, VRP、车间作业调度问题 Job-shop Scheduling Problem, JSP和动态组合规划问题如通信领域的路由器问题中均得到了胜利的应用；目前针对蚁群算法在数学理论、算法改进、实际应用等方面的讨论是当前国内外讨论的热点；1.4 蚁群算法的产生与进展ACO 是一种用来在图中查找优化路径的机率型算法；它由 Marco Dorigo等人3于 1991 年在第一届欧洲人工生命会议 European Conference on Artificial In

11、telligence, ECAI 上提出,其灵感来源于蚂蚁在觅食过程中发觉路径的行为；蚁群算法是一种模拟进化算法,与遗传算法、粒子群算法、免疫算法等同属于仿生优化算法；第一种 ACO 算法是蚂蚁系统 Ant System, AS,该方法是以 NP-Hard 的TSP 问题作为应用实例提出的；AS 算法初步形成的时候虽然能够找到问题的优2 / 24 名师归纳总结 - - - - - - -第 5 页,共 24 页精选学习资料 - - - - - - - - - 化结果,但是其算法的执行效率并不优于其他传统算法,因此 ACO 并未受到国际学术界的广泛认可,在刚提出的那五年时间里面有关方面的讨论也处

12、于停滞不前的状态；直到 1996 年 Dorigo 的 Ant System：optimization by a colony of cooperating agents 一 文4 正 式 在 IEEE Transaction on System, Man , and Cybernetics 上发表；这篇文章具体的介绍了 AS 的基本原理和算法流程,并对AS 提出了三个版本：蚂蚁密度 ant-density、蚂蚁数量 ant-quantity和蚂蚁圈 ant-cycle；目前 AS 一般特指蚂蚁圈,前两者由于性能不佳导致关注度降低；Dorigo 仍在该文中将 AS 的性能与众多算法,如遗传算法

13、、模拟退火、禁忌搜索等算法进行比较,发觉在大多数的情形下 群优化算法进展历史上的一个里程碑,从今,关注；1.5 蚁群算法的现状AS 的寻优才能是正确的；这是蚁 ACO 在国内外受到了越来越多的蚁群算法的改进策略包括精华蚂蚁系统 Elitist AS, EAS、最大最小蚂蚁系统 MAX-MIN AS , MMAS 、基于排列的蚂蚁系统 rank-based AS, ASrank等,他们大多是在 AS 上直接操刀改进；在1997 年, ACO 的创始人 Dorigo 提出了一种大幅度改动 AS 特点的算法蚁群系统 Ant Colony System, ACS5；试验结果说明 ACS 的性能明显优于

14、AS,之后蚁群算法连续进展,新的蚁群扩展算法不断显现；到了 21 世纪,各种连续算法的显现,更是扩大了蚁群算法的领域；1.6 本文的讨论内容TSP 问题作为蚁群算法产生之初所讨论的第一个典型的离散组合优化问题,在蚁群算法的进展史中占有不行替代的位置,本文主要基于 ACO 的蚁群基数来讨论特定的 TSP 问题,通过试验分析得到求解该1.7 本文的组织结构3 / 24 TSP 问题的正确蚁群基数；名师归纳总结 - - - - - - -第 6 页,共 24 页精选学习资料 - - - - - - - - - 本文主要由以下三个章节组成：第一章引言；主要介绍TSP 问题、 TSP 问题的意义及求解方

15、法、蚁群算法的产生和进展、现在的讨论情形、已经取得的胜利和以后进展的方向,以及本文主要讨论的内容；其次章 蚁群算法；介绍蚁群算法的基本原理和基本流程,然后再简要介绍一下当下的几种较流行的ACO 改进算法和 ACS 的工作流程；第三章 试验设计与分析；包括试验假设的提出、试验步骤的设计、试验结果的处理分析、得出结论；在文章的最终,将会对本文做一个总结；4 / 24 名师归纳总结 - - - - - - -第 7 页,共 24 页精选学习资料 - - - - - - - - - 2 蚁群算法2.1 蚁群算法的基本原理仿生学家通过长期的讨论和试验得出：蚁群在觅食过程中会产生一种化学 物质信息素 ph

16、eromone；蚂蚁在查找食物的过程中挑选的路径往往是随机 的,在沿着路径查找的过程中,他们一边释放自身的信息素,一边感知当前地 面上的信息素浓度,并倾向于向高信息素浓度的方向前进；由于信息素由蚂蚁 自身释放,所以它就充当了蚁群内部间接通信的物质；由于较短路径上的蚂蚁 来回时间比较短,所以在单位的挥发时间内,经过的蚂蚁数量比较多,留下的 信息素自然也比较浓,因此后面的蚂蚁在经过的时候就会依据信息素的浓度而 挑选较短的路径前进；这种正反馈机制会使得蚁群所找到的最短路径上信息素 的浓度越来越浓,而其他的路径就会随着信息素的渐渐挥发而被剔除,最终所 有的蚂蚁都会沿着最短路径前进；有生物学家将蚁群上述

17、行为描述成以下三种机制：挑选机制：信息素越多的路径,被选中的概率越大；更新机制：路径上面的信息素会随着蚂蚁的经过而增加,同样也会随着时 间的推移而挥发消逝；和谐机制：蚂蚁之间实际是通过分泌物来相互通信、协同工作的；此外,蚁群的自适应才能特殊强,假设在路径上突然显现障碍物,蚁群也 能够绕过障碍并很快重新探究出一条新的最优路径；蚁群算法正是充分运用了这三种机制和一群的自适应力,使之具备强大的 发觉最优解的才能；2.2 蚁群算法的基本流程5 / 24 名师归纳总结 - - - - - - -第 8 页,共 24 页精选学习资料 - - - - - - - - - 前面已经简要介绍了TSP 问题,接下

18、来我先将TSP 问题以较专业的语言再进行简洁描述,然后再具体介绍AS 算法对 TSP 的求解流程；TSP 问题是指在具有 N 个城市节点的集合中找到一条最短的回路,这条回路必需从一个节点动身,遍历该节点集里面的全部节点,并最终回到初始节点 已知任意两个节点之间的欧几里德距离,这样的回路也称之为哈密顿回路,如下图所示： a属于较简洁的 TSP 问题, b的节点较多,求解也相对复杂很多； 图 2-1 TSP问题示意图AS 算法对 TSP问题求解主要有两大步骤：路径构建和信息素更新；1. 路径构建每一只蚂蚁都随机挑选一个城市节点作为动身城市,每到达一个城市后,更新自己的路径记忆向量,记k R ,来存

19、放该蚂蚁依次走过的城市节点,确保不会走已经走过的节点,对于仍没有走过的城市节点依据随机比例规章：pki,jJkii,j,ui,j,u,jJki,jii0 , other 2-1随机挑选出一个作为该蚂蚁下一步要到达的城市节点；其中,p k i , j 表示蚂蚁k 从 i 城市节点走向 j 城市节点的概率；J k i 表示当前城市节点 i 可以直接到达6 / 24 名师归纳总结 - - - - - - -第 9 页,共 24 页精选学习资料 - - - - - - - - - 且仍未走过的城市节点集；i,j表示能见度,i,j1dij,d 表示城市节点i与j之间的距离；i, j 表示城市节点i,j连

20、线间的信息素浓度,在算法的初始化时,问题空间上的信息素会被初始化为一个相同的值；和 是两个预先设置好的参数,用来调剂信息素浓度 和能见度 之间的相对重要程度 6；2信息素更新当全部蚂蚁都遍历过这些城市节点后,问题空间上全部路径的信息素都会发生挥发,所以我们要对路径上的信息素进行更新,以突出较短的路径,摒弃较差的路径,信息素依据以下公式7进行更新：m01；k i2-2 i,j1.i.jki,jki,jQ/L k,i,jk 1R k,0其他,j表这里,m表示蚁群的数量,是信息素的挥发率,并有示蚂蚁k在本次循环中经过城市节点i 和j间的连线时留下的信息素量,在ki,j的运算公式中：Q 是常数,L 表

21、示蚂蚁 k 本次循环所经过路径的总长度；2.3 蚁群优化算法的改进版本蚁群算法虽然具有并行式启示机制、鲁棒性强、搜寻才能好、简洁与其他 启示式算法结合使用等优点,但同样也具有搜寻时间过长、简洁陷于局部最优 解等突出的缺点；针对这些缺点,众多国内外学者在蚁群算法的改进上做了大 量讨论工作,也取得不菲的成果：1. 精华蚂蚁系统 EAS EAS 是第一次基于基础AS 上改进的 ACO8,它在原 AS 信息素更新的规就中增加了一个对至今最优路径的强化手段,即在每一轮搜寻完成后,对当前搜寻到的最优路径 用T 来表示 增加额外的信息素； EAS 中信息素的更新公式7 / 24 名师归纳总结 - - - -

22、 - - -第 10 页,共 24 页精选学习资料 - - - - - - - - - 如下：mi,j1.i,jki,jebi,jj2-3 k1ki,jQLk,i,jRk0 ,otherbi,jQLb,i,j在路径T b上并定义了参数0 ,other式2.3中除了式 2.2中的各个符号意义外,新增了b,e作为b,j的权值；L 表示至今最优路径的长度；可见,在EAS 算法中每一次迭代后属于T 边的信息素的增量为eQL b；通过引入这种信息素强化的操作会起到引导蚂蚁搜寻的功能,加快算法的收敛速度； Dorigo 等人的试验也已经证明白 更快的速度；2.基于排列的蚂蚁系统 ASrank 虽然 EAS

23、 在解 TSP问题上的求解质量较EAS 有着较 AS 求解更高的精度和AS 来之高,但解元素之间的相互联系也削减了,导致挑选概率也相对削减了,使得在搜寻过程中更简洁集合在 局部最优解的邻近,从而阻碍了对更优解的进一步探究 9；ASrank 较 EAS 的不同之处在于,在每一轮的迭代完成之后,选取至今最优蚂蚁和本轮排名前w1只蚂蚁,并且只答应它们释放信息素每只蚂蚁的信息素释放量就依靠于它们本轮的排名；具体的信息素更新公式如下： i,jj1. i,jjkki,jb i,j2-4 k1Q/L k,i,i,k Rk,0otherbi,jQ/L b,i,j在路径T b上0,other从以上公式可以看出：

24、至今最优路径的蚂蚁所释放的信息量最多,然后当前排名 在 前w1位 的 蚂 蚁 按 照 排 名 的 下 降 , 所 释 放 的 信 息 素 也 依 次 下 降 ；8 / 24 名师归纳总结 - - - - - - -第 11 页,共 24 页精选学习资料 - - - - - - - - - Bullnheimer10的试验结果也说明ASrank 较之 AS 和 EAS 具备更高的寻优才能和求解速度；3. 最大最小蚂蚁系统 MMAS MMAS 也是在 AS 算法的基础上进行改进,改进的方面有以下四点：1 每次迭代完之后,只对本次迭代的最优解或者当前全局最优解进行信 息素更新；2 为了防止迭代停滞,

25、限制信息素的取值范畴在区间min,max内,当max 的时,取max ；当min 时,取min11；3 信息素初始值为max ,并相伴着一个较小的信息素蒸发率,以确保算法初期能够尽可能多的搜寻路径；4 每当系统进入停滞状态,问题空间上的全部边的信息素都将被重新初 始化；改进 1正是借鉴于EAS,但又有所不同,在MMAS 中有权对信息素更新的不仅是至今最优的蚂蚁,也可以是本次迭代最优的蚂蚁,两者可能显现交替使用的情形；改进 1可以确保寻优速度的加快,而改进2的缘由正是可怕因为信息素的增长过快,而导致“ 早熟” 现象,以至于搜寻的是一条局部最优解而不是全局最优解；改进3,会使得算法刚开头执行的时候

26、起点较高,信息素的蒸发又比较慢,且 2很好的保证了信息素的增长不会过于快速,因此在算法 的初期, MMAS 较 AS、EAS、ASrank 有着更好的搜寻才能,视野更宽阔,所搜结果为全局最优的机会更大；1、2、3的提出可以确保在单次算法执行过程的性能优于AS、EAS、ASrank ,而 4的提出就更增强了MMAS 的性能；不论 AS、EAS 仍是 ASrank,在算法执行陷入停滞状态时,就会终止运算,而MMAS 在接近或已经进入停滞状态的时候会重新初始化问题空间上的信息素浓度,从而保证了算法的连续搜寻；MMAS 是目前最受关注的ACO 算法之一,而它的四项改进规章也频繁地被后续的各种 ACO

27、算法所借鉴；4. 蚁群系统 ACSEAS、ASrank 以及 MMAS 都是基于AS 算法进行小量的修改得到的,蚁群9 / 24 名师归纳总结 - - - - - - -第 12 页,共 24 页精选学习资料 - - - - - - - - - 算法就是在 AS 算法上大幅操刀而得到的一种具有全新机制的 ACO 算法,它与蚂蚁系统的不同之处主要表现在以下三点：1 从一个城市到另一个城市的过程中,运用的状态转移规章不同；在ACS 中采纳伪随机比例规章：对于每只蚂蚁k , 路径记忆向量R 次序地记忆了已经走过的城市,设当前蚂蚁k 处于城市 i ,就它要拜访的下一个城市arg max j J k i

28、 i , j i , j , q q 0jS , other 2-5其中,J k i 表示从城市i可以直接到达但又不在 R 中的城市集合；i , j表示能见度,i, j 表示城市节点i,j连线间的信息素浓度,用来调剂信息素浓度 和能见度 之间的相对重要程度；q 是一个随机数,q 是在 0 1, 内的参数,当 q q 0 时有：i , j i , j , j J k iS p k i , jJ k i i , u i , u 2-6 0 , other2 信息素更新采纳信息素全局更新规章；只在属于至今最优路径的边进行信息素的更新 蒸发和释放 ；在每轮迭代中,当全部的蚂蚁均完成路径构建后,信息素全

29、局更新规章才可以使用：其中,i,j和 1.i,j.bi,j,i,jTb2-7 b i,j分别表示i,j之间的信息素和信息素的蒸发速率；在ACS算法中,信息素的更新只在至今最优路径上进行,故其信息素更新运算的复杂度也降低为On；3 新增了信息素局部更新规章；蚂蚁每次经过问题空间的某一边,都会去除该边上肯定量的信息素,通过这种方式来增加后续蚂蚁探究其他路径的可能性；局部更新的公式如下：其中 i,j1. i,j.0；2-8 表示信息素的局部挥发率,满意010 是信息素的初始值；局部10 / 24 名师归纳总结 - - - - - - -第 13 页,共 24 页精选学习资料 - - - - - -

30、- - - 更新规章大大增加了算法的探究才能,后续蚂蚁会倾向于探究未被探究过的边,有效防止了算法的停滞；3 试验设计与分析TSP 问题虽然是蚁群算法所讨论的主流方向和热门方向之一,但是由于蚁 群算法的搜寻时间长及简洁陷于局部最优解等缺点,想要克服这些困难,除了可以挑选当下比较先进的算法进行讨论之外,仍可以针对对应的 TSP 问题,去 转变算法里面的参数的设置值,依次来达到优化解的成效；本文就是通过讨论蚁群的基数变化对求解TSP问题的影响,以此来推断出求解该TSP 问题的正确蚁群基数；3.1 试验分析蚁群算法求解 TSP 问题：在保持其他条件因素不变的情形下,如转变蚁群 的基数,会对求解和时间和

31、解的精确性发生变化,并且变化遵循以下规章：1 当蚁群的基数增大时,求得的最优解的精确性增大,但求解的时间也 会增加；2 当蚁群的基数减小时,求得的求得的最优解的精确性减小,但求解的 时间也会削减；3.2 试验设计本试验的TSP 问题的节点设置n=30 个,蚁群基数初始值m =10,增量11 / 24 名师归纳总结 - - - - - - -第 14 页,共 24 页精选学习资料 - - - - - - - - - k=10,最大值m MAX=80,其他因素的初始值如下表：表 3-1 蚁群算法各因素对比表参数名对比蚁群算法中的因素初始值1alpha常系数1beta5rho0.1Q1Eta路径长度

32、除了以上那些可以影响求解结果的参数外,仍有一些记录参数和常规参数；表 3-2 其余参数对比表参数名参数含义参数取值D路径总距离zerosn,n Tau 信息素矩阵onesn,n 路径记录表Table zerosm,n iter/iter_max 迭代初始值 / 迭代最大值1/200 Route_best 各代正确路径zerositer_max,n Length_best 各代正确路径的长度zerositer_max,1 Length_ave 各代路径的平均长度zerositer_max,1 对每个 m 值运行十次,得到十个最短路径d 和时间 t,记录数据,对这些数据进行处理：对 d 和 t 分

33、别求平均,并指出当前基数下的最优路径；最终将十个平均值绘成图,通过分析得到求解该3.3 试验结果及结果分析TSP 问题的正确蚁群数量；12 / 24 名师归纳总结 - - - - - - -第 15 页,共 24 页精选学习资料 - - - - - - - - - 将不同蚁群基数运行程序后得到的最短路径图列出如下：a m=10 b m=20 13 / 24 名师归纳总结 - - - - - - -第 16 页,共 24 页精选学习资料 - - - - - - - - - c m=30 d m=40 14 / 24 名师归纳总结 - - - - - - -第 17 页,共 24 页精选学习资料

34、- - - - - - - - - e m=50 f m=60 15 / 24 名师归纳总结 - - - - - - -第 18 页,共 24 页精选学习资料 - - - - - - - - - g m=70 h m=80 图 3-1 蚁群基数与其对应最短路径图将分析完后的各组数据进行处理,得到以下结果：16 / 24 名师归纳总结 - - - - - - -第 19 页,共 24 页精选学习资料 - - - - - - - - - 表 3-3 蚁群基数及其对应的 TSP问题解m平均路径10 20 30 40 11027.75 10907.63 10815.06 10818.59 m平均时间5

35、.642 10.956 16.295 20.138 最优路径10659.65 10735.31 10475.69 10321.33 50 60 70 80 平均路径10785.73 10800.37 10838.50 10793.18 平均时间26.025 31.086 35.895 41.121 最优路径10435.35 9950.886 10267.58 9608.489 由上表可知,虽然随着蚁群基数的增大,最短路径也会呈减短的趋势,但是平均路径并未得到大幅度的减小,最优解具有更大的偶然性,所以无法确定所求的最优解是否有效,因此求解的最短路径不能作为求解TSP 问题时考量正确蚁群基数的一个

36、指标；将最短路径之外的两个结果在MATLAB工具箱中绘制出来,由于两个结果的数量级相差较大,为便利观看,将两个结果分别绘图如下：a m-t bm-d 图 3-2 蚁群基数与最优路径和搜寻时间关系图分析图 3-2：随着蚁群数量从10 到 80 有规律地递增,算法的搜寻时间也几乎呈线性增长；而在寻优方面,在蚁群数量从 10 递增到 30 的过程中,所寻的平均最优路径的质量有着明显的提高,但是当蚁群数量连续增加时 30-80,所寻的平均最优路径基本保持在肯定范畴内上下波动,无明显变化；虽然在 m=50和 m=80 两处的平均最优路径较m=30 处的平均最优路径有所改善,但变化不大,且所用搜寻时间更长,因此,对于该 TSP 问题而言,正确蚁群基数是m=30；17 / 24 名师归纳总结 - - - - - - -第 20 页,共 24 页精选学习资料 - - - - - - - - - 据此可以得出：对于一个特定TSP 问题,蚁群基数与求解该TSP问题所需时间呈线性相关的关系,即当蚁群基数增大时,求解TSP 问题所需时长也会出现类似线性的增加,反之亦然；当蚁群基数m所要讨论的TSP 问题的结点个数n时,求