李清霞

東莞城市學(xué)院 計算機與信息學(xué)院，廣東 東莞 523419

在科學(xué)和工程領(lǐng)域，諸如航班調(diào)度和網(wǎng)絡(luò)負載均衡等問題都是約束優(yōu)化問題（constrained optimization problem，COP）[1]，并且至今仍是一個具有挑戰(zhàn)性的研究領(lǐng)域。由于約束優(yōu)化問題在科學(xué)及工程問題中的重要性，許多處理約束優(yōu)化問題的算法被提出[2-7]?；谔荻鹊膬?yōu)化方法作為處理約束優(yōu)化問題的一個典型方法得到了廣泛的應(yīng)用，但是后來人們發(fā)現(xiàn)基于梯度的優(yōu)化方法不足以解決所有的約束優(yōu)化問題，特別是對于具有多個局部最優(yōu)解的優(yōu)化問題。因此，進化算法應(yīng)運而生。該類算法不需要使用任何梯度信息，而且更容易實現(xiàn)，更為重要的是其能以最低的計算效率得到最優(yōu)解。

近幾十年來，進化算法得到了空前的發(fā)展，特別是能夠處理約束優(yōu)化問題的進化算法，主要包括遺傳算法（genetic algorithm，GA）[2]、粒子群優(yōu)化算法（particle swarm optimization，PSO）[3]、差分進化算法（differential evolution，DE）[4]、蜜蜂算法（artificial bee colony，ABC）[5]、共生生物搜索算法（symbiotic organisms search，SOS）[6]和風(fēng)驅(qū)動水波優(yōu) 化 算 法（ wind-driven water wave optimization，WDWWO）[7]等。這些進化算法大多數(shù)都是受自然啟發(fā)的，這意味著它們起源于生態(tài)系統(tǒng)中生物的行為或相互作用。例如，差分進化算法源自于種群進化選擇過程，粒子群優(yōu)化算法取自生物體的運動行為，共生生物搜索算法來自生態(tài)系統(tǒng)中生物體的共生相互作用。在所有進化算法中，都是從初始種群開始搜索，并將其引導(dǎo)到具有更好適應(yīng)值的解。然而根據(jù)“沒有免費的午餐”理論[8]，沒有哪種單一的進化算法能夠?qū)λ械募s束優(yōu)化問題都具有良好的優(yōu)化效果。這是因為所有進化算法對于約束優(yōu)化問題求解都存在各自的優(yōu)勢，即不同的進化算法都存在著各自的優(yōu)缺點，某一類進化算法可能只適合于求解某些類型的約束優(yōu)化問題，這使得混合多種進化算法求解約束優(yōu)化問題成為了可能。

混合多種進化算法就是使混合的各算法相互合作，提高求解優(yōu)化問題的性能[9]。因此許多著名的進化算法的組合已經(jīng)被提出用于解決約束優(yōu)化 問 題， 如PSGA[10]、PSO-DE[11]、GWO-DE[12]、HCS-LSAL[13]、HABCDE[14]等。這 些 混合進化 算法（如PSGA）與其他單一的進化算法相比，能夠通過較少的函數(shù)評估次數(shù)就可獲得最優(yōu)解。

