粒子群优化算法

粒子群优化算法

ParticleSwarmOptimization

优化问题函数极值问题背包问题最短路径问题形状优化多孔材料的设计拓扑问题传统求解最优化问题的优化算法多阶段决策整数规划非线性规划线性规划动态规划法分支定界法共轭梯度法单纯形法优化问题优化方法优化问题优化方法群智能优化算法人工蜂群算法蚁群算法人工鱼群算法蛙跳算法粒子群算法发展简介Reynolds：Boid(Bird-oid)模型（1987）

避免碰撞：飞离最近的个体，以避免碰撞三条规则速度一致：向目标前进，和邻近个体的平均速度保持一致

中心群集：向邻近个体的平均位置移动，向群体的中心运动Heppner：新的鸟类模型（1990）受栖息地吸引的特性Kennedy和Eberhart：粒子群算法（1995）粒子群算法的基本思想食物搜寻目前离的食物最近的鸟的周围区域根据自己飞行的经验判断食物所在已知鸟的位置鸟当前位置和食物之间的距离求解找到食物的最优策略PSO概述每个寻优的问题解都被想像成一只鸟，称为“粒子”。所有的粒子都由一个FitnessFunction确定适应值以判断目前的位置好坏。每一个粒子必须赋予记忆功能，能记住所搜寻到的最佳位置。每一个粒子还有一个速度以决定飞行的距离和方向。这个速度根据它本身的飞行经验以及同伴的飞行经验进行动态调整。PSO求最优解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]内。pbestxigbestviPSO求最优解粒子i的第d维速度更新公式：

粒子i的第d维位置更新公式：

—第k次迭代粒子i飞行速度矢量的第d维分量

—第k次迭代粒子i位置矢量的第d维分量

c1,c2—加速度常数，调节学习最大步长

r1,r2—两个随机函数，取值范围[0，1]，以增加搜索随机性

w—惯性权重，非负数，调节对解空间的搜索范围PSO求最优解

区域最佳解全域最佳解运动向量惯性向量StudyFactorgbestInertia

Weight惯性部分社会认知个体认知pbest

PSO算法流程InitializeEvaluationFindthePbestFindtheGbestUpdatethePositionConvergenceJudgmentEvaluation根据

FitnessFunction计算出其FitnessValue以作为判断每一Particle之好坏Initialize将群族初始化，以随机的方式求出每一Particle的初始位置与速度PSO算法流程FindthePbestFindtheGbestUpdatethePositionConvergenceJudgmentFindthePbest找出每个Particle到目前为止的搜寻过程中最优解，这个最优解我们称为PbestPastBestSolutionEvaluationInitializePSO算法流程FindthePbestFindtheGbestUpdatethePositionConvergenceJudgmentEvaluationInitializeFindtheGbest找出所有Particle到目前为止所搜寻到的全体最优解，此最优解我们称之为GbestGlobalBestSolutionPastBestSolutionPSO算法流程FindthePbestFindtheGbestUpdatethePositionConvergenceJudgmentEvaluationInitializeUpdatethePosition根据速度和位移更新公式，更新每个Particle的移动方向与速度ConvergenceJudgment通常算法达到最大迭代次数Gmax或者最佳适应度函数值的增量小于某个给定的罚值时算法停止；否则返回步骤2。PSO算法流程图粒子群算法的构成要素群体大小mm是一个整形参数m很小：陷入局部最优解的可能性很大m很大：PSO的优化能力很好，计算量大粒子群算法的构成要素权重因子——惯性权重w

w=0：粒子很容易趋向于同一位置w小：倾向于局部探索,精细搜索目前的小区域

w大：扩展新的搜索区域,利于全局搜索StudyFactorInertia

Weight惯性部分社会认知个体认知粒子群算法的构成要素权重因子——学习因子c1，c2StudyFactorInertia

Weight惯性部分社会认知个体认知C1=0社会模型只有社会，没有自我迅速丧失群体多样性易陷入局优而无法跳出C2=0认知模型只有自我，没有社会完全没有社会信息共享算法收敛速度缓慢C1,C2≠0完全模型收敛速度搜索效果粒子群算法的构成要素最大速度Vm

作用：

维护算法的探索能力与开发能力的平衡Vm较大时，探索能力增强，但粒子容易飞过最优解Vm较小时，开发能力增强，但容易陷入局部最优．Vm一般设为每维变量的取值范围。粒子群算法的构成要素邻域的拓扑结构全局模型粒子自己历史最优值粒子群体的全局最优值收敛速度快容易陷入局部最优解局部模型粒子自己历史最优值粒子邻域内粒子的最优值收敛速度慢不易陷入局部最优解GbestPbest粒子群算法的优点与应用优点

1、参数较少，容易调整

2、局部与全局结合，收敛速度快应用1、神经网络的训练连接权重、网络结构和学习算法

2、连续问题参数优化机器人路径规划，电路优化设计，数控加工参数优化3、组合优化车间调度

4、其他应用多目标优化，动态目标检测，数据挖掘，系统辨识Matlab应用实例Matlab应用实例ω=0.618c1=c2=2swamSize=3maxgen=3Vmax=1Vmin=-1popmax=4

popmin=0

参数设置

Matlab应用实例Matlab应用实例Matlab应用实例Matlab应用实例Matlab应用实例Matlab应用实例Matlab应用实例Matlab应用实例ω=0.618c1=c2=2swamSize=10maxgen=10Vmax=1Vmin=-1popmax=4

popmin=0Tolerance=1e-3

Matlab应用实例Matlab应用实例Matlab应用实例Matlab应用实例Matlab应用实例Matlab应用实例Matlab应用实例Matlab应用实例Matlab应用实例Matlab应用实例Matlab应用实例结果分析

maxgen=6

x=0.9383，y

=1.3706

Tolerance=4.308e-4

Matlab应用实例参数设置

ω=0.618c1=c2=2swamSize=50maxgen=10Vmax=1Vmin=-1popmax=4

popmin=0Tolerance=1e-3

Matlab应用实例Matlab应用实例Matlab应用实例Matlab应用实例Matlab应用实例Matlab应用实例结果分析

maxgenxyTol1060.9383461.370594.308e-45020.9359861.370573.070e-4Matlab应用实例参数设置

ω=0.618c1=c2=2swamSize=50maxgen=10Vmax=1Vmin=-1popmax=2

popmin=0Tolerance=1e-3

Matlab应用实例Matlab应用实例Matlab应用实例Matlab应用实例Matlab应用实例Matlab应用实例Matlab应用实例结果分析

maxgenxyTol4

1060.9383461.370594.308e-445020.9359861.370573.070e-4250