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

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

1 引言

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

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

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

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

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

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

不失一般性，一個帶有等式約束、不等式約束的最小化優(yōu)化問題用數(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個不等式約束，hj(x)表示第j個等式約束。

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

(2)

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

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

(3)

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

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

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

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

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

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

(4)

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

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

3 改進(jìn)算法

3.1 元胞遺傳算法

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

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

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

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

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

(5)

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

3.3 ε比較準(zhǔn)則

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

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

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

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

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

(6)

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

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

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

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

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

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

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

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

柯西分布的基本分布如下

(7)

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

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

(8)

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

當(dāng)種群的進(jìn)化代數(shù)達(dá)到截斷代數(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é)合的方式，以在約束問題上表現(xiàn)良好的差分算子為遺傳工具來處理約束問題。

步驟1：生成初始化種群，設(shè)置初始參數(shù)，包括種群規(guī)模N，縮放因子F，交叉因子CR以及種群最大迭代次數(shù)。初始種群的生成方法為：隨機(jī)生成種群，種群中的每個個體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為個體Vi的第j維分量，rand(j)表示0到1的一個隨機(jī)數(shù)，xij為xi的第j維分量。

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

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

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

4 實驗及分析

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

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

表1 ε CGA與ε COA對比實驗結(jié)果

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

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

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

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

5 結(jié)束語

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