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

1、12函數(shù)極值問(wèn)題函數(shù)極值問(wèn)題背包問(wèn)題背包問(wèn)題最短路徑最短路徑問(wèn)題問(wèn)題形狀優(yōu)化形狀優(yōu)化多孔材料的設(shè)計(jì)多孔材料的設(shè)計(jì)拓?fù)渫負(fù)鋯?wèn)題問(wèn)題3多階段決策多階段決策整數(shù)規(guī)劃整數(shù)規(guī)劃非線(xiàn)性規(guī)劃非線(xiàn)性規(guī)劃線(xiàn)性規(guī)劃線(xiàn)性規(guī)劃動(dòng)態(tài)規(guī)劃法動(dòng)態(tài)規(guī)劃法分支定界法分支定界法共軛梯度法共軛梯度法單純形法單純形法優(yōu)化問(wèn)題優(yōu)化問(wèn)題優(yōu)化方法優(yōu)化方法優(yōu)化問(wèn)題優(yōu)化方法4人工蜂群算法人工蜂群算法蟻群蟻群算法算法人工魚(yú)群算法人工魚(yú)群算法蛙跳算法蛙跳算法5q Reynolds：Boid(Bird-oid) 模型（1987） 避免碰撞：飛離最近的個(gè)體，以避免碰撞 三條規(guī)則 速度一致：向目標(biāo)前進(jìn)，和鄰近個(gè)體的平均速度保持一致 中心群集：向鄰近個(gè)體

2、的平均位置移動(dòng)，向群體的中心運(yùn)動(dòng)q Heppner：新的鳥(niǎo)類(lèi)模型（1990） 受棲息地吸引的特性q Kennedy和Eberhart：粒子群算法（1995）6食物食物搜尋目前離搜尋目前離的的食物最近的鳥(niǎo)的周?chē)鷧^(qū)域食物最近的鳥(niǎo)的周?chē)鷧^(qū)域根據(jù)自己飛行的經(jīng)驗(yàn)判斷食物所在根據(jù)自己飛行的經(jīng)驗(yàn)判斷食物所在已知鳥(niǎo)的位置鳥(niǎo)當(dāng)前位置和食物之間的距離求解找到食物的最優(yōu)策略7q每個(gè)尋優(yōu)的問(wèn)題解都被想像成一只鳥(niǎo)，稱(chēng)為“粒子”。q所有的粒子都由一個(gè)Fitness Function 確定適應(yīng)值以判斷目前的位置好壞。q每一個(gè)粒子必須賦予記憶功能，能記住所搜尋到的最佳位置。q每一個(gè)粒子還有一個(gè)速度以決定飛行的距離和方向。這個(gè)

3、速度根據(jù)它本身的飛行經(jīng)驗(yàn)以及同伴的飛行經(jīng)驗(yàn)進(jìn)行動(dòng)態(tài)調(diào)整。 8q D維空間中，有m個(gè)粒子； 粒子i位置：x xi i=(xi1,xi2,xiD)，將xi代入適應(yīng)函數(shù)F(xi)求適應(yīng)值； 粒子i速度：v vi i=(vi1,vi2,viD) 粒子i個(gè)體經(jīng)歷過(guò)的最好位置：pbestpbesti i=(pi1,pi2,piD) 種群所經(jīng)歷過(guò)的最好位置：gbestgbest=(g1,g2,gD)q 通常，在第d（1dD）維的位置變化范圍限定在Xmin,d ,Xmax,d內(nèi)，速度變化范圍限定在-Vmax,d ,Vmax,d內(nèi)。pbestx xi igbestv vi i9q 粒子i的第d維速度更新公式：

4、q 粒子i的第d維位置更新公式： 第k次迭代粒子i飛行速度矢量的第d維分量 第k次迭代粒子i位置矢量的第d維分量 c c1 1,c,c2 2加速度常數(shù)，調(diào)節(jié)學(xué)習(xí)最大步長(zhǎng) r r1 1,r,r2 2兩個(gè)隨機(jī)函數(shù)，取值范圍0，1，以增加搜索隨機(jī)性 w w 慣性權(quán)重，非負(fù)數(shù)，調(diào)節(jié)對(duì)解空間的搜索范圍kk-111idid1 12 2v =wv()()kkididdidc r pbestxc r gbestx11kkkidididxxvkidvkidx10 區(qū)域區(qū)域最佳最佳解解全域全域最佳解最佳解運(yùn)動(dòng)運(yùn)動(dòng)向量向量慣性慣性向量向量gbest慣性慣性部分部分社會(huì)認(rèn)知社會(huì)認(rèn)知個(gè)體認(rèn)知個(gè)體認(rèn)知kk-111idid

5、1 12 2v =wv()()kkididdidc r pbestxc r gbestx11kkkidididxxvpbest11InitializeEvaluationFind the PbestFind the GbestUpdate the PositionConvergence JudgmentnEvaluationn根據(jù) Fitness Function計(jì)算出其 Fitness Value 以作為判斷每一Particle之好壞nInitializen將群族初始化，以隨機(jī)的方式求出每一Particle的初始位置與速度12Find the PbestFind the GbestUpdat

6、e the PositionConvergence Judgmentn找出每個(gè)Particle 到目前為止的搜尋過(guò)程中最優(yōu)解，這個(gè)最優(yōu)解我們稱(chēng)為PbestPast Best SolutionEvaluationInitialize13Find the PbestFind the GbestUpdate the PositionConvergence JudgmentEvaluationInitializenFind the Gbestn找出所有Particle 到目前為止所搜尋到的全體最優(yōu)解，此最優(yōu)解我們稱(chēng)之為GbestGlobal Best SolutionPast Best Solutio

