采用群智能算法的多約束問題優(yōu)化

郜懷通，王榮杰,2，曾廣淼，劉文霞

(1．集美大學(xué)輪機(jī)工程學(xué)院，福建 廈門 361021；2．福建省船舶與海洋重點實驗室，福建 廈門 361021)

0 引言

為了應(yīng)對越來越復(fù)雜的優(yōu)化問題，人們基于生命系統(tǒng)，研究出了諸多優(yōu)化算法，比如基于“優(yōu)勝劣汰，適者生存”的進(jìn)化類算法，典型代表有：通過遺傳和變異進(jìn)行求解的遺傳優(yōu)化算法(genetic algorithm,GA)[1]、模仿生物群體的合作和競爭進(jìn)行求解的差分進(jìn)化方法(differential evolution,DE)[2]、模仿生物體內(nèi)免疫系統(tǒng)的進(jìn)化進(jìn)行求解的免疫算法(immune algorithm,IA)[3]等。模仿生物種群覓食和遷徙行為群智能算法典型代表有：模仿鳥群遷徙行為求解的粒子群優(yōu)化算法(particle swarm optimization,PSO)[4]、模仿蜂群覓食行為求解的人工蜂群優(yōu)化算法(artificial bee colony,ABC)[5]、模仿蟻群覓食行為求解的蟻群優(yōu)化算法(ant colony optimization,ACO)[6]等。

國內(nèi)外主要將群智能優(yōu)化算法應(yīng)用于解決多約束問題，Kamil等[7]提出了一種使用群智能算法來增強(qiáng)水下圖像顏色的方法;Guan等[8]將改進(jìn)的群算法用于船舶內(nèi)殼的參數(shù)設(shè)計與優(yōu)化，在保證船舶安全性的同時，極大地提高了船舶的載運能力；Zhang等[9]將群智能算法用于圖像分割，可以更加精確地從圖像中提取有意義的特征，提高了圖像識別的精度。

ABC算法和PSO算法，在無約束目標(biāo)優(yōu)化中展現(xiàn)出了較好的收斂性和搜索性。本文使用這兩種算法對多個約束優(yōu)化問題進(jìn)行處理。文中對約束處理有如下的創(chuàng)新：

1)對算法第k次迭代得到的優(yōu)化解,將其滿足約束條件的個數(shù)q(k)設(shè)定為權(quán)值，進(jìn)行優(yōu)化解替換時,優(yōu)先考慮權(quán)值的大小，使更新解始終滿足q(k)≥q(k-1)，k≥2。

2)改進(jìn)的群智能算法將步長由確定值改為每次迭代都會變化的隨機(jī)值，增強(qiáng)了算法的搜索能力。

1 約束問題

約束優(yōu)化問題的形式如式(1)所示：

適應(yīng)度函數(shù)：f(x1,…,xn)。

約束條件：

(1)

式(1)中，存在n個自變量x1,…,xn，定義域為[zi,oi]，求得的向量x=[x1,…,xn]在使得f(x1,…,xn)的解最優(yōu)的同時，需要滿足所有約束函數(shù)gj(x1,…,xi)的值域。

求解過程中，一次需要求出多組優(yōu)化解，分別儲存在向量x1,…,xK中，設(shè)定k=1,…,K，如果向量xk滿足約束條件的個數(shù)大于向量xk+1滿足約束條件的個數(shù)，則xk優(yōu)于xk+1;如果xk滿足約束條件的個數(shù)等于xk+1滿足約束條件的個數(shù)，則比較xk與xk+1的適應(yīng)度函數(shù)，確定最優(yōu)值。即以xk滿足約束條件的個數(shù)(即等式/不等式gj(x)成立的個數(shù))作為最高評價準(zhǔn)則，其次比較xk的適應(yīng)度函數(shù)值f(xk)。

這就要求在通過算法求解的過程中需要建立評價函數(shù)，將每組自變量滿足條件的個數(shù)，儲存在向量aevaluate中，用于選擇優(yōu)質(zhì)的自變量。

本文選擇解決方案由式(2)所示。

(2)

其中：F(x)用來存放適應(yīng)度函數(shù)；f(x)max是滿足所有約束的解中可行性最差的解。如果求得的解均不能滿足所有的約束條件，則f(x)max取值為0。

2 群智能算法

2.1 ABC算法

ABC算法主要分為初始化、工蜂(EB)、觀察蜂(OB)、偵查蜂(SB)四個階段[10-11]。初始化階段設(shè)定蜂群的規(guī)模為sn，維度為n，使用式(3)隨機(jī)生成初始解ai,j,

