基于自適應(yīng)變異算子的實數(shù)編碼遺傳算法

王劍楠，崔英花

(北京信息科技大學(xué) 信息與通信工程學(xué)院，北京 100192)

0 引言

遺傳算法作為一種隨機全局搜索尋優(yōu)算法，在工程領(lǐng)域中獲得了廣泛的應(yīng)用。實際工程中許多問題可歸并成多峰函數(shù)優(yōu)化問題。在問題的可行解范圍內(nèi)最優(yōu)解附近常有多個局部極值點存在，如神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化以及權(quán)值優(yōu)化問題，復(fù)雜系統(tǒng)參數(shù)及結(jié)構(gòu)辨識問題[1]，因此使遺傳算法獲得多峰函數(shù)全局最優(yōu)解成為了一個重要的研究方向。但遺傳算法存在固有缺陷，在解決多峰函數(shù)優(yōu)化問題時，常在獲得全局最優(yōu)解前在某個局部極值處發(fā)生未成熟收斂，從而喪失了向上進化的能力，此時種群中的個體由于選擇算子幾乎全部跳入某個峰值之中，個體之間適應(yīng)度高度趨同，即便某次變異使某個個體跳出該峰值，也有很大概率會因適應(yīng)度值無法超過該峰值而遭到選擇算子的淘汰，故而已經(jīng)陷入局部極值的遺傳算法很難跳出局部峰值。因此解決算法“早熟”問題的關(guān)鍵在于如何保持種群的多樣性，使種群中總有個體存在于各個不同的“峰”之中，這樣種群才有機會一直保持進化。

在遺傳算法的早期操作中大多采用二進制編碼，二進制編碼遺傳算法(binary coded genetic algorithm，BCGA)[2]中問題的可行解被編碼成由0和1組成的字符串。這種算法對于可行解范圍較小和對解精度要求不高的問題性能或許比較理想，但對于精度要求較高的高維問題，則會占用過多的存儲空間，并在計算上產(chǎn)生過多的時間開銷。為了克服這些缺陷，本文選擇實數(shù)編碼方式的遺傳算法。實數(shù)編碼遺傳算法(real coded genetic algorithm，RCGA)[3]問題的可行解以實數(shù)形式表示。

實數(shù)編碼遺傳算法進化過程中的種群多樣性與交叉算子和變異算子的聯(lián)系密不可分。交叉算子對兩個個體的基因結(jié)構(gòu)進行破壞重組，對個體結(jié)構(gòu)的改變比較劇烈，因此交叉操作決定了算法的全局搜索能力。在種群進化后期，從可行解全局搜索區(qū)域來看交叉算子已經(jīng)鎖定了某個可能存在最優(yōu)解的范圍，利用交叉算子搜索該區(qū)域內(nèi)的細節(jié)會比較困難，這時可以利用變異算子對該區(qū)域內(nèi)的“山峰”進行局部搜索。因此在種群多樣性下降時應(yīng)加強變異算子對基因的擾動程度。

傳統(tǒng)的實數(shù)編碼遺傳算法變異算子大致分為4類：均勻變異、邊界變異、高斯變異、非均勻變異(non-uniform mutation，NM)[4]。相比于前3類，非均勻變異可隨進化代數(shù)調(diào)整變異元素，重點搜索原個體附近的微小區(qū)域。然而隨著進化代數(shù)的增加，變異基因值越來越接近原基因值直至完全相同，不能達到維持種群進化能力的目的。

為了提高傳統(tǒng)變異算子的性能，許多學(xué)者對其進行了改進。文獻[5]提出的自適應(yīng)變異尺度調(diào)整了變異元素產(chǎn)生的區(qū)域。Kusum和Manoj提出的冪型變異算子(power mutation，PM)[6]，通過限定范圍內(nèi)的冪函數(shù)的密度函數(shù)為隨機擾動函數(shù)，代替?zhèn)鹘y(tǒng)非均勻變異以進化代數(shù)為決策變量的擾動函數(shù)，相比于傳統(tǒng)非均勻變異算子，對變異強度有所強化。文獻[7]提出的基于方向的指數(shù)型變異算子 (direction-based exponential mutation operator，DEM)利用可行解的方向信息和指數(shù)函數(shù)來生成突變解，對方向信息的先驗知識的運用使種群快速收斂到有效解區(qū)域。

