求解約束優(yōu)化問(wèn)題的改進(jìn)元胞遺傳算法

謝蘊(yùn)文，魯宇明，劉 毅

(南昌航空大學(xué)航空制造工程學(xué)院，江西 南昌 330063)

1 引言

在航空航天、圖像處理、經(jīng)濟(jì)管理學(xué)等諸多領(lǐng)域當(dāng)中，約束優(yōu)化問(wèn)題廣泛存在，相對(duì)于普通優(yōu)化問(wèn)題，約束優(yōu)化問(wèn)題由于約束條件的限制，可行域會(huì)變得十分復(fù)雜，給問(wèn)題的求解帶來(lái)了極大的難度。傳統(tǒng)的數(shù)學(xué)規(guī)劃方法難以求解這種不連續(xù)，不可微的問(wèn)題，因此普遍采用群智能優(yōu)化方法處理此類問(wèn)題。

元胞遺傳算法(Cellular Genetic Algorithms，CGA)是將元胞遺傳算法和元胞自動(dòng)機(jī)相結(jié)合的進(jìn)化算法[1]。該算法可以使種群的多樣性保存的更加完整，從而在全局搜索以及局部尋優(yōu)之間可以得到充足的平衡。近些年來(lái)，元胞遺傳算法在路徑尋優(yōu)、多目標(biāo)優(yōu)化、車間布局等諸多領(lǐng)域都有著廣泛應(yīng)用且取得良好效果。

在處理約束優(yōu)化問(wèn)題上，一般采用約束處理技術(shù)與智能算法相結(jié)合的方法。董寧[2]等人采用多目標(biāo)約束處理技術(shù)與差分進(jìn)化算法相結(jié)合處理約束處理問(wèn)題；李二超[3]等人采用不同階段、對(duì)種群進(jìn)行不同存檔策略來(lái)對(duì)約束優(yōu)化問(wèn)題進(jìn)行處理；趙立進(jìn)[4]，陳健[5]等人采用ε約束處理技術(shù)與智能算法相結(jié)合也取得了良好的效果。

本文為改善約束優(yōu)化問(wèn)題在高維函數(shù)測(cè)試中效果不佳的情況，利用元胞遺傳算法多樣性保持良好的優(yōu)點(diǎn)，將元胞遺傳算法與改進(jìn)ε比較準(zhǔn)則相結(jié)合，提出偏好性指標(biāo)、改進(jìn)柯西變異算子的改進(jìn)方法。通過(guò)對(duì)一組標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行試驗(yàn)，驗(yàn)證了算法在高維問(wèn)題中的優(yōu)越性并在收斂精度上取得了良好的效果。

2 約束處理問(wèn)題及約束處理技術(shù)

2.1 約束優(yōu)化問(wèn)題

不失一般性，一個(gè)帶有等式約束、不等式約束的最小化優(yōu)化問(wèn)題用數(shù)學(xué)表達(dá)式可以描述為：

minf(x)，x=(x1，x2，…，xn)

s.tgi(x)≤0，i=1，2，3，…，q

hj(x)=0，j=q+1，…，m

(1)

其中f(x)為目標(biāo)函數(shù)，gi(x)表示第i個(gè)不等式約束，hj(x)表示第j個(gè)等式約束。

對(duì)于等式約束，一般方法就是把等式約束轉(zhuǎn)化成不等式約束，具體方法是給予等式約束一個(gè)極小的約束容忍度，如式(2)所示

(2)

其中δ代表等式約束的容忍度，一般取值為0.0001。

為了準(zhǔn)確表達(dá)種群中個(gè)體相對(duì)于可行域的距離，提出約束違反度的概念，其值越大，代表個(gè)體離可行域越遠(yuǎn)。約束違反度表達(dá)公式如式(3)所示

(3)

2.2 約束處理技術(shù)的比較準(zhǔn)則

為了對(duì)可行個(gè)體與不可行個(gè)體進(jìn)行比較，提出ε比較準(zhǔn)則[6]，以求最小值為例，主要由下面三條準(zhǔn)則構(gòu)成：