ai,j=a_minj+rand[0 1]·(a_maxj-a_minj)。

(3)

其中：rand[0 1]表示在0～1產(chǎn)生一個隨機(jī)數(shù)；a_maxj和a_minj分別為蜜源a第j維的解能取到的最大值和最小值，j=1,2,…,n,i=1,2,…,sn。將a存入矩陣v。

EB、OB和SB階段蜜源的位置由式(4)進(jìn)行更新，

a(i,j)=v(i,j)+2{rand[0 1]-0.5}[v(i,j)-v(r,j)]。

(4)

其中：r是[1sn]之間隨機(jī)的一個整數(shù)，且不等于i。

ABC算法的運算流程如圖1所示。

ABC算法在實際應(yīng)用中被發(fā)現(xiàn)了一些固有的缺點。例如，在處理單峰問題時，收斂速度比差分優(yōu)化算法慢。除此之外，在解決復(fù)雜的多模態(tài)問題時，極容易陷入局部最優(yōu)[13]。為了平衡ABC算法的探索和開發(fā)能力，眾多研究人員開始對ABC算法進(jìn)行改進(jìn)。比如使用自適應(yīng)方法改進(jìn)ABC算法[13-14]，引入其他群智能算法的搜索方程改進(jìn)ABC算法[15-16]。

本文中使用了文獻(xiàn)[17]提出的MABC算法。MABC算法參考了具有較強(qiáng)全局收斂能力和穩(wěn)健性的DE算法[18]，引入了DE算法的搜索方程。MABC算法的搜索方程如下所示。

EB階段:ebi,j=amin,j+rand[0 1](amax,j-amin,j);

OB階段:obi,j=ebi,j+rand[0 1](ebr,j-ebi,j);

SB階段:sbi,j=obi,j+2{rand[0 1]-0.5}(obi,j-obk,j)。

其中：ebi,j、obi,jsbi,j分別代表EB、OB、SB階段的更新解；amin,j和amax,j分別代表蜜源ai,j第j維的最小值和最大值；r,l,k皆為[1np]之間一個隨機(jī)的整數(shù)，且r≠l≠i,k≠i。

2.2 PSO算法

PSO算法的初始化方程如式(5)所示：

(5)

其中：ai,j是粒子群的初始位置；vi,j是粒子群的初始速度；amin,j和amax,j分別是位于矩陣a第j維的最小值和最大值；vmin,j和vmax,j分別是速度v第j維的最小值和最大值。

進(jìn)行一次搜索之后，粒子群的位置和速度根據(jù)式(6)進(jìn)行更新：

Vi,j=w-vi,j+c1rand[0 1](pj-ai,j)+

c2rand[0 1](gj-ai,j)，Xi,j=ai,j+Vi,j。

(6)

其中：p是粒子群的個體最優(yōu)位置；g是粒子群的全局最優(yōu)位置；w是粒子的慣性權(quán)重，代表粒子有維持自己先前速度的趨勢，用來平衡算法的全局收斂能力和局部收斂能力，一般取值為[0.8，1.2]；c1、c2是粒子群的學(xué)習(xí)因子，用來調(diào)節(jié)粒子向p和g方向的搜索長度，一般都取值為1.5。

PSO算法優(yōu)化流程如圖2所示。

3 算法的多約束問題優(yōu)化

3.1 ABC算法的實現(xiàn)

使用ABC算法進(jìn)行優(yōu)化時，步驟如下。

步驟1：設(shè)定蜂群的數(shù)量為sn，i=1,2,…,sn，蜂群維度為n，j=1,2,…,n。最大迭代次數(shù)設(shè)為K；迭代次數(shù)計數(shù)器為k，k=0,1,2,…。允許連續(xù)得不到更優(yōu)解的次數(shù)設(shè)為Klimit，連續(xù)得不到更優(yōu)解的計數(shù)器為t，t=0,1,2,…；創(chuàng)建存儲矩陣G。

步驟2：蜂群初始化。

1)設(shè)定第j維的優(yōu)化解能取到的最大值為a_maxj，最小值為a_minj；k=0。

2)初始化蜂群，通過式(3)創(chuàng)建初始解a。將初始解a存入矩陣v，矩陣a、v第i行數(shù)據(jù)分別表示為ai和vi。

3)設(shè)定適應(yīng)度函數(shù)f(x)，約束函數(shù)gd(x)，d=1,…,D，D為約束函數(shù)的個數(shù)。設(shè)定第i組解滿足約束函數(shù)個數(shù)的計數(shù)器為ddi，ddi=1,…,D。滿足的約束條件越多，適應(yīng)度函數(shù)的值越靠近目標(biāo)值，尋到的解越好。

