第8講粒子算法

第8講智能優(yōu)化算法—粒子群算法（7.2)粒子群算法簡介基本粒子群算法改進的粒子群算法粒子群算法軟件計算粒子群算法應(yīng)用

粒子群算法簡介

一、粒子群算法原理粒子群優(yōu)化算法(ParticleSwarmOptimization,PSO)是Eberhart和kennedy博士發(fā)明。源于對鳥群捕食的行為研究，PSO同遺傳算法類似，是一種基于迭代的優(yōu)化工具。系統(tǒng)初始化為一組隨機解，通過迭代搜索尋最優(yōu)值。在PSO算法中，每個優(yōu)化問題的解都是搜索空間中的一只鳥，被抽象為沒有質(zhì)量和體積的微粒，并將其延伸到N維空間，離子i在N維空間中的位置表示為一個矢量，每個粒子的飛行速度也為一個矢量，所有粒子都有一個被優(yōu)化的函數(shù)決定的適應(yīng)值(fitness)，每個粒子還有一個決定他們飛翔的方向和距離。粒子們知道到目前為止發(fā)現(xiàn)的最好位置（pbest）和現(xiàn)在的位置，這個可以看做是粒子自己的飛行經(jīng)驗，除此之外，每個粒子還知道目前為止所有粒子發(fā)現(xiàn)的最好位置（gbest,gbest是pbest中最好值），著可以看做是粒子同伴的經(jīng)驗。粒子是通過自己的經(jīng)驗和同伴中最好的經(jīng)驗來決定下一步的運動。

粒子群算法簡介二、粒子群算法技術(shù)問題粒子群算法的性能很大程度取決于算法的控制參數(shù)，粒子數(shù)、最大速度、學(xué)習(xí)因子、慣性權(quán)重等，各個參數(shù)的選取原則如下：1粒子數(shù)：粒子數(shù)的多少根據(jù)問題的復(fù)雜度自行決定。對于一般的優(yōu)化問題取20至40個；對比較簡單的問題10個粒子就可以；對于比較復(fù)雜的或特定的問題，粒子數(shù)可取100以上。2粒子的維度：由優(yōu)化問題決定；為解的維度，3粒子的范圍：由優(yōu)化問題決定，每一維可設(shè)定不同的范圍；4最大速度：決定粒子在一個循環(huán)中最大的移動距離，通常設(shè)定為粒子的范圍寬度；5學(xué)習(xí)因子：學(xué)習(xí)因子使粒子具有自我總結(jié)和向群體中優(yōu)秀個體學(xué)習(xí)的能力，從而向群體內(nèi)或鄰域內(nèi)最近點靠近，通常取為2，也可以相等，取值范圍0到4。6慣性權(quán)重：決定了對粒子當前速度繼承的多少，適合的選擇可以使粒子具有均衡的探索能力和開發(fā)能力，慣性權(quán)重的取法一般有常數(shù)法、線性遞減法、自適應(yīng)法等粒子群算法簡介三、粒子群算法的特點及應(yīng)用領(lǐng)域

1特點（1）粒子群算法以決策變量的編碼作為運算對象。

（2）粒子群算法直接以適應(yīng)度作為搜索信息，無需導(dǎo)數(shù)等其它輔助信息。

（3）粒子群算法使用多個點的搜索信息，具有隱含并行性。（4）粒子群算法使用概率搜索技術(shù)，而非確定性規(guī)則。

2應(yīng)用領(lǐng)域（1）函數(shù)優(yōu)化（2）組合優(yōu)化（3）生產(chǎn)調(diào)度（4）自動控制

（5）機器人學(xué)

（6）圖象處理

基本粒子群算法(7.2.1)

一、基本粒子群算法的構(gòu)成要素

1粒子數(shù)

2最大速度

3學(xué)習(xí)因子

4慣性權(quán)重基本粒子群算法(7.2.1)二、基本粒子群算法步驟

1隨機初始化種群中各種微粒的位置和速度；

2評價每個微粒的適應(yīng)度,將當前各微粒的位置和適應(yīng)值存儲在各微粒的pbest中,將所有pbest中適應(yīng)值最優(yōu)個體的位置和適應(yīng)值存于gbest中；

