基于蚁群算法的路径最优研究___毕业答辩

1、基于蚁群算法的路径最优问题研基于蚁群算法的路径最优问题研究究Page 2论文的结构和主要内容论文的结构和主要内容n 第一部分第一部分 选题的背景与意义n 第二部分第二部分 国内外研究现状n 第三部分第三部分 研究内容与方法n 第四部分第四部分 研究中可能存在的问题n 第五部分 预期结果Page 3一一 选题背景与意义选题背景与意义 2001年至今1996年-2001年意大利学者Dorigo1991年启发各种改进算法的提出，应用领域更广各种改进算法的提出，应用领域更广 引起学者关注，在应用领域得到拓宽ACO首次被系统的提出首次被系统的提出自然界中真实蚁群集体行为Page 4一一 选题背景与意义选

2、题背景与意义u 蚁群算法的由来：蚂蚁是地球上最常见、数量最多的昆虫种类之一，蚁群算法的由来：蚂蚁是地球上最常见、数量最多的昆虫种类之一，常常成群结队地出现在人类的日常生活环境中。这些昆虫的群体生物常常成群结队地出现在人类的日常生活环境中。这些昆虫的群体生物智能特征，引起了一些学者的注意。意大利学者智能特征，引起了一些学者的注意。意大利学者M.DorigoM.Dorigo，V.ManiezzoV.Maniezzo等人在观察蚂蚁的觅食习性时发现，蚂蚁总能找到巢穴与等人在观察蚂蚁的觅食习性时发现，蚂蚁总能找到巢穴与食物源之间的最短路径。食物源之间的最短路径。u 经研究发现，蚂蚁的这种群体协作功能是通

3、过一种遗留在其来往路经研究发现，蚂蚁的这种群体协作功能是通过一种遗留在其来往路径上的叫做信息素径上的叫做信息素(Pheromone)(Pheromone)的挥发性化学物质来进行通信和协调的挥发性化学物质来进行通信和协调的。化学通信是蚂蚁采取的基本信息交流方式之一，在蚂蚁的生活习的。化学通信是蚂蚁采取的基本信息交流方式之一，在蚂蚁的生活习性中起着重要的作用。通过对蚂蚁觅食行为的研究，他们发现，整个性中起着重要的作用。通过对蚂蚁觅食行为的研究，他们发现，整个蚁群就是通过这种信息素进行相互协作，形成正反馈，从而使多个路蚁群就是通过这种信息素进行相互协作，形成正反馈，从而使多个路径上的蚂蚁都逐渐聚集到

4、最短的那条路径上。径上的蚂蚁都逐渐聚集到最短的那条路径上。Page 5二二 国内外研究现状国内外研究现状n 目前，蚁群算法己经成为一个备受关注的研究热点和前沿性课题。人目前，蚁群算法己经成为一个备受关注的研究热点和前沿性课题。人们对蚁群算法的研究已经由当初的们对蚁群算法的研究已经由当初的TSPTSP领域渗透到多个应用领域，由领域渗透到多个应用领域，由解决解决一维静态优化问题发展到解决优化问题发展到解决多维动态组合优化问题，由组合优化问题，由离散域范围内研究逐渐拓展到了范围内研究逐渐拓展到了连续域范围内研究。同时在蚁群算法的模型范围内研究。同时在蚁群算法的模型改进以及改进以及其他仿生优化算法的融

5、合方面也取得了相当丰富的研究成果，方面也取得了相当丰富的研究成果，从而使这种新兴的仿生优化算法展现出前所未有的生机。从而使这种新兴的仿生优化算法展现出前所未有的生机。Page 6三三 研究内容与方法研究内容与方法 1.1.基本蚁群算法及其改进算法基本蚁群算法及其改进算法（1 1）基本蚁群算法）基本蚁群算法（2 2）蚁群系统）蚁群系统（3 3）最大）最大- -最小蚂蚁系统最小蚂蚁系统2.2.蚁群算法与蚁群算法与TSPTSP应用应用（1 1）蚁群算法的思想、原理）蚁群算法的思想、原理（2 2）蚁群算法的实现方式）蚁群算法的实现方式（3 3）TSPTSP应用举例应用举例Page 7 3.1.1蚁群算

