基于雙鏈染色體結構的遺傳算法研究*

錢 菲，陳賢富

(中國科學技術大學 信息科學技術學院，安徽 合肥 230026)

0 引言

遺傳算法作為一種全局優化搜索算法，是模擬生物進化過程中“適者生存”的計算模型。傳統的遺傳算法使用簡單，魯棒性強，易于并行化，因而應用研究已從初期的組合優化求解擴展到了許多高新工程化的應用方面[1]。

但是，傳統遺傳算法的局部搜索能力差，容易出現早熟收斂現象[2]。而且每個個體都是用一條染色體表示,這種通過單個變量的遺傳操作只有染色體的交叉、變異和復制卻沒有基因的分離重組的過程，不僅難以表示很多實際應用的對象，而且會造成模式的丟失，不利于保持種群多樣性[3]。本文針對這些不足，對其進行了改進，引入了更加符合生物特性的雙鏈染色體，并重新定義了染色體的重組、交叉和變異操作。

1 雙鏈染色體模型

雙鏈染色體模擬生物學中的二倍體結構，即含有兩個同源染色體組。每個同源染色體組的兩個染色單體分別來自于父母，組成姐妹染色單體。如圖1所示，二倍體的生物遺傳主要通過同源染色體組的非姐妹染色單體之間交叉互換實現基因重組，因此維持了生物特性的世代相傳。本算法中雙鏈染色體特有的“雙鏈”結構具有冗余記憶能力，不僅能夠更好地保留上代的優質基因，而且擴大了基因所攜帶的信息量，較單倍體單鏈結構而言具有更強的適應能力[4-6]。

圖1 同源染色體交叉互換

2 基于雙鏈染色體結構的遺傳算法

基于雙鏈染色體結構的遺傳算法比傳統遺傳算法多出了一組基因信息[7]，因此將傳統遺傳算法的選擇、交叉、變異操作應用到基于雙鏈染色體結構的遺傳算法上時需要進行改進。為了模擬生物繁殖的特性，引入染色體分離重組操作，并用自適應交叉方式來強調兩個基因鏈的共同作用。為了防止優質基因丟失，提出挑選子代再變異和最優個體保存操作[8]。

2.1 染色體分離重組

染色體分離重組就是依照孟德爾分離定律將父代的雙鏈染色體拆分成四個配子，然后將配子重新組合產生四個新的子代，如圖2所示。本文將配子稱為基因鏈，而每個子代都是由含有父代信息的雜型基因鏈重組而成，不僅很好地保持了基因信息的傳遞，而且增加了種群多樣性，為交叉操作做好準備。

圖2 染色體分離重組

2.2 自適應交叉

交叉操作使得遺傳算法具有全局搜索能力，是區別于其他傳統優化方法的重要標志。常見的交叉方式有一點交叉、兩點交叉、多點交叉和一致交叉等。區別于基本遺傳算法的交叉策略，本文提出了自適應交叉方式，以提高搜索效率。自適應交叉是將與或交叉與兩點交叉相結合。與或交叉對基因鏈的模式破壞作用大，能非常好地提高搜索速度，加速收斂。但是這種交叉方式往往會出現偏0或偏1，導致種群多向性降低。因此在此基礎上結合對基因鏈的模式破壞作用不大的兩點交叉，即當采用與或交叉出現種群多樣性下降明顯時換用兩點交叉。

2.3 挑選子代再變異

為了提高局部隨機搜索能力，維持種群的多樣性，提出了挑選子代再變異的操作。根據與或交叉的性質，個體的優秀基因可能存在于適應度高的個體中，也有可能在適應度低的個體中。因此在與或交叉后挑選基因鏈中適應度較高和較低的兩個子代作為遺傳對象來更新種群，其他的全部淘汰。對于兩點交叉，是在種群多樣性下降明顯時自適應采用的，因此在選擇較高適應度的三條基因鏈后再隨機生成一條基因鏈組成兩個新個體來更新種群。這樣不僅能擴大局部搜索范圍，而且維持了種群多樣性，能較好地抑制算法出現局部最優解。