3用下面的式子更新粒子的速度和位移；

4對每個微粒子;將其適應(yīng)值與其經(jīng)歷過的最好位置作比較,如果較好,則將其作為當前的最好位置；

5比較當前所有pbest和gbes的值，更新gbes；

6若滿足停止條件（通常為預(yù)設(shè)的運算精度或迭代步數(shù)），搜索停止，輸出結(jié)果，否則返回3，繼續(xù)搜索。二階粒子群算法(7.2.2)一、二階粒子群算法原理在標準PSO算法中，微粒的飛行速度僅僅是微粒當前位置的函數(shù)，而二階粒子群算法中微粒飛行速度的變化與微粒位置的變化有關(guān)，其速度更新公式為：二階粒子群算法(7.2.2)二、二階粒子群算法步驟

1隨機初始化種群中各種微粒的位置和速度；

2評價每個微粒的適應(yīng)度,將當前各微粒的位置和適應(yīng)值存儲在各微粒的pbest中,將所有pbest中適應(yīng)值最優(yōu)個體的位置和適應(yīng)值存于gbest中；

3用下面的式子更新粒子的速度和位移；

4對每個微粒子;將其適應(yīng)值與其經(jīng)歷過的最好位置作比較,如果較好,則將其作為當前的最好位置；

5比較當前所有pbest和gbes的值，更新gbes；

6若滿足停止條件（通常為預(yù)設(shè)的運算精度或迭代步數(shù)），搜索停止，輸出結(jié)果，否則返回3，繼續(xù)搜索。基于選擇的粒子群算法(7.2.3)一、基于選擇的粒子群算法原理

將遺傳算法中的選擇機理與粒子群算法相結(jié)合就得到基于選擇的粒子群算法?；舅枷耄好看蔚^程將整個粒子群按適應(yīng)值排序,用群體最好的一半的粒子的速度和位置替換最差的一半的位置和速度,同時保留原來每個個體所記憶的歷史最優(yōu)值。基于選擇的粒子群算法(7.2.3)二、基于選擇的粒子群算法步驟

1隨機初始化種群中各種微粒的位置和速度；

2評價每個微粒的適應(yīng)度,將當前各微粒的位置和適應(yīng)值存儲在各微粒的pbest中,將所有pbest中適應(yīng)值最優(yōu)個體的位置和適應(yīng)值存于gbest中；

3用下面的式子更新粒子的速度和位移；

4對每個微粒子;將其適應(yīng)值與其經(jīng)歷過的最好位置作比較,如果較好,則將其作為當前的最好位置；

5比較當前所有pbest和gbes的值，更新gbes；

6將整個粒子群按適應(yīng)值排序，用群體中最好的一半的粒子的速度和位置替換最差的一半的位置和速度，保持pbest和gbest不變。

7若滿足停止條件（通常為預(yù)設(shè)的運算精度或迭代步數(shù)），搜索停止，輸出結(jié)果，否則返回3，繼續(xù)搜索?；诮徊娴牧Ｗ尤核惴?7.2.4)一、基于交叉的粒子群算法原理借鑒遺傳算法中的交叉概念，在每次迭代中，根據(jù)交叉概率選取制定數(shù)量的粒子放入交叉池內(nèi)，池中的粒子隨機兩輛交叉，產(chǎn)生同樣數(shù)目的子代粒子（child），并用子代粒子替換親代粒子（parent）。子代位置由父代位置進行算術(shù)交叉得到：其中

p是0到1之間的隨機數(shù)。子代的速度由下式計算或或基于交叉的粒子群算法(7.2.4)二、基于交叉的粒子群算法步驟

1隨機初始化種群中各種微粒的位置和速度；

2評價每個微粒的適應(yīng)度,將當前各微粒的位置和適應(yīng)值存儲在各微粒的pbest中,將所有pbest中適應(yīng)值最優(yōu)個體的位置和適應(yīng)值存于gbest中；

3用下面的式子更新粒子的速度和位移；

4對每個微粒子;將其適應(yīng)值與其經(jīng)歷過的最好位置作比較,如果較好,則將其作為當前的最好位置；