然而上述方法存在一定的缺陷：1)任子武等提出的變異算子變異尺度依然自適應(yīng)于進化代數(shù)，在種群進化后期變異強度趨于零；2)PM的變異強度帶有一定的隨機性，沒有考慮到種群的進化狀態(tài)信息，變異強度與種群進化階段缺乏適應(yīng)性；3)DEM調(diào)整變異算子時過于傾向于當前種群最優(yōu)解，有一定可能導(dǎo)致種群早熟收斂。

自適應(yīng)遺傳算法[8]自Srinivas等提出以來受到了國內(nèi)外學(xué)者的廣泛關(guān)注。最原始的自適應(yīng)遺傳算法是使變異概率根據(jù)個體適應(yīng)度值的大小自適應(yīng)地調(diào)整，由適應(yīng)度值決定個體變異的可能性的大小。王玉冰等[9]進一步對變異概率進行改進，根據(jù)刻畫種群多樣性的信息熵和進化代數(shù)自適應(yīng)地調(diào)整變異概率，由種群進化的階段和進化的程度控制種群中變異個體的比例。文獻[10]和文獻[11]繼續(xù)改進了變異概率公式，設(shè)計的變異概率集成了個體適應(yīng)度值和種群進化程度信息，既從微觀上依據(jù)個體適應(yīng)度值決定個體需要變異的概率，又根據(jù)種群宏觀整體上進行調(diào)控。然而這些學(xué)者所做的改進僅僅停留在變異概率公式[12]的設(shè)計上，變異概率只決定了種群中發(fā)生變異的個體的比例，即只考慮到變異的范圍，而忽視了變異的強度。

為了解決上述問題，本文集合了自適應(yīng)遺傳算法自適應(yīng)調(diào)整變異概率的思想和變異強度對種群多樣性的影響，設(shè)計了一種新的具有自適應(yīng)性的強度可變的變異算子。提出了一種基于種群多樣性的變異強度控制函數(shù)，以種群多樣性評價標準為決策變量控制變異強度，綜合了種群進化狀態(tài)信息與變異強度對變異元素的影響。

1 種群多樣性指標及應(yīng)用

1.1 方差因子

在遺傳算法迭代過程中，種群能夠不斷進化依賴于種群的多樣性。豐富的個體是保持種群進化的動力，如何設(shè)計種群多樣性評價標準是衡量種群進化狀態(tài)的關(guān)鍵。個體本質(zhì)上是由不同的基因所構(gòu)成，種群中個體之間的差異本質(zhì)是各個維度上的基因的差異，也就是個體結(jié)構(gòu)組成上的差異。不同個體結(jié)構(gòu)的差異程度可用種群基因偏離程度進行刻畫。顯然基因離散程度越高，個體之間結(jié)構(gòu)差異越大。

(1)

其中：

(2)

由此定義第t代種群的方差為

(3)

其中：

(4)

(5)

方差是個體結(jié)構(gòu)差異的一種度量準則，僅反映了個體間基因偏離程度，還不能完全反映種群的多樣性特征。為了反映個體在各個子群體中的分布情況，本文引入描述種群多樣性的第二個量——熵。

1.2 種群熵因子

定義2設(shè)第t代種群有Q個子集：S1(t),S2(t),…,SQ(t) ，各個子集所包含的個體數(shù)目記為n1,n2,nQ，且對任意p，q∈{1,2,…,Q}有

(6)

其中A(t)為第t代種群的集合。則種群的熵為

(7)

式中pj(t)=nj/N，N為種群中個體的數(shù)目。由種群熵定義可知，種群中N個個體均位于不同的子集時，Q=N，種群熵最大，Emax=log(N)。當所有個體全部集中在同一個子集中時，Q=1，種群熵最小，Emin=0。種群基因類型越豐富，個體分布就越均勻，從而種群熵就越大。本文為了建立變異強度控制函數(shù)與種群熵的函數(shù)關(guān)系，用γ表示種群熵因子，γ=E(t)，監(jiān)測個體在各個子群體中的分布情況。

