基于改進BA網(wǎng)絡的遺傳算法

李 陽，田興華，張紀會

(青島大學復雜性科學研究所，山東 青島 266071)

0 引言

20世紀70年代，美國Michigan大學的Holland教授與其同事、學生從試圖解釋自然系統(tǒng)中生物種群的復雜適應過程入手，提出了一種模擬生物自然進化的系統(tǒng)的模型—遺傳算法(Genetic Algorithm，GA)[1]。

遺傳算法基本思想是：從問題可能解集的一個種群(population)出發(fā)，根據(jù)適應度(fitness)的大小，按照達爾文生物進化論中的“適者生存”的原理來選擇個體，然后通過交叉(crossover)、變異(mutation)形成新的個體，新個體組合成新的種群。這個過程將導致種群像自然進化一樣，后代種群比前代種群更能適應環(huán)境，最終，末代種群的最優(yōu)個體通過解碼可作為問題的近似最優(yōu)解[1]。其本質(zhì)是一種高度并行的全局搜索算法[2]。利用各種映射技術和適當?shù)倪m應度，可以定制許多類型問題的解決方案[3]。

遺傳算法由于其結構簡單，適應性強，并且具有很好的魯棒特性，在眾多領域得到了廣泛應用。但是遺傳算法同樣存在許多不足，遺傳算法由于信息交互雜亂，使得遺傳算法搜索速度較慢，且易出現(xiàn)“早熟”收斂，在高維函數(shù)優(yōu)化中，若種群最大迭代次數(shù)較小，則很難找到讓人滿意的最優(yōu)解。

對于遺傳算法的改進工作是目前文獻研究最多的內(nèi)容，主要的改進方法有：

1) 混合遺傳算法：將不同算法的優(yōu)點有機結合彌補傳統(tǒng)遺傳算法的不足，如：陳輝提出的實數(shù)編碼混沌量子遺傳算法(RCQGA)[4]；張曉偉提出的信賴域遺傳算法[5]；彭勇剛提出的模糊自適應模擬退火遺傳算法(FASAGA)[6]；Javadi提出的與神經(jīng)網(wǎng)絡結合的遺傳算法[7]等。

2) 自適應遺傳算法：遺傳算法的結構、參數(shù)等關鍵因素隨著種群的迭代動態(tài)改變，使算法在運行過程中一直保持最佳狀態(tài)，如：Srinivas提出了一種交叉率和變異率自適應的遺傳算法[8]；黃宜軍提出了一種新的自適應退火策略用于遺傳算法[9]；王嶸冰提出一種自適應非支配排序遺傳算法[10]。

為了改進遺傳算法的不足，提升算法的性能，本文在網(wǎng)絡進化算法的基礎上，提出了一種新型改進BA網(wǎng)絡與遺傳算法相結合的算法，采用網(wǎng)絡分析方法表征種群的特性，用改進BA網(wǎng)絡適應度模型[32]取代遺傳算法中完全連通的全連接模型，把網(wǎng)絡科學與進化算法相結合，并對遺傳算法中的一些操作進行改進，給出詳細的結合策略，通過實驗驗證結合算法的性能。

1 改進BA網(wǎng)絡的遺傳算法

1.1 遺傳算法

遺傳算法具有簡單的結構，通用性強，對于問題minf(x),X∈[a,b]，其中X=(x1,x2,…,xn)，a=(a1,a2,…,an)，b=(b1,b2,…,bn)，xi∈[ai,bi],i=1,2,…,n的求解是一種很有效的方法，其主要包括以下操作：產(chǎn)生初始種群、選擇、交叉、變異。

1) 產(chǎn)生初始種群

遺傳算法首先在函數(shù)定義域內(nèi)隨機產(chǎn)生含有N個函數(shù)潛在解編碼個體的一個種群，N為預先設置的種群中包含個體的數(shù)目。個體編碼方式有：

(1) 浮點數(shù)編碼：個體的每個基因值用某一范圍內(nèi)的一個浮點數(shù)來表示。

