资源描述:
《《粒子群优化算法》PPT课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、粒子群优化算法ParticleSwarmOptimization优化问题函数极值问题背包问题最短路径问题形状优化多孔材料的设计拓扑问题传统求解最优化问题的优化算法多阶段决策整数规划非线性规划线性规划动态规划法分支定界法共轭梯度法单纯形法优化问题优化方法优化问题优化方法群智能优化算法人工蜂群算法蚁群算法人工鱼群算法蛙跳算法粒子群算法发展简介Reynolds:Boid(Bird-oid)模型(1987)避免碰撞:飞离最近的个体,以避免碰撞三条规则速度一致:向目标前进,和邻近个体的平均速度保持一致中心群集:向邻近个体的平均位置移动,向群体的中心运动Heppner:新的鸟类模型(1990)受栖
2、息地吸引的特性Kennedy和Eberhart:粒子群算法(1995)粒子群算法的基本思想食物搜寻目前离的食物最近的鸟的周围区域根据自己飞行的经验判断食物所在已知鸟的位置鸟当前位置和食物之间的距离求解找到食物的最优策略PSO概述每个寻优的问题解都被想像成一只鸟,称为“粒子”。所有的粒子都由一个FitnessFunction确定适应值以判断目前的位置好坏。每一个粒子必须赋予记忆功能,能记住所搜寻到的最佳位置。每一个粒子还有一个速度以决定飞行的距离和方向。这个速度根据它本身的飞行经验以及同伴的飞行经验进行动态调整。PSO求最优解D维空间中,有m个粒子;粒子i位置:xi=(xi1,xi2,…
3、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]内。pbestxigbestviPSO求最优解粒子i的第d维速度更新公式:粒子i的第d维位置更新公式:—第k次迭代粒子i飞行速度矢量的第d维分量—第k次迭代粒子i位置矢量的第d维分量c1,c2—加速度常数,调节学习最大步长r1,r2—两个
4、随机函数,取值范围[0,1],以增加搜索随机性w—惯性权重,非负数,调节对解空间的搜索范围PSO求最优解区域最佳解全域最佳解运动向量惯性向量StudyFactorgbestInertiaWeight惯性部分社会认知个体认知pbestPSO算法流程InitializeEvaluationFindthePbestFindtheGbestUpdatethePositionConvergenceJudgmentEvaluation根据FitnessFunction计算出其FitnessValue以作为判断每一Particle之好坏Initialize将群族初始化,以随机的方式求出每一Parti
5、cle的初始位置与速度PSO算法流程FindthePbestFindtheGbestUpdatethePositionConvergenceJudgmentFindthePbest找出每个Particle到目前为止的搜寻过程中最优解,这个最优解我们称为PbestPastBestSolutionEvaluationInitializePSO算法流程FindthePbestFindtheGbestUpdatethePositionConvergenceJudgmentEvaluationInitializeFindtheGbest找出所有Particle到目前为止所搜寻到的全体最优解,此最
6、优解我们称之为GbestGlobalBestSolutionPastBestSolutionPSO算法流程FindthePbestFindtheGbestUpdatethePositionConvergenceJudgmentEvaluationInitializeUpdatethePosition根据速度和位移更新公式,更新每个Particle的移动方向与速度ConvergenceJudgment通常算法达到最大迭代次数Gmax或者最佳适应度函数值的增量小于某个给定的罚值时算法停止;否则返回步骤2。PSO算法流程图粒子群算法的构成要素群体大小mm是一个整形参数m很小:陷入局部最优解的
7、可能性很大m很大:PSO的优化能力很好,计算量大粒子群算法的构成要素权重因子——惯性权重ww=0:粒子很容易趋向于同一位置w小:倾向于局部探索,精细搜索目前的小区域w大:扩展新的搜索区域,利于全局搜索StudyFactorInertiaWeight惯性部分社会认知个体认知粒子群算法的构成要素权重因子——学习因子c1,c2StudyFactorInertiaWeight惯性部分社会认知个体认知C1=0社会模型只有社会,没有自我迅速丧失群体多样性易