為了設(shè)計出更好的混合進化算法，則需要了解每一種進化算法的優(yōu)勢和不足，也需要在搜索過程中充分平衡探索和勘探，以獲得最佳的搜索結(jié)果。探索和勘探本質(zhì)上是相互矛盾的，如差分進化算法在探索過程中表現(xiàn)良好，那么它在勘探性搜索中就會表現(xiàn)得很弱，反之亦然。粒子群優(yōu)化算法是一種基于種群的算法，在面對多模態(tài)函數(shù)時，它往往很快收斂到一個局部極小值，從而錯過了全局最優(yōu)的機會。共生生物搜索算法是一種簡單而強大的進化算法，它模擬了生物在生態(tài)系統(tǒng)中生存和繁殖所采取的共生互動策略。該算法的主要優(yōu)點是不需要在算法開始時設(shè)置任何特定的參數(shù)[6]。利用這種優(yōu)勢，只需設(shè)置幾個參數(shù)就可以與其他進化算法進行混合。差分進化算法在種群擇優(yōu)選擇的時候存在偶然性，它按概率進行擇優(yōu)，選擇更優(yōu)的種群進行迭代。另外，粒子群優(yōu)化算法具有學(xué)習(xí)策略，即在每次迭代中，它為種群中的每個元素存儲最優(yōu)的子代。共生生物搜索算法雖然沒有采用學(xué)習(xí)策略存儲每個生物體的最優(yōu)解，但它的最優(yōu)解卻會影響下一代的迭代結(jié)果。利用每種進化算法的優(yōu)點，結(jié)合它們的進化特性，彌補各自的不足，本文提出了一種混合差分進化、粒子群優(yōu)化和共生生物搜索的進化算法（簡稱HDPS）用以解決約束工程優(yōu)化問題。由于以往混合的進化算法基本上都是兩類進化算法的組合，導(dǎo)致了求解約束優(yōu)化問題的優(yōu)勢并沒有完全展現(xiàn)出來。因此我們將差分進化、粒子群優(yōu)化和共生生物搜索這3 種進化算法結(jié)合起來，通過改進的懲罰函數(shù)和互利操作控制算法的可行性及多樣性，達到求解約束優(yōu)化工程問題的最佳效果。這3 種算法的結(jié)合不僅沒有增加執(zhí)行時間，而且大大減少了執(zhí)行時間，即HDPS 算法具有較低的時間復(fù)雜度。實驗結(jié)果表明，與其他非混合或混合的進化算法相比，HDPS 算法能夠更快地解決大多數(shù)約束優(yōu)化問題，并且具有更高的成功率。

1 相關(guān)背景

1.1 約束優(yōu)化問題

一般搜索空間S中的約束優(yōu)化問題可由如下幾個方面構(gòu)成[1]：

1）目標(biāo)函數(shù)f(x)；

2）可行解向量x= (x1,x2, … ,xd)；

3）約束變量C=c1,c2, … ,cm為可行解滿足的約束條件。

其中d為問題空間維度，m為約束條件個數(shù)。一般的約束優(yōu)化問題可表示為

式中：gj(x)≤0 和hj(x)=0 分別表示q個不等式約束和m-q個等式約束，ui和li分別為向量xi的上界和下界。

1.2 差分進化算法

差分進化算法是目前最流行、應(yīng)用最廣泛的基于種群優(yōu)化的進化算法，依賴于偶然性搜索[4]。在差分進化算法中，種群大小一般設(shè)為N，每個種群中包含d維個體向量，t為迭代次數(shù)。差分進化算法主要有3 種操作：變異，交叉和選擇。

1）變異：通過變異操作隨時產(chǎn)生新的目標(biāo)向量，計算公式為

式中：xi,t=[xi,1,t,xi,2,t,…,xi,d,t]，其中i=1, 2,…,N，t為當(dāng)前種群的代數(shù)；F為縮放因子，是[0, 1]的隨機數(shù)。

2）交叉：交叉操作主要產(chǎn)生試驗變量ui,t，計算公式為

式中：i=1, 2,…,N,j=1, 2,…,d；jrand為[1,d]的一個隨機整數(shù)；randj(0, 1)為對于每個j產(chǎn)生[0,1]均勻分布的隨機數(shù)。

3）選擇：以一定的概率從種群中選擇更優(yōu)的個體進入下一代。一般，選擇過程是一種基于適應(yīng)度的優(yōu)勝劣汰的過程。

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

粒子群優(yōu)化算法首先是由Kennedy 等[3]提出的，其靈感來源于自然界中鳥類或魚類等生物的運動行為。它為種群中的每個個體調(diào)整策略，以搜索一個目標(biāo)函數(shù)空間。這些個體被稱為粒子，并用xi表示。在粒子群優(yōu)化算法中，首先在搜索空間中建立粒子的初始種群。在d維搜索空間中，每個粒子都有速度，速度用vi表示。每個粒子的最佳位置pbesti和種群的最佳位置gbest在每次迭代中存儲和更新，即粒子群優(yōu)化算法的本質(zhì)就是利用迭代過程中的運動經(jīng)驗進行最優(yōu)化求解。假設(shè)t是迭代次數(shù)，則粒子群優(yōu)化算法中粒子的速度和位置更新計算為

1.4 共生生物搜索算法