6、法的基本思想蚁群算法的基本思想 在自然界中，蚂蚁的食物源往往随机散布于蚁巢周围，在自然界中，蚂蚁的食物源往往随机散布于蚁巢周围，通通过过观察可以发现，经过一段时间后，蚂蚁总能找到一条从蚁巢到观察可以发现，经过一段时间后，蚂蚁总能找到一条从蚁巢到食物源的最短路径。自然界中的蚂蚁虽然视觉能力十分有限，食物源的最短路径。自然界中的蚂蚁虽然视觉能力十分有限，但它们在觅食过程中，却能够通过播撒、感知信息素与其它同但它们在觅食过程中，却能够通过播撒、感知信息素与其它同伴建立起通讯关系，并以此相互协调、分工、合作来找到食物伴建立起通讯关系，并以此相互协调、分工、合作来找到食物源和巢穴之间的最短路径。并且在相

7、同的时间内，路径越短则源和巢穴之间的最短路径。并且在相同的时间内，路径越短则遗留的信息素浓度就越大，而蚂蚁在选择路径时，倾向于那些遗留的信息素浓度就越大，而蚂蚁在选择路径时，倾向于那些信息素浓度较高的路径，这样选择较短路径的蚂蚁也随之增多。信息素浓度较高的路径，这样选择较短路径的蚂蚁也随之增多。因此，由大量蚂蚁组成的蚁群集体觅食行为表现出了一种正反因此，由大量蚂蚁组成的蚁群集体觅食行为表现出了一种正反馈现象：一条路径上走过的蚂蚁越多，则后来者选择这条路径馈现象：一条路径上走过的蚂蚁越多，则后来者选择这条路径的概率就越高。蚂蚁个体之间就是通过这种信息素的交流机制，的概率就越高。蚂蚁个体之间就是通

8、过这种信息素的交流机制，来搜索食物，并最终找到最短路径。来搜索食物，并最终找到最短路径。Page 83.1.2蚂蚁觅食原理：蚂蚁觅食原理：n 自然界中，蚂蚁这种视盲生物，在没有任何先知经验的情况下总能找自然界中，蚂蚁这种视盲生物，在没有任何先知经验的情况下总能找到从其巢穴到食物源的最佳路径，甚至在该路径上放置障碍物之后，到从其巢穴到食物源的最佳路径，甚至在该路径上放置障碍物之后，它们仍然能很快重新找到新的最佳路线。它们仍然能很快重新找到新的最佳路线。Page 9蚂蚁觅食原理蚂蚁觅食原理n 这是因为在蚂蚁个体之间是通过一种称为信息素的物质进行信息传递的。蚂这是因为在蚂蚁个体之间是通过一种称为信息

9、素的物质进行信息传递的。蚂蚁在运动过程中，不但能够在它所经过的路径上留下该物质，而且能够感知蚁在运动过程中，不但能够在它所经过的路径上留下该物质，而且能够感知这种物质的存在及其强度，并朝着该物质强度高的方向移动，为此指导自己这种物质的存在及其强度，并朝着该物质强度高的方向移动，为此指导自己的运动方向。因此，由大量蚂蚁组成的蚁群集体行为表现出一种信息正反馈的运动方向。因此，由大量蚂蚁组成的蚁群集体行为表现出一种信息正反馈现象。在一定时间内较短路径通过的蚂蚁要多于较长路径，而某一路径上走现象。在一定时间内较短路径通过的蚂蚁要多于较长路径，而某一路径上走过的蚂蚁越多，则后来的蚂蚁选择该路径的概率就越

10、大。过的蚂蚁越多，则后来的蚂蚁选择该路径的概率就越大。n 蚁群算法的蚁群算法的基本原理基本原理简单来说就是：简单来说就是：n 1 1、蚂蚁、蚂蚁在路径上释放在路径上释放信息素信息素。n 2 2、碰到还没走过的路口碰到还没走过的路口，就就随机挑选随机挑选一条路一条路走走。同时，同时，释放释放与路径长度有与路径长度有关的信息素。关的信息素。n 3 3、信息素浓度与路径长度成反比。信息素浓度与路径长度成反比。后来的蚂蚁再次碰到后来的蚂蚁再次碰到该该路口路口时，就时，就选择选择信息素信息素浓度较高路径浓度较高路径。n 4 4、最优路径上的最优路径上的信息素信息素浓度浓度越来越大越来越大n 5 5、最终

