文档介绍：硕士毕业论文答辩(参考)
之蚁群算法研究及其应用
主要内容
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:信息素更新策略的改进
本文算法改进——研究过程(2)
2:路径选择策略的改进
相关文献表明,自然蚂蚁无视觉能力,无法感知距离的远近,在节点选择
时,仅能依靠信息素浓度。为更好的模拟自然蚂蚁,本文改进算法在选择
下一个城市时不再考虑距离因素,仅考虑信息素浓度。同时为有效的提高
优化速度,降低局部最优解停滞的可能性,本文采用伪随机性选择策略,并在搜索过程中动态地调整确定性选择的概率。即蚂蚁在 t时刻有城市 i 到城市 j 的转移概率由下式确定:
3:信息素更新策略策略的改进
本文算法改进——研究过程(3)
两层信息素更新策略:
第1层:原有信息素的挥发
第2层:借鉴奖惩蚁群算法思想,在完成每次循环进行信息素挥发后,根据蚂蚁所建立路径的长短,进行排序,只有前w只建立短路径的蚂蚁被挑选出来进行奖励,其
他(m-w )只建立路径的蚂蚁进行惩罚。
最大最小蚁群算法思想:若某段路径弧段的信息素相对其他路径弧段的信息
素而言在数量上占据绝对的优势时,会引起算法过早地收敛。对这一不足,本文借
鉴MMAS思想,对各路径上的信息素量施加最小最大限制。
采用两层信息素更新策略和最大最小蚁群算法思想