共生生物搜索算法是由Cheng 等[6]提出來的一種進化算法，其靈感來源于生態(tài)系統(tǒng)中生存的共生生物。共生生物搜索算法模擬了生態(tài)系統(tǒng)中成對生物關(guān)系的共生交互行為，試圖尋找合適的生物。在共生生物搜索算法中，種群中的個體被稱為生物體，每個生物體代表搜索空間中的一個點。共生生物搜索算法的一個顯著優(yōu)勢就是不需要在算法開始階段設(shè)置特定的參數(shù)，因此共生生物搜索算法比較容易實現(xiàn)，它的主要運算操作是采用類似于生物相互作用的互利共生、偏利共生和寄生操作更新每次迭代中有生物位置。即在每一個階段，如果這種關(guān)系使生物體i或j的適應(yīng)值更好，生物體的位置就會更新。

1）互利共生：互利共生主義就是對建立共生關(guān)系的2 個生物體都有利。例如與種群中第i個成員對應(yīng)的生物體xi和隨機選擇的生物體xj建立了共生關(guān)系，他們都希望在生態(tài)系統(tǒng)中增加彼此的生存優(yōu)勢，并從中受益，則生物體xi和xj的新位置可以表示為

式中：M為生物體xi和xj之間的關(guān)系；B1和B2為獲益因子，它們表示共生作用對于每個生物體的獲益情況，一般隨機取值1 或2；xbest為目前為止的最優(yōu)個體。

2）偏利共生：偏利共生是指對建立共生關(guān)系的2 個生物體中的一方有利，另一方不受影響（既不意味著獲益也不意味著受害）。與互利共生相似，在這一階段，生物體xj隨機地與生物體xi相互作用，但只有生物體xi受益于共生關(guān)系，而對生物體xj沒有影響。其更新計算公式為

3）寄生：寄生是指對建立共生關(guān)系的2 個生物體中的一方有利，同時另一方受害。例如在瘧蚊與人的關(guān)系中可以看到寄生現(xiàn)象，蚊子有益，人受到傷害。由于在這個階段有一個生物體受到傷害，就必須殺死受傷害的生物體，并用另一個替代它。此時，隨機選擇生物體xj作為寄生蟲載體的受害者，然后生物體xi在搜索空間中隨機選擇某些維度創(chuàng)建寄生向量。如果寄生蟲載體比選擇的xj更好，那么它會殺死xj并占據(jù)它的位置；否則xj將對寄生蟲有免疫力，并且可以比寄生蟲活得更長。

2 混合進化算法HDPS

2.1 算法思想

對于混合進化算法HDPS，采用差分進化算法從父輩選擇最優(yōu)的子代，這有助于粒子群優(yōu)化算法在更優(yōu)的子代中找到最優(yōu)解，并幫助共生生物搜索算法在共生互動中獲得更好的生存機會。差分進化算法與共生生物搜索算法組合后，由差分進化算法的變異和交叉操作產(chǎn)生更多優(yōu)質(zhì)的種群。共生生物搜索算法將利用這些優(yōu)質(zhì)的種群進行迭代，而不是使用自己產(chǎn)生的種群迭代。在通過差分進化算法選擇最優(yōu)種群之后，再使用粒子群優(yōu)化算法對比鄰居種群以獲得更好的解。因此在HDPS 算法中，迭代種群中的每一個個體都可以保證是最優(yōu)的。HDPS 算法步驟也可以這樣理解：在每個迭代周期中，首先采用差分進化算法產(chǎn)生初始種群，并運用差分進化算法的變異、交叉和選擇操作產(chǎn)生最優(yōu)子種群xbest，每個子種群包括了速度、位置、代價和最優(yōu)經(jīng)驗值等4 個參數(shù)。然后通過粒子群優(yōu)化算法檢查鄰居的解以獲得更好的解。在這個階段，如果位置移動能夠為個體帶來更好的適應(yīng)值，那么就更新位置，否則不作任何改變；如果個體的最優(yōu)適應(yīng)值優(yōu)于xbest（全局最優(yōu)），那么就更新xbest；所以粒子群優(yōu)化算法通過速度公式檢查該區(qū)域，并存儲每個個體的最優(yōu)適應(yīng)值并更新全局最優(yōu)。最后通過共生生物搜索算法的共生相互作用（互利、偏利和寄生）使它們獲得更好的適應(yīng)值；即如果個體交互得到了更好的適應(yīng)值，則更新個體的適應(yīng)值，否則不變。

2.2 改進的懲罰函數(shù)

