群智能算法教学讲义.docx
- 文档编号:13578836
- 上传时间:2023-06-15
- 格式:DOCX
- 页数:30
- 大小:24.68KB
群智能算法教学讲义.docx
《群智能算法教学讲义.docx》由会员分享,可在线阅读,更多相关《群智能算法教学讲义.docx(30页珍藏版)》请在冰点文库上搜索。
群智能算法教学讲义
第六章群智能算法
智能优化计算
6.1群智能
6.1.1群智能的概念
6.1.2群智能算法
6.2蚁群优化算法原理
6.2.1蚁群算法的起源
6.2.2蚁群算法的原理分析
6.3基本蚁群优化算法
6.3.1蚂蚁系统的模型与实现
6.3.2蚂蚁系统的参数设置和基本属性
6.4改进的蚁群优化算法
6.4.1蚂蚁系统的优点与不足
6.4.2最优解保留策略蚂蚁系统
6.4.3蚁群系统
6.4.4最人一最小蚂蚁系统
6.4.5基于排序的蚂蚁系统
6.4.6各种蚁群优化算法的比较
智能优化计算
6.5蚁群优化算法的应用
6.5.1典型应用
6.5.2医学诊断的数据挖掘
6.6粒子群算法的基本原理
6.6.1粒子群算法的提出
6.6.2粒子群算法的原理描述
6.7基本粒子群优化算法
6.7.1基本粒子群算法描述
6.7.2参数分析
6.7.3与遗传算法的比较
6.8改进粒子群优化算法
6.8.1离散二进制PSO
6.8.2惯性权重模型
6.8.3收敛因子模型
6.8.4研究现状
智能优化计算
6.9粒子群优化算法的应用
6.9.1求解TSP问题
6.9.2其它应用
6.10群智能算法的特点与不足
智能优化计算
6.1群智能
智能优化计算
群智能(SwarmIntelligence,SI)
人们把群居昆虫的集体行为称作“群智能”(“群体智能”、“群集智能”、“集群智能”等)
特点
个体的行为很简单,但当它们一起协同工作时,却能够突现出非常复杂(智能)的行为特征。
6.1.1群智能的概念
6.1群智能
智能优化计算
描述
群智能作为一种新兴的演化计算技术已成为研究焦点,它与人工生命,特别是进化策略以及遗传算法有着极为特殊的关系。
特性
指无智能的主体通过合作表现出智能行为的特性,在没有集中控制且不提供全局模型的前提下,为寻找复杂的分布式问题求解方案提供了基础。
6.1.2群智能算法
6.1群智能
智能优化计算
优点
灵活性:
群体可以适应随时变化的环境;
稳健性:
即使个体失败,整个群体仍能完成任务:
自我组织:
活动既不受中央控制,也不受局部监管。
典型算法
蚁群算法(蚂蚁觅食)
粒子群算法(鸟群捕食)
6.1.2群智能算法
6.2蚁群优化算法原理
智能优化计算
蚁群的自组织行为
“双桥实验”
通过遗留在来往路径
上的信息素
(Pheromone)的挥
发性化学物质来进行
通信和协调。
6.2.1蚁群算法的起源
6.2蚁群优化算法原理
智能优化计算
蚁群的自组织行为
“双桥实验”
6.2.1蚁群算法的起源
6.2蚁群优化算法原理
智能优化计算
提出蚁群系统
1992年,意大利学者M.Dorigo在其博士论文中提出
蚂蚁系统(AntSystem)。
近年来,M.Dorigo等人进一步将蚂蚁算法发展为一种通用的优化技术一一蚁群优化(antcolonyoptimization,ACO)。
6.2.1蚁群算法的起源
蚂蚁从A点出发,随机选择路线ABD或ACD。
经过9个时间单位时:
走ABD的蚂蚁到达终点,走ACD的蚂蚁刚好走到C点。
6.2蚁群优化算法原理
智能优化计算
6.2.2蚁群算法的原理分析
蚁巢
食物
6.2蚁群优化算法原理
智能优化计算
经过18个时间单位时:
走ABD的蚂蚁到达终点后得到食物又返回了起点A,而走ACD的蚂蚁刚好走到D点。
6.2.2蚁群算法的原理分析蚁巢食•物
最后的极限是所有的蚂蚁只选择ABD路线。
(正反馈过程)
6.2蚁群优化算法原理
智能优化计算
6.2.2蚁群算法的原理分析
蚁巢
食物
6.3基本蚁群优化算法
智能优化计算
解决TSP问题
在算法的初始时刻,将m只蚂蚁随机放到n座城市;
将每只蚂蚁k的禁忌表tabuk(s)的第一个元素tabuk(l)设置为它当前所在城市;
设各路径上的信息素tij(O)=C(C为一较小的常数);
6.3.1蚂蚁系统的模型与实现
6.3基本蚁群优化算法
智能优化计算
解决TSP问题
每只蚂蚁根据路径上的信息素和启发式信息(两城市间距离)独立地选择下一座城市:
在时刻t,蚂蚁k从城市i转移到城市j的概率为
a、B分别表示信息素和启发式因子的相对重要程度。
6.3.1蚂蚁系统的模型与实现
下一步允许的城市的集合
6.3基本蚁群优化算法
智能优化计算
解决TSP问题
当所有蚂蚁完成一次周游后,各路径上的信息素将进行更新:
其中,P(0
6.3.1蚂蚁系统的模型与实现
6.3基本蚁群优化算法
智能优化计算
算法流程
6.3.1蚂蚁系统的模型与实现
6.3基本蚁群优化算法
智能优化计算
初始参数
城市数30;
蚂蚁数30:
a=l;
P=5;
p=0.5;
最大迭代代数200;
Q=100;
6.3.1蚂蚁系统的模型与实现
6.3基本蚁群优化算法智能优化计算运行结果
6.3.1蚂蚁系统的模型与实现
6.3基本蚁群优化算法智能优化计算运行结果
6.3.1蚂蚁系统的模型与实现
6.3基本蚁群优化算法智能优化计算运行结果
6.3.1蚂蚁系统的模型与实现
6.3基本蚁群优化算法智能优化计算运行结果
6.3.1蚂蚁系统的模型与实现
6.3基本蚁群优化算法智能优化计算运行结果
6.3.1蚂蚁系统的模型与实现
6.3基本蚁群优化算法智能优化计算运行结果
6.3.1蚂蚁系统的模型与实现智能优化计算三种模型
ant-cycle:
(蚁周)
ant-quantity:
(蚁量)
ant-density:
(蚁密)
6.3基本蚁群优化算法
6.3.1蚂蚁系统的模型与实现
智能优化计算
三种模型
在Ant-density和Ant-quantity中蚂蚁在两个位置节点间每移动一次后即更新信息素(局部信息),而在Ant-cycle中当所有的蚂蚁都完成了自己的行程后(全局信息)才对信息素进行更新。
6.3基本蚁群优化算法
6.3.1蚂蚁系统的模型与实现
智能优化计算三种模型的比较
模型ant-density,ant-quantity,ant-cycle的比较(M.Dorigoz1996)
6.3基本蚁群优化算法
6.3.1蚂蚁系统的模型与实现
智能优化计算
信息素的分布
6.3基本蚁群优化算法
6.3.2蚂蚁系统的参数设置和基本属性智能优化计算信息素的分布
蒸发系数的影响:
6.3基本蚁群优化算法
6.3.2蚂蚁系统的参数设置和基本属性
P=0.05
P=0.95
智能优化计算
参数a、B对算法性能的影响
停滞现象(Stagnationbehavior):
所有蚂蚁都选择相同的路径,即系统不再搜索更好的解。
原因在于较好路径上的信息素远人于其他边上的,从而使所有蚂蚁都选择该路径。
6.3基本蚁群优化算法
6.3.2蚂蚁系统的参数设置和基本属性
智能优化计算
参数a、B对算法性能的影响
a取较人值时,意味着在选择路径时,路径上的信息素非常重要:
当a取较小值
时,变成随机的贪婪算法。
6.3基本蚁群优化算法
6.3.2蚂蚁系统的参数设置和基本属性
智能优化计算
参数a、B对算法性能的影响
a=0,蚂蚁之间无协同作用;a=1,有协同作用
6.3基本蚁群优化算法
6.3.2蚂蚁系统的参数设置和基本属性
a=0
a=1
智能优化计算
蚂蚁数m对算法的影响
m^n时,ant-cycle可以在最少迭代次数内找到最优解。
6.3基本蚁群优化算法
6.3.2蚂蚁系统的参数设置和基本属性
m=15
m=150
m=30
智能优化计算
蚂蚁的初始分布
两种情况实验:
(1)所有蚂蚁初始时刻放在同一城市;
(2)蚂蚁分布在不同城市中。
第
(2)中情况可获得较高性能。
(3)在不同城市分布时,随机分布与统一分布的差别不人。
6.3基本蚁群优化算法
6.3.2蚂蚁系统的参数设置和基本属性
智能优化计算
优点
较强的鲁棒性;
分布式计算;
易于与其他方法结合。
缺点
搜索时间较长:
容易出现停滞现彖。
6.4改进的蚁群优化算法
6.4.1蚂蚁系统的优点与不足
智能优化计算
最优解保留策略(AntSystemwithElitist,ASelite)
每次迭代完成后,对全局最优解更进一步地进行利用;
信息素更新策略
c为最优蚂蚁数,Lgb为全局最优解。
6.4改进的蚁群优化算法
6.4.2最优解保留策略蚂蚁系统
智能优化计算
最优解保留策略(AntSystemwithElitist,ASelite)
该策略能够以更快的速度获得最好解,但是如果选择的精英过多则算法会由于较早收敛于局部次优解而导致搜索的过早停滞。
6.4改进的蚁群优化算法
6.4.2最优解保留策略蚂蚁系统
智能优化计算
蚁群系统(AntColonySystem,ACS)的改进之处
(1)在选择下一城市时,更多地利用了当前最好解;
(2)只在全局最优解所属边上增加信息素:
(3)每次蚂蚁从城市i转移到城市j时,边ij上的信息素将会适当减少,从而实现一种信息素的局部调整以减少已选择过的路径再次被选择的概率。
6.4改进的蚁群优化算法
6.4.3蚁群系统
智能优化计算
可行解的构造
伪随机比率选择规则:
蚂蚁以概率qO(0〜1间的常数)移动到最人可能的城市
q为0〜1的随机数,S为一随机变量,当q>qO时,S以以下概率来选择:
6.4改进的蚁群优化算法
6.4.3蚁群系统
智能优化计算
局部信息素更新
使已选的边对后来的蚂蚁具有较小的影响力,从而使蚂蚁对没有选中的边有更强
的探索能力。
当蚂蚁从城市i转移到城市j后,边ij上的信息素更新为:
其中,10为常数,gG(0,l)为可调参数。
6.4改进的蚁群优化算法
6.4.3蚁群系统
智能优化计算
全局信息素更新
只针对全局最优解进行更新:
6.4改进的蚁群优化算法
6.4.3蚁群系统智能优化计算
最人一最小蚂蚁系统(max-minantsystem,MMAS)的改进之处
(1)每次迭代后,只有最优解(最优蚂蚁)所属路径上的信息被更新:
(2)为了避免过早收敛,将各条路径可能的信息素限制于[tminimax];
(3)初始时刻,各路径上信息素设置为Tmax,在算法初始时刻,P取较小值时算法有更好的发现较好解的能力。
6.4改进的蚁群优化算法
6.4.4最大一最小蚂蚁系统
智能优化计算
信息素的全局更新
使所有蚂蚁完成一次迭代后,进行信息素更新:
6.4改进的蚁群优化算法
6.4.4最大一最小蚂蚁系统
智能优化计算
基于排序的蚂蚁系统(rank-basedversionofantsystem,ASrank)
每次迭代完成后,蚂蚁所经路径按从小到大的顺序排列,并对它们赋予不同权值,
路径越短权值越大。
全局最优解权值为w,第r个最优解的权值为max{0,w-r}a
6.4改进的蚁群优化算法
6.4.5基于排序的蚂蚁系统
智能优化计算
基于排序的蚂蚁系统(rank-basedversionofantsystem,ASrank)
信息素更新:
6.4改进的蚁群优化算法
6.4.5基于排序的蚂蚁系统
智能优化计算
优化结果比较
对对称TSP各迭代10000次,对非对称TSP各迭代20000次:
6.4改进的蚁群优化算法
6.4.6各种蚁群优化算法的比较
智能优化计算
典型应用列表
6.5蚁群优化算法的应用
6.5.1典型应用
智能优化计算
如何应用
用蚁群算法解决数据分类(数据挖掘任务中的一种)的问题:
预先定义一组类,然后把数据系中的每一个数据根据该数据的属性,归入这些类中的一个。
当数据量很人时,难以人为判别分类。
6.5蚁群优化算法的应用
6.5.2医学诊断的数据挖掘
智能优化计算
如何应用
分类的规则:
IF
每个term是一个三元组(属性、关系符、属性取值)
希望在一个规则中使用最少的判别语句,采用蚁群优化算法达到最优的选择。
6.5蚁群优化算法的应用
6.5.2医学诊断的数据挖掘
智能优化计算
例:
非典型肺炎
考虑如下因素:
6.5蚁群优化算法的应用
6.5.2医学诊断的数据挖掘
智能优化计算
例:
非典型肺炎
结构图:
一个蚂蚁从始点行走至终点,得到一条路径{0,2,1,0},其对应的规则为
IF(职业=其他人员)AND(胸部阴影=无)THEN(非典型肺炎)
对此路径,应给予非常差的评价。
6.5蚁群优化算法的应用
6.5.2医学诊断的数据挖掘
智能优化计算
蚁群算法的实现
假设a表示属性的总个数,第i个属性的取值域中可取bi个数值。
一只蚂蚁的行走
k步的路径可以表示为
route[k]=(yl,y2/.../ya)
yi=0表示不包含属性io
6.5蚁群优化算法的应用
6.5.2医学诊断的数据挖掘
智能优化计算
评价函数
解的评价函数定义为:
Q的数值越接近1,说明对该
类的判断越准确。
TP—truepositives
TN—truenegatives
FP—falsepositives
FN—falsenegatives
6.5蚁群优化算法的应用
6.5.2医学诊断的数据挖掘
True:
判断结果,正确
False:
判断结果,失误
Positives:
真实属性,属于
Negatives:
真实属性,不属于智能优化计算
转移概率
Hij表示每个条件项的启发式参数值(信息爛人"j(t)表示第i个属性的第j个取值在t时刻的信息素。
6.5蚁群优化算法的应用
6.5.2医学诊断的数据挖掘
智能优化计算
信息素增加
R是当前规则中所有包含的条件项;信息素挥发
减少没被选中的三元组的信息量。
6.5蚁群优化算法的应用
6.5.2医学诊断的数据挖掘
智能优化计算
结果分析
诊断准确度比较
6.5蚁群优化算法的应用
6.5.2医学诊断的数据挖掘
智能优化计算
结果分析
诊断规则数比较
6.5蚁群优化算法的应用
6.5.2医学诊断的数据挖掘
智能优化计算
由JamesKenney(社会心理学博士)和RussEberhart(电子工程学博士,http:
//www.engr.iupui.edu/~eberhart/)于1995年提出粒子群算法(ParticleSwarmOptimization,PSO)
6.6粒子群算法的基本原理
6.6.1粒子群算法的提出
智能优化计算
源于对鸟群捕食行为的研究,是基于迭代的方法
简单易于实现,需要调整的参数相对较少
在函数优化、神经网络训练、工业系统优化和模糊系统控制等领域得到了广泛的应用。
6.6粒子群算法的基本原理
6.6.1粒子群算法的提出
智能优化计算
鸟群:
假设一个区域,所有的鸟都不知道食物的位置,但是它们知道当前位置离食物还有多远。
PSO算法
每个解看作一只鸟,称为“粒子(particle)”,所有的粒子都有一个适应值,每个粒子都有一个速度决定它们的飞翔方向和距离,粒子们追随当前最优粒子在解空间中搜索。
6.6粒子群算法的基本原理
6.6.2粒子群算法的原理描述
智能优化计算
PSO算法
初始化为一群随机粒子,通过迭代找到最优。
每次迭代中,粒子通过跟踪“个体极值(pbest)”和“全局极值(gbest)”来
更新自己的位置。
6.6粒子群算法的基本原理
6.6.2粒子群算法的原理描述
智能优化计算
粒子速度和位置的更新
假设在D维搜索空间中,有m个粒子;
其中第i个粒子的位置为矢量
其飞翔速度也是一个矢量,记为
第i个粒子搜索到的最优位置为
整个粒子群搜索到的最优位置为
第i个粒子的位置和速度更新为:
6.7基本粒子群优化算法
6.7.1基本粒子群算法描述
智能优化计算
粒子速度和位置的更新
其中,w称为惯性权重,cl和c2为两个正常数,称为加速因子。
将vidk限制在一个最人速度vmax内。
6.7基本粒子群优化算法
6.7.1基本粒子群算法描述
智能优化计算
粒子速度和位置的更新
6.7基本粒子群优化算法
6.7.1基本粒子群算法描述
“惯性部分”,对自身运动状态的信任
“认知部分”,对微粒本身的思考,即来源于自己经验的部分
“社会部分”,微粒间的信息共享,来源于群体中的其它优秀微粒的经验智能优化计算
迭代过程
6.7基本粒子群优化算法
6.7.1基本粒子群算法描述智能优化计算
算法流程
6.7基本粒子群优化算法
Start
Initializeparticleswithrandomposition
andvelocityvectors・
Foreachparticle'sposition(xi)
evaluatefitness
Iffitness(xi)betterthan
fitness(p)thenp=xi
Loopuntilallparticlesexhaust
SetbestofpsasgBest
Updateparticlesvelocityand
position
Loopuntilmaxiter
Stop:
givinggBest,optimalsolution.
6.7.1基本粒子群算法描述
智能优化计算
惯性权重w
使粒子保持运动惯性,使其有扩展搜索空间的趋势,有能力探索新的区域。
表示微粒对当前自身运动状态的信任,依据自身的速度进行惯性运动。
较人的W有利于跳出局部极值,而较小的W有利于算法收敛。
6.7基本粒子群优化算法
6.7.2参数分析
智能优化计算
加速常数cl和c2
代表将微粒推向pbest和gbest位置的统计加速项的权重。
表示粒子的动作来源于自己经验的部分和其它粒子
经验的部分。
低的值允许粒子在被拉回之前可以在目标区域外徘
徊,而高的值则导致粒子突然冲向或越过目标区域。
6.7基本粒子群优化算法
6.7.2参数分析
智能优化计算
加速常数cl和c2
将cl和c2统一为一个控制参数,e=cl+c2
如果e很小,微粒群运动轨迹将非常缓慢;
如果e很大,则微粒位置变化非常快;
实验表明,当(通常cl=2.0,c2=2.0)时,具有很好的收敛效果。
6.7基本粒子群优化算法
6.7.2参数分析
智能优化计算
粒子数
一般取20〜40,对较难或特定类别的问题可以取
100〜200。
最大速度vmax
决定粒子在一个循坏中最人的移动距离,通常设定为粒子的范围宽度。
终止条件
最大循环数以及最小错误要求。
6.7基本粒子群优化算法
6.7.2参数分析
智能优化计算
共性
(1)都属于仿生算法;
(2)都属于全局优化方法;
(3)都属于随机搜索算法;
(4)都隐含并行性;
(5)根据个体的适配信息进行搜索,因此不受函数约束条件的限制,如连续性、可导性等;
(6)对高维复杂问题,往往会遇到早熟收敛和收敛性能差的缺点,都无法保证收敛到最优点。
6.7基本粒子群优化算法
6.7.3与遗传算法的比较
智能优化计算
差异
(1)PSO有记忆,所有粒子都保存较优解的知识,而GA,以前的知识随着种群的改变被改变;
(2)PSO中的粒子是一种单向共享信息机制。
而GA中的染色体之间相互共享信息,
使得整个种群都向最优区域移动;
(3)GA需要编码和遗传操作,而PSO没有交叉和变异操作,粒子只是通过内部速度进行更新,因此原理更简单、参数更少、实现更容易。
6.7基本粒子群优化算法
6.7.3与遗传算法的比较
智能优化计算
用途
基本PSO是用来解决连续问题优化的,离散二进制PSO用来解决组合优化问题。
运动方程不同
粒子的位置只有(0,1)两种状态。
速度值越人,则粒子位置取1的可能性越人,反之越小。
6.8改进粒子群优化算法
6.8.1离散二进制PSO
智能优化计算
思路
在考虑实际优化问题时,往往希望先采用全局搜索,使搜索空间快速收敛于某一区域,然后采用局部精细搜索以获得高精度的解。
研究发现,较犬的w值有利于跳出局部极小点,而
较小的w值有利于算法收敛,因此提出了自适应调
整的策略,即随着迭代的进行,线性地减小w的
值。
6.8改进粒子群优化算法
6.8.2惯性权重模型
智能优化计算
变化的惯性权重
wmax、wmin分别是w的最人值和最小值:
iter、itermax分别是当前迭代次数和最人迭代次数。
6.8改进粒子群优化算法
6.8.2惯性权重模型
智能优化计算
提出
1999年Clerc对算法的研究证明,采用收敛因子能
够确保算法的收敛。
收敛因子模型
通常将设为4.1,经计算k为0.729o
6.8改进粒子群优化算法
6.8.3收敛因子模型智能优化计算
主要研究方向
主要集中于对算法结构和性能的改善方面,包括:
参数设置、粒子多样性、种群结构和算法的融合。
发展方向
目前人部分成果都是通过大量试验获得的,缺少对算法机理的研究,对PSO中的参数分析没有实质性的认识,还处于试验分析阶段。
6.8改进粒子群优化算法
6.8.4研究现状
智能优化计算
交换子和交换序
设n个节点的TSP问题的解序列为s=(ai),i=l-no定义交换子S0(ilJ2)为交换解S中的点ail和ai2,则S'=S+S0(il,i2)为解S经算子S0(il,i2)操作后的新解。
一个或多个交换子的有序队列就是交换序,记作SS,SS=(S01,S02/-S0N)o其中,SOI,…,SON等是交换子,之间的顺序是有意义的,意味着所有的交换子依次作用于某解上。
6.9粒子群优化算法的应用
6.9.1求解TSP问题
智能优化计算
符号的定义
若干个交换序可以合并成一个新的交换序,定义为两个交换序的合并算
子。
设两个交换序SS1和SS2按先后顺序作用于解S±,得到新解S'。
假设另外有一个交换序SS'作用于同一解S上,能够得到形同的解S',可定义
6.9粒子群优化算法的应用
6.9.1求解TSP问题
智能优化计算
符号的定义
和属于同一等价集,在交换序等价集中,拥有最少
交换子的交换序称为该等价集的基本交换序。
6.9粒子群优化算法的应用
6.9.1求解TSP问题
智能优化计算
解决TSP问题的速度算式定义
a、B为[0,1]上的随机数。
vid表示交换序,xid表示路径序列(解)。
6.9粒子群优化算法的应用
6.9.1求解TSP问题
智能优化计算
算法流程
1.初始化粒子群,给每个粒子一个初始解(xid)和随机的交换序(vid);
2.如果满足结束条件,转步骤5;
3.根据粒子当前位置xid计算下一新解xid';
4.如果整个群体找到一个更好的解,更新Pgd,转步骤2
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 智能 算法 教学 讲义