采用群智能算法的多約束問題優化

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

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

0 引言

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

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

ABC算法和PSO算法，在無約束目標優化中展現出了較好的收斂性和搜索性。本文使用這兩種算法對多個約束優化問題進行處理。文中對約束處理有如下的創新：

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

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

1 約束問題

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

適應度函數：f(x1,…,xn)。

約束條件：

(1)

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

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

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

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

(2)

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

2 群智能算法

2.1 ABC算法

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

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

(3)

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

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

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

(4)

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

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

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

本文中使用了文獻[17]提出的MABC算法。MABC算法參考了具有較強全局收斂能力和穩健性的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]之間一個隨機的整數，且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維的最小值和最大值。

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

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是粒子群的個體最優位置；g是粒子群的全局最優位置；w是粒子的慣性權重，代表粒子有維持自己先前速度的趨勢，用來平衡算法的全局收斂能力和局部收斂能力，一般取值為[0.8，1.2]；c1、c2是粒子群的學習因子，用來調節粒子向p和g方向的搜索長度，一般都取值為1.5。

PSO算法優化流程如圖2所示。

3 算法的多約束問題優化

3.1 ABC算法的實現

使用ABC算法進行優化時，步驟如下。

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

步驟2：蜂群初始化。

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

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

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

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

步驟3：EB階段。

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

2)如若出現ai,j>a_maxj或ai,j

3)計算更新解a第i組解的適應度函數值f_eb(xi)和滿足約束的個數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)更靠近目標值，將vi替換為ai，否則保留vi。i=1,2,…,sn。

5)若適應度函數最優值沒有得到更新，t=t+1。

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

步驟4：OB階段。

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

2)如若出現ai,j>a_maxj或ai,j

3)計算更新解a第i組解的適應度函數值f_ob(xi)和滿足約束的個數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)更靠近目標值，將vi替換為ai，否則保留vi。i=1,2,…,sn。

5)若適應度函數最優值沒有得到更新，t=t+1。

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

步驟5：SB階段。

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

2)如若出現ai,j>a_maxj或ai,j

3)計算更新解a第i組解的適應度函數值f_sb(xi)和滿足約束的個數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)更靠近目標值，將vi替換為ai，否則保留vi。i=1,2,…,sn。

5)若適應度函數最優值沒有得到更新，t=t+1。

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

7)令k=k+1。

8)Gk,1～n儲存第k次迭代中的最優解，Gk,n+1儲存對應的適應度函數值。

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

10)輸出最優解儲存矩陣G。

3.2 PSO算法的實現

使用PSO算法進行優化時，步驟如下。

步驟1：設定粒子群的數量為sn，i=1,2,…,sn，粒子群的維度為n，j=1,2,…,n。最大迭代次數設為K；迭代次數計數器為k，k=0,1,2,…；慣性權重設為ω；學習因子設為c1和c2；創建存儲矩陣G，儲存個體最優位置的向量P，儲存全局最優位置的向量g。

步驟2：粒子群初始化。

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

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

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

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

步驟3：更新粒子群。

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

2)如若出現Vi,j>v_maxj，Vi,ja_maxj或Ai,j

3)計算更新解A第i組解的適應度函數值f_A(xi)和滿足約束的個數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)更靠近目標值，將ai替換為Ai，vi替換為Vi，否則保留保留ai和vi,i=1,2,…,sn，更新向量p和g。

5)令k=k+1。

6)Gk,1～n儲存第k次迭代中的最優解，Gk,n+1儲存對應的適應度函數值。

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

步驟4：輸出最優解儲存矩陣G。

4 仿真實驗分析

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

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

測試函數1。

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

測試函數2。

約束函數：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。

測試函數3。

適應度函數：

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

測試函數4。

約束函數：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。

測試函數5。

適應度函數：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。

測試函數6。

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

約束函數：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算法分別對測試函數進行優化計算，每個函數計算30次，對這30次計算的最優值、最差值、中值、平均值進行統計，結果如表1所示。

表1 優化結果

由表1可得，MABC算法和ABC算法對約束問題的處理能力強于PSO算法。同樣的迭代次數，MABC算法得到的解優于ABC算法得到的解。由約束函數5可知，PSO算法會陷入局部最優，導致結果會出現較大的波動。

將約束函數每次迭代得到的最優值進行統計，繪制出每個約束函數的適應度進化曲線，用來評價函數的收斂能力，如圖3所示。

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

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

如圖3c所示，約束函數3中，三個算法尋找到的最優解皆能滿足全部約束條件。搜索過程中因為以滿足約束條件作為第一標準，PSO算法出現了大程度的波動。三個算法中最優值仍然由MABC算法尋到。

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

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

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

表2 種群數量對算法優化能力的影響

5 結論

本文提出利用群智能算法處理多約束優化問題。首先構造同時計算約束條件和優化適應度的目標函數，然后建立約束問題的數學模型，進行ABC算法和PSO算法的仿真實驗。仿真結果可知，MABC算法的收斂和搜索能力強于ABC算法和PSO算法；PSO算法在約束問題的處理上，容易陷入局部最優，普適性弱于ABC和MABC算法。本文基于群智能算法的多約束問題優化方法可以廣泛應用于油船內殼結構優化，規劃無人機的航行軌跡等工程領域。