粒子群算法課件

粒子群算法粒子群算法1223Reynolds,Heppner,Grenader等發(fā)現(xiàn)，鳥群在行進(jìn)過程中會突然同步地改變方向，散開或聚集。一定有種潛在的規(guī)則在起作用，據(jù)此他們提出了對鳥群行為的模擬。在他們的早期模型中，僅僅依賴個體間距的操作，即群體的同步是個體之間努力保持最優(yōu)距離的結(jié)果。3Reynolds,Heppner,Grenader等發(fā)現(xiàn)，41987年Reynolds對鳥群社會系統(tǒng)的仿真研究，一群鳥在空中飛行，每個鳥遵守以下三條規(guī)則：1）避免與相鄰的鳥發(fā)生碰撞沖突；2）盡量與自己周圍的鳥在速度上保持協(xié)調(diào)和一致；3）盡量試圖向自己所認(rèn)為的群體中靠近。僅通過使用這三條規(guī)則，系統(tǒng)就出現(xiàn)非常逼真的群體聚集行為，鳥成群地在空中飛行，當(dāng)遇到障礙時它們會分開繞行而過，隨后又會重新形成群體。作為CAS實例41987年Reynolds對鳥群社會系統(tǒng)的仿真研究，一群鳥5Kennedy和Eberhart在CAS中加入了一個特定點，定義為食物，鳥根據(jù)周圍鳥的覓食行為來尋找食物。他們的初衷是希望通過這種模型來模擬鳥群尋找食源的現(xiàn)象，然而實驗結(jié)果卻揭示這個仿真模型中蘊(yùn)涵著很強(qiáng)的優(yōu)化能力，尤其是在多維空間尋優(yōu)中。5Kennedy和Eberhart在CAS中加入了一個特定點6鳥群覓食行為FoodGlobalBestSolutionPastBestSolution6鳥群覓食行為FoodGlobalBestSolutio7算法介紹PSO算法是一種進(jìn)化計算技術(shù)（evolutionarycomputation)，由Eberhart博士和Kennedy博士于1995年提出（KennedyJ,EberhartR.Particleswarmoptimization.ProceedingsofIEEEInternationalConferenceonNeuralNetworks.1995,1942~1948).其基本思想是通過群體中個體之間的協(xié)作和信息共享來尋找最優(yōu)解。7算法介紹PSO算法是一種進(jìn)化計算技術(shù)（evolution基本PSO算法每個粒子在n維空間中，位置表示為矢量飛行速度表示為矢量

基本PSO算法每個粒子在n維空間中，位置表示為矢量

89基本PSO算法PSO初始化為一群隨機(jī)粒子（隨機(jī)解）。然后通過迭代尋找最優(yōu)解。每次迭代中，粒子通過跟蹤兩個極值（pbest：某個粒子到現(xiàn)在為止發(fā)現(xiàn)的最好位置。gbest:整個群體到目前為止發(fā)現(xiàn)的最好位置）來更新自己。更新的公式如下：（1）速度更新：

(2)位置更新：

其中c1和c2是學(xué)習(xí)因子(加速因子)，通常取c1=c2=2,rand()為[0，1]之間的隨機(jī)數(shù)；在每一維，粒子都有一個最大限制速度Vmax。應(yīng)將Vi限制在[-Vmax,Vmax]之間。

9基本PSO算法PSO初始化為一群隨機(jī)粒子（隨機(jī)解）。然后通10基本PSO算法

10基本PSO算法

11

11

12標(biāo)準(zhǔn)PSO算法流程：1、初始化一群微粒（規(guī)模為m），包括隨機(jī)位置和速度。2、評價每個微粒的適應(yīng)度3、尋找每個微粒的pbest4、尋找到目前為止的gbest5、調(diào)整(更新)各微粒的速度和位置6、未達(dá)到結(jié)束條件則轉(zhuǎn)到2迭代終止條件一般選為最大迭代次數(shù)或（和）誤差滿足預(yù)定閾值。群體規(guī)模m一般取20~40，對較難或特定類別的問題可取到100~20012標(biāo)準(zhǔn)PSO算法流程：1、初始化一群微粒（規(guī)模為m），包13其中，C1,C2為正常數(shù)，稱為加速因子；rand()為[0，1]之間的隨機(jī)數(shù)；w稱慣性因子，w較大適于對解空間進(jìn)行大范圍探查(exploration)，w較小適于進(jìn)行小范圍開挖(exploitation)。w大則全局尋優(yōu)能力強(qiáng)，局部尋優(yōu)能力弱。w小則反之。實驗發(fā)現(xiàn)，動態(tài)改變w效果可能更好。慣性系數(shù)

