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

沈 暢 樂 天

（浙江海洋學院數理與信息學院 浙江 舟山 316000）

0 引言

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

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

1 變異算子的發展

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

1.1 傳統的變異算子

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

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

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

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

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

1.2 改進的變異算子

在成熟的傳統變異算子的基礎上不少學者做了大量的研究和探索，從理論，克服早熟現象和應用等方面提出了許多改進方法，有效提高遺傳算法的性能。

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

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

1.2.2 變異算子在克服早熟現象上的改進

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

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

1.2.3 變異算子在TSP的改進

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

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

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

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

2.1 加強遺傳算法基礎理論的研究

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

2.2 變異算子與其他技術的結合

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

2.3 相關應用問題的拓寬

遺傳算法應用領域比較廣泛，對變異算子的改進主要應用于函數優化問題，今后可以探討變異算子在不同問題中的改進方法。

3 結束語

遺傳算法提供解決問題的基本框架，確實帶來一定優勢，但基本遺傳算法的性能有待提高。可以從不同的角度進行遺傳算法的改進，其改進的切入點不僅和所解決的問題相關，也和所使用的編碼，遺傳算子及相關的參數相關。本文從變異算子的角度介紹了對遺傳算法的改進方法，加強了變異算子對傳統遺傳算法的作用，改善了算法的搜索效率，克服過早收斂的缺點，為今后的遺傳算法的發展提供借鑒。

［1］周明，孫樹棟，等.遺傳算法原理及應用[M].北京：國防工業出版社，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］鞏敦衛，等.基于模式定理的遺傳算法交叉和變異概率上限[J].控制與決策，2004，19(5)：554-556.

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

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

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

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

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

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

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

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

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

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