2 基于種群多樣性的變異算子

本研究提出了一種新的基于種群多樣性的非均勻變異算子(diversity based non-uniform mutation operator，DNM)用于實數(shù)編碼遺傳算法，這個新開發(fā)的算子受底數(shù)u、進化代數(shù)t、種群多樣性信息s和γ等因素的影響。提出了一種新型變異強度控制函數(shù)s(t)用于變異算子，變異強度根據(jù)函數(shù)s(t)進行自適應(yīng)變化。在種群可能出現(xiàn)未成熟收斂時，變異強度控制函數(shù)擴展了算子的可操作空間，使算法有能力跳出局部最優(yōu)解。設(shè)父代染色體為x=[x1,x2，…,xk,…,xn]，元素xk∈[Lk,Uk]為待變異元素，變異后的元素yk隨機產(chǎn)生于區(qū)間Ω：

Ω={xk-s(t)(xk-Lk),xk+s(t)(Uk-xk)}

(8)

其中：

s(t)=1-u(1-sγ)t

(9)

式中：t為進化代數(shù)；u∈[0,1]，本文取值為0.2。從式(9)可以看出，種群在進化早期sγ較大，s(t)≈0，此時算法處于全局搜索階段，交叉算子發(fā)揮主要作用，變異強度可以偏小以加快搜索速度。隨著種群的進化，優(yōu)勢個體出現(xiàn)并有逐漸占領(lǐng)種群的趨勢，種群多樣性逐漸下降，故而sγ減小。當sγ≈0時，s(t)≈1-u，變異空間較大增加了變異強度，賦予了個體跳出局部“山峰”的能力，提高了算法的局部搜索能力。

3 仿真

3.1 與傳統(tǒng)非均勻變異算法的對比

傳統(tǒng)非均勻變異操作為

s(t)=1-u(1-t/T)b

(10)

式中：t為進化代數(shù)；T為最大進化代數(shù)；b多取經(jīng)驗值3。為了確定加速因子在變異強度函數(shù)中的作用，t/T可以看作是一個不斷以線性速率增大的變量。對于傳統(tǒng)非均勻變異算子中的t/T，本文選擇以sγ替代以監(jiān)測種群多樣性信息。令sγ=x，令y=1-u(1-x)bx,y∈[0,1]，分別取b為2、3、4、100進行仿真實驗，如圖1所示。

圖1 加速因子對比曲線

從圖1可以看出，隨著b的增大，曲線越來越陡峭。在種群初期sγ趨向于1，b值過高會導(dǎo)致y≈0進而變異強度為0。由于進化初期依然需要一定的變異強度來積極探索種群空間，因此在種群進化初始階段應(yīng)取較小的b值保證變異算子的變異強度。隨著種群的不斷進化，sγ向零處收斂，此時需要增加變異強度以增強局部搜索能力，然而過大的變異強度會使算法淪為隨機搜索算法且收斂速度會因此變慢。此時為了平衡變異強度與變異給算法搜索帶來的隨機性之間的矛盾，應(yīng)適當降低變異強度。在x值相同的情況下，b值越大y越小，因此在種群進化后期宜采取較大的b值。用進化代數(shù)t代替b，可以保證在進化初期y不至于過低且在進化后期y不至于過高。

為了驗證改進的非均勻變異算子的優(yōu)勢，對式(9)和(10)采用仿真對比。采用經(jīng)典遺傳算法，選擇策略為輪盤賭選擇法，進化代數(shù)T取100，種群規(guī)模為100，Pc為0.8，Pm為0.05。測試函數(shù)選擇schaffer函數(shù)：

xi∈[-5,5]；i=(1,2)

(11)

該函數(shù)有無限個局部極大點，其中只有一個全局最大點，即f(0,0)=1，在最大值周圍有峰值圈脊，算法易在圈脊中某個值處停滯。

