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

謝蘊文，魯宇明，劉 毅

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

1 引言

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

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

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

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

2 約束處理問題及約束處理技術

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

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

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)為目標函數(shù)，gi(x)表示第i個不等式約束，hj(x)表示第j個等式約束。

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

(2)

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

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

(3)

2.2 約束處理技術的比較準則

為了對可行個體與不可行個體進行比較，提出ε比較準則[6]，以求最小值為例，主要由下面三條準則構成：

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

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

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

ε的設置公式為：

(4)

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

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

3 改進算法

3.1 元胞遺傳算法

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

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

3.2 差分進化算法

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

下面表示三種一般的差分進化算法的變異策略

(5)

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

3.3 ε比較準則

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

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

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

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

ε自適應方程為

(6)

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

3.4 算法措施的改進

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

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

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

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

3.4.2 改進的柯西變異算子

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

柯西分布的基本分布如下

(7)

基礎的柯西變異公式為

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

(8)

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

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

差分進化變異算法與改進的柯西變異結合的公式為

(9)

3.5 算法步驟

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

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

圖2 ε CGA算法流程圖

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

步驟4：采用一般的差分進化算法交叉方式

(10)

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

步驟5：按照改進的ε比較準則比較個體并進行選擇。

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

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

4 實驗及分析

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

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

表1 ε CGA與ε COA對比實驗結果

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

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

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

從表2可以看出，其中g02由于決策變量較高，4種算法都沒一致達到最優(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 結束語

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