4)計算矩陣v第i組解的f(xi)和ddi，i=1,2,…,sn。

步驟3：EB階段。

1)若t≤Klimit,使用式(4)創(chuàng)建更新解a；若t≥Klimit，使用式(3)創(chuàng)建更新解a且令t=0。

2)如若出現(xiàn)ai,j>a_maxj或ai,j

3)計算更新解a第i組解的適應(yīng)度函數(shù)值f_eb(xi)和滿足約束的個數(shù)dd_ebi，i=1,2,…,sn。

4)對比ddi和dd_ebi，如果ddidd_ebi保留vi；若ddi=dd_ebi，對比f(xi)和f_eb(xi)，若f_eb(xi)比f(xi)更靠近目標(biāo)值，將vi替換為ai，否則保留vi。i=1,2,…,sn。

5)若適應(yīng)度函數(shù)最優(yōu)值沒有得到更新，t=t+1。

6)若t>Klimit，則跳至步驟3 1)。

步驟4：OB階段。

1)使用式(4)創(chuàng)建更新解a。

2)如若出現(xiàn)ai,j>a_maxj或ai,j

3)計算更新解a第i組解的適應(yīng)度函數(shù)值f_ob(xi)和滿足約束的個數(shù)dd_obi，i=1,2,…,sn。

4)對比ddi和dd_obi，如果ddidd_obi，保留vi；若ddi=dd_obi，對比f(xi)和f_ob(xi)，若f_ob(xi)比f(xi)更靠近目標(biāo)值，將vi替換為ai，否則保留vi。i=1,2,…,sn。

5)若適應(yīng)度函數(shù)最優(yōu)值沒有得到更新，t=t+1。

6)若t>Klimit，則跳至步驟3 1)。

步驟5：SB階段。

1)使用式(4)創(chuàng)建更新解a。

2)如若出現(xiàn)ai,j>a_maxj或ai,j

3)計算更新解a第i組解的適應(yīng)度函數(shù)值f_sb(xi)和滿足約束的個數(shù)dd_sbi，i=1,2,…,sn。

4)對比ddi和dd_sbi，如果ddidd_sbi，保留vi；若ddi=dd_sbi，對比f(xi)和f_sb(xi)，若f_sb(xi)比f(xi)更靠近目標(biāo)值，將vi替換為ai，否則保留vi。i=1,2,…,sn。

5)若適應(yīng)度函數(shù)最優(yōu)值沒有得到更新，t=t+1。

6)若t>Klimit，則跳至步驟3 1)。

7)令k=k+1。

8)Gk,1～n儲存第k次迭代中的最優(yōu)解，Gk,n+1儲存對應(yīng)的適應(yīng)度函數(shù)值。

9)若k≥K，進(jìn)行步驟f；不然跳至步驟3 1)。

10)輸出最優(yōu)解儲存矩陣G。

3.2 PSO算法的實現(xiàn)

使用PSO算法進(jìn)行優(yōu)化時，步驟如下。

步驟1：設(shè)定粒子群的數(shù)量為sn，i=1,2,…,sn，粒子群的維度為n，j=1,2,…,n。最大迭代次數(shù)設(shè)為K；迭代次數(shù)計數(shù)器為k，k=0,1,2,…；慣性權(quán)重設(shè)為ω；學(xué)習(xí)因子設(shè)為c1和c2；創(chuàng)建存儲矩陣G，儲存?zhèn)€體最優(yōu)位置的向量P，儲存全局最優(yōu)位置的向量g。

步驟2：粒子群初始化。

1)設(shè)定第j維的優(yōu)化解的能取到的最大值為amax,j，最小值為amin,j，最大速度為vmax,j，最小速度為vmin,j；k=0。

2)初始化粒子群，通過式(5)創(chuàng)建粒子群初始位置a，粒子群初始速度v，矩陣a和v的第i行數(shù)據(jù)分別表示為ai和vi。

3)設(shè)定適應(yīng)度函數(shù)f(x)，約束函數(shù)gd(x)，d=1,…,D，D為約束函數(shù)的個數(shù)。設(shè)定第i組解滿足約束函數(shù)的個數(shù)的計數(shù)器為ddi，ddi=1,…,D。滿足的約束條件越多，適應(yīng)度函數(shù)的值越靠近目標(biāo)值，尋到的解越好。

4)計算初始解a第i組解的f(xi)和ddi，i=1,2,…,sn。

步驟3：更新粒子群。