7、n14Find the PbestFind the GbestUpdate the PositionConvergence JudgmentEvaluationInitializenUpdate the Positionn根據(jù)速度和位移更新公式，更新每個(gè)Particle的移動(dòng)方向與速度nConvergence Judgmentn通常算法達(dá)到最大迭代次數(shù)Gmax或者最佳適應(yīng)度函數(shù)值的增量小于某個(gè)給定的罰值時(shí)算法停止；否則返回步驟2。1516q 群體大小m m是一個(gè)整形參數(shù) m很?。合萑刖植孔顑?yōu)解的可能性很大 m很大：PSO的優(yōu)化能力很好，計(jì)算量大17q 權(quán)重因子慣性權(quán)重w w=0：粒子很容易趨向

8、于同一位置 w小：傾向于局部探索,精細(xì)搜索目前的小區(qū)域 w大：擴(kuò)展新的搜索區(qū)域,利于全局搜索慣性慣性部分部分社會(huì)認(rèn)知社會(huì)認(rèn)知個(gè)體認(rèn)知個(gè)體認(rèn)知kk-111idid1 12 2v =wv()()kkididdidc r pbestxc r gbestx18q 權(quán)重因子學(xué)習(xí)因子c1，c2慣性慣性部分部分社會(huì)認(rèn)知社會(huì)認(rèn)知個(gè)體認(rèn)知個(gè)體認(rèn)知kk-111idid1 12 2v =wv()()kkididdidc r pbestxc r gbestxC1=0社會(huì)模型 只有社會(huì)，沒(méi)有自我 迅速喪失群體多樣性 易陷入局優(yōu)而無(wú)法跳出C2=0認(rèn)知模型 只有自我，沒(méi)有社會(huì) 完全沒(méi)有社會(huì)信息共享 算法收斂速度緩慢C1,C

9、20完全模型 收斂速度 搜索效果19q 最大速度Vm 作用： 維護(hù)算法的探索能力與開(kāi)發(fā)能力的平衡維護(hù)算法的探索能力與開(kāi)發(fā)能力的平衡 V Vm m較較大大時(shí)，探索能力增強(qiáng)，時(shí)，探索能力增強(qiáng)， 但但粒子粒子容易飛過(guò)容易飛過(guò)最優(yōu)解最優(yōu)解 V Vm m較較小小時(shí)，開(kāi)發(fā)能力時(shí)，開(kāi)發(fā)能力增強(qiáng)，增強(qiáng)， 但但容易容易陷入局部最優(yōu)陷入局部最優(yōu) V Vm m一般設(shè)為每維一般設(shè)為每維變量的取值范圍。變量的取值范圍。 20q 鄰域的拓?fù)浣Y(jié)構(gòu)全局模型p 粒子自己歷粒子自己歷史最優(yōu)值史最優(yōu)值p 粒子粒子群體群體的的全局最優(yōu)值全局最優(yōu)值p 收斂速度快收斂速度快p 容易容易陷入局陷入局部最優(yōu)解部最優(yōu)解局部模型u粒子自己歷粒子

10、自己歷史最優(yōu)值史最優(yōu)值u粒子粒子鄰域鄰域內(nèi)粒內(nèi)粒子的最優(yōu)值子的最優(yōu)值u收斂速度慢收斂速度慢u不易不易陷入局陷入局部最優(yōu)解部最優(yōu)解GbestPbest21q 優(yōu)點(diǎn) 1 1、參數(shù)較少，容易調(diào)整、參數(shù)較少，容易調(diào)整 2 2、局部與全局結(jié)合，收斂速度快、局部與全局結(jié)合，收斂速度快q 應(yīng)用 1 1、神經(jīng)網(wǎng)絡(luò)的訓(xùn)練、神經(jīng)網(wǎng)絡(luò)的訓(xùn)練 連接權(quán)重、網(wǎng)絡(luò)結(jié)構(gòu)和學(xué)習(xí)算法 2 2、連續(xù)問(wèn)題參數(shù)優(yōu)化、連續(xù)問(wèn)題參數(shù)優(yōu)化 機(jī)器人路徑規(guī)劃，電路優(yōu)化設(shè)計(jì)，數(shù)控加工參數(shù)優(yōu)化 3 3、組合優(yōu)化、組合優(yōu)化 車(chē)間調(diào)度 4 4、其他應(yīng)用、其他應(yīng)用 多目標(biāo)優(yōu)化，動(dòng)態(tài)目標(biāo)檢測(cè)，數(shù)據(jù)挖掘，系統(tǒng)辨識(shí)2223 = 0.618 c1 = c2 =2

11、swamSize = 3 maxgen = 3Vmax = 1 Vmin = -1popmax = 4 popmin = 0 參數(shù)設(shè)置參數(shù)設(shè)置2425262728293031 = 0.618 c1 = c2 =2swamSize = 10 maxgen = 10Vmax = 1 Vmin = -1popmax = 4 popmin = 0Tolerance = 1e-3 323334353637383940414243結(jié)果分析結(jié)果分析maxgen = 6x = 0.9383 ，y = 1.3706Tolerance = 4.308e-4 44參數(shù)設(shè)置參數(shù)設(shè)置 = 0.618 c1 = c2 =

12、2swamSize = 50 maxgen = 10Vmax = 1 Vmin = -1popmax = 4 popmin = 0Tolerance = 1e-3 454647484950結(jié)果分析結(jié)果分析maxgenxyTol10 60.9383461.370594.308e-45020.9359861.370573.070e-451參數(shù)設(shè)置參數(shù)設(shè)置 = 0.618 c1 = c2 =2swamSize = 50 maxgen = 10Vmax = 1 Vmin = -1popmax = 2 popmin = 0Tolerance = 1e-3 52535455565758結(jié)果分析結(jié)果分析maxgenxyTol4 10 60.9383461.370594.308e-44 5