懲罰函數(shù)是一種比較簡單可行的約束處理技術(shù)， 主 要 用 于 控 制1～2 個 約 束 條 件。 但在HDPS 算法中，必須要處理2 個以上的多個約束條件，因此就需要對傳統(tǒng)的懲罰函數(shù)進行改進以使HDPS 算法有更好的搜索性能。在HDPS 算法中，改進的懲罰函數(shù)能夠處理多個不等式或等式約束。對于違反約束條件的情況，則設(shè)違反約束程度為非零（ki=1），對于沒有違反約束條件的情況，則設(shè)違反約束程度為零（ki=0）。違反約束計算可表示為

懲罰函數(shù)的本質(zhì)就是將約束問題轉(zhuǎn)化為無約束問題來控制約束，如式(8)所示。在式(7)和式(8)中，φ(x)是新的目標(biāo)函數(shù)，ri是控制參數(shù)（違反約束因子），Vi是第i個約束沖突，ε=10-4。當(dāng)解不可行時，ki=1，否則ki=0。在HDPS 算法中，對于所有求解的問題，違反約束因子ri=10。

2.3 改進的互利操作

為了使共生生物搜索算法在求解問題時獲得更好的解，最優(yōu)個體xbest不需要在所有維度都和M向量做減法運算，而是選擇一個隨機維度執(zhí)行減法運算。假設(shè)用xbest,r表示最優(yōu)個體的一個隨機維度，Zr為{1, 2,…,d}內(nèi)的隨機整數(shù)，d為維度。則采用這種改進的互利操作后，生物體xi和xj不總是朝著最好的方向移動，而是朝著隨機的方向移動，這樣就給了其鄰居的機會，實現(xiàn)了種群的多樣性。改進之后的互利操作公式為

2.4 算法步驟

根據(jù)算法思想，HDPS 算法的具體步驟偽代碼如下：

圖1 HDPS 算法流程

2.5 時間復(fù)雜度分析

HDPS 算法包括了4 個主要部分，除了初始化部分，其他3 個部分都處于循環(huán)迭代中，這3 個部分分別對應(yīng)3 種混合算法的執(zhí)行過程。因此HDPS 算法的時間復(fù)雜度由這3 種混合算法的主要操作決定，這些操作主要包括：差分進化算法變異和交叉、粒子群優(yōu)化算法速度方程以及共生生物搜索算法交互算子（互利、偏利和寄生）。

設(shè)種群的大小為N，每個種群包含了由d維向量組成的個體。通過對算法的分析知道，差分進化算法變異和交叉操作的時間復(fù)雜度為O(Nd)，粒子群優(yōu)化算法中的速度方程和個體適應(yīng)值判斷的時間復(fù)雜度為O(Nd)，共生生物搜索算法計算個體適應(yīng)值和判斷新舊適應(yīng)值更新的時間復(fù)雜度也為O(Nd)。所以綜上所述，HDPS 算法的時間復(fù)雜度為O(Nd)。

3 實驗測試

本文對HDPS 算法和當(dāng)前幾個比較著名的混合和非混合的進化算法進行了實驗對比測試，測試用例為壓力容器設(shè)計工程優(yōu)化問題和減速器設(shè)計工程優(yōu)化問題。實驗軟件環(huán)境為Matlab 2013 和Windows 10 操作系統(tǒng)，硬件環(huán)境為Intel Core i7 CPU 2.1 GHZ 和8 GB 內(nèi)存。在參數(shù)設(shè)置方面，對于差分進化算法，交叉概率RC=0.7，縮放因子F=0.9；對于粒子群優(yōu)化算法，c1=c2=2。對于共生生物搜索算法則不需要設(shè)置參數(shù)。

3.1 壓力容器設(shè)計工程優(yōu)化問題

壓力容器設(shè)計工程優(yōu)化問題是約束工程優(yōu)化問題領(lǐng)域的經(jīng)典案例之一[15]，它的結(jié)構(gòu)包括一個半球形封頭蓋和一個圓柱體。對這個問題進行優(yōu)化的目標(biāo)是最小化生產(chǎn)總成本，包括材料成本、成形成本和焊接成本等。為了控制這些成本，在壓力容器的設(shè)計過程中，需要選擇一些參數(shù)，如殼體和封頭的厚度（Ts和Th）、內(nèi)半徑（R）和圓柱截面的長度（L），以使其成本最小化。該問題形式化為

