沈 暢 樂 天

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

0 引言

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

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

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

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

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

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

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

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

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

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

1.2 改進的變異算子

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

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

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

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

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

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

1.2.3 變異算子在TSP的改進

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

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

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

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

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

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

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

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

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

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

3 結(jié)束語

遺傳算法提供解決問題的基本框架，確實帶來一定優(yōu)勢，但基本遺傳算法的性能有待提高?？梢詮牟煌慕嵌冗M行遺傳算法的改進，其改進的切入點不僅和所解決的問題相關(guān)，也和所使用的編碼，遺傳算子及相關(guān)的參數(shù)相關(guān)。本文從變異算子的角度介紹了對遺傳算法的改進方法，加強了變異算子對傳統(tǒng)遺傳算法的作用，改善了算法的搜索效率，克服過早收斂的缺點，為今后的遺傳算法的發(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é)報，2009，23 (3)：32-36.

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

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

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

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

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

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

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

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

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