1)使用式(6)更新粒子群的速度V和位置A，矩陣A、V的第i行數(shù)據(jù)分別表示為Ai和Vi。

2)如若出現(xiàn)Vi,j>v_maxj，Vi,ja_maxj或Ai,j

3)計算更新解A第i組解的適應(yīng)度函數(shù)值f_A(xi)和滿足約束的個數(shù)dd_Ai，i=1,2,…,sn。

4)對比ddi和dd_Ai，如果ddidd_Ai保留ai和vi；若ddi=dd_Ai，對比f(xi)和f_A(xi)，若f_A(xi)比f(xi)更靠近目標(biāo)值，將ai替換為Ai，vi替換為Vi，否則保留保留ai和vi,i=1,2,…,sn，更新向量p和g。

5)令k=k+1。

6)Gk,1～n儲存第k次迭代中的最優(yōu)解，Gk,n+1儲存對應(yīng)的適應(yīng)度函數(shù)值。

7)若k≥K，進(jìn)行步驟d；不然跳至步驟3 1)。

步驟4：輸出最優(yōu)解儲存矩陣G。

4 仿真實驗分析

本節(jié)中，使用6個測試函數(shù)，分別用三個算法進(jìn)行計算，所有的問題中，都從不同的初始自變量開始運行30次，ABC算法和MABC算法中的蜂群個數(shù)sn都設(shè)置為20，PSO中的粒子群個數(shù)sn設(shè)置為100。

本文使用的6個測試函數(shù)如下所示。

測試函數(shù)1。

約束函數(shù)：g1(x)=4.84-(x1-0.05)2-(x2-2.5)2≥0；

測試函數(shù)2。

約束函數(shù)：g1(x)=10-(2x1+2x2+x10+x11)≥0；

g2(x)=10-(2x1+2x3+x10+x12)≥0；

g3(x)=10-(2x1+2x3+x10+x12)≥0；

g4(x)=-(-8x1+x10)≥0；

g5(x)=-(-8x2+x11)≥0；

g6(x)=-(-8x3+x12)≥0；

g7(x)=-(-2x4-x5+x10)≥0；

g8(x)=-(-2x6-x7+x11)≥0；

g9(x)=-(-2x8-x9+x12)≥0；

0≤xi≤1,i=1,…,9，0≤xi≤100,i=10,11,12，0≤xi≤1,i=13。

測試函數(shù)3。

適應(yīng)度函數(shù)：

-10≤xi≤10,i=1,2,…,7。

測試函數(shù)4。

約束函數(shù)：g1(x)=85.334 407+0.005 685 8x2x5+0.000 626 2x1x4-0.002 205 3x3x5≥0；

g2(x)=92-(85.334 407+0.005 685 8x2x5+0.000 626 2x1x4-0.002 205 3x3x5)≥0；

g3(x)=80.512 49+0.071 317x2x5+0.002 995 5x1x2+0.002 181 3x3-90≥0;

g4(x)=110-(80.512 49+0.0713 17x2x5+0.002 995 5x1x2+0.002 181 3x3)≥0;

g5(x)=9.300 961+0.004 702 6x3x5+0.001 254 7x1x3+0.001 908 5x3x4-20≥0；

g6(x)=25-(9.300 961+0.004 702 6x3x5+0.001 254 7x1x3+0.001 908 5x3x4)≥0，

78≤x1≤102， 33≤x2≤45， 27≤xi≤45,i=3,4,5。

測試函數(shù)5。

適應(yīng)度函數(shù)：f5(x)=-0.5(x1x4-x2x3+x3x9-x5x9+x5x8-x6x7)。

g5(x)=-((x1-x5)2+(x2-x6)2-1)≥0；

g6(x)=-((x1-x7)2+(x2-x8)2-1)≥0；

g7(x)=-((x3-x5)2+(x4-x6)2-1)≥0；

g8(x)=-((x3-x7)2+(x4-x8)2-1)≥0；

g10(x)=-(x2x3-x1x4)≥0；

g11(x)=x3x9≥0；

g12(x)=-x5x9≥0；

g13(x)=-(x6x7-x5x8)≥0；

-10≤xi≤10,i=1,…,8，0≤x9≤20。

測試函數(shù)6。

2(x6-1)2+5x7+7(x8-11)2+2(x9-10)2+(x10-7)2+45。

約束函數(shù)：g1(x)=105-4x1-5x2+3x7-9x8≥0;

g2(x)=-10x1+8x2+17x7-2x8≥0；

g3(x)=8x1-2x2-5x9+2x10+12≥0；

g8(x)=3x1-6x2-12(x9-8)2+7x10≥0,