(2) 二進制編碼：每個個體由一定長度的二進制編碼構成。

傳統(tǒng)遺傳算法的種群結構為簡單的全連接結構，即任意兩個個體之間都可以進行信息的交互，全種群信息共享。

2) 選擇

遺傳算法的選擇操作是根據(jù)適應度的大小來選擇個體的，適應度大的個體，也就是高質(zhì)量的個體，其被選擇的概率就越大，這樣個體的優(yōu)良基因遺傳給下一代的概率也就越大，于是優(yōu)良個體不斷地以高概率去分享它的信息，使得整個種群的質(zhì)量不斷地得到改善。

3) 交叉

根據(jù)適應度選擇兩個個體，讓兩個個體依一定的概率交換信息，從而以一定概率形成兩個新的個體。

4) 變異

對新產(chǎn)生的個體依概率改變一位或多位基因。

1.2 基于改進BA網(wǎng)絡的遺傳算法

依照BA網(wǎng)絡的網(wǎng)絡結構，我們改進了傳統(tǒng)的遺傳算法，采用BA網(wǎng)絡的適應度模型模擬生物種群，并使用改進的選擇選擇策略適應種群結構，加快種群優(yōu)化速度，并動態(tài)控制種群規(guī)模，優(yōu)化迭代過程。

改進算法種群與網(wǎng)絡演化過程如圖1所示：長方形代表種群個體，不同的顏色代表個體所攜帶的基因，個體之間的連線代表在網(wǎng)絡結構中相互連接，即個體之間可以相互交換信息。

圖1 改進算法種群演化圖Fig.1 Population evolution diagram of the improved algorithm

具體改進如下：

第三，繼承：對于新個體與節(jié)點度的處理，在每一代中，交叉變異后會生新的個體，對于新的個體(節(jié)點)在網(wǎng)絡結構中就會有新的度，為了避免每一代都重新按概率連接所有的個體，我們采用節(jié)點度繼承策略，對于新產(chǎn)生的子代種群，我們按照適應度越好，在網(wǎng)絡節(jié)點中度越大的原則，把我們新種群中的個體去分配到父代所形成的網(wǎng)絡結構中，即kmax?Fmax,…,kmin?Fmin，k為節(jié)點的度，F(xiàn)為個體的適應度。

第五，對于種群個體數(shù)目自適應的調(diào)整：由于BA網(wǎng)絡模型的節(jié)點是逐漸增加的，每一次迭代會增加新的節(jié)點，對應于我們的種群中個體的數(shù)量也需要逐漸增長，然而如果無限增長會帶來計算量上的劇增，而且過多的種群個體數(shù)量對于求解精度的提高并沒有過于明顯的幫助，導致資源的浪費。所以，我們設置動態(tài)的種群個體數(shù)目，種群規(guī)模GPi+1=GPi+n,if GPi≥200,GPi=50,GPi為種群規(guī)模，n為每次增加的個體數(shù)量，即使種群中個體數(shù)目在50-200內(nèi)循環(huán)。既保證了尋優(yōu)能力以及求解精度，同時也避免了資源的浪費。

根據(jù)改進策略，算法步驟如下：

1) 隨機產(chǎn)生種群規(guī)模為的初始種群，隨機產(chǎn)生規(guī)模大小為的BA網(wǎng)絡，種群個體和網(wǎng)絡節(jié)點按編號1-P一一對應；

2) 計算種群的適應度Fi以及BA網(wǎng)絡中節(jié)點的度ki，根據(jù)改進的選擇策略選擇個體；

3) 對于選擇的個體進行交叉、變異，產(chǎn)生后代種群，同時計算后代種群個體的適應度Fi；

圖2 改進算法流程圖Fig.2 Flow chart of the improved algorithm

5) 根據(jù)新種群中的個體與網(wǎng)絡節(jié)點的對應關系，將新個體與BA網(wǎng)絡中節(jié)點一一對應；

6) 判斷種群規(guī)模是否超過設定值，重復步驟2。