1)當(dāng)兩個(gè)個(gè)體都是可行個(gè)體時(shí)，取目標(biāo)函數(shù)值較小的個(gè)體

2)當(dāng)兩個(gè)個(gè)體都是不可行個(gè)體時(shí)，取約束違反度較小的個(gè)體

3)當(dāng)一個(gè)是可行個(gè)體而另一個(gè)個(gè)體是不可行個(gè)體時(shí)，如果不可行個(gè)體的約束違反度小于ε，則取目標(biāo)函數(shù)值較小的個(gè)體，如果不可行個(gè)體的約束違反度大于ε，則取可行個(gè)體。

ε的設(shè)置公式為：

(4)

式中，gen為進(jìn)化代數(shù)；ε(0)=1

方法的缺陷在于對(duì)于復(fù)雜的約束問(wèn)題收斂精度不高，多樣性不足。

3 改進(jìn)算法

3.1 元胞遺傳算法

元胞遺傳算法是將元胞自動(dòng)機(jī)與遺傳算法相結(jié)合發(fā)展起來(lái)的優(yōu)質(zhì)算法，其主要原理是把種群隨機(jī)分布在一個(gè)二維的拓?fù)浣Y(jié)構(gòu)中，把個(gè)體的競(jìng)爭(zhēng)與雜交行為都限制在一個(gè)局部范圍內(nèi)，保證了種群的多樣性，不容易陷入局部最優(yōu)解。圖1代表一般元胞遺傳算法的遺傳操作。

圖1 元胞遺傳算法的遺傳圖

3.2 差分進(jìn)化算法

差分進(jìn)化算法是目前處理約束優(yōu)化問(wèn)題表現(xiàn)最好的算法之一。其主要是利用個(gè)體之間的距離和方向距離對(duì)種群進(jìn)行直接搜索。文獻(xiàn)[7-9]對(duì)差分進(jìn)化算法中變異操作是生成下一代個(gè)體的化算法的常見(jiàn)方法進(jìn)行了論述。

下面表示三種一般的差分進(jìn)化算法的變異策略

(5)

其中F代表縮放因子，i、r1、r2代表[1，NP]中的隨機(jī)整數(shù)，且不相等。其中‘rand’的變異方式具有良好的全局搜索能力，能有效保持種群的多樣性；‘best’的變異方式以當(dāng)前種群中較好的個(gè)體作為基矢量，具有良好的收斂能力；‘current-to-best’的變異方式則對(duì)種群多樣性的保持和增強(qiáng)種群的收斂性有著良好的平衡作用。

3.3 ε比較準(zhǔn)則

為了改善ε比較準(zhǔn)則的缺陷，本文引用了畢曉君等人提出的改進(jìn)ε比較準(zhǔn)則以及ε自適應(yīng)調(diào)整策略[10]，判斷準(zhǔn)則為：

1)當(dāng)兩個(gè)個(gè)體都是可行個(gè)體時(shí)，取目標(biāo)函數(shù)值較小的個(gè)體。

2)當(dāng)一個(gè)個(gè)體是可行個(gè)體而另一個(gè)個(gè)體是不可行個(gè)體時(shí)，可以分為以下兩種情況進(jìn)行選擇：①如果不可行個(gè)體約束違反度小于ε，則取目標(biāo)函數(shù)值較小的個(gè)體；②否則可行個(gè)體獲勝。

3)當(dāng)兩個(gè)個(gè)體都是不可行個(gè)體時(shí)，如果兩個(gè)個(gè)體約束違反度都要小于ε，取目標(biāo)函數(shù)值較小的個(gè)體；如果一個(gè)個(gè)體約束違反度大于ε，一個(gè)個(gè)體約束違反度小于ε，取約束違反度較小的個(gè)體；如果兩個(gè)不可行個(gè)體的約束違反度都大于ε，以較大概率取約束違反度較小的個(gè)體，以較小概率取約束違反度較小的個(gè)體。

ε自適應(yīng)方程為

(6)