13其中，C1,C2為正常數(shù)，稱為加速因子；rand()14目前采用較多的是線性遞減權(quán)值（linearlydecreasingweight,LDW)策略：

w(t)=(wini-wend)(Gk-t)/Gk+wend

Gk為最大進(jìn)化代數(shù)，wini為初始慣性權(quán)值，wend為迭代至最大代數(shù)時慣性權(quán)值。典型取值為：wini=0.9,wend=0.4.

t是當(dāng)前代數(shù)。

慣性系數(shù)14目前采用較多的是線性遞減權(quán)值（linearlydecr15PSO算法的特點（1）PSO算法搜索過程是從一組解迭代到另一組解，采用同時處理群體中多個個體的方法，具有本質(zhì)的并行性；（2）PSO算法采用實數(shù)進(jìn)行編碼，直接在問題域上進(jìn)行處理，無需轉(zhuǎn)換，因此算法簡單，易于實現(xiàn)；（3）PSO算法的各粒子的移動具有隨機(jī)性，可搜索不確定的復(fù)雜區(qū)域（4）PSO算法具備有效的全局/局部搜索的平衡能力，避免早熟；（5）PSO算法在優(yōu)化過程中，每個粒子通過自身經(jīng)驗與群體經(jīng)驗進(jìn)行更新，具有學(xué)習(xí)能力；（6）PSO算法得到的解的質(zhì)量不依賴初始點的選取，保證收斂性；（7）PSO算法可求解帶離散變量的優(yōu)化問題，但是對離散變量的取整可能導(dǎo)致較大的誤差15PSO算法的特點（1）PSO算法搜索過程是從一組解迭代到粒子群算法ppt課件1617標(biāo)準(zhǔn)PSO算法流程：1、初始化一群微粒（規(guī)模為m），包括隨機(jī)位置和速度。2、評價每個微粒的適應(yīng)度3、尋找每個微粒的pbest4、尋找到目前為止的gbest5、調(diào)整(更新)各微粒的速度和位置6、未達(dá)到結(jié)束條件則轉(zhuǎn)到2迭代終止條件一般選為最大迭代次數(shù)或（和）誤差滿足預(yù)定閾值。群體規(guī)模m一般取20~40，對較難或特定類別的問題可取到100~20017標(biāo)準(zhǔn)PSO算法流程：1、初始化一群微粒（規(guī)模為m），包c1=1.49445;c2=1.49445;maxgen=300;%進(jìn)化次數(shù)sizepop=20;%種群規(guī)模Vmax=0.5;Vmin=-0.5;popmax=2;popmin=-2;fori=1:sizepop

pop(i,:)=2*rands(1,2);%初始種群V(i,:)=0.5*rands(1,2);%初始化速度

%計算適應(yīng)度

fitness(i)=fun(pop(i,:));%染色體的適應(yīng)度endc1=1.49445;18%%個體極值和群體極值[bestfitnessbestindex]=max(fitness);zbest=pop(bestindex,:);%全局最佳gbest=pop;%個體最佳fitnessgbest=fitness;%個體最佳適應(yīng)度值fitnesszbest=bestfitness;%全局最佳適應(yīng)度值%%個體極值和群體極值19%%迭代尋優(yōu)fori=1:maxgenforj=1:sizepop

%速度更新

V(j,:)=V(j,:)+c1*rand*(gbest(j,:)-pop(j,:))+c2*rand*(zbest-pop(j,:));V(j,find(V(j,:)>Vmax))=Vmax;V(j,find(V(j,:)<Vmin))=Vmin;

%種群更新

pop(j,:)=pop(j,:)+V(j,:);pop(j,find(pop(j,:)>popmax))=popmax;pop(j,find(pop(j,:)<popmin))=popmin;%適應(yīng)度值

fitness(j)=fun(pop(j,:));end%%迭代尋優(yōu)20

forj=1:sizepop

%個體最優(yōu)更新

iffitness(j)>fitnessgbest(j)gbest(j,:)=pop(j,:);fitnessgbest(j)=fitness(j);

end

%群體最優(yōu)更新

iffitness(j)>fitnesszbestzbest=pop(j,:);fitnesszbest=fitness(j);end

endyy(i)=fitnesszbest;forj=1:sizepop2122目前，常用的粒子群算法將全體粒子群(Global)分成若干個有部分粒子重疊的相鄰子群，每個粒子根據(jù)子群(Local)內(nèi)歷史最優(yōu)Pl調(diào)整位置子群22子群23Note合理解目前最優(yōu)解區(qū)域最佳解全域區(qū)域23Note合理解目前最優(yōu)解區(qū)域最佳解全域區(qū)域24鳥群覓食行為FoodGlobalBestSolutionPastBestSolution24鳥群覓食行為FoodGlobalBestSoluti25