圖2是分別使用兩種變異算子的算法目標函數(shù)值的仿真對比。從圖中可以看出，使用傳統(tǒng)非均勻變異算子的算法在0.998附近陷入局部收斂。而對于應(yīng)用DNM的算法，加速因子取t時比取b時獲得更快的收斂速度。經(jīng)計算DNM加速因子為b時絕對誤差為3.138 6，遠大于DNM加速因子為t時的絕對誤差(接近于0)。同時可以看到，加速因子為b時算法似乎也收斂到最優(yōu)解f(0,0)處，進化曲線顯示最優(yōu)值無限趨近于1，然而不能看出DNM加速因子為b時算法是否陷入局部收斂。

圖2 最優(yōu)解進化曲線對比

本文分別計算了3種情況下算法的最優(yōu)解位置，如圖3所示。從圖中可以看出，DNM加速因子為b時算法收斂點根本不在最優(yōu)解所在山峰，由此判斷盡管DNM加速因子為b時獲得較好的適應(yīng)度最優(yōu)值進化曲線，但仍易陷入局部最優(yōu)解。

圖3 最優(yōu)解位置對比

為了驗證本文所提算法在進化后期種群多樣性有所提高且在一定程度上克服了“早熟”收斂，對比了使用不同算子的算法下經(jīng)過100次進化后的種群個體分布情況，如圖4所示。圖中一個空心圓代表種群中的一個個體。可以看出，傳統(tǒng)NM算子不能使算法很好地保持種群多樣性；而使用DNM算子的算法則保持了一定水平的種群多樣性。

3.2 與使用其他改進變異算子的算法的對比

為了驗證本文所提變異算法的有效性和優(yōu)越性，將其與前文所述的使用幾種改進的變異算子的算法進行對比：Kusum和Manoj提出的PM和文獻[7]提出的DEM。在經(jīng)典遺傳算法上使用3種變異算子，選擇策略和其他控制參數(shù)不變。測試函數(shù)依然選擇schaffer函數(shù)，3種算法的最優(yōu)解隨迭代次數(shù)的進化曲線如圖5所示，從最優(yōu)解進化曲線可以看出本文算法收斂速度高于其他兩種算法。圖6展示了最優(yōu)解位置，從圖6可以看出本文算法優(yōu)化后最優(yōu)解離f(0,0)更近，其他兩種算法盡管最后均無限接近f(0,0)，但收斂值與(0,0)不在同一個“山峰”，由此證明本文所提算法在求解精度方面也存在一定的優(yōu)勢。

3.3 應(yīng)用DNM于自適應(yīng)遺傳算法

為了驗證本文所提變異算子對自適應(yīng)遺傳算法有所改善，本文選擇文獻[10]提出的自適應(yīng)遺傳算法進行仿真。文獻[10]采用輪盤賭結(jié)合最優(yōu)個體保留的策略，本文采用實數(shù)編碼策略，Pc1和Pc2分別為0.9和0.6，Pm1和Pm2分別為0.1和0.001。將DNM嵌入自適應(yīng)遺傳算法中代替原自適應(yīng)遺傳算法的變異算子，與原自適應(yīng)遺傳算法對比，最優(yōu)解隨進化代數(shù)曲線如圖7所示。從圖7可以看出，應(yīng)用DNM的自適應(yīng)遺傳算法收斂速度和收斂精度明顯好于原自適應(yīng)遺傳算法。

圖4 種群個體分布

圖5 三種算子最優(yōu)解進化曲線對比

圖6 三種算子最優(yōu)位置對比

圖7 最優(yōu)解進化曲線對比

4 結(jié)束語

現(xiàn)有自適應(yīng)遺傳算法只考慮了發(fā)生變異的個體的比例，僅通過設(shè)計變異概率控制變異的范圍，而忽視了變異的強度。傳統(tǒng)非均勻變異算子對現(xiàn)有自適應(yīng)遺傳算法做出了改進，但不能很好地維持種群的多樣性。本文對傳統(tǒng)的非均勻變異算子提出了相應(yīng)的改進策略。種群繼續(xù)向前進化的主要依據(jù)和原動力是種群的多樣性，本文從基因內(nèi)部結(jié)構(gòu)差異和個體分布的均勻程度為切入點設(shè)計種群多樣性指標，以此指導(dǎo)變異強度使種群更好地完成進化。通過兩組對比仿真實驗，表明本文所提變異算子保持了一定的種群多樣性，增強了算法的局部搜索能力。