基于交叉的粒子群算法(7.2.4)二、基于交叉的粒子群算法步驟

5比較當前所有pbest和gbes的值，更新gbes；

6根據(jù)交叉概率選取指定數(shù)量的粒子放入交叉池內(nèi)，池中的粒子隨機兩兩交叉產(chǎn)生同樣數(shù)目的子代粒子，子代的位置和速度計算公式如下：

保持pbest和gbest不變。

7若滿足停止條件（通常為預(yù)設(shè)的運算精度或迭代步數(shù)），搜索停止，輸出結(jié)果，否則返回3，繼續(xù)搜索。粒子群算法的軟件實現(xiàn)一、基本粒子群算法的Matlab實現(xiàn)

1計算函數(shù)的格式函數(shù)：PSO。功能：用基本粒子群算法求解無約束極值問題。調(diào)用格式：[xv,fv]=PSO(fitness,N,c1,c2,w,M,D)

其中：fitness:待優(yōu)化的目標函數(shù);N:粒子數(shù)目;c1:學(xué)習(xí)因子1;c2:學(xué)習(xí)因子2;w:慣性權(quán)重;M:最大迭代次數(shù);D:問題的維數(shù);xv:目標函數(shù)的最小值點;fv:目標函數(shù)的最小值。

粒子群算法的軟件計算一、基本粒子群算法的Matlab實現(xiàn)

2舉例例7-4采用基本粒子群算法求SphereModel的最小值。解：首先建立目標函數(shù)文件fitness.m，輸入內(nèi)容如下：

FunctionF=fitness(x)F=0; fori=1:30F=F+x(i)^2;end

在MATLAB命令窗口中輸入：>>[xv,fv]=PSO(@fitness,40,2,2,0.5,1000,30)>>[xv,fv]=PSO(@fitness,40,2,2,0.5,5000,30)>>[xv,fv]=PSO(@fitness,40,2,2,0.5,10000,30)粒子群算法的軟件計算一、基本粒子群算法的Matlab實現(xiàn)

迭代步數(shù)1000500010000x10.171159151-0.09655836-0.015987273x20.1420736240.008334669-0.001818132x3-0.1819121030.0186364210.004625648x40.1003362930.1037824360.038768164x5-0.166995445-0.0301029570.007716967x60.0356615090.0060840490.015746696x70.037148320.013657669-0.00238339x80.0457441510.010931290.023852163x9-0.171087980.0429103380.007423934x100.055131632-0.15093465-0.014160336x110.0457441510.076321997-0.032519146x12-0.171087980.0044026080.006066822x130.0551316320.026024016-0.007677664x140.2564633330.011989153-0.027326272x15-0.1307773830.0166517660.01974572x160.116058331-0.0073606770.014704575表7-1迭代步數(shù)不同時粒子群法求解結(jié)果比較表迭代步數(shù)1000500010000x17-0.098250698-0.038645847-0.037417556x18-0.168572745-0.012203864-0.061915582x190.0833436250.038583338-0.046837159x200.0988520890.089216026-0.022234846x210.07067315-0.074770647-0.071276469x22-0.2220526430.0072028790.049688358x23-0.0408937950.015707451-0.006258405x240.210061935-0.0290495680.090448281x25-0.1281979520.019223623-0.013524576x260.216501635-0.0202020740.01044023x27-0.0875019130.007375891-0.040697535x280.060820255-0.036771138-0.00546114x29-0.24635774-0.041702041-0.04696722x30-0.013847313-0.0616090710.010652994函數(shù)極值0.6475372570.078922440.033415582粒子群算法的軟件計算一、基本粒子群算法的Matlab實現(xiàn)

從表7-1的求解結(jié)果可以看出,在其他參數(shù)不變的情況下,一般迭代步數(shù)越大,求得的精度越高,但這并不是絕對的,因為PSO算法本質(zhì)上也是一種隨機算法,即使用同樣的參數(shù),每次求解也可能得出不同的結(jié)果,同時如果對于多峰函數(shù),PSO算法還可能陷入局部最優(yōu)點。