25

26標(biāo)準(zhǔn)PSO算法流程：1、初始化一群微粒（規(guī)模為m），包括隨機(jī)位置和速度。2、評價每個微粒的適應(yīng)度3、尋找每個微粒的pbest4、尋找到目前為止的gbest5、調(diào)整(更新)各微粒的速度和位置6、未達(dá)到結(jié)束條件則轉(zhuǎn)到2迭代終止條件一般選為最大迭代次數(shù)或（和）誤差滿足預(yù)定閾值。群體規(guī)模m一般取20~40，對較難或特定類別的問題可取到100~20026標(biāo)準(zhǔn)PSO算法流程：1、初始化一群微粒（規(guī)模為m），包27其中，C1,C2為正常數(shù)，稱為加速因子；rand()為[0，1]之間的隨機(jī)數(shù)；w稱慣性因子，w較大適于對解空間進(jìn)行大范圍探查(exploration)，w較小適于進(jìn)行小范圍開挖(exploitation)。w大則全局尋優(yōu)能力強(qiáng)，局部尋優(yōu)能力弱。w小則反之。實驗發(fā)現(xiàn)，動態(tài)改變w效果可能更好。慣性系數(shù)

27其中，C1,C2為正常數(shù)，稱為加速因子；rand()28目前采用較多的是線性遞減權(quán)值（linearlydecreasingweight,LDW)策略：

w(t)=(wini-wend)(Gk-t)/Gk+wend

Gk為最大進(jìn)化代數(shù)，wini為初始慣性權(quán)值，wend為迭代至最大代數(shù)時慣性權(quán)值。典型取值為：wini=0.9,wend=0.4.

t是當(dāng)前代數(shù)。

慣性系數(shù)28目前采用較多的是線性遞減權(quán)值（linearlydecr29車輛路徑問題

車輛路徑問題(VehicleRoutingProblem，VRP)由Dantzig和Ramser于1959年首次提出的，它是指對一系列發(fā)貨點(或收貨點)，組成適當(dāng)?shù)男熊嚶窂?，使車輛有序地通過它們，在滿足一定約束條件的情況下，達(dá)到一定的目標(biāo)(諸如路程最短、費(fèi)用最小，耗費(fèi)時間盡量少等)，屬于NP完全問題，在運(yùn)籌、計算機(jī)、物流、管理等學(xué)科均有重要意義。29車輛路徑問題車輛路徑問題(VehicleRout30車輛路徑問題

如何找到一個合適的表達(dá)（部分）解的方法，使粒子與解對應(yīng)，是實現(xiàn)算法的關(guān)鍵難點之一。30車輛路徑問題如何找到一個合適的表達(dá)（部分）解的方法，31車輛路徑問題構(gòu)造一個2L維的空間對應(yīng)有L個發(fā)貨點任務(wù)的VRP問題，每個發(fā)貨點任務(wù)對應(yīng)兩維：完成該任務(wù)車輛的編號k，該任務(wù)在k車行駛路徑中的次序r為表達(dá)和計算方便，將每個粒子對應(yīng)的2L維向量X分成兩個L維向量：Xv

(表示各任務(wù)對應(yīng)的車輛)和Xr(表示各任務(wù)在對應(yīng)的車輛路徑中的執(zhí)行次序)。31車輛路徑問題構(gòu)造一個2L維的空間對應(yīng)有L個發(fā)貨點任務(wù)的V32例如，設(shè)VRP問題中發(fā)貨點任務(wù)數(shù)為7，車輛數(shù)為3，若某粒子的位置向量X為：發(fā)貨點任務(wù)號:1234567

Xv

：1222233

Xr：1431221則該粒子對應(yīng)解路徑為：車1：0

1

0車2：0

4

5

3

2

0車3：0

7

6

0粒子速度向量V與之對應(yīng)表示為Vv和Vr。32例如，設(shè)VRP問題中發(fā)貨點任務(wù)數(shù)為7，車輛數(shù)為3，若某粒33

該表示方法的最大優(yōu)點是使每個發(fā)貨點都得到車輛的配送服務(wù)，并限制每個發(fā)貨點的需求僅能由某一車輛來完成，使解的可行化過程計算大大減少。雖然該表示方法的維數(shù)較高，但由于PSO算法在多維尋優(yōu)問題有著非常好的特性，維數(shù)的增加并未增加計算的復(fù)雜性，這一點在實驗結(jié)果中可以看到。33該表示方法的最大優(yōu)點是使每個發(fā)貨點都得到車輛的配送34VRP問題為整數(shù)規(guī)劃問題，因此在算法實現(xiàn)過程中要做相應(yīng)修改。具體實現(xiàn)步驟如下：Step1：初始化粒子群。

1.1粒子群劃分成若干個兩兩相互重疊的相鄰子群；

1.2每個粒子位置向量Xv的每一維隨機(jī)取1～K（車輛數(shù)）之間的整數(shù)，Xr的每一維隨機(jī)取1～L(發(fā)貨點任務(wù)數(shù))之間的實數(shù)；

1.3每個速度向量Vv的每一維隨機(jī)取-(K-1)～(K-1)（車輛數(shù)）之間的整數(shù)，Vr的每一維隨機(jī)取-(L-1)～(L-1)之間的實數(shù)；

1.4用評價函數(shù)Eval評價所有粒子；

1.5將初始評價值作為個體歷史最優(yōu)解Pi，并尋找各子群內(nèi)的最優(yōu)解Pl和總?cè)后w內(nèi)最優(yōu)解Pg。34VRP問題為整數(shù)規(guī)劃問題，因此在算法實現(xiàn)過程中要做相應(yīng)修35Step2：重復(fù)執(zhí)行以下步驟，直到滿足終止條件或達(dá)到最大迭代次數(shù)。

