遺傳算法中的變異算子的述評

沈 暢 樂 天

（浙江海洋學(xué)院數(shù)理與信息學(xué)院 浙江 舟山 316000）

0 引言

遺傳算法于1969年由美國Michigan大學(xué)的Holland教授提出后，在保持其基本框架的基礎(chǔ)上，許多學(xué)者提出了不同的改進(jìn)方法，如自適應(yīng)遺傳算法、混沌遺傳算法、量子遺傳算法、混合遺傳算法等。但算法的改進(jìn)和問題本身相關(guān)，并且遺傳算法的基礎(chǔ)理論仍未根本解決，在進(jìn)行算法改進(jìn)時(shí)缺少理論的指導(dǎo)，所以改進(jìn)的算法沒有普遍的適用性。雖然遺傳算法有自身的不足，但因其具有較強(qiáng)的魯棒性，在如金融，自動控制，模式識別，組合優(yōu)化，故障診斷等領(lǐng)域都有成功的應(yīng)用。

在遺傳算法中，變異算子通過模擬生物遺傳和進(jìn)化過程中的變異環(huán)節(jié)對個體進(jìn)行變異，雖然發(fā)生變異的可能性比較的小，但也是產(chǎn)生新物種的一個不可忽視的原因[1]。通過變異不斷在交叉算子產(chǎn)生的新個體的基礎(chǔ)上進(jìn)行微調(diào)、增加種群的多樣性、使遺傳算法在交叉算子決定的全局搜索能力的基礎(chǔ)上還具有一定的局部搜索能力。變異算子被認(rèn)為是必不可少的產(chǎn)生新個體的輔助方法，文獻(xiàn)[2]認(rèn)為變異算子能夠成為一個重要的遺傳算子，特別體現(xiàn)在維持種群的多樣性問題上。正是變異算子在遺傳算法中的不可或缺性，本文在總結(jié)相關(guān)文獻(xiàn)資料的基礎(chǔ)上，從不同角度對變異算子的改進(jìn)進(jìn)行討論，并展望其發(fā)展方向，為遺傳算法中變異算子的進(jìn)一步發(fā)展提供參考。

1 變異算子的發(fā)展

簡單遺傳以初始種群為基點(diǎn)，經(jīng)過選擇、交叉、變異操作生成新的種群，如此更新種群直到滿足終止條件。遺傳算法中變異算子的具體操作是以變異概率Pm用新的基因值替代原有的基因值，產(chǎn)生新的個體。變異算子對個體編碼串的基因做了局部的改變，維持種群的多樣性，這樣有利于防止出現(xiàn)早熟現(xiàn)象。

1.1 傳統(tǒng)的變異算子

用遺傳算法求解問題時(shí)，對于變異算子的選擇首先會考慮已有的成熟的變異算子。幾種常用的變異算子主要有基本位變異、均勻變異和高斯變異等。

1.1.1 基本位變異是指對個體的每一個基因座，依變異概率Pm指定其為變異點(diǎn)，對變異點(diǎn)的基因值進(jìn)行反轉(zhuǎn)或用其他等位基因值來代替。

1.1.2 均勻變異操作是指分別用符合某一范圍內(nèi)均勻分布的隨機(jī)數(shù)，以某一較小的概率替換個體編碼串中各個基因座上的原有基因值。

1.1.3 高斯變異操作是指進(jìn)行變異操作時(shí)，用符合均值為μ、方差為σ的正態(tài)分布的一個隨機(jī)數(shù)來替換原有基因值。

還有如邊界變異、非均勻變異等等，這里不贅述了?？梢钥闯鲎儺愃阕拥脑O(shè)計(jì)會涉及變異點(diǎn)位置的確定和基因值的替換兩個方面。這兩個問題的解決與編碼及所解決的問題是密切聯(lián)系的。上述的變異算子對多值編碼都適用，但考慮問題的特殊性，變異算子又不能一概簡單進(jìn)行操作。如對TSP問題，若用數(shù)字代表城市，如用52134編碼串表示5個城市的一種旅行路線。因問題本身要求城市不能重復(fù)出現(xiàn)，這使得變異時(shí)不能通過對基因座上的基因值進(jìn)行替換來實(shí)現(xiàn)。出現(xiàn)了如倒位變異和交換變異等變異算子。倒位變異是指將隨機(jī)選取的兩個基因座之間的基因進(jìn)行逆序排序。變換變異是指對于隨機(jī)選取的基因座之間的基因值進(jìn)行交換。

1.2 改進(jìn)的變異算子

在成熟的傳統(tǒng)變異算子的基礎(chǔ)上不少學(xué)者做了大量的研究和探索，從理論，克服早熟現(xiàn)象和應(yīng)用等方面提出了許多改進(jìn)方法，有效提高遺傳算法的性能。

