毕业论文答辩--蚁群算法研究及应用.ppt

蚁群算法研究及其应用 主要内容 1:论文研究背景 2:本文改进算法 3:蚁群算法参数组合优化 4:TSP仿真系统介绍 5:本文结论 6:致谢 研究背景——蚁群算法原理 蚂蚁算法是一种用来寻找最优解决方案的机率型技术,其灵感来源于蚂蚁在寻找食物过程中发现最短路径的行为. 自然蚂蚁寻找食物行为：蚂蚁在路径上前进时会根据前边走过的蚂蚁所留下的分泌物(信息素)选择其要走的路径。其选择一条路径的概率与该路径上分泌物的强度成正比。因此，由大量蚂蚁组成的群体的集体行为实际上构成一种学习信息的正反馈现象：某一条路径走过的蚂蚁越多，后面的蚂蚁选择该路径的可能性就越大。蚂蚁的个体间通过这种信息的交流寻求通向食物的最短路径。 这种优化过程的本质: 协调机制：蚂蚁间实际上是通过分泌物来互相通信、协同工作的。 选择机制：信息素越多的路径，被选择的概率越大。 更新机制：路径上面的信息素会随蚂蚁的经过而增长，而且同时也随时间的推移逐渐挥发消失。 研究背景——蚁群算法数学模型(1) 初始时刻( )，各条路径上的信息素相等. 选择机制：在 t( ) 时刻，蚂蚁在运动过程中根据各条路 径上信息素和路径长度因素共同决定移动方向，蚂蚁由位 置i移动到位置j 的转移概率的计算公式如下: 本文以著名的旅行商问题(TSP)为例，建立蚁群算法数学模型，该问 题可以描述为：一个旅行商从n个城市的某一出发个访问其他所有城市一 次且仅一次后再回到出发城市，要求找出一条最短的路径；该问题可抽象 像为求完全图( n个节点)的最短路径问题。 更新机制：在 t+n时刻，此时所有的蚂蚁完成了一次遍历，为了避免 残留信息素过多而淹没距离因素，在每只蚂蚁走完一步或者迭代一次后 ，要对路径上的信息素进行更新操作，各路径上信息素可根据以下公式 做调整： 根据计算方式不同，有蚁周模型、蚁量模型和蚁密模型三种基本模型 ，本文的研究都是基于蚁周模型的，其模型为： 研究背景——蚁群算法数学模型(2) 研究背景——蚁群算法研究方向 算法理论改进 参数分析 应用推广 数学证明 1:算法易出现局部最优、停滞等不良现象 2:在求解较大规模问题时，算法的运行时间过长 3:算法的收敛速度慢 4:算法参数的设置带有很强的经验性和随机性，没有严格的理论认证 研究表明蚁群算法具有较强的鲁棒性、分布式计算、易于与其优化算法结合等优点；但随着问题规模的扩大，算法的运行时间和最优解都不能认人满意，性能明显下降。大量研究表明蚁群算法也存在一些不足，主要有： 蚁群算法研究方向: 算法改进——研究背景 针对蚁群算法存在的不足，国内外学者开展了大量有意义的研究。研究成果主要涉及路径搜索策略、信息素更新策略和最优解保留策略等方面；研究行为主要是进行算法改进或验证。有些改进算法的性能相比基本蚁群算法而言有了较大水平的提高，如最大最小蚁群算法是目前求解TSP问题的最好方法之一；有些已成为主流的蚁群算法,如：蚁群系统，基于排序的蚁群系统，最优最差蚁群系统等。 针对基本蚁群算法的不足，本文在借鉴其他算法优点的基础上提出一种改进的蚁群算法。该算法从以下几个方面对基本蚁群算法进行了改进： 1:初始信息素的改进 2:路径选择策略的改进 3:信息素更新策略的改进 本文算法改进——研究过程(1) 基本蚁群算法中，路径上的初始信息素大小是相同的，蚁群创建的第一条路径所获得的信息主要是城市之间的距离信息，此时，蚁群算法相当于贪婪算法。第一次循环中蚁群在所经过的路径上留下的信息素不一定能反映出最优路径的方向。正反馈的作用会使得这条不是最优解的路径上的信息素得到不应有的增强，阻碍以后的蚂蚁发现更好的全局最优解。为此，本文改进算法在任意两个城市之间安排的信息素是等量的,但是这等量的信息素要平均到两个之间的路径上,由于城市之间的距离是不相同的,所以平均到每一小段上的信息素量就是距离的倒数与分配到这两城市之间的信息素量之积。为提高初始阶段蚂蚁的搜索能力，改进算法将各路径上的初始信息素的值按照最大最小蚁群算法思想限定其大小。所以其数学模型为： 1：初始信息素 本文算法改进——研究过程(2) 2:路径选择策略的改进 相关文献表明，自然蚂蚁无视觉能力，无法感知距离的远近,在节点选择 时，仅能依靠信息素浓度。为更好的模拟自然蚂蚁,本文改进算法在选择 下一个城市时不再考虑距离因素,仅考虑信息素浓度。同时为有效的提高 优化速度,降低局部最优解停滞的可能性,本文采用伪随机性选择策略,并在搜索过程中动态地调整确定性选择的概率。即蚂蚁 在 t时刻有城市 i 到城市 j 的转移概率由下式确定： 3:信息素更新策略策略的改进 本文算法改进——研究过程(3) 两层信息素更新策略： 第