Te代表截?cái)噙M(jìn)化代數(shù)，可以用來(lái)調(diào)整ε(t)的大小。其中a=amin+τ×(amax-amin)，其中τ代表可行個(gè)體在種群中的比例。由文獻(xiàn)[10]可知，在進(jìn)化代數(shù)為10000時(shí)，Te一般設(shè)為1000，本文也將使用此數(shù)值。

3.4 算法措施的改進(jìn)

本文在改進(jìn)ε比較準(zhǔn)則基礎(chǔ)上結(jié)合元胞遺傳算法進(jìn)行改進(jìn)，根據(jù)其截?cái)啻鷶?shù)的前期和后期分別應(yīng)用不同的改進(jìn)方式來(lái)進(jìn)行計(jì)算。

3.4.1 偏好指標(biāo)的實(shí)現(xiàn)

在截?cái)啻鷶?shù)之前，即種群剛開(kāi)始進(jìn)化時(shí)，此時(shí)根據(jù)改進(jìn)的ε比較準(zhǔn)則可以得知：此時(shí)種群里面可能含有約束違反度小于ε的不可行個(gè)體，而此時(shí)希望種群可以快速且均勻的向可行域范圍逼近。

這樣做的好處在于進(jìn)行差分變異操作時(shí)，選擇的基準(zhǔn)個(gè)體大概率選擇到對(duì)于約束違反度這個(gè)指標(biāo)比較良好的個(gè)體，種群可以更快的收斂到可行域的附近，最后幫助收斂到全局最優(yōu)解。

3.4.2 改進(jìn)的柯西變異算子

柯西分布是一種連續(xù)概率分布，柯西變異算子可以加強(qiáng)種群的全局搜索能力以及穩(wěn)定性，近些年來(lái)，采用基于柯西變異的蟻獅優(yōu)化算法[11]，基于柯西變異的多策略協(xié)同進(jìn)化粒子群算法[12]都取得了良好的優(yōu)化效果。

柯西分布的基本分布如下

(7)

基礎(chǔ)的柯西變異公式為

xij=xij+τ*C(0，1)

(8)

其中η表示控制一個(gè)步長(zhǎng)大小的常數(shù)，C(0，1)代表當(dāng)t=1時(shí)的一個(gè)隨機(jī)柯西變異數(shù)。

當(dāng)種群的進(jìn)化代數(shù)達(dá)到截?cái)啻鷶?shù)之后。為了讓種群進(jìn)化后期逃離局部最優(yōu)，本文提出改進(jìn)柯西變異與差分變異的結(jié)合算子，使得算法可以加強(qiáng)搜索能力，有助于得到全局最優(yōu)解。

差分進(jìn)化變異算法與改進(jìn)的柯西變異結(jié)合的公式為

(9)

3.5 算法步驟

本文εCGA算法采用改進(jìn)的ε比較準(zhǔn)則和元胞遺傳算法相結(jié)合的方式，以在約束問(wèn)題上表現(xiàn)良好的差分算子為遺傳工具來(lái)處理約束問(wèn)題。

步驟1：生成初始化種群，設(shè)置初始參數(shù)，包括種群規(guī)模N，縮放因子F，交叉因子CR以及種群最大迭代次數(shù)。初始種群的生成方法為：隨機(jī)生成種群，種群中的每個(gè)個(gè)體Xi=(x1，x2，…，xn)的第j維分量設(shè)置為xj=lj+rand()×uj(j=1，2，…，n;i=1，2，…，N)，其中rand表示0到1的隨機(jī)數(shù)，xj∈[lj，uj]；

圖2 ε CGA算法流程圖

步驟2：判斷算法終止條件，如果達(dá)到最大進(jìn)化迭代次數(shù)Tmax，算法結(jié)束。

步驟4：采用一般的差分進(jìn)化算法交叉方式

(10)

t表示進(jìn)化代數(shù)，uij為個(gè)體Vi的第j維分量，rand(j)表示0到1的一個(gè)隨機(jī)數(shù)，xij為xi的第j維分量。

步驟5：按照改進(jìn)的ε比較準(zhǔn)則比較個(gè)體并進(jìn)行選擇。

步驟6：根據(jù)式(6)對(duì)ε(t)進(jìn)行更新。