1.2.1 變異算子在理論方面的研究

變異算子在理論方面的深入研究不多，文獻(xiàn)[3]給出了基于模式定理的變異概率上限確定公式，由公式可知，可以通過選擇適當(dāng)?shù)淖儺惛怕?，使得某模式所含個體數(shù)目經(jīng)過選擇、交叉和單點(diǎn)變異等操作后得到增長。 文獻(xiàn)[4]提出了基于位變異的模式遺傳算法。直接把模式作為個體，使用的編碼策略本質(zhì)上比SGA的編碼策略更加直接。并對其收斂性進(jìn)行了分析。

1.2.2 變異算子在克服早熟現(xiàn)象上的改進(jìn)

對變異算子的改進(jìn)主要是針對遺傳算法的局部搜索能力較弱及存在早熟現(xiàn)象，許多研究者提出了許多改進(jìn)的方法，下面對此做個總結(jié)。

文獻(xiàn)[5]提出基于細(xì)分變異算子的遺傳算法。將變異算子細(xì)分為最優(yōu)調(diào)教算子和大步前進(jìn)算子兩種算子的形式。文獻(xiàn)[6]提出了一種新的改進(jìn)遺傳算法雙變異算子遺傳算法。通過將所有產(chǎn)生的子代個體與父代個體混合作為下一代種群，在種群選擇前對適應(yīng)度值較低的個體進(jìn)行一次變異，然后通過選擇、交叉，再一次變異產(chǎn)生新種群，再利用自適應(yīng)算法改變交叉和變異率及最優(yōu)保存策略保護(hù)歷代最優(yōu)個體，雙變異算子的遺傳算法能夠最大限度使種群多樣性，這樣最有可能得到最優(yōu)解，也易突破局部收斂的局限而達(dá)到全局最優(yōu)。文獻(xiàn)[7]提出了一種雙變異率的改進(jìn)遺傳算法。在進(jìn)化過程中，引入廣義海明距離這個概念，當(dāng)由廣義海明距離控制的交叉操作產(chǎn)生個體數(shù)不足種群規(guī)模時(shí)，對原種群進(jìn)行局部小變異，這樣在避免近親繁殖的同時(shí)又可擴(kuò)大搜索空間，增加種群多樣性，有效地抑制了早熟收斂；隨后進(jìn)行的全局大變異保證整個過程全局收斂。文獻(xiàn)[8]提出了一種基于位變異的防止遺傳算法過早收斂的算法。該算法通過種群熵來判斷過早收斂的發(fā)生。當(dāng)發(fā)生過早收斂時(shí)，在單調(diào)系數(shù)的指導(dǎo)下進(jìn)行有針對性的位變異，從局部最優(yōu)解的范圍內(nèi)擺脫出來，算法重新具有進(jìn)化能力。文獻(xiàn)[9]提出一種采用新的解碼方案的動態(tài)變異遺傳算法。文獻(xiàn)[10]根據(jù)個體適應(yīng)度不同對變異概率進(jìn)行自適應(yīng)調(diào)整，使群體中的優(yōu)良模式不易被破壞，同時(shí)又保證了種群個體的多樣性，從而提高了算法的搜索效率。算法中改變了交叉與變異的操作順序，避免了個體適應(yīng)度的重復(fù)計(jì)算，提高運(yùn)行速度。文獻(xiàn)[11]提出了一種將強(qiáng)制變異、最佳解保留和自適應(yīng)交叉變異參數(shù)調(diào)整相結(jié)合的改進(jìn)遺傳算法。這種方法將進(jìn)化過程中群體的平均適應(yīng)度與最大適應(yīng)度進(jìn)行比較，以確定是否需要對群體實(shí)施強(qiáng)制變異或采用自適應(yīng)交叉、變異概率調(diào)整。這種方法可有效地克服早熟現(xiàn)象，提高全局優(yōu)化能力。

1.2.3 變異算子在TSP的改進(jìn)

組合優(yōu)化問題是遺傳算法通常解決的應(yīng)用問題，TSP是典型的組合優(yōu)化問題，屬于NP難問題。其變異算子的設(shè)計(jì)有其特殊性，有學(xué)者在這方面也做了相應(yīng)的研究。

文獻(xiàn)[12]通過分析TSP問題的特征，結(jié)合以減少周游路線中交叉邊為啟發(fā)式信息，引入了一個遺傳算法中新的變異策略用于TSP求解。該變異策略能夠引導(dǎo)算法通過有指導(dǎo)性的變異更快地收斂到更好的解。文獻(xiàn)[13]也在遺傳算法解決tsp問題中進(jìn)行了改進(jìn)。提出多步強(qiáng)化變異，其是在單步強(qiáng)化變異策略的基礎(chǔ)上進(jìn)行了改進(jìn)，通過向前考察幾步個體進(jìn)化效果，將該信息向回傳遞，影響個體變異策略。

