服装企业网站模板,wordpress延迟加载js,网站快速刷排名工具,wordpress主题选项【人工智能Ⅰ】4-蚁群算法 文章目录 【人工智能Ⅰ】4-蚁群算法4.1 群智能概述群群智能 4.2 蚁群算法ACO概念特征 4.3 ACO伪代码4.4 TSP问题中的应用【1】初始化【2】选择路径【3】更新信息【4】输出结果 4.5 ACO基本思想4.6 关键参数选取4.7 算法参数设计策略组合参数设计策略终…【人工智能Ⅰ】4-蚁群算法 文章目录 【人工智能Ⅰ】4-蚁群算法4.1 群智能概述群群智能 4.2 蚁群算法ACO概念特征 4.3 ACO伪代码4.4 TSP问题中的应用【1】初始化【2】选择路径【3】更新信息【4】输出结果 4.5 ACO基本思想4.6 关键参数选取4.7 算法参数设计策略组合参数设计策略终止条件 4.8 改进的ACO4.9 一般ACO的框架组成4.10 ACO应用4.11 与其他算法的比较 4.1 群智能概述
群
群swarm平等的、相互间能够协调运动的个体的集合
个体群的每个成员
群成员之间是平等关系没有主从关系
群智能
个体——简单智能群体——高级智能
群成员的集体运动以及他们之间的相互作用是从每个群成员个体所遵循的一些简单行为规则自底向上的一种突现
1蚁群行为
三个选择机制
路径概率选择机制信息素浓度高的路线
信息素更新机制短路径增长快
协同工作机制个体间信息素传递信息
2鸟群行为
两个社会行为要素
个体经验学习单个个体
社会学习学习鸟群
3鱼群行为
四个游动行为
觅食行为向食物方向游动
追尾行为向视野内的其他觅食行为的鱼游动
聚群行为避免被捕食向同类多的地方游动
随机行为无目的游动
4.2 蚁群算法ACO
概念
在图中寻找优化路径的机率型算法
核心机制
1信息素蚂蚁途径的地方留下信息素越多蚂蚁经过越多信息素
2正反馈现象信息素越多的路径蚂蚁选择概率越大
人工蚁群 和 自然蚁群 的不同
1人工蚁群有记忆能力
2人工蚁群会针对性选择路径即不是盲目选择
特征
1原理是一种正反馈机制或增强型学习系统信息素的不断更新导致路径收敛于近似最优解
2通用型随机优化实际情况 人工智能
3分布式优化串行计算机 并行计算机
4全局优化单目标优化问题 多目标优化问题
5启发式算法复杂度为O(epoch × m × n × n)epoch是迭代次数、m是蚂蚁数、n是节点数
4.3 ACO伪代码
1开始
2初始化
3迭代次数NCNC1
4蚂蚁数k1
5蚂蚁数kk1
6按照状态转移概率公式选择下一个元素
7修改禁忌表
8判断k是否大于蚂蚁总数m若是则进入9否则继续进入4
9按照公式更新信息素
10判断是否满足结束条件若是则进入11否则继续进入3
11输出程序计算结果
12结束
4.4 TSP问题中的应用
【1】初始化
将m只蚂蚁随机放到n个城市每只蚂蚁的禁忌表人工蚁群的记忆功能旨在不走重复道路是蚂蚁当前所在城市各边信息素初始化为c
【2】选择路径
t时刻蚂蚁k从城市i走到城市j的概率 P k ( i , j ) [ ε ( i , j ) ] α ∗ [ η ( i , j ) ] β / Σ s ∈ J k ( i ) 当 j ∈ J k 时否则为 0 P^k(i,j)[ε(i,j)]^α*[η(i,j)]^β/Σ_{s∈J_k(i)}当j∈J_k时否则为0 Pk(i,j)[ε(i,j)]α∗[η(i,j)]β/Σs∈Jk(i)当j∈Jk时否则为0 T_k保存每只蚂蚁k已经访问过的城市集合
J_k没有访问过的城市集合大小是N-T_k
α信息素对蚂蚁选择路径的影响程度若为0则变为选择最近城市
β距离对蚂蚁选择路径的影响程度若为0则只根据信息素浓度确定路径
ε(i,j)边L(i,j)上的信息素强度
η(i,j)城市i到城市j的期望程度 η ( i , j ) 1 / d i j η(i,j)1/d_{ij} η(i,j)1/dij 合适的α与β范围 α[1,2] β[2,5] 【3】更新信息
在所有蚂蚁找到一条合法路径后更新信息 ε i j ( t 1 ) ( 1 − ρ ) ε i j ( t ) Σ m Δ ε i j k ( t , t 1 ) ε_{ij}(t1)(1-ρ)ε_{ij}(t)Σ_mΔε_{ij}^{k}(t,t1) εij(t1)(1−ρ)εij(t)ΣmΔεijk(t,t1) Δ ε i j k ( t , t 1 ) Q / L k 当蚂蚁经过 i , j 时否则为 0 Δε_{ij}^{k}(t,t1)Q/L_k当蚂蚁经过i,j时否则为0 Δεijk(t,t1)Q/Lk当蚂蚁经过i,j时否则为0
ρ信息素的挥发速率是小于1的正数 合适的ρ范围 ρ0.5 作用防止信息素积累提高搜索能力 Δε所有蚂蚁在这轮运行在边(i,j)上增加的信息素强度
Δε^k蚂蚁k在边(i,j)上增加的信息素强度
Q蚂蚁所留轨迹正常数
L_k蚂蚁k在这轮运行走过的路径长度和
【4】输出结果
若未达到终止条件则继续【2】否则输出最优解
蚁群大小根据计算规模确定
终止条件
1-外循环的最大数目有足够蚂蚁工作
2-最优解连续K次相同K为给定整数算法已收敛
3-目标值控制目标值与给定下界的差小于给定误差值
4.5 ACO基本思想
1根据具体问题设置多只蚂蚁分头并行搜索
2每只蚂蚁完成一次周游后在行进的路上释放信息素信息素量与解的质量成正比
3蚂蚁路径的选择根据信息素强度大小初始信息素量设为相等同时考虑两点之间的距离采用随机的局部搜索策略。这使得距离较短的边其上的信息素量较大后来的蚂蚁选择该边的概率也较大
4每只蚂蚁只能走合法路线经过每个城市1次且仅1次为此设置禁忌表来控制
5所有蚂蚁都搜索完一次就是迭代一次每迭代一次就对所有的边做一次信息素更新原来的蚂蚁死掉新的蚂蚁进行新一轮搜索
6更新信息素包括原有信息素的蒸发和经过的路径上信息素的增加
7达到预定的迭代步数或出现停滞现象所有蚂蚁都选择同样的路径解不再变化则算法结束以当前最优解作为问题的解输出
4.6 关键参数选取
1蚂蚁数量m
过大信息素变化趋于平均
过小未搜索路径信息素提前减到0 一般情况m1.5MM是城市数量 2信息素因子α
过大选择走以前的路径概率大
过小提前局部最优 一般情况α[1,4] 3启发函数因子β
过大提前局部最优
过小随机搜索 一般情况β[3,4.5] 4信息素挥发因子ρ 一般情况ρ[0.2,0.5] 5信息素常数Q
越大已遍历路径的信息素积累越快有利于收敛 一般情况Q[10,1000] 6最大迭代次数epoch
过大资源浪费
过小算法未收敛就结束 一般情况epoch[100,500] 建议起初epoch200然后根据收敛轨迹修改 4.7 算法参数设计策略
组合参数设计策略
1确定mm1.5M
2粗调即调整取值范围较大的α、β、Q
3微调即调整取值范围较小的ρ
终止条件
1给定外循环的最大数目
2最优解连续K次相同已收敛
4.8 改进的ACO
ASelite最优解保留策略蚂蚁系统精英策略
ACS蚁群系统
MMAS最大-最小蚂蚁系统
ASrank基于优化排序的蚂蚁系统
BWAS最优最差蚂蚁系统
AACA一种自适应蚁群算法
HBACA基于混合行为的蚁群算法
4.9 一般ACO的框架组成
1蚁群活动
2信息素挥发
3信息素增强
主要体现转移概率公式 信息素更新公式p和ε
4.10 ACO应用
1网络路由问题
2电力系统领域
3航迹规划问题
4混流装配线调度
4.11 与其他算法的比较
解质量ACO GA 退火
收敛速度ACO GA 退火ACO个体之间不断进行信息交流和传递