11、最终蚁群找到蚁群找到最优最优寻食路径。寻食路径。Page 103.1.3蚁群算法的优缺点蚁群算法的优缺点蚁群算法的优点蚁群算法的优点n 不依赖于所求问题的具体数学表达式描述，具有很强的找到全局最优不依赖于所求问题的具体数学表达式描述，具有很强的找到全局最优解的优化能力。解的优化能力。n 该算法具有正反馈、较强的鲁棒性、全局性、普遍性、优良的分布式该算法具有正反馈、较强的鲁棒性、全局性、普遍性、优良的分布式并行计算机制、易于与其他方法相结合等诸多优点。并行计算机制、易于与其他方法相结合等诸多优点。Page 11蚁群算法的缺点：蚁群算法的缺点：n 蚁群算法的成功主要在实验层次上，很少有理论来解释利

12、蚁群算法的成功主要在实验层次上，很少有理论来解释利用蚁群算法为什么能够成功地解决这些问题，它没有坚实用蚁群算法为什么能够成功地解决这些问题，它没有坚实的数学基础；的数学基础；n 蚁群算法的模型普适性不强，其模型不能直接应用于实际蚁群算法的模型普适性不强，其模型不能直接应用于实际优化问题；优化问题；n 蚁群算法的局部搜索能力较弱，易于出现停滞和局部收敛、蚁群算法的局部搜索能力较弱，易于出现停滞和局部收敛、收敛速度慢等问题，因而往往需要嵌入一些专门的辅助技收敛速度慢等问题，因而往往需要嵌入一些专门的辅助技巧；巧；n 长时间花费在解的构造上，从而导致搜索时间过长，长时间花费在解的构造上，从而导致搜索

13、时间过长，n 算法最先基于离散问题，不能直接解决连续优化问题。算法最先基于离散问题，不能直接解决连续优化问题。Page 123.2 自然蚁群与人工蚁群自然蚁群与人工蚁群 蚁群算法都是从自然界中真实蚂蚁寻找食物行为得到启发提出来的。蚁群算法都是从自然界中真实蚂蚁寻找食物行为得到启发提出来的。人们只有通过对蚁群行为的一种模拟来满足实际问题的求解需要。所以人们只有通过对蚁群行为的一种模拟来满足实际问题的求解需要。所以人工蚁群与真实蚁群之间存在一定的异同。人工蚁群与真实蚁群之间存在一定的异同。 相似之处在于：都是优先选择信息素浓度大的路径。相似之处在于：都是优先选择信息素浓度大的路径。 两者的区别：两

14、者的区别： （1）在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。）在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。 （2）人工蚁群选择路径时不是盲目的。而是按一定规律有意识地寻找）人工蚁群选择路径时不是盲目的。而是按一定规律有意识地寻找最短路径。例如，在最短路径。例如，在TSP问题中，可以预先知道当前城市到下一个目的问题中，可以预先知道当前城市到下一个目的地的距离。地的距离。Page 133.3.3 3.1 .1 基本蚁群算法基本蚁群算法( )kijP t( )( ),( )( )( )0,kisiskkisisijx allowkttsallowttP tsallowu蚂蚁

15、蚂蚁k(k=1,2k(k=1,2，,m),m)根据各个城市间连接路径上的信根据各个城市间连接路径上的信息素浓度决定其下一个访问城市，设息素浓度决定其下一个访问城市，设 表示表示t t时刻蚂蚁时刻蚂蚁k k从城市从城市i i转移到城市转移到城市j j的概率，其计算公式为：的概率，其计算公式为： u信息更新公式为：信息更新公式为：1(1)(1)( ),01ijijijnkijiiktt Page 14u针对蚂蚁释放信息是问题，针对蚂蚁释放信息是问题，M.DorigoM.Dorigo等人曾给出等人曾给出3 3中不同的模型，分中不同的模型，分别为蚁周系统、蚁量系统和蚁密系统，其计算公式如下：别为蚁周系