2 遺傳算法中變異算子的未來研究方向展望

通過與遺傳算法中變異算子相關(guān)的文獻(xiàn)的整理，我們知道變異算子的改進(jìn)有助于遺傳算法性能的提高，在總結(jié)已有研究的基礎(chǔ)上，提出以下幾點(diǎn)未來研究方向：

2.1 加強(qiáng)遺傳算法基礎(chǔ)理論的研究

幾乎對遺傳算法中變異算子的改變都是從處理的實(shí)際問題出發(fā)的，這種改進(jìn)對于處理其他問題的遺傳算法是否有效值得商榷。這種改進(jìn)還是受到遺傳算法基礎(chǔ)理論的薄弱的限制。從遺傳算法的收斂性，早熟機(jī)理等方面從數(shù)學(xué)角度進(jìn)行分析，剖析變異算子的作用機(jī)理，更好地改進(jìn)變異算子。

2.2 變異算子與其他技術(shù)的結(jié)合

從上述的研究看，變異算子的改進(jìn)還是集中在對算子本身的直接改進(jìn)，可以借鑒其他算法特別是優(yōu)化算法，與變異算子進(jìn)行結(jié)合，提高變異算子對算法搜索性能的作用。

2.3 相關(guān)應(yīng)用問題的拓寬

遺傳算法應(yīng)用領(lǐng)域比較廣泛，對變異算子的改進(jìn)主要應(yīng)用于函數(shù)優(yōu)化問題，今后可以探討變異算子在不同問題中的改進(jìn)方法。

3 結(jié)束語

遺傳算法提供解決問題的基本框架，確實(shí)帶來一定優(yōu)勢，但基本遺傳算法的性能有待提高?？梢詮牟煌慕嵌冗M(jìn)行遺傳算法的改進(jìn)，其改進(jìn)的切入點(diǎn)不僅和所解決的問題相關(guān)，也和所使用的編碼，遺傳算子及相關(guān)的參數(shù)相關(guān)。本文從變異算子的角度介紹了對遺傳算法的改進(jìn)方法，加強(qiáng)了變異算子對傳統(tǒng)遺傳算法的作用，改善了算法的搜索效率，克服過早收斂的缺點(diǎn)，為今后的遺傳算法的發(fā)展提供借鑒。

［1］周明，孫樹棟，等.遺傳算法原理及應(yīng)用[M].北京：國防工業(yè)出版社，1999.

［2］Muehlenbein H.How genetic algorithms really work：mutation and hill climbing [C].In Proc，and Workshop Parallel Problem Solving from Nature，1992：15-25.

［3］鞏敦衛(wèi)，等.基于模式定理的遺傳算法交叉和變異概率上限[J].控制與決策，2004，19(5)：554-556.

［4］張愛華.基于位變異的模式遺傳算法[J].五邑大學(xué)學(xué)報(bào)，2009，23 (3)：32-36.

［5］王乾龍，等.基于細(xì)分變異算子策略的遺傳算法[J].濟(jì)南大學(xué)學(xué)報(bào)，2012，26(1)：15-19.

［6］魯群，等.雙變異算子遺傳算法的應(yīng)用 [J].計(jì)算機(jī)技術(shù)與發(fā)展，2008，18(7)：42-44.

［7］王杰，等.一種雙變異率的改進(jìn)遺傳算法及其仿真研究[J].計(jì)算機(jī)工程與應(yīng)用，2008，44(3)：57-59.

［8］萬定生，等.基于位變異防止遺傳算法過早收斂的算法[J].微電子學(xué)與計(jì)算機(jī)，2005，22(8)：117-120.

［9］鄭磊，等.基于動態(tài)變異遺傳算法的組播路由算法[J].計(jì)算機(jī)工程與應(yīng)用，2005，31：141-143.

［10］劉德朋.基于變異概率自適應(yīng)調(diào)整的逆序遺傳算法研究[J].杭州電子工業(yè)學(xué)院學(xué)報(bào)，2004，24(1)：8-11.

［11］孔祥蕾，等.一種引入強(qiáng)制變異的改進(jìn)遺傳算法[J].中國科學(xué)院研究生院學(xué)報(bào)，2003，20(3)：317-320.

［12］張曉玲，等.用一種含啟發(fā)式變異策略的遺傳算法求解TSP[J].計(jì)算機(jī)應(yīng)用與軟件，2010，27(3)：237-240.

［13］劉菲，等.基于多步強(qiáng)化變異算子的混合遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用，2011，47(29)：46-48.