基于雙鏈染色體結(jié)構(gòu)的遺傳算法研究*

錢 菲，陳賢富

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

0 引言

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

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

1 雙鏈染色體模型

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

圖1 同源染色體交叉互換

2 基于雙鏈染色體結(jié)構(gòu)的遺傳算法

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

2.1 染色體分離重組

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

圖2 染色體分離重組

2.2 自適應(yīng)交叉

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

2.3 挑選子代再變異

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

2.4 最優(yōu)個體保存

更新種群時為了防止適應(yīng)度較高的個體被淘汰，本文根據(jù)雙鏈染色體特有的“雙鏈”結(jié)構(gòu)，提出了保存最優(yōu)個體的策略：

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

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

2.5 算法步驟

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

(2)對初始種群進(jìn)行適應(yīng)度計(jì)算和多樣性計(jì)算，標(biāo)記最優(yōu)、最差種群個體信息，然后進(jìn)行染色體的遺傳配對，更新子代。

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

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

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

(6)判斷新種群個體數(shù)是否小于種群規(guī)模。若是，則轉(zhuǎn)步驟(4)，繼續(xù)循環(huán)；若不是，則繼續(xù)。

(7)統(tǒng)計(jì)生成的新一代種群適應(yīng)度。

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

(9)更新種群，統(tǒng)計(jì)適應(yīng)度和多樣性，轉(zhuǎn)步驟(3)。

3 實(shí)驗(yàn)分析

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

實(shí)驗(yàn)環(huán)境為Windows 7 64位操作系統(tǒng)，使用Visio Studio 2013，采用C++語言編碼實(shí)現(xiàn)。

實(shí)驗(yàn)中設(shè)置各控制參數(shù)如下：最大遺傳代數(shù)為300，選取交叉概率為0.5，變異概率為0.07，種群規(guī)模為200，染色體長度為50，比較基于雙鏈染色體結(jié)構(gòu)的遺傳算法和基本遺傳算法的計(jì)算結(jié)果質(zhì)量和收斂速度，如圖3所示。

圖3 適應(yīng)度對比圖

由圖3可知傳統(tǒng)遺傳算法收斂速度慢，而且容易出現(xiàn)局部最優(yōu)解，如果進(jìn)化代數(shù)不夠，很難找到一個滿意的解，算法質(zhì)量比較差。而本算法能以較快的收斂速度達(dá)到全局最優(yōu)解，基本沒有出現(xiàn)局部最優(yōu)的過渡，這樣無需進(jìn)化很多代就能找到一個滿意的解。

種群多樣性是影響種群發(fā)展的重要因素之一。隨著進(jìn)化的推演，種群的多樣性會隨之降低。而且不同的進(jìn)化方式對種群的多樣性影響不同。對比兩種算法的種群多樣性，如圖4所示，能看出本算法在初期因?yàn)槠涮赜械碾p鏈結(jié)構(gòu)，其多樣性是基本遺傳算法的2倍，但進(jìn)化一定代數(shù)后，多樣性急速下降后維持穩(wěn)定。這是由于進(jìn)化初期使用與或交叉方法所導(dǎo)致的。雖然多樣性在這階段下降明顯，但對比圖3可以知道，本算法在前期已經(jīng)收斂，而且種群的平均多樣性明顯高于傳統(tǒng)遺傳算法。

圖4 多樣性對比圖

從圖3、圖4的結(jié)果顯示可知，由于染色體“雙鏈”結(jié)構(gòu)的特殊性，本算法在收斂速度、計(jì)算結(jié)果的質(zhì)量和種群多樣性的表現(xiàn)上都有明顯的改進(jìn)。

4 結(jié)束語

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

但本算法遺留的一個重要問題是自適應(yīng)交叉操作的分界點(diǎn)問題。在算法操作中根據(jù)多樣性下降明顯的點(diǎn)進(jìn)行變換交叉方式，但左右移動分界點(diǎn)對結(jié)果有明顯影響。后續(xù)將繼續(xù)研究自適應(yīng)交叉方式的分界點(diǎn)問題，并將該改進(jìn)算法應(yīng)用到巨災(zāi)情景構(gòu)建及應(yīng)急能力評估模型優(yōu)化上。