16、统、蚁量系统和蚁密系统，其计算公式如下：1.1.蚁周系统模型蚁周系统模型2.2.蚁量系统模型蚁量系统模型3.3.蚁密系统模型蚁密系统模型ij/kij0,kiiQ d，第 只蚂蚁从城市访问城市其他kij0,kiiQ，第 只蚂蚁从城市 访问城市其他/kij0,kkiiQ L，第 只蚂蚁从城市 访问城市其他其中，其中，Q Q为常数，表示蚂蚁循环一次所释放的信息素总量；为常数，表示蚂蚁循环一次所释放的信息素总量；L L为第为第k k只蚂蚁经只蚂蚁经过路径的长度。过路径的长度。d d为城市间的距离。为城市间的距离。Page 153.3.3 3.2 .2 蚁群系统蚁群系统u蚁群系统的状态转移规则蚁群系统的

17、状态转移规则 一只位于节点一只位于节点r r的蚂蚁通过应用下式给出的规则选择下一个将要移的蚂蚁通过应用下式给出的规则选择下一个将要移动到的城市动到的城市s s： 其中，其中，S S根据下列公式得到根据下列公式得到 q q是在是在0,10,1区间均匀分布的随机数区间均匀分布的随机数 q0 q0的大小决定了利用先验知识与探索新路径之间的相对重要性。的大小决定了利用先验知识与探索新路径之间的相对重要性。0arg max ( , ) ( , ) ,ku allowedr ur uqqsS如果按先验知识选择路径否则( )( ),( )( )( )0,kijijkkisisijs allowedttjal

18、lowedttPtotherwisePage 16 1,( , )0,gbLr s如果(r,s) 全局最优路径否则u蚂蚁系统全局更新原则蚂蚁系统全局更新原则只有全局最优的蚂蚁才被允许释放信息素。只有全局最优的蚂蚁才被允许释放信息素。目的：使蚂蚁的搜索主要集中在当前循环为止所找出的最好目的：使蚂蚁的搜索主要集中在当前循环为止所找出的最好路径领域内。路径领域内。全局更新在所有蚂蚁都完成它们的路径之后执行，试用下式全局更新在所有蚂蚁都完成它们的路径之后执行，试用下式对所建立的路径进行更新：对所建立的路径进行更新： 为信息素挥发因数，为信息素挥发因数，0 10 1。 为到目前为止找出的全局为到目前为止

19、找出的全局最优路径。最优路径。gbL( , )(1) ( , )( , )r sr sr s Page 17 u蚁群系统局部更新原则蚁群系统局部更新原则 蚂蚁应用下列局部更新原则对它们所经过的边进行激素更新：蚂蚁应用下列局部更新原则对它们所经过的边进行激素更新： 实验发现，实验发现， 可以产生好的结果，其中可以产生好的结果，其中n n是城市的数量，是城市的数量， 是由是由最近的邻域启发产生的一个路径长度。局部更新原则可以有效的避免最近的邻域启发产生的一个路径长度。局部更新原则可以有效的避免收敛到同一路径。收敛到同一路径。( , )(1)( , )( , )01r sr sr s其中, 为一个参

20、数,01nnn LnnLPage 183.3.3 3.3 .3 最大最大- -最小蚂蚁系统最小蚂蚁系统(1)( )ijbestijijtt1()ijbestbestf s()bestf su信息素轨迹更新信息素轨迹更新在在 MMAS MMAS中，只有一只蚂蚁用于在每次循环后更新中，只有一只蚂蚁用于在每次循环后更新信息轨迹。经修改的轨迹更新原则如下：信息轨迹。经修改的轨迹更新原则如下： 表示迭代最优解或全局最优解的值。在蚁表示迭代最优解或全局最优解的值。在蚁群算法中主要使用全局最优解，而在群算法中主要使用全局最优解，而在MMASMMAS中则主要中则主要使用迭代最优解使用迭代最优解。Page 19

21、 MMASMMAS对信息素轨迹的最小值和最大值分别施加了对信息素轨迹的最小值和最大值分别施加了 和和 的限制，从而使得对所有信息素轨迹的限制，从而使得对所有信息素轨迹 ，有，有minmax( )ijtm inm ax( )ijtmaxm ax11( )()ijttio p titfsopt其中,f(s)为对于一个具体问题的最优解minu信息素轨迹的限制信息素轨迹的限制的选取： 的选取要基于两点假设：的选取要基于两点假设： l最优解在搜索停滞发生之前不久被找出。最优解在搜索停滞发生之前不久被找出。l对解构造的主要影响是由信息素轨迹的上限与下限之间的相对对解构造的主要影响是由信息素轨迹的上限与下限