下面再看粒子群規(guī)模對結(jié)果的影響，學(xué)習(xí)因子都為2，慣性權(quán)重為0.5，迭代步數(shù)都為10000，粒子群規(guī)模分別取50、60和80。在MATLAB命令窗口中輸入：>>[xv,fv]=PSO(@fitness,50,2,2,0.5,10000,30)>>[xv,fv]=PSO(@fitness,60,2,2,0.5,10000,30)>>[xv,fv]=PSO(@fitness,80,2,2,0.5,10000,30)粒子群算法的軟件計算一、基本粒子群算法的Matlab實現(xiàn)

迭代步數(shù)506080x1-0.0113103460.0074255830.032168404x20.0043878460.0048179140.018358567x3-0.0066672460.0018556090.022236195x40.0059684390.0143353340.011242284x50.00915497-0.001267227-0.020372561x6-0.051987837-0.0054969170.022033454x7-0.0286875740.00010960.052377912x8-0.0177265260.008815249-0.023582598x90.012876614-0.00195790.03170092x100.011624676-0.0015827040.0014189874x11-0.0233624320.034052767-0.013562149x12-0.042501880.015367050.046835547x130.0132199080.0066061990.032128767x14-0.010243719-0.0087775810.040258144x15-0.011879719-0.000378132-0.000129326x16-0.031978858-0.004513022-0.049016752表7-2種群數(shù)不同時粒子群法求解結(jié)果比較表

迭代步數(shù)506080x17-0.021793246-0.013723932-0.083971611x18-0.014866581-0.0009891410.021355323x190.032450927-0.0036157330.007294525x20-0.025591814-0.005227237-0.027505171x21-0.0091624940.0036420450.030514614x220.053509427-0.007972992-0.006440302x23-0.004734495-0.0059175490.043635763x240.007099750.0127190950.021021241x25-0.0004611460.0003873220.04026069x26-0.003042356-0.0026208750.016406857x27-0.0052418520.006107442-0.051622937x28-0.009992668-0.07381692-0.021966852x290.01191555-0.0120409020.038647243x300.012901919-0.0024714870.060333511函數(shù)極值0.0141168710.0026933620.036639153粒子群算法的軟件計算一、基本粒子群算法的Matlab實現(xiàn)

從表7-2的求解結(jié)果可以看出，粒子群的規(guī)模不是越大越好，關(guān)鍵是各參數(shù)之間的搭配，搭配好才能求得比較好的結(jié)果。這需要反復(fù)試算。粒子群算法的軟件實現(xiàn)二、二階粒子群算法的Matlab實現(xiàn)

1計算函數(shù)的格式函數(shù)：SecPSO。功能：用基本粒子群算法求解無約束極值問題。調(diào)用格式：[xv,fv]=SecPSO(fitness,N,c1,c2,w,M,D)

其中：fitness:待優(yōu)化的目標函數(shù);N:粒子數(shù)目;、

c1:學(xué)習(xí)因子1;c2:學(xué)習(xí)因子2;w:慣性權(quán)重;M:最大迭代次數(shù);D:問題的維數(shù);xv:目標函數(shù)的最小值點;fv:目標函數(shù)的最小值。

粒子群算法的軟件計算二、二階粒子群算法的Matlab實現(xiàn)

2舉例例7-5

采用二階粒子群算法實現(xiàn)求下面函數(shù)的最小值取粒子數(shù)為40，學(xué)習(xí)因子都取1，慣性權(quán)重取0.7，迭代步數(shù)取100000。解：首先建立目標函數(shù)文件fitness.m，輸入內(nèi)容如下：

FunctionF=fitness(x)F=(x(2)-5.1*x(1)^2/4/pi/pi+5*x(1)/pi-6)^2+10*(1-1/8/pi)*cos(x(1))+10;

在MATLAB命令窗口中輸入：>>[xv,fv]=SecPSO(@fitness,40,0.7,1,1,10000,2)所得結(jié)果：xv=3.1415926630158902.274999989919220fv=0.397887357729738粒子群算法的軟件實現(xiàn)三、基于選擇的粒子群算法的Matlab實現(xiàn)

1計算函數(shù)的格式

函數(shù)：SelPSO。功能：用基本粒子群算