您好,欢迎访问三七文档
当前位置:首页 > 行业资料 > 交通运输 > 基于蚁群算法的路径最优研究---毕业答辩
导师:王康平答辩人:刘媛媛专业:计算机科学与技术基于蚁群算法的路径最优问题研究Page2论文的结构和主要内容第一部分选题的背景与意义第二部分国内外研究现状第三部分研究内容与方法第四部分研究中可能存在的问题第五部分预期结果Page3一选题背景与意义2001年至今1996年-2001年意大利学者Dorigo1991年启发Page4一选题背景与意义蚁群算法的由来:蚂蚁是地球上最常见、数量最多的昆虫种类之一,常常成群结队地出现在人类的日常生活环境中。这些昆虫的群体生物智能特征,引起了一些学者的注意。意大利学者M.Dorigo,V.Maniezzo等人在观察蚂蚁的觅食习性时发现,蚂蚁总能找到巢穴与食物源之间的最短路径。经研究发现,蚂蚁的这种群体协作功能是通过一种遗留在其来往路径上的叫做信息素(Pheromone)的挥发性化学物质来进行通信和协调的。化学通信是蚂蚁采取的基本信息交流方式之一,在蚂蚁的生活习性中起着重要的作用。通过对蚂蚁觅食行为的研究,他们发现,整个蚁群就是通过这种信息素进行相互协作,形成正反馈,从而使多个路径上的蚂蚁都逐渐聚集到最短的那条路径上。Page5二国内外研究现状目前,蚁群算法己经成为一个备受关注的研究热点和前沿性课题。人们对蚁群算法的研究已经由当初的TSP领域渗透到多个应用领域,由解决一维静态优化问题发展到解决多维动态组合优化问题,由离散域范围内研究逐渐拓展到了连续域范围内研究。同时在蚁群算法的模型改进以及其他仿生优化算法的融合方面也取得了相当丰富的研究成果,从而使这种新兴的仿生优化算法展现出前所未有的生机。Page6三研究内容与方法1.基本蚁群算法及其改进算法(1)基本蚁群算法(2)蚁群系统(3)最大-最小蚂蚁系统2.蚁群算法与TSP应用(1)蚁群算法的思想、原理(2)蚁群算法的实现方式(3)TSP应用举例Page73.1.1蚁群算法的基本思想在自然界中,蚂蚁的食物源往往随机散布于蚁巢周围,通过观察可以发现,经过一段时间后,蚂蚁总能找到一条从蚁巢到食物源的最短路径。自然界中的蚂蚁虽然视觉能力十分有限,但它们在觅食过程中,却能够通过播撒、感知信息素与其它同伴建立起通讯关系,并以此相互协调、分工、合作来找到食物源和巢穴之间的最短路径。并且在相同的时间内,路径越短则遗留的信息素浓度就越大,而蚂蚁在选择路径时,倾向于那些信息素浓度较高的路径,这样选择较短路径的蚂蚁也随之增多。因此,由大量蚂蚁组成的蚁群集体觅食行为表现出了一种正反馈现象:一条路径上走过的蚂蚁越多,则后来者选择这条路径的概率就越高。蚂蚁个体之间就是通过这种信息素的交流机制,来搜索食物,并最终找到最短路径。Page83.1.2蚂蚁觅食原理:自然界中,蚂蚁这种视盲生物,在没有任何先知经验的情况下总能找到从其巢穴到食物源的最佳路径,甚至在该路径上放置障碍物之后,它们仍然能很快重新找到新的最佳路线。Page9蚂蚁觅食原理这是因为在蚂蚁个体之间是通过一种称为信息素的物质进行信息传递的。蚂蚁在运动过程中,不但能够在它所经过的路径上留下该物质,而且能够感知这种物质的存在及其强度,并朝着该物质强度高的方向移动,为此指导自己的运动方向。因此,由大量蚂蚁组成的蚁群集体行为表现出一种信息正反馈现象。在一定时间内较短路径通过的蚂蚁要多于较长路径,而某一路径上走过的蚂蚁越多,则后来的蚂蚁选择该路径的概率就越大。蚁群算法的基本原理简单来说就是:1、蚂蚁在路径上释放信息素。2、碰到还没走过的路口,就随机挑选一条路走。同时,释放与路径长度有关的信息素。3、信息素浓度与路径长度成反比。后来的蚂蚁再次碰到该路口时,就选择信息素浓度较高路径。4、最优路径上的信息素浓度越来越大.5、最终蚁群找到最优寻食路径。Page103.1.3蚁群算法的优缺点蚁群算法的优点不依赖于所求问题的具体数学表达式描述,具有很强的找到全局最优解的优化能力。该算法具有正反馈、较强的鲁棒性、全局性、普遍性、优良的分布式并行计算机制、易于与其他方法相结合等诸多优点。Page11蚁群算法的缺点:蚁群算法的成功主要在实验层次上,很少有理论来解释利用蚁群算法为什么能够成功地解决这些问题,它没有坚实的数学基础;蚁群算法的模型普适性不强,其模型不能直接应用于实际优化问题;蚁群算法的局部搜索能力较弱,易于出现停滞和局部收敛、收敛速度慢等问题,因而往往需要嵌入一些专门的辅助技巧;长时间花费在解的构造上,从而导致搜索时间过长,算法最先基于离散问题,不能直接解决连续优化问题。Page123.2自然蚁群与人工蚁群蚁群算法都是从自然界中真实蚂蚁寻找食物行为得到启发提出来的。人们只有通过对蚁群行为的一种模拟来满足实际问题的求解需要。所以人工蚁群与真实蚁群之间存在一定的异同。相似之处在于:都是优先选择信息素浓度大的路径。两者的区别:(1)在于人工蚁群有一定的记忆能力,能够记忆已经访问过的节点。(2)人工蚁群选择路径时不是盲目的。而是按一定规律有意识地寻找最短路径。例如,在TSP问题中,可以预先知道当前城市到下一个目的地的距离。Page133.3.1基本蚁群算法()kijPt()(),()()()0,kisiskkisisijxallowkttsallowttPtsallow蚂蚁k(k=1,2,…,m)根据各个城市间连接路径上的信息素浓度决定其下一个访问城市,设表示t时刻蚂蚁k从城市i转移到城市j的概率,其计算公式为:信息更新公式为:1(1)(1)(),01ijijijnkijiikttPage14针对蚂蚁释放信息是问题,M.Dorigo等人曾给出3中不同的模型,分别为蚁周系统、蚁量系统和蚁密系统,其计算公式如下:1.蚁周系统模型2.蚁量系统模型3.蚁密系统模型ij/kij0,kiiQd,第只蚂蚁从城市访问城市其他kij0,kiiQ,第只蚂蚁从城市访问城市其他/kij0,kkiiQL,第只蚂蚁从城市访问城市其他其中,Q为常数,表示蚂蚁循环一次所释放的信息素总量;L为第k只蚂蚁经过路径的长度。d为城市间的距离。Page153.3.2蚁群系统蚁群系统的状态转移规则一只位于节点r的蚂蚁通过应用下式给出的规则选择下一个将要移动到的城市s:其中,S根据下列公式得到q是在[0,1]区间均匀分布的随机数q0的大小决定了利用先验知识与探索新路径之间的相对重要性。0argmax{[(,)][(,)]},,kuallowedruruqqsS如果按先验知识选择路径否则()(),()()()0,kijijkkisisijsallowedttjallowedttPtotherwisePage161,(,)0,gbLrs如果(r,s)全局最优路径否则蚂蚁系统全局更新原则只有全局最优的蚂蚁才被允许释放信息素。目的:使蚂蚁的搜索主要集中在当前循环为止所找出的最好路径领域内。全局更新在所有蚂蚁都完成它们的路径之后执行,试用下式对所建立的路径进行更新:为信息素挥发因数,01。为到目前为止找出的全局最优路径。gbL(,)(1)(,)(,)rsrsrsPage17蚁群系统局部更新原则蚂蚁应用下列局部更新原则对它们所经过的边进行激素更新:实验发现,可以产生好的结果,其中n是城市的数量,是由最近的邻域启发产生的一个路径长度。局部更新原则可以有效的避免收敛到同一路径。(,)(1)(,)(,)01rsrsrs其中,为一个参数,01nnnLnnLPage183.3.3最大-最小蚂蚁系统(1)()ijbestijijtt1()ijbestbestfs()bestfs信息素轨迹更新在MMAS中,只有一只蚂蚁用于在每次循环后更新信息轨迹。经修改的轨迹更新原则如下:表示迭代最优解或全局最优解的值。在蚁群算法中主要使用全局最优解,而在MMAS中则主要使用迭代最优解。Page19MMAS对信息素轨迹的最小值和最大值分别施加了和的限制,从而使得对所有信息素轨迹,有minmax()ijtminmax()ijtmaxmax11()()ijttioptitfsopt其中,f(s)为对于一个具体问题的最优解min信息素轨迹的限制的选取:的选取要基于两点假设:最优解在搜索停滞发生之前不久被找出。对解构造的主要影响是由信息素轨迹的上限与下限之间的相对差异决定。Page203.4蚁群算法的实现(1)参数初始化。令时间t=0和循环次数Nc=0,设置最大循环次数Ncmax,将m个蚂蚁置于n个元素(城市)上,令有向图上每条边(i,j)的初始化信息量τij(t)=const,其中const表示常数,且初始时刻Δτij(0)=0(2)循环次数Nc←Nc+1。(3)蚂蚁的禁忌表索引号k=1。(4)蚂蚁数目k←k+1。(5)蚂蚁个体根据状态转移概率公式(1)计算的概率选择元素(城市)j并前进,j∈{C-tabuk}。(6)修改禁忌表指针,即选择好之后将蚂蚁移动到新的元素(城市),并把该元素(城市)移动到该蚂蚁个体的禁忌表中。(7)若集合C中元素(城市)未遍历完,即km,则跳转到第(4)步,否则执行第(8)步。(8)根据公式(2)和式(3)更新每条路径上的信息量。(9)若满足结束条件,即如果循环次数Nc≥Ncmax则循环结束并输出程序计算结果,否则清空禁忌表并跳转到第(2)步。Page21四预期结果对于信息素挥发因子ρ、启发式因子α、自启发因子β、蚂蚁的数目m对于蚁群算法性能的影响进行了实验研究,发现蚁群算法中各个参数的取值对最后的求解性能有很大的影响,目前还是靠经验对各个参数取值。在分析各个参数的作用及对算法性能的影响的基础上,并通过大量实验验证,给出了蚁群算法中各参数的一个较理想取值范围。Page22五研究中可能遇到的问题问题一蚁群算法参数选择很重要,选择不当的话会出现搜索的过早停滞现象或陷入局部最优问题。问题二蚁群算法对非线性系统辨识中对输入信号的选择是一个难点。Page23结论蚁群算法解决了TSP问题只是解决了众多组合优化问题的一种,但是围绕着TSP问题的解决才有了蚁群算法的发展和创新,它涉及了仿生学,程序设计学,计算机科学仿真技术多个学科,是信息处理领域中的一项前沿技术。本文的前期工作是介绍了基本蚁群算法的原理和蚁群算法的机制原则。在本文中,对蚁群算法的基本原理以及TSP问题做了基本的介绍,在此基础上提出了改进的蚁群算法并通过数值模拟实验结果的比较证明了算法的有效性和实用性。主要工作包括以下几个方面:1、对基本蚁群算法的原理、算法的实现步骤进行了总结,并给出了应用基本蚁群算法求解TSP问题的基本步骤。2、本文的重点是利用蚁群算法解决TSP问题,并利用C++语言对其进行了测试,重点讨论了如何通过选择合理参数配置蚁群算法性能得到提高,并用大量实验结果予以证明。Page24由于作者的知识水平的限制,本文的工作还存在着较多的不足之处。比如用改进的蚁群算法求解大型的TSP问题结果就差一些,并且运行时间很长,效果不是很理想。本文所提出的改进的算法还只是应用于旅行商问题,对于一定的旅行商问题的求解有了提高,但对其他的算法是否适用还有待探讨。Page25大学本科的学习生活即将结束。在此,我要感谢所有曾经教导过我的老师和关心过我的同学,他们在我成长过程中给予了我很大的帮助。本文能够顺利完成,要特别感谢我的导师王康平老师,还有郭力争老师,感谢各位系的老师的关心和帮助。最后向所有关心和帮助过我的人表示真心的感谢。致谢Page26
本文标题:基于蚁群算法的路径最优研究---毕业答辩
链接地址:https://www.777doc.com/doc-5718325 .html