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

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

ParticleSwarmOptimization

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

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

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

粒子i位置：xi=(xi1,xi2,…xiD)，將xi代入適應(yīng)函數(shù)F(xi)求適應(yīng)值；粒子i速度：vi=(vi1,vi2,…viD)粒子i個(gè)體經(jīng)歷過(guò)的最好位置：pbesti=(pi1,pi2,…piD)種群所經(jīng)歷過(guò)的最好位置：gbest=(g1,g2,…gD)通常，在第d（1≤d≤D）維的位置變化范圍限定在[Xmin,d,Xmax,d]內(nèi)，速度變化范圍限定在[-Vmax,d,Vmax,d]內(nèi)。pbestxigbestviPSO求最優(yōu)解粒子i的第d維速度更新公式：

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

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

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

c1,c2—加速度常數(shù)，調(diào)節(jié)學(xué)習(xí)最大步長(zhǎng)

r1,r2—兩個(gè)隨機(jī)函數(shù)，取值范圍[0，1]，以增加搜索隨機(jī)性

w—慣性權(quán)重，非負(fù)數(shù)，調(diào)節(jié)對(duì)解空間的搜索范圍PSO求最優(yōu)解

區(qū)域最佳解全域最佳解運(yùn)動(dòng)向量慣性向量StudyFactorgbestInertia

Weight慣性部分社會(huì)認(rèn)知個(gè)體認(rèn)知pbest

PSO算法流程InitializeEvaluationFindthePbestFindtheGbestUpdatethePositionConvergenceJudgmentEvaluation根據(jù)

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

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

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

Weight慣性部分社會(huì)認(rèn)知個(gè)體認(rèn)知粒子群算法的構(gòu)成要素權(quán)重因子——學(xué)習(xí)因子c1，c2StudyFactorInertia

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

作用：

維護(hù)算法的探索能力與開(kāi)發(fā)能力的平衡Vm較大時(shí)，探索能力增強(qiáng)，但粒子容易飛過(guò)最優(yōu)解Vm較小時(shí)，開(kāi)發(fā)能力增強(qiáng)，但容易陷入局部最優(yōu)．Vm一般設(shè)為每維變量的取值范圍。粒子群算法的構(gòu)成要素鄰域的拓?fù)浣Y(jié)構(gòu)全局模型粒子自己歷史最優(yōu)值粒子群體的全局最優(yōu)值收斂速度快容易陷入局部最優(yōu)解局部模型粒子自己歷史最優(yōu)值粒子鄰域內(nèi)粒子的最優(yōu)值收斂速度慢不易陷入局部最優(yōu)解GbestPbest粒子群算法的優(yōu)點(diǎn)與應(yīng)用優(yōu)點(diǎn)

1、參數(shù)較少，容易調(diào)整

2、局部與全局結(jié)合，收斂速度快應(yīng)用1、神經(jīng)網(wǎng)絡(luò)的訓(xùn)練連接權(quán)重、網(wǎng)絡(luò)結(jié)構(gòu)和學(xué)習(xí)算法

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

4、其他應(yīng)用多目標(biāo)優(yōu)化，動(dòng)態(tài)目標(biāo)檢測(cè)，數(shù)據(jù)挖掘，系統(tǒng)辨識(shí)Matlab應(yīng)用實(shí)例Matlab應(yīng)用實(shí)例ω=0.618c1=c2=2swamSize=3maxgen=3Vmax=1Vmin=-1popmax=4

popmin=0

參數(shù)設(shè)置

Matlab應(yīng)用實(shí)例Matlab應(yīng)用實(shí)例Matlab應(yīng)用實(shí)例Matlab應(yīng)用實(shí)例Matlab應(yīng)用實(shí)例Matlab應(yīng)用實(shí)例Matlab應(yīng)用實(shí)例Matlab應(yīng)用實(shí)例ω=0.618c1=c2=2swamSize=10maxgen=10Vmax=1Vmin=-1popmax=4

popmin=0Tolerance=1e-3

Matlab應(yīng)用實(shí)例Matlab應(yīng)用實(shí)例Matlab應(yīng)用實(shí)例Matlab應(yīng)用實(shí)例Matlab應(yīng)用實(shí)例Matlab應(yīng)用實(shí)例Matlab應(yīng)用實(shí)例Matlab應(yīng)用實(shí)例Matlab應(yīng)用實(shí)例Matlab應(yīng)用實(shí)例Matlab應(yīng)用實(shí)例結(jié)果分析

maxgen=6

x=0.9383，y

=1.3706

Tolerance=4.308e-4

Matlab應(yīng)用實(shí)例參數(shù)設(shè)置

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

popmin=0Tolerance=1e-3

Matlab應(yīng)用實(shí)例Matlab應(yīng)用實(shí)例Matlab應(yīng)用實(shí)例Matlab應(yīng)用實(shí)例Matlab應(yīng)用實(shí)例Matlab應(yīng)用實(shí)例結(jié)果分析

maxgenxyTol1060.9383461.370594.308e-45020.9359861.370573.070e-4Matlab應(yīng)用實(shí)例參數(shù)設(shè)置

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

popmin=0Tolerance=1e-3

Matlab應(yīng)用實(shí)例Matlab應(yīng)用實(shí)例Matlab應(yīng)用實(shí)例Matlab應(yīng)用實(shí)例Matlab應(yīng)用實(shí)例Matlab應(yīng)用實(shí)例Matlab應(yīng)用實(shí)例結(jié)果分析

maxgenxyTol4

1060.9383461.370594.308e-445020.9359861.370573.070e-4250