綜上，改進算法的流程圖如圖2所示。

2 數(shù)值實驗

為了驗證改進算法對于不同類型函數(shù)的尋優(yōu)能力，我們選取幾種不同類型的基準函數(shù)來評估改進算法，并與傳統(tǒng)遺傳算法以及網(wǎng)絡進化算法做對比，分析改進算法的優(yōu)缺點。

2.1 實驗

為了驗證我們算法的性能，我們選取一些基本的測試函數(shù)進行運算，具體參數(shù)如表1[30]所示:

表1 測試函數(shù)公式列表Tab.1 List of test functions

表2 參數(shù)設置Tab.2 Parameter settings

其中F1-F2為單峰函數(shù)，F(xiàn)4-F7為多峰函數(shù)。

算法的具體參數(shù)設置如下：

為了測試改進后算法的性能，我們用改進的算法對每個測試函數(shù)分別運行50次，用均值作為我們最終的運行結果，并把結果與表4[30]中基本遺傳算法以及網(wǎng)絡進化(N-GA)算法(最大迭代次數(shù)為2 000)的結果做對比，改進算法運行測試結果如表3所示：

表3 改進算法運行結果Tab.3 Running results of the improved algorithm

表4 GA與N-GA運行結果[21]Tab.4 Running results of GA and N-GA

2.2 實驗結果分析

根據(jù)實驗數(shù)據(jù)，我們可以看出，在種群最大迭代代數(shù)為500的情況下，改進的基于改進BA網(wǎng)絡的遺傳算法對于高維函數(shù)F1-F4、F6的尋優(yōu)能力都遠遠優(yōu)于基本的遺傳算法以及網(wǎng)絡進化算法(運行2 000代)的結果，尋優(yōu)速度提高明顯，并且運行結果非常接近全局最優(yōu)解，性能表現(xiàn)良好，方差很小，性能比較穩(wěn)定，能夠達到我們的預期結果。對于函數(shù)F5，F(xiàn)7的運行結果，迭代次數(shù)為500代時F5的平均尋優(yōu)結果只能達到101級別，與傳統(tǒng)進化算法以及網(wǎng)絡進化算法(運行2 000代)的平均性能相近，但是并沒有達到預期結果，F(xiàn)7的尋憂結果在500代時只能達到101級別，結果略差，并且方差較大，尋憂結果波動明顯。綜上，改進算法能大大提高尋優(yōu)性能，但是對個別函數(shù)尋優(yōu)能力較差，所以，對于改進算法的性能有待于進一步提高，使其能夠適用于各種函數(shù)。

對于不同測試函數(shù)，該算法的尋優(yōu)過程如圖3所示，根據(jù)尋優(yōu)過程中每代最優(yōu)解的圖形，我們可以發(fā)現(xiàn)改進算法的尋優(yōu)速度較快，一般在200代以內(nèi)就可以達到最優(yōu)解附近，并且能夠在最優(yōu)解附近穩(wěn)定尋找全局最優(yōu)解。

圖3 尋優(yōu)過程圖Fig.3 The optimization process

圖4 50次結果匯總圖Fig.4 Summary of 50 results

從結果匯總圖4我們可以看出，除函數(shù)F5，F(xiàn)7最優(yōu)值波動較大，其余函數(shù)的尋優(yōu)結果都比較平穩(wěn)，進一步說明我們改進算法性能比較穩(wěn)定。

3 結論

對于群體之間信息的挖掘以及充分利用，對改進算法的性能有積極的作用。本文采用一種新的網(wǎng)絡結構代替普通種群結構去挖掘和利用種群信息，使算法的性能得到了明顯的改善。未來的工作我們需要進一步完善改進算法，使其結果更為精確，更好地解決不同特點函數(shù)優(yōu)化問題，同時對于群體之間信息進一步的挖掘和利用需要更深入探討，比如使用復雜網(wǎng)絡中各類網(wǎng)絡結構對種群結構進一步完善，使信息的利用更加充分高效，從而進一步提升算法的性能。