2.1對每一個粒子，按式(1)計算Ｖv、Ｖr；按照式(2)計算Xv、Xr，其中Xv向上取整；當(dāng)Ｖ、X超過其范圍時按邊界取值；

2.2用評價函數(shù)Eval評價所有粒子；

2.3若某個粒子的當(dāng)前評價值優(yōu)于其歷史最優(yōu)評價值，則記當(dāng)前評價值為該歷史最優(yōu)評價值，同時將當(dāng)前位置向量記為該粒子歷史最優(yōu)位置Pi;2.4尋找當(dāng)前各相鄰子群內(nèi)最優(yōu)和總?cè)后w內(nèi)最優(yōu)解，若優(yōu)于歷史最優(yōu)解則更新Pl

、Pg。對于子群內(nèi)有多個體同為最優(yōu)值的情況，則隨機(jī)取其中一個為子群內(nèi)當(dāng)前最優(yōu)解。3536其中，評價函數(shù)Eval完成以下任務(wù):1、根據(jù)公式計算該粒子所代表路徑方案的行駛成本Z，在計算中發(fā)貨點任務(wù)的執(zhí)行次序要根據(jù)對應(yīng)Xr值的大小順序，由小到大執(zhí)行。2、將Xr按執(zhí)行順序進(jìn)行重新整數(shù)序規(guī)范。例如，某粒子迭代一次后結(jié)果如下：

Xv

：1222233

Xr：53.26.21.22.5

0.54.2評價后重新規(guī)范的Xr是：1341212說明：對于整數(shù)序規(guī)范的理解請觀察對車輛2的排序和整理結(jié)果。36其中，評價函數(shù)Eval完成以下任務(wù):37實驗：問題為一個有7個發(fā)貨點任務(wù)的車輛路徑問題，各任務(wù)點的坐標(biāo)及貨運(yùn)量見下表：表1各發(fā)貨點坐標(biāo)及貨運(yùn)量序號01234567坐標(biāo)(18,54)(22,60)(58,69)(71,71)(83,46)(91,38)(24,42)(18,40)貨運(yùn)量(gi)0.890.140.280.330.210.410.57注：序號0表示中心倉庫，設(shè)車輛容量皆為q=1.0，由3輛車完成所有任務(wù)。(最優(yōu)路徑距離為217.81)37實驗：問題為一個有7個發(fā)貨點任務(wù)的車輛路徑問題，各任務(wù)點38GA參數(shù)：群體規(guī)模n=40；交叉概率Pc=0.6；變異概率Pm=0.2；輪盤賭法選擇子代，最大代數(shù)200。PSO參數(shù)：粒子數(shù)n=40；分為2個子群，子群規(guī)模為22，子群間重疊的粒子數(shù)為2個（子群規(guī)模的1/10）；w=0.729；c1=c2=1.49445；最大代數(shù)200。兩種方法各運(yùn)行50次，結(jié)果如下表所示。

實驗1GA、PSO方法結(jié)果對比方法達(dá)到最優(yōu)路徑次數(shù)未達(dá)最優(yōu)路徑次數(shù)達(dá)到最優(yōu)路徑平均代數(shù)達(dá)到最優(yōu)路徑的平均時間(s)GA321853.932.3PSO50028.363.0438GA參數(shù)：群體規(guī)模n=40；交叉概率Pc=0.6；變異概39帶時間窗車輛路徑問題