式中：1×0.062 5≤xi≤99×0.062 5 (i= 1, 2)；10≤xi≤200 (i=3, 4)。

針對壓力容器設(shè)計問題，HDPS 算法與GA3[16]、PSO[3]、CPSO[17]、HPSO[18]、PSO-DE[11]、HCS-LSAL[13]、CMA-ES[19]、TLBO[20]、εDE-LS[21]以及εDE-PCGA[22]等算法進行了實驗對比。實驗結(jié)果如表1 和表2 所示。在表1中，與其他5 種算法相比，HDPS 算法可以達到最優(yōu)解，也就是達到設(shè)計要求的最小值6 059.714 3。在函數(shù)評估數(shù)和標(biāo)準(zhǔn)差方面，為了達到最優(yōu)解，HDPS 算法的函數(shù)評估次數(shù)NFEs=17 320，100 次獨立運行的標(biāo)準(zhǔn)偏差為4.36×10-13。由表2 可以看出，與其他算法相比，HDPS 算法在任何方面（函數(shù)評估次數(shù)NFEs、標(biāo)準(zhǔn)差Sstd等）都是最好的。

表1 HDPS 算法與其他算法針對壓力容器設(shè)計問題在最優(yōu)解方面的比較

表2 HDPS 算法與其他算法針對壓力容器設(shè)計問題在函數(shù)評估數(shù)和標(biāo)準(zhǔn)差方面的比較

3.2 減速器設(shè)計工程優(yōu)化問題

減速器設(shè)計工程優(yōu)化問題是由Golinski[23]提出的另一經(jīng)典的約束工程優(yōu)化問題，這個問題的目標(biāo)是使減速器的重量最小化。從設(shè)計結(jié)構(gòu)上看，減速器包含了2 個安裝了齒輪的獨立軸，這2 個軸通過軸承依次連接到主機架上。減速器設(shè)計工程優(yōu)化問題包含11 個不等式約束，需要通過選擇適當(dāng)?shù)脑O(shè)計參數(shù)來控制其重量的最小化：面寬(x1)、齒模(x2)、小齒輪齒數(shù)(x3)、軸承間第一軸長度(x4)、軸承間第二軸長度（x5）、第一軸直徑（x6）以及第二軸的直徑(x7)。

式中：2.6≤x1≤3.6, 0.7≤x2≤0.8, 17≤x3≤28, 7.3≤x4≤8.3, 7.3≤x5≤8.3, 2.9≤x6≤3.9, 5.0≤x7≤5.5。

針對減速器設(shè)計工程優(yōu)化問題，HDPS 算法與DELC[24]，DEDS[25]，HEAA[26]，HCPS[27]，PSGA[10]、CMA-ES[19]、HCS-LSAL[13]、MBA[28]、εDE-LS[21]和εDE-PCGA[22]等算法進行了對比實驗，實驗結(jié)果如表3 和表4 所示。從表3 可以看出，HDPS 算法與HCS-LSAL 算法都達到了設(shè)計所要求的最佳值；從表4 可以進一步發(fā)現(xiàn)，HDPS 算法的函數(shù)評估次數(shù)是所有算法中是最低的。

表3 HDPS 算法與其他算法針對減速器設(shè)計問題在最優(yōu)解方面的比較

表4 HDPS 算法與其他算法針對減速器設(shè)計問題在函數(shù)評估數(shù)和標(biāo)準(zhǔn)差方面的比較

4 結(jié)論

本文基于差分進化算法、粒子群優(yōu)化算法和共生生物搜索算法，提出了一種求解約束工程優(yōu)化問題的混合進化算法HDPS。該算法將差分進化算法、粒子群優(yōu)化算法和共生生物搜索3 種算法操作算子結(jié)合起來，對其中的部分算子進行了改進，提高了算法的效率和成功率。例如對共生生物搜索算法互利操作算子進行了改進，使其在一些約束問題上獲得了最佳搜索解的效果，這是其他算法所無法實現(xiàn)的。最后將HDPS 算法應(yīng)用到兩類經(jīng)典的約束工程設(shè)計優(yōu)化問題中進行實驗測試，實驗結(jié)果表明，與混合或非混合的進化算法相比，HDPS 算法不僅提升了問題求解精度，而且大大減少了函數(shù)評估的次數(shù)。