基于改進BA網絡的遺傳算法

李 陽，田興華，張紀會

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

0 引言

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

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

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

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

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

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

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

1 改進BA網絡的遺傳算法

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的求解是一種很有效的方法，其主要包括以下操作：產生初始種群、選擇、交叉、變異。

1) 產生初始種群

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

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

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

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

2) 選擇

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

3) 交叉

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

4) 變異

對新產生的個體依概率改變一位或多位基因。

1.2 基于改進BA網絡的遺傳算法

依照BA網絡的網絡結構，我們改進了傳統的遺傳算法，采用BA網絡的適應度模型模擬生物種群，并使用改進的選擇選擇策略適應種群結構，加快種群優化速度，并動態控制種群規模，優化迭代過程。

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

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

具體改進如下：

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

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

根據改進策略，算法步驟如下：

1) 隨機產生種群規模為的初始種群，隨機產生規模大小為的BA網絡，種群個體和網絡節點按編號1-P一一對應；

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

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

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

5) 根據新種群中的個體與網絡節點的對應關系，將新個體與BA網絡中節點一一對應；

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

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

2 數值實驗

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

2.1 實驗

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

表1 測試函數公式列表Tab.1 List of test functions

表2 參數設置Tab.2 Parameter settings

其中F1-F2為單峰函數，F4-F7為多峰函數。

算法的具體參數設置如下：

為了測試改進后算法的性能，我們用改進的算法對每個測試函數分別運行50次，用均值作為我們最終的運行結果，并把結果與表4[30]中基本遺傳算法以及網絡進化(N-GA)算法(最大迭代次數為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 實驗結果分析

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

對于不同測試函數，該算法的尋優過程如圖3所示，根據尋優過程中每代最優解的圖形，我們可以發現改進算法的尋優速度較快，一般在200代以內就可以達到最優解附近，并且能夠在最優解附近穩定尋找全局最優解。

圖3 尋優過程圖Fig.3 The optimization process

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

從結果匯總圖4我們可以看出，除函數F5，F7最優值波動較大，其余函數的尋優結果都比較平穩，進一步說明我們改進算法性能比較穩定。

3 結論

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