文档介绍：蚁群算法研究及其应用
编辑课件
主要内容
1:论文研究背景
2:本文改进算法
3:蚁群算法参数组合优化
4:TSP仿真系统介绍
5:本文结论
6:致谢
编辑课件
研究背景——蚁群算法原理
蚂蚁算法是一种用来寻找最优解决方：
编辑课件
3:信息素更新策略策略的改进
本文算法改进——研究过程(3)
两层信息素更新策略：
第1层:原有信息素的挥发
第2层:借鉴奖惩蚁群算法思想，在完成每次循环进行信息素挥发后，根据蚂蚁所建立路径的长短，进行排序，只有前w只建立短路径的蚂蚁被挑选出来进行奖励，其
他 (m-w )只建立路径的蚂蚁进行惩罚。
最大最小蚁群算法思想：若某段路径弧段的信息素相对其他路径弧段的信息
素而言在数量上占据绝对的优势时,会引起算法过早地收敛。对这一不足,本文借
鉴MMAS思想,对各路径上的信息素量施加最小最大限制。
采用两层信息素更新策略和最大最小蚁群算法思想
编辑课件
开始
初始化
蚂蚁构建路径
所有蚂蚁结束？
路径排序
信息素更新
满足结束条件？
结束
N
Y
N
Y
本文算法改进——算法流程
编辑课件
本文算法改进——性能验证
算法
平均最优解
平均迭代次数
平均运行时间(s)
基本蚁群算法

124
29
最大最小蚁群算法

98
29
本文改进算法

104
23
文献[48]算法

未知
31
文献[49]算法

未知
33
TSP51问题各算法性能比较表
算法
平均最优解
平均迭代次数
平均运行时间
基本蚁群算法

238
39
最大最小蚁群系统

198
34
本文改进算法

189
26
TSP76问题的实验结果
编辑课件
编辑课件
参数组合优化——研究背景
蚁群算法的参数数目众多，参数对算法性能的影响较大。文献表明:蚁群算法参数的合理组合能够在一定程度上提高算法的全局搜索能力和加快算法的收敛速度，但遗憾的是，目前各参数该如何取值只是根据经验来选取合适的参数值。
针对蚁群算法参数空间大、参数选择难的问题，本文对蚁群算法参数的组合优化问题进行了讨论。采用实例仿真法确定各个参数的合理取值区间，采用粒子群算法首次对蚁群算法的五个重要参数的组合优化问题进行了探讨，提出了基于粒子群的蚁群算法参数最优组合优化方案。
编辑课件
参数组合优化——研究过程
提出问题:本文将蚁群算法抽象为一个函数，其五个参数为函数的自变量，则有函数，那么参数的连续区域优化问题可以定义为：确定蚁群算法五个主要参数的值，使得函数取得最优值。由这个定义我们自然地可以将参数的优化看成一个组合优化问题，而且是一个连续域的组合优化问题。
选定方法:粒子群算法，因粒子群优化算法具有很强的全局优化能力，能较快地收敛于可接受解；而且粒子群优化算法参数少，算法简单易实现，效率较高。
解决问题:
实例仿真法：综合考虑算法的全局搜索能力和收敛速度两项性能指标，确定各参数的合理区间.
采用“三步走”策略确定蚁群算法参数的较优组合：
(1)利用实例仿真法确定的各个参数的合理区间
(2)利用粒子群优化算法，确定参数的最佳组合
(3)多次结果，求平均
编辑课件
结束
初始化
生成粒子群
循环迭代
求全局最佳位置以及最优适应度函数值
求每个粒子个体最佳位置
移动粒子
更新粒子速度向量
满足循环条件？
开始
N
Y
Y
N
参数组合优化——关键技术
编辑课件
参数组合优化——有效性验证
参数类型
组次
参数取值
最优路径长度
参数最
佳组合
1

34

4

2

33

5

3

30

5

4

34

6

参数随
机组合
5

20

1

6

34

8

7

40

9

8

28

4