10≤xi≤10,i=1,…,10。

使用MABC、ABC、PSO算法分別對測試函數(shù)進(jìn)行優(yōu)化計算，每個函數(shù)計算30次，對這30次計算的最優(yōu)值、最差值、中值、平均值進(jìn)行統(tǒng)計，結(jié)果如表1所示。

表1 優(yōu)化結(jié)果

由表1可得，MABC算法和ABC算法對約束問題的處理能力強(qiáng)于PSO算法。同樣的迭代次數(shù)，MABC算法得到的解優(yōu)于ABC算法得到的解。由約束函數(shù)5可知，PSO算法會陷入局部最優(yōu)，導(dǎo)致結(jié)果會出現(xiàn)較大的波動。

將約束函數(shù)每次迭代得到的最優(yōu)值進(jìn)行統(tǒng)計，繪制出每個約束函數(shù)的適應(yīng)度進(jìn)化曲線，用來評價函數(shù)的收斂能力，如圖3所示。

如圖3a和圖3e所示，f1和f5中，ABC算法和MABC算法均尋到了滿足全部約束的解，MABC算法的收斂能力優(yōu)于ABC算法的收斂能力。PSO算法陷入了局部最優(yōu)，尋不到滿足所有約束的解。

如圖3b所示，約束函數(shù)2中，三種算法都尋到了滿足全部約束條件的解，PSO算法得到的解相較于其他兩種算法差。MABC算法對最優(yōu)值的搜索能力優(yōu)于ABC算法。

如圖3c所示，約束函數(shù)3中，三個算法尋找到的最優(yōu)解皆能滿足全部約束條件。搜索過程中因為以滿足約束條件作為第一標(biāo)準(zhǔn)，PSO算法出現(xiàn)了大程度的波動。三個算法中最優(yōu)值仍然由MABC算法尋到。

如圖3d和圖3f所示，約束函數(shù)4和約束函數(shù)6中，MABC算法和ABC算法都搜索到了滿足所有約束函數(shù)的解，但MABC算法搜索到的解明顯優(yōu)于ABC算法搜索到的解。PSO算法陷入局部最優(yōu)，沒能搜索到滿足全部約束的解。

在群智能算法中種群數(shù)量的大小對算法的收斂能力和搜索能力有著較大的影響，上文使用的MABC算法的蜂群數(shù)量都為20，為了進(jìn)一步分析種群數(shù)量對MABC算法性能的影響，將蜂群數(shù)量分別更改為5、10、15、25、30、50，并統(tǒng)計了這7種情況取的最優(yōu)解所需的迭代次數(shù)，如表2所示。

由表2可得：在相同的迭代次數(shù)的情況下，蜂群數(shù)量為5和10時，收斂和搜索能力，相較于上文選擇的20都有明顯的下降，容易出現(xiàn)不能滿足全部約束的情況，容易出現(xiàn)局部最優(yōu)的情況；蜂群數(shù)量為15，在進(jìn)行足夠迭代次數(shù)的情況下，可以取得最優(yōu)解；蜂群數(shù)量為25和30時，對仿真結(jié)果的收斂速度有一定的影響，但均能得到讓人滿意的最優(yōu)解；蜂群數(shù)量為50時，算法會在較少迭代次數(shù)的情況下得到最優(yōu)解，收斂曲線會在開始就出現(xiàn)斷崖式下跌，不利于比較算法的優(yōu)化能力。最后的仿真結(jié)果發(fā)現(xiàn)群智能算法中的種群數(shù)量對算法收斂和搜索的能力有著極大的影響，優(yōu)化過程中應(yīng)通過多次嘗試，盡可能地選擇合適的種群數(shù)量。

表2 種群數(shù)量對算法優(yōu)化能力的影響

5 結(jié)論

本文提出利用群智能算法處理多約束優(yōu)化問題。首先構(gòu)造同時計算約束條件和優(yōu)化適應(yīng)度的目標(biāo)函數(shù)，然后建立約束問題的數(shù)學(xué)模型，進(jìn)行ABC算法和PSO算法的仿真實驗。仿真結(jié)果可知，MABC算法的收斂和搜索能力強(qiáng)于ABC算法和PSO算法；PSO算法在約束問題的處理上，容易陷入局部最優(yōu)，普適性弱于ABC和MABC算法。本文基于群智能算法的多約束問題優(yōu)化方法可以廣泛應(yīng)用于油船內(nèi)殼結(jié)構(gòu)優(yōu)化，規(guī)劃無人機(jī)的航行軌跡等工程領(lǐng)域。