改進的交叉算子在遺傳算法中的研究及應用

袁桂霞

遺傳算法是模擬生物在自然環境下的遺傳和進化過程而形成的一種自適應全局優化概率搜索方法。它最早由美國密西根大學的H.Holland教授提出，起源于20世紀60年代對自然和人工自適應系統的研究。1967年，Bagley發表了關于遺傳算法應用的論文，在其論文中首次使用“遺傳算法”一詞。20世紀70年代 De Jong基于遺傳算法的思想在計算機上進行了大量的純數值函數優化計算實驗。在一系列研究工作的基礎上，20世紀80年代由Goldberg進行歸納總結，形成了遺傳算法的基本框架。[1-3]。算法受到進化思想“優勝劣汰，適者生存”的啟發，將這一思想引入到優化問題中。首先用合適的編碼形式形成染色體種群，根據問題的約束條件選取適應度函數作為評價個體優劣的標準，通過遺傳算子即選擇、交叉、變異對個體操作篩選，使適應度函數值高的個體進入下一代進化中，迭代該過程直到滿足一定的條件。

遺傳算法具有天然的并行性，可以更快地得到全局最優解。[4]但它也存在許多不足，如容易出現陷入局部最優等。[5]遺傳算子用來進行在整個解空間中廣泛搜索并且能從局部最優中逃離，進而可以搜索到解空間中新的區域。選擇算子就是執行復制操作，根據每個個體的適應值和選擇的規則從種群中剔除低適應值的個體，把高適應值的個體進行復制，使得搜索朝著解空間靠近。不過此過程并沒有產生新的個體，而是保留了精英個體為交叉操作的進行做準備。變異算子則是對部分個體信息進行變異，小概率改變個體染色體的基因。而交叉算子是對雙親個體進行操作得到不同的兩個新個體的過程。交叉算子可以將父代優良基因傳給下一代，這個過程也算是一種變異操作，而且利用增加群體染色體的多樣性，防止陷入早熟，所以遺傳算子中主要的算子是交叉算子，交叉算子的改進對于解決局部最優有很好的作用[6-7]。目前也有許多相關的改進算法，但改進的算法通用性不明顯。只有對其算子做本質的改進才能發揮更廣泛的作用。

對交叉算子的改進可以從兩方面展開，首先遺傳算法的控制參數包括種群大小、交叉概率、變異概率等，而這些參數的選取會對遺傳算法的性能產生很大的影響，也就是參數的合理性關系到算法尋優的成敗，所以對交叉算子改進的第一個方面是對交叉概率參數的選取，另一方面就是對交叉算子的操作策略。[8]

一、交叉概率的改進

遺傳算法本身就具備“優勝劣汰，適者生存”的規律，個體有根據周圍環境變化自適應的能力，即種群中個體適應度值與平均適應度值都能逐漸演化為某一范圍。在算法設計中，應該引導個體適應環境保留好的模式，使其更好地適應環境。[9]這也是改進交叉概率的出發點。

交叉概率控制了交叉算子進行操作的頻度，頻度過高雖然可以一時增強遺傳算法搜索新區域的能力，但根據Holland提出的模式定理和積木塊定理，高頻度的交叉算子也會破壞高性能的模式，不利于低階、高適應值的個體快速增長；頻度過低，也會導致遺傳算法可能陷入遲鈍狀態，產生局部最優解，尋找不到全局最優解，進而不利于進化的完成。所以一般遺傳算法交叉概率的選取都介于0.4-0.9之間。但是具體的交叉概率還是不能確定實際可行的值，本文在標準遺傳算法的基礎上提出一種自適應交叉概率選取的方法，在一定交叉概率范圍內再結合適應度值來動態調整交叉概率，進而改進了交叉算子，用于求解函數優化問題，具體實現方法如下。

交叉算子可以產生新個體，在種群的大范圍內搜索避免過早收斂，不過到了進化的后期，要針對性地在局部范圍內搜索，盡可能提高解的精度。所以前提的交叉概率應該大一些，盡量覆蓋全局，后期應該針對適應度高的進行大概率操作，其他進行小概率操作。按照公式(1)進行自適應交叉概率操作。

(1)

本文采用權重的思想來對各個階段適應度值的個體交叉概率進行調整，其中f代表要交叉的兩個個體中較大適應度值，交叉概率的取值范圍介于0.4-0.9之間，對適應度值劃分了低適應度值fmin、平均適應度值favg和高適應度值fmax三個層次作為種群適應度值的集中程度，對應的把交叉概率的范圍也分為三個層次依次是Pc1=0.4，Pc2=0.6，Pc3=0.9。按照上面介紹的原則，以一代種群為單位，自適應地改變整個種群的交叉概率Pc，使其隨著個體的適應度值在種群的低適應度值fmin、平均適應度值favg和高適應度值fmax之間進行調整。改進的交叉概率Pc有以下特點：