2.4 最優個體保存

更新種群時為了防止適應度較高的個體被淘汰，本文根據雙鏈染色體特有的“雙鏈”結構，提出了保存最優個體的策略：

(1)如果更新子代時，子代最優個體基因鏈的適應度超過父代最優個體基因鏈，則子代最優個體為新的最優個體；

(2)如果更新子代后，子代的最優個體基因鏈的適應度未超過父代最優個體基因鏈，則將父代的最優個體基因鏈放進子代的最差個體基因鏈中，組成新的最優個體。

2.5 算法步驟

(1)初始化種群，設置控制參數，令最大進化代數為G，進化代數變量為g=0。

(2)對初始種群進行適應度計算和多樣性計算，標記最優、最差種群個體信息，然后進行染色體的遺傳配對，更新子代。

(3)判斷g與G的大小關系，如果g

(4)選擇兩個個體進行染色體分離重組，根據當前種群的多樣性，對重組后的個體進行基因鏈的自適應交叉。

(5)計算交叉后所有基因鏈的適應度并排序，然后按適應度值挑選基因鏈組合成新的子代在進行變異。

(6)判斷新種群個體數是否小于種群規模。若是，則轉步驟(4)，繼續循環；若不是，則繼續。

(7)統計生成的新一代種群適應度。

(8)對新舊種群的最優個體進行比較，保存最優個體基因鏈。

(9)更新種群，統計適應度和多樣性，轉步驟(3)。

3 實驗分析

為了能夠驗證基于雙鏈染色體結構的遺傳算法比傳統遺傳算法具有一定的優勢，將兩者進行試驗比較。同時用兩者解決50個貨物的背包問題，從算法質量、收斂速度和種群多樣性三個方面進行分析。

實驗環境為Windows 7 64位操作系統，使用Visio Studio 2013，采用C++語言編碼實現。

實驗中設置各控制參數如下：最大遺傳代數為300，選取交叉概率為0.5，變異概率為0.07，種群規模為200，染色體長度為50，比較基于雙鏈染色體結構的遺傳算法和基本遺傳算法的計算結果質量和收斂速度，如圖3所示。

圖3 適應度對比圖

由圖3可知傳統遺傳算法收斂速度慢，而且容易出現局部最優解，如果進化代數不夠，很難找到一個滿意的解，算法質量比較差。而本算法能以較快的收斂速度達到全局最優解，基本沒有出現局部最優的過渡，這樣無需進化很多代就能找到一個滿意的解。

種群多樣性是影響種群發展的重要因素之一。隨著進化的推演，種群的多樣性會隨之降低。而且不同的進化方式對種群的多樣性影響不同。對比兩種算法的種群多樣性，如圖4所示，能看出本算法在初期因為其特有的雙鏈結構，其多樣性是基本遺傳算法的2倍，但進化一定代數后，多樣性急速下降后維持穩定。這是由于進化初期使用與或交叉方法所導致的。雖然多樣性在這階段下降明顯，但對比圖3可以知道，本算法在前期已經收斂，而且種群的平均多樣性明顯高于傳統遺傳算法。

圖4 多樣性對比圖

從圖3、圖4的結果顯示可知，由于染色體“雙鏈”結構的特殊性，本算法在收斂速度、計算結果的質量和種群多樣性的表現上都有明顯的改進。

4 結束語

本文提出的改進算法基于染色體的“雙鏈”結構，引入染色體分離重組、自適應交叉、挑選子代再變異和最優保存策略的操作。經試驗表明，本算法不僅有效抑制了算法的早熟現象，提高收斂速度，而且維持了種群的多樣性。

但本算法遺留的一個重要問題是自適應交叉操作的分界點問題。在算法操作中根據多樣性下降明顯的點進行變換交叉方式，但左右移動分界點對結果有明顯影響。后續將繼續研究自適應交叉方式的分界點問題，并將該改進算法應用到巨災情景構建及應急能力評估模型優化上。