粒子群優(yōu)化算法

粒子群優(yōu)化算法

ParticleSwarmOptimization

優(yōu)化問題函數極值問題背包問題最短路徑問題形狀優(yōu)化多孔材料的設計拓撲問題傳統(tǒng)求解最優(yōu)化問題的優(yōu)化算法多階段決策整數規(guī)劃非線性規(guī)劃線性規(guī)劃動態(tài)規(guī)劃法分支定界法共軛梯度法單純形法優(yōu)化問題優(yōu)化方法優(yōu)化問題優(yōu)化方法群智能優(yōu)化算法人工蜂群算法蟻群算法人工魚群算法蛙跳算法粒子群算法發(fā)展簡介Reynolds：Boid(Bird-oid)模型（1987）

避免碰撞：飛離最近的個體，以避免碰撞三條規(guī)則速度一致：向目標前進，和鄰近個體的平均速度保持一致

中心群集：向鄰近個體的平均位置移動，向群體的中心運動Heppner：新的鳥類模型（1990）受棲息地吸引的特性Kennedy和Eberhart：粒子群算法（1995）粒子群算法的基本思想食物搜尋目前離的食物最近的鳥的周圍區(qū)域根據自己飛行的經驗判斷食物所在已知鳥的位置鳥當前位置和食物之間的距離求解找到食物的最優(yōu)策略PSO概述每個尋優(yōu)的問題解都被想像成一只鳥，稱為“粒子”。所有的粒子都由一個FitnessFunction確定適應值以判斷目前的位置好壞。每一個粒子必須賦予記憶功能，能記住所搜尋到的最佳位置。每一個粒子還有一個速度以決定飛行的距離和方向。這個速度根據它本身的飛行經驗以及同伴的飛行經驗進行動態(tài)調整。PSO求最優(yōu)解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求最優(yōu)解粒子i的第d維速度更新公式：

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

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

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

c1,c2—加速度常數，調節(jié)學習最大步長

r1,r2—兩個隨機函數，取值范圍[0，1]，以增加搜索隨機性

w—慣性權重，非負數，調節(jié)對解空間的搜索范圍PSO求最優(yōu)解

區(qū)域最佳解全域最佳解運動向量慣性向量StudyFactorgbestInertia

Weight慣性部分社會認知個體認知pbest

PSO算法流程InitializeEvaluationFindthePbestFindtheGbestUpdatethePositionConvergenceJudgmentEvaluation根據

FitnessFunction計算出其FitnessValue以作為判斷每一Particle之好壞Initialize將群族初始化，以隨機的方式求出每一Particle的初始位置與速度PSO算法流程FindthePbestFindtheGbestUpdatethePositionConvergenceJudgmentFindthePbest找出每個Particle到目前為止的搜尋過程中最優(yōu)解，這個最優(yōu)解我們稱為PbestPastBestSolutionEvaluationInitializePSO算法流程FindthePbestFindtheGbestUpdatethePositionConvergenceJudgmentEvaluationInitializeFindtheGbest找出所有Particle到目前為止所搜尋到的全體最優(yōu)解，此最優(yōu)解我們稱之為GbestGlobalBestSolutionPastBestSolutionPSO算法流程FindthePbestFindtheGbestUpdatethePositionConvergenceJudgmentEvaluationInitializeUpdatethePosition根據速度和位移更新公式，更新每個Particle的移動方向與速度ConvergenceJudgment通常算法達到最大迭代次數Gmax或者最佳適應度函數值的增量小于某個給定的罰值時算法停止；否則返回步驟2。PSO算法流程圖粒子群算法的構成要素群體大小mm是一個整形參數m很?。合萑刖植孔顑?yōu)解的可能性很大m很大：PSO的優(yōu)化能力很好，計算量大粒子群算法的構成要素權重因子——慣性權重w

w=0：粒子很容易趨向于同一位置w?。簝A向于局部探索,精細搜索目前的小區(qū)域

w大：擴展新的搜索區(qū)域,利于全局搜索StudyFactorInertia

Weight慣性部分社會認知個體認知粒子群算法的構成要素權重因子——學習因子c1，c2StudyFactorInertia

Weight慣性部分社會認知個體認知C1=0社會模型只有社會，沒有自我迅速喪失群體多樣性易陷入局優(yōu)而無法跳出C2=0認知模型只有自我，沒有社會完全沒有社會信息共享算法收斂速度緩慢C1,C2≠0完全模型收斂速度搜索效果粒子群算法的構成要素最大速度Vm

作用：

維護算法的探索能力與開發(fā)能力的平衡Vm較大時，探索能力增強，但粒子容易飛過最優(yōu)解Vm較小時，開發(fā)能力增強，但容易陷入局部最優(yōu)．Vm一般設為每維變量的取值范圍。粒子群算法的構成要素鄰域的拓撲結構全局模型粒子自己歷史最優(yōu)值粒子群體的全局最優(yōu)值收斂速度快容易陷入局部最優(yōu)解局部模型粒子自己歷史最優(yōu)值粒子鄰域內粒子的最優(yōu)值收斂速度慢不易陷入局部最優(yōu)解GbestPbest粒子群算法的優(yōu)點與應用優(yōu)點

1、參數較少，容易調整

2、局部與全局結合，收斂速度快應用1、神經網絡的訓練連接權重、網絡結構和學習算法

2、連續(xù)問題參數優(yōu)化機器人路徑規(guī)劃，電路優(yōu)化設計，數控加工參數優(yōu)化3、組合優(yōu)化車間調度

4、其他應用多目標優(yōu)化，動態(tài)目標檢測，數據挖掘，系統(tǒng)辨識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