(1) 當個體的適應度值f小于平均適應度值favg時，適應度值處于偏低集中狀態，容易陷入局部最優，此時通過調整權重增大交叉概率偏向Pc，提高搜索全局的能力，這樣可以增加種群中個體的多樣性。

(2) 當個體的適應度值f大于平均適應度值favg時，適應度值處于偏高分散狀態，容易陷入隨機搜索沒有目的而導致收斂慢，此時通過調整權重減小交叉概率Pc，提高算法的收斂速度。

(3) 交叉概率總是介于0.4和0.9之間，如果個體的適應度值f小于平均適應度值favg時，交叉概率介于0.6和0.9之間，越靠近低適應度值，交叉概率越接近最大交叉概率即0.9；反之，若個體的適應度值f大于平均適應度值favg時，交叉概率介于0.6和0.4之間，越靠近高適應度值，交叉概率越接近0.4。

根據以上提出的自適應交叉概率調整公式可以得到交叉概率Pc的變曲線，如圖1所示。

圖1 自適應的交叉概率調整圖

改進后的交叉概率在最佳交叉概率參數下，隨著適應度值的變化不斷調整，既避免了陷入局部最優，又加快了算法的收斂速度，不至于出現近似停滯不前的狀態。對于遺傳算法的改進具有很好的指導作用。

二、交叉算子的混合策略

交叉算子是根據交叉原則和交叉概率對雙親結合來產生后來的算子，其策略關鍵是確定交叉點位置和交換部分基因信息。經常用到的遺傳交叉算子包括單點交叉、兩點交叉、均勻交叉等，下面具體舉例如下：

(1)單點交叉：對兩個個體的編碼串隨機選擇同樣的交叉點，組合第一交叉點前的編碼串和第二個交叉點后的編碼串為一個新個體，另外第二個交叉點前的編碼串和第一個交叉點后的編碼串組合為另一個新個體。例如圖2單點交叉，兩個雙親個體p1和p2(交叉點以“|”標記)將按照單點交叉的方式產生后代o1和o2。

圖2 單點交叉

這種單點交叉方式簡單易行，但是卻容易破壞種群中的長定義距模式和染色體串尾重要基因。為改進這一缺點，給出兩點交叉，也是實際中經常用到的交叉算子。

(2)兩點交叉：為了盡量保留染色體的串尾重要基因，給雙親個體都同時設定兩個交叉點，位置相同，分別交換其兩個交叉點之間的染色體串。例如圖3兩點交叉，兩個雙親個體p1和p2(交叉點以“|”標記)按照兩點交叉的方式產生后代o1和o2。

圖3 兩點交叉

(3)均勻交叉：與上兩個交叉策略不同，它的交叉點可能是每一個位置，不是固定的，具體是由下面成為二進制屏蔽字的隨機生成串決定。步驟如下：

① 隨機生成一個二進制屏蔽字p=W1W2…Wn，長度n與染色體編碼長度相同，它決定了父代具體復制位置。

② 按下列規則從p1和p2兩個父代個體中產生兩個新后代個體o1和o2。

若Wi=0，其中1

若Wi=1，其中1

③ 具體操作過程如圖4所示。

圖4 均勻交叉

均勻交叉相對于前兩種交叉而言，對于定義距較大的模式有保護作用，而對于定義距較小的模式破壞較大，因此具有更好的魯棒性。

除了上述的三種交叉算子策略還有多點交叉方式，多點交叉是比兩點交叉多了幾個固定交叉點，一般而言，多點交叉較少采用。因為在多點交叉時被保存的結構很少，也就是說，多點交叉不能有效地保存某些重要的模式。

在實際情況中有時需要滿足約束條件，如交換后要求所有的基因不能重復且不能丟失，就必須對交換操作進行修正。如果交換后出現交叉段外與交叉段內的基因位值重復，則將原來的交叉段內的映射關系按位再反映射施行到重復編碼上。

筆者采用改進的交叉概率和交叉策略相結合的方式，并應用到函數優化過程中。

三、算法的收斂性

遺傳算法與其他一些隨機搜索算法(如模擬退火算法)的不同之處在于，它維持了應該具有一定數目個體的種群。定義遺傳算法的收斂性存在兩種思路:一種是針對整個種群進行定義，另一種思路是針對個體進行定義。在本算法中，需要考慮保證，并盡可能高地提供算法的收斂速度。De Jong博士提出了“精英選擇(elitist selection or elitism)”策略，也稱為“精英保留”(elitist preservation)策略。該策略的思想是，把群體在進化過程中迄今出現的最好個體(稱為精英個體elitist)不進行配對交叉而直接復制到下一代中。20世紀90年代，Rudo1Ph基于 Markov chain理論證明了保留精英的遺傳算法(EGA)以概率1收斂[10-11]。筆者在實際算法的設計中也采用此方法來保證收斂性。