帶時間窗的車輛路徑問題(VehicleRoutingProblemWithTimeWindows,VRPTW)是在VRP問題上加了客戶要求訪問的時間窗口（時間段）。由于在現(xiàn)實生活中許多問題都可以歸結(jié)為VRPTW問題來處理(如郵政投遞、火車及公共汽車的調(diào)度等)，其處理的好壞將直接影響到企業(yè)的服務(wù)質(zhì)量,所以對它的研究越來越受到人們的重視。先后出現(xiàn)了一般啟發(fā)式算法和神經(jīng)網(wǎng)絡(luò)、遺傳算法、禁忌搜索和模擬退火等智能化啟發(fā)式算法，也取得了一些較好的效果。39帶時間窗車輛路徑問題帶時間窗的車輛路徑問題(Vehi40帶時間窗車輛路徑問題時間窗車輛路徑問題一般描述為：有一個中心倉庫，擁有車K輛，容量分別為qk

(k=1,..,K)；現(xiàn)有L個發(fā)貨點運(yùn)輸任務(wù)需要完成，以1,…,L表示。第i個發(fā)貨點的貨運(yùn)量為gi(i=1,…,L)，(max(gi)≤max(qi))，完成發(fā)貨點i任務(wù)需要的時間(裝貸或卸貨)表示為Ti，且任務(wù)i且必須在時間窗口[ETi,LTi]完成，其中ETi為任務(wù)i的允許最早開始時間，LTi為任務(wù)i的允許最遲開始時間。如果車輛到達(dá)發(fā)貨點i的時間早于ETi，則車輛需在i處等待；如果車輛到達(dá)時間晚于LTi，任務(wù)i將被延遲進(jìn)行。pE為在某地點等待的單位時間成本，pL為在某地點未完成任務(wù)的罰金。求滿足貨運(yùn)要求的運(yùn)行費(fèi)用最少的車輛行駛線路。40帶時間窗車輛路徑問題時間窗車輛路徑問題一般描述為：有一個41容量約束為地點i運(yùn)貨的卡車只能有一輛如果kj為1，有且僅有1個i去往j卡車k從i駛向j如果ki為1，從i出發(fā)的弧段有一個為141容量約束為地點i運(yùn)貨的卡車只能有一輛如果kj為1，有且cij表示地點i和j之間路徑上的行駛代價，xijk表示為卡車k從i駛向j，yki表示表示編號為k的車為地點i發(fā)貨，si表示第i個地點的開始卸貨的時間，pE表示管理者認(rèn)為由于提前到達(dá)某個地點而未完成任務(wù)所導(dǎo)致的損失大小，pL表示管理者認(rèn)為由于晚到某個地點而未完成任務(wù)所帶來的損失大小，其中(2)號約束表示每輛車k的運(yùn)貨總量gi*yki應(yīng)該小于該車的容量qk。（3）和（8）決定為地點i運(yùn)貨的卡車只能有一輛（4）表示：如果卡車k為地點j送貨，那么它只能從｛1..L｝中的1個且僅1個地點出發(fā)駛向j。（5）表示如果卡車k為地點i運(yùn)貨，那么卡車k應(yīng)該離開地點i。cij表示地點i和j之間路徑上的行駛代價，xijk表示為卡車4243

實驗2，采用VRPTW的例子，該問題有8項貨物運(yùn)輸任務(wù)，貨物點位置及時間窗略。實驗結(jié)果如下：實驗2GA、PSO方法結(jié)果對比搜索成功率平均行駛成本平均成功搜索時間GA24%993.618.41sPSO46%940.58.53s43實驗2，采用VRPTW的例子，該問題有8項貨物運(yùn)輸44ParticleSwarm研究熱點IEEETRANSACTIONONEVOLUTIONARYCOMPUTION于2004年出版了第3卷：SPECIALISSUEONPSO。RussellC.Eberhart,YuhuiShi在卷首語中指出了當(dāng)前PSO研究的幾個主要方向及熱點：1

算法分析；2粒子群拓?fù)浣Y(jié)構(gòu)；3參數(shù)選擇與優(yōu)化；4與其他演化計算的融合；5應(yīng)用。44ParticleSwarm研究熱點IEEETR動態(tài)拓?fù)涞牧Ｗ尤簝?yōu)化動態(tài)計算差異度，并斷開差異度小的邊動態(tài)拓?fù)涞牧Ｗ尤簝?yōu)化動態(tài)計