步驟7：t=t+1，返回步驟2。

4 實(shí)驗(yàn)及分析

本文所有實(shí)驗(yàn)都是在硬件配置為Inter Core，CPU：i7-6700，8GB內(nèi)存，主頻3.4GHz的計(jì)算機(jī)上進(jìn)行，程序采用matlab2016編寫(xiě)。

為了驗(yàn)證本文提出ε CGA算法的可行性，對(duì)文獻(xiàn)[14]中的7個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行了測(cè)試。在實(shí)驗(yàn)中，各個(gè)參數(shù)的取值如下：元胞種群采用30×30的種群大小，一共為900個(gè)個(gè)體，采用的縮放因子F和交叉概率CR分別為0.7和0.8，其中g(shù)02測(cè)試函數(shù)最大迭代次數(shù)設(shè)置為15000代，其他測(cè)試函數(shù)最大迭代次數(shù)設(shè)置為10000代，截?cái)啻鷶?shù)設(shè)置為1000代，等式約束的違反容忍值δ=0.0001。算法的獨(dú)立測(cè)試實(shí)驗(yàn)為30次。首先為了驗(yàn)證本文ε CGA算法的有效性，與文獻(xiàn)[10]進(jìn)行了對(duì)比。

表1 ε CGA與ε COA對(duì)比實(shí)驗(yàn)結(jié)果

由上表可知：在g02這種高維變量測(cè)試函數(shù)中，ε CGA的平均值以及最差值都要優(yōu)于ε COA算法；而在其它一些低維變量測(cè)試函數(shù)中，本文算法也都能找到全局最優(yōu)解，僅在少許測(cè)試函數(shù)中魯棒性稍差。

為了進(jìn)一步說(shuō)明本文ε CGA算法的先進(jìn)性，將 CGA算法與S-ABC算法[15]、DE算法[6]、ISR算法[16]進(jìn)行了對(duì)比實(shí)驗(yàn)。對(duì)每個(gè)測(cè)試函數(shù)在相同的條件下運(yùn)行了30次，實(shí)驗(yàn)結(jié)果如表2所示。

表2 ε CGA與其它三種算法的比較結(jié)果

從表2可以看出，其中g(shù)02由于決策變量較高，4種算法都沒(méi)一致達(dá)到最優(yōu)解，但ε CGA算法的最差值以及平均值都優(yōu)于其它算法，可以看出元胞遺傳算法在處理這種多變量問(wèn)題上有著一定的優(yōu)勢(shì)。在其它6個(gè)測(cè)試函數(shù)中，與SA-ABC算法相比，除了在g01函數(shù)中魯棒性稍差，其它全面優(yōu)于SA-ABC算法。與DE算法相比，除了在g01與g03函數(shù)中方差要大，在其它測(cè)試函數(shù)中基本一致收斂到最優(yōu)解，且魯棒性更好；與ISR算法相比，也僅僅在g01，g03，g05測(cè)試函數(shù)中魯棒性稍差，而在其它測(cè)試函數(shù)中也優(yōu)于ISR算法。從以上分析中可以得知，本文提出的算法在高維測(cè)試函數(shù)中表現(xiàn)良好，在收斂精度上都能收斂得到全局最優(yōu)解，只是在少許測(cè)試函數(shù)中魯棒性稍差。

5 結(jié)束語(yǔ)

本文從保持種群多樣性的角度出發(fā)，提出用改進(jìn)ε約束處理技術(shù)結(jié)合元胞遺傳算法來(lái)求解約束優(yōu)化問(wèn)題。該算法采用偏好性指標(biāo)和改進(jìn)柯西算子的改進(jìn)策略，與其它算法進(jìn)行對(duì)比可以得出以下三個(gè)結(jié)論：①算法在高維函數(shù)測(cè)試中表現(xiàn)良好，得到的平均值和最優(yōu)值都優(yōu)于其它算法；②算法多樣性保持良好，收斂精度總體上也好于其它算法；③算法在少數(shù)測(cè)試函數(shù)中魯棒性不強(qiáng)，這將成為日后研究重點(diǎn)。