粒子群优化算法

1粒子群优化算法ParticleSwarmOptimization2优化问题函数极值问题背包问题最短路径问题形状优化多孔材料的设计拓扑问题3传统求解最优化问题的优化算法多阶段决策整数规划非线性规划线性规划动态规划法分支定界法共轭梯度法单纯形法优化问题优化方法优化问题优化方法4群智能优化算法人工蜂群算法蚁群算法人工鱼群算法蛙跳算法5粒子群算法发展简介Reynolds：Boid(Bird-oid)模型（1987）避免碰撞：飞离最近的个体，以避免碰撞三条规则速度一致：向目标前进，和邻近个体的平均速度保持一致中心群集：向邻近个体的平均位置移动，向群体的中心运动Heppner：新的鸟类模型（1990）受栖息地吸引的特性Kennedy和Eberhart：粒子群算法（1995）6粒子群算法的基本思想食物搜寻目前离的食物最近的鸟的周围区域根据自己飞行的经验判断食物所在已知鸟的位置鸟当前位置和食物之间的距离求解找到食物的最优策略7PSO概述每个寻优的问题解都被想像成一只鸟，称为“粒子”。所有的粒子都由一个FitnessFunction确定适应值以判断目前的位置好坏。每一个粒子必须赋予记忆功能，能记住所搜寻到的最佳位置。每一个粒子还有一个速度以决定飞行的距离和方向。这个速度根据它本身的飞行经验以及同伴的飞行经验进行动态调整。8PSO求最优解D维空间中，有m个粒子；粒子i位置：xi=(xi1,xi2,…xiD)，将xi代入适应函数F(xi)求适应值；粒子i速度：vi=(vi1,vi2,…viD)粒子i个体经历过的最好位置：pbesti=(pi1,pi2,…piD)种群所经历过的最好位置：gbest=(g1,g2,…gD)通常，在第d（1≤d≤D）维的位置变化范围限定在[Xmin,d,Xmax,d]内，速度变化范围限定在[-Vmax,d,Vmax,d]内。xivi9PSO求最优解粒子i的第d维速度更新公式：粒子i的第d维位置更新公式：—第k次迭代粒子i飞行速度矢量的第d维分量—第k次迭代粒子i位置矢量的第d维分量c1,c2—加速度常数，调节学习最大步长r1,r2—两个随机函数，取值范围[0，1]，以增加搜索随机性w—惯性权重，非负数，调节对解空间的搜索范围kk-111idid1122v=wv()()kkididdidcrpbestxcrgbestx11kkkidididxxvkidvkidx10PSO求最优解区域最佳解全域最佳解运动向量惯性向量StudyFactorInertiaWeight惯性部分社会认知个体认知kk-111idid1122v=wv()()kkididdidcrpbestxcrgbestx11kkkidididxxv𝑥𝑖𝑑𝑘𝑥𝑖𝑑𝑘−111PSO算法流程InitializeEvaluationFindthePbestFindtheGbestUpdatethePositionConvergenceJudgmentEvaluation根据FitnessFunction计算出其FitnessValue以作为判断每一Particle之好坏Initialize将群族初始化，以随机的方式求出每一Particle的初始位置与速度12PSO算法流程FindthePbestFindtheGbestUpdatethePositionConvergenceJudgmentFindthePbest找出每个Particle到目前为止的搜寻过程中最优解，这个最优解我们称为PbestPastBestSolutionEvaluationInitialize13PSO算法流程FindthePbestFindtheGbestUpdatethePositionConvergenceJudgmentEvaluationInitializeFindtheGbest找出所有Particle到目前为止所搜寻到的全体最优解，此最优解我们称之为GbestGlobalBestSolutionPastBestSolution14PSO算法流程FindthePbestFindtheGbestUpdatethePositionConvergenceJudgmentEvaluationInitializeUpdatethePosition根据速度和位移更新公式，更新每个Particle的移动方向与速度ConvergenceJudgment通常算法达到最大迭代次数Gmax或者最佳适应度函数值的增量小于某个给定的罚值时算法停止；否则返回步骤2。15PSO算法流程图开始设定参数产生初始族群计算适应度更新速度和位置产生新族群满足停止条件结束NoYes16粒子群算法的构成要素群体大小mm是一个整形参数m很小：陷入局部最优解的可能性很大m很大：PSO的优化能力很好，计算量大17粒子群算法的构成要素权重因子——惯性权重ww=0：粒子很容易趋向于同一位置w小：倾向于局部探索,精细搜索目前的小区域w大：扩展新的搜索区域,利于全局搜索StudyFactorInertiaWeight惯性部分社会认知个体认知kk-111idid1122v=wv()()kkididdidcrpbestxcrgbestx18粒子群算法的构成要素权重因子——学习因子c1，c2StudyFactorInertiaWeight惯性部分社会认知个体认知kk-111idid1122v=wv()()kkididdidcrpbestxcrgbestxC1=0社会模型•只有社会，没有自我•迅速丧失群体多样性•易陷入局优而无法跳出C2=0认知模型•只有自我，没有社会•完全没有社会信息共享•算法收敛速度缓慢C1,C2≠0完全模型•收敛速度•搜索效果19粒子群算法的构成要素最大速度Vm作用：维护算法的探索能力与开发能力的平衡Vm较大时，探索能力增强，但粒子容易飞过最优解Vm较小时，开发能力增强，但容易陷入局部最优．Vm一般设为每维变量的取值范围。20粒子群算法的构成要素邻域的拓扑结构全局模型粒子自己历史最优值粒子群体的全局最优值收敛速度快容易陷入局部最优解局部模型粒子自己历史最优值粒子邻域内粒子的最优值收敛速度慢不易陷入局部最优解GbestPbest21粒子群算法的优点与应用优点1、参数较少，容易调整2、局部与全局结合，收敛速度快应用1、神经网络的训练连接权重、网络结构和学习算法2、连续问题参数优化机器人路径规划，电路优化设计，数控加工参数优化3、组合优化车间调度4、其他应用多目标优化，动态目标检测，数据挖掘，系统辨识22Matlab应用实例23Matlab应用实例ω=0.618c1=c2=2swamSize=3maxgen=3Vmax=1Vmin=-1popmax=4popmin=0参数设置24Matlab应用实例25Matlab应用实例26Matlab应用实例27Matlab应用实例28Matlab应用实例29Matlab应用实例30Matlab应用实例31Matlab应用实例ω=0.618c1=c2=2swamSize=10maxgen=10Vmax=1Vmin=-1popmax=4popmin=0Tolerance=1e-332Matlab应用实例33Matlab应用实例34Matlab应用实例35Matlab应用实例36Matlab应用实例37Matlab应用实例38Matlab应用实例39Matlab应用实例40Matlab应用实例41Matlab应用实例42Matlab应用实例43结果分析maxgen=6x=0.9383，y=1.3706Tolerance=4.308e-4Matlab应用实例44参数设置ω=0.618c1=c2=2swamSize=50maxgen=10Vmax=1Vmin=-1popmax=4popmin=0Tolerance=1e-3Matlab应用实例45Matlab应用实例46Matlab应用实例47Matlab应用实例48Matlab应用实例49Matlab应用实例50结果分析maxgenxyTol1060.9383461.370594.308e-45020.9359861.370573.070e-4Matlab应用实例51参数设置ω=0.618c1=c2=2swamSize=50maxgen=10Vmax=1Vmin=-1popmax=2popmin=0Tolerance=1e-3Matlab应用实例52Matlab应用实例53Matlab应用实例54Matlab应用实例55Matlab应用实例56Matlab应用实例57Matlab应用实例58结果分析maxgenxyTol41060.9383461.370594.308e-445020.9359861.370573.070e-425020.9294201.370602.628e-4Matlab应用实例59Matlab应用实例60结果分析maxgenxyTol41060.9383461.370594.308e-445020.9359861.370573.070e-425020.9294201.370602.628e-425010.9401811.370614.878e-5Matlab应用实例61