四、改進交叉算子在遺傳算法中的應用

1.算法步驟

(1) 初始化種群：隨進生成N個二進制編碼的染色體，組成初始化種群P。

(2) 計算適應度值：對初始化種群中的所有個體計算其適應度值。

(3) 選擇：根據適應度值進行選擇復制操作，這個過程都是對高適應度值的個體進行選擇，使搜索朝著解空間靠近，盡早收斂到全局最優解。同時為保證算法的收斂性，對選擇操作進行部分改進，采用EGA的思路保留當前最佳個體(精英)，且不參與遺傳操作。

(4) 交叉：按照本文改進的交叉概率和交叉策略進行操作，對個體雙親結合產生新的個體作為后代。

(5) 變異：本文給定的變異概率對個體編碼中的部分信息實施變異，產生新的個體。

(6) 終止條件判斷：如果滿足終止添加，則執行步驟(7)，否則執行步驟(2)。

(7) 輸出：最后把群體中最好個體作為遺傳算法的解輸出，即問題的最優解。

2.試驗結果分析

本文改進的自適應的交叉概率調整算法ICGA要應用到具體的函數優化當中，同時給出比較典型的Schaffer’s F6函數，通過與經典遺傳算法SGA的比較，分析本文改進算法的優良特性，具體函數如下：

(2)

函數定義域為[-100，100]，實驗中采用二進制編碼，本文分別對標準遺傳算法和改進的交叉算子的遺傳算法應用到該函數優化中，獨立運行30次作為一次實驗，種群代數設為200。

對于標準遺傳算法SGA參數為：種群N=100，Pc=0.65，Pm=0.01；對于改進的交叉算子遺傳算法ICGA種群N=100，Pm=0.01。所得實驗結果比較如圖5所示。

圖5 SGA、ICGA算法最大適應度值比較

從結果可以看出，改進后的交叉算子在遺傳算法中有較強的自適應性能和較強的尋優能力，避免了初期陷入局部收斂的情況，同時在全局收斂和全局最優之間也得到了平衡。在收斂性方面，通過采用保留精英個體方式，有效地提供了收斂速度，多次實驗結果表明，由于采用了保留精英方法，其收斂速度較不采用方式約提升20%-30%。實驗結果進一步證明了改進交叉算子的算法應用到遺傳算法中的有效性。

五、結論與展望

筆者對遺傳算法的主要遺傳算子交叉算子進行了改進，用提出的自適應交叉概率參與遺傳操作，細致分析了交叉操作的幾種策略，并在此基礎上提出了一種新的改進算子的遺傳算法，并采用EGA方式提升了收斂速度。通過該算法可以抑制優化初期的“早熟現象”，加快后期的收斂速度，實現全局尋優，獲取最優解。但它也存在一些缺點，目前應用到函數優化上效果比較好，其他應用還需要進一步的探討。

[1] Illinois Genetic Algorithms Laboratory，University of Illinois at Urbana-Champaign，Illinois Genetic Algorithms Laboratory Home[EB/OL].[2006-10-13].http:∥www-illigal.ge.uiuc.edu.

[2] 周明，孫樹棟，遺傳算法原理及應用[M].北京：國防工業出版社，1999：4.

[3] 王小平，曹立明，遺傳算法——理論、應用與軟件實現[M].西安：西安交通大學出版社，2002：34.

[4] Holland J H.Adaptation in Natural and Artificial System[M].Mit Press，Cambridge,Mass,1975.

[5] 李敏強，寇紀凇.遺傳算法的基本理論與應用[M].北京：科學出版社，2002.

[6] 盧厚清.一種遺傳算法交叉算子的改進算法[J].解放軍理工大學學報：自然科學版，2007(3):250-251.

[7] 田東平.遺傳算法中的交叉算子研究[J].內蒙古師范大學學報：自然科學漢文版，2007(3)，308-309.

[8] 屠惠遠.交叉算子的性質分析[J].武漢大學學報：理學版，2005(2)，22-24.

[9] 袁桂霞.運用項目反應理論的試題評價模塊的設計與實現[D].蘇州：蘇州大學，2006.

[10] Rudolph G.Convergence Analysis of Canonical Genetic Algorithms[J].IEEE Trans Neural Networks，1994，5(l):96-101.

[11] 張文修，梁怡.遺傳算法的數學基礎[M].西安：西安交通大學出版社，2000.