22、之间的相对差异决定。差异决定。Page 203.4 蚁群算法的实现蚁群算法的实现 (1)(1)参数初始化。令时间参数初始化。令时间t=0t=0和循环次数和循环次数Nc=0Nc=0，设置最大循环次数，设置最大循环次数Ncmax, Ncmax, 将将 m m个蚂蚁置于个蚂蚁置于n n个元素个元素( (城市城市) )上，令有向图上每条边上，令有向图上每条边(i, j)(i, j)的初始化信息量的初始化信息量ij(t)=ij(t)=, , 其中其中constconst表示常数，且初始时刻表示常数，且初始时刻ij(0)=0ij(0)=0 (2) (2)循环次数循环次数Nc Nc+1Nc Nc+1。 (3

23、) (3)蚂蚁的禁忌表索引号蚂蚁的禁忌表索引号k=1k=1。 (4) (4)蚂蚁数目蚂蚁数目 kk+1 kk+1 。 (5) (5)蚂蚁个体根据状态转移概率公式蚂蚁个体根据状态转移概率公式(1)(1)计算的概率选择元素计算的概率选择元素( (城市城市) j ) j 并前并前进，进，jC - tabukjC - tabuk。 (6) (6)修改禁忌表指针，即选择好之后将蚂蚁移动到新的元素修改禁忌表指针，即选择好之后将蚂蚁移动到新的元素( (城市城市) )，并把该，并把该元素元素( (城市城市) )移动到该蚂蚁个体的禁忌表中。移动到该蚂蚁个体的禁忌表中。 (7) (7)若集合若集合C C中元素中元

24、素( (城市城市) )未遍历完，即未遍历完，即kmkm，则跳转到第，则跳转到第(4)(4)步，否则执行步，否则执行第第(8)(8)步。步。 (8) (8)根据公式根据公式(2)(2)和式和式(3)(3)更新每条路径上的信息量。更新每条路径上的信息量。 (9) (9)若满足结束条件，即如果循环次数若满足结束条件，即如果循环次数Nc Ncmax Nc Ncmax 则循环结束并输出程序则循环结束并输出程序计算结果，否则清空禁忌表并跳转到第计算结果，否则清空禁忌表并跳转到第(2)(2)步。步。Page 21四四 预期结果预期结果n 对于信息素挥发因子对于信息素挥发因子、启发式因子、启发式因子、自启、自

25、启发因子发因子、蚂蚁的数目、蚂蚁的数目m m对于蚁群算法性能的影响对于蚁群算法性能的影响进行了实验研究，发现蚁群算法中各个参数的取进行了实验研究，发现蚁群算法中各个参数的取值对最后的求解性能有很大的影响，目前还是靠值对最后的求解性能有很大的影响，目前还是靠经验对各个参数取值。在分析各个参数的作用及经验对各个参数取值。在分析各个参数的作用及对算法性能的影响的基础上，并通过大量实验验对算法性能的影响的基础上，并通过大量实验验证，给出了蚁群算法中各参数的一个较理想取值证，给出了蚁群算法中各参数的一个较理想取值范围范围。Page 22五五 研究中可能遇到的问题研究中可能遇到的问题n 问题一 蚁群算法参

26、数选择很重要，选择不当的话会出现搜索的过早停滞现象或陷入局部最优问题。n 问题二 蚁群算法对非线性系统辨识中对 输入信号的选择是一个难点。Page 23结论结论 蚁群算法解决了蚁群算法解决了TSPTSP问题只是解决了众多组合优化问题的一种，问题只是解决了众多组合优化问题的一种，但是围绕着但是围绕着TSPTSP问题的解决才有了蚁群算法的发展和创新，它涉及了问题的解决才有了蚁群算法的发展和创新，它涉及了仿生学，程序设计学，计算机科学仿真技术多个学科，是信息处理仿生学，程序设计学，计算机科学仿真技术多个学科，是信息处理领域中的一项前沿技术。本文的前期工作是介绍了基本蚁群算法的领域中的一项前沿技术。本文的前期工作是介绍了基本蚁群算法的原理和蚁群算法的机制原则。原理和蚁群算法的机制原则。 在本文中，对蚁群算法的基本原理以及在本文中，对蚁群算法的基本原理以及TSPTSP问题做了基本的介绍，问题做了基本的介绍，在此基础上提出了改进的蚁群算法并通过数值模拟实验结果的比较在此基础上提出了改进的蚁群算法并