摘 要：遺傳算法是一種搜索最優(yōu)解的仿生算法，是模擬生物進化過程的計算模型，在自動控制、生產調度、圖像處理等眾多領域有著廣泛的應用，但遺傳算法中的早熟收斂是一個不可忽視的現(xiàn)象，導致不能搜索到全局最優(yōu)解。本文對遺傳算法作了深入的研究，分析導致早熟收斂的原因，提出防止早熟收斂的各種措施。

關鍵詞：遺傳算法；早熟收斂；分析與防止

中圖分類號：TP301.6 文獻標識碼：A

1 引言

遺傳算法[1]（Genetic Algorithm，GA）是由美國J.Holland教授和他的學生于1975建立起來的，主要思想是模擬生物進化中“適者生存”的規(guī)律。在解決多參數(shù)和非線性問題中，傳統(tǒng)的優(yōu)化方法不但效率低，而且有可能得不到結果。遺傳算法具有極強魯棒性和很高的搜索能力，為解決這類問題提供了一種有效的信息途徑，其強大的搜索能力和突出的優(yōu)點，受到人們越來越多的重視。但遺傳算法也有自己的不足之處，其中之一就是早熟收斂（也稱未成熟收斂）問題，也是目前最難處理的關鍵問題。早熟收斂使算法進入局部最優(yōu)解，而遺傳算法的一些優(yōu)良性能將無法完全體現(xiàn)。本文深入分析產生早熟現(xiàn)象的原因，并提出防止早熟收斂的一些措施。

2 遺傳算法實現(xiàn)原理

遺傳算法模擬生物進化的過程，設計合理的編碼方法將各類實際問題轉換為染色體形式的表示方式，并利用復制、交叉、變異等遺傳算子的操作，經過對逐代解的優(yōu)勝劣汰，最終搜索到問題的全局最優(yōu)的解決方案[2，3]。

遺傳算法步驟中的兩個關鍵問題是編碼方法和遺傳算子的設計。它把需要解決問題的參數(shù)編成某種數(shù)制的編碼，如二進制或十進制編碼，這種編碼我們把它稱它稱為基因，若干基因組合就成為一個染色體，每一個染色體對應問題的一個解決方案，據此可執(zhí)行相應的復制、交叉和變異算子的操作[4]。

（1）復制算子

復制算子任務是按某種方法從父代群體中選取一些個體，遺傳到下一代群體。復制算子按某一概率在群體中成對選擇個體，個體選擇的概率與其適應度值成正比，適應度值高的個體，被遺傳到下一代群體中的概率就大。其在選擇算子的操作過程中，首先根據特定的適應值函數(shù)計算方法得到群體中所有個體的適應值，依一定概率選擇需復制的個體，然后按指定的選擇方法確定優(yōu)良個體。個體復制的分配方法包括按比例的適應度分配、基于排序的適應度分配等方法。

（2）交叉算子

所謂交叉算子就是將兩個相互交配的染色體以某種方式（點式交叉、基于位置交叉）相互交換部分基因，產生兩個新的個體。交叉算子可以防止某些遺傳信息不會被丟失，其交叉過程就是產生新個體的過程。交叉運算在遺傳算法中新個體的產生起著關鍵的作用，是區(qū)別于其他進化運算的重要特征。

（3）變異算子

變異是指在群體中隨機選擇一個個體，以較小的概率改變某部分基因，用新的基因替換原有基因，改變原個體的編碼結構，實現(xiàn)群體的多樣性。

利用復制算子將一些適應度值高的優(yōu)良的個體遺傳到下一代群體中，體現(xiàn)出自然界優(yōu)勝劣汰的規(guī)律；利用交叉算子進行模式重組，不但繼承了父代個體的優(yōu)良基因，而且在一定程度上能夠維持群體的多樣性；利用變異算子進行模式突變，能夠進一步保證群體的多樣性。群體中的個體經過復制、交叉、變異一系列操作，逐步向較好的方向進化，最終得到問題的最優(yōu)解。

3 遺傳算法的求解步驟

遺傳算法求解步驟如下：

（1）一組第0代的初始的候選解群體的生成。

（2）使用復制算子操作生成復制后代。

（3）根據交叉概率，將交叉算子作用于候選解群體，個體隨機兩兩配對，生成新的候選解。

（4）根據變異概率，對步驟（3）中生成的候選解群進行變異操作，形成新一代的候選解群體。

（5）計算群體中各個候選解的適應值，如果候選解不滿足算法終止條件，返回步驟（2）否則結束算法。

遺傳算法的操作流程圖如圖1所示。

4 遺傳算法的早熟問題

4.1 早熟現(xiàn)象

“早熟”是指遺傳算法早期，在種群中出現(xiàn)了超級個體，該個體的適應值將會大大超過當前種群的平均個體適應值∑fi/N，從而使得該個體很快在種群中占有絕對的比例，使算法較早收斂于局部最優(yōu)點的現(xiàn)象[5]。早熟收斂問題表現(xiàn)為會使接近最優(yōu)解的個體總是被淘汰和群體中所有個體都陷入同一極值而停止進化。群體中個體結構的多樣性急劇減少是遺傳算法中的較為突出的問題之一，在找到最優(yōu)解或滿意解之前，遺傳算法希望群體中個體結構保持多樣性，搜索不斷進行。早熟收斂與局部極小值問題有很大的不同，早熟收斂并不一定在局部極小點出現(xiàn)，而且早熟是難預見是否會出現(xiàn)，它是隨機性產生的。

4.2 早熟產生的主要原因

早熟產生的主要原因主要有以下幾點：

（1）遺傳算法在進化過程中，會產生一些超常的個體，這些個體由于競爭力非常強，常?？刂浦x擇運算過程，結果只得到算法某個局部最優(yōu)解，并非全局最優(yōu)解，即遺傳欺騙。

（2）在理論上，遺傳算法中的交叉、復制、變異操作都是精準的，具有搜索整個空間的能力，但是在實現(xiàn)時這個要求很難達到。

（3）由于遺傳算法中存在隨機取樣誤差和隨機選擇誤差，因此當所選的串并非相似子集的代表時，就會存在誤差。如果選擇的個體沒有按期望的概率進行，選擇誤差在所難免。

上述三個方面都有可能過早地丟失群體中個體的多樣性，結果獲得只是局部最優(yōu)解，而非全局最優(yōu)解，即產生早熟收斂現(xiàn)象。當經過多代進化，算法進行到后期，種群中超級個體占據了絕大多數(shù)，傳統(tǒng)的交叉操作已不能產生新個體，失去了作用，而變異操作雖然能夠為補充新個體，但發(fā)生的概率畢竟非常小。

通常，種群規(guī)模較大，可以增加優(yōu)化信息，阻止早熟收斂的發(fā)生，但是會增加計算量，以致收斂時間過長，收斂速度較慢；種群太小則不能提供足夠的采樣點，造成算法性能較差。復制操作使適應度高的個體能夠以更大的概率生存，提高了遺傳算法的全局收斂性。交叉操作產生新的個體是在解空間中進行有效搜索，當交叉概率太大，種群中個體更新快，會導致適應度高的個體很快被破壞掉；當概率過小時，很少會進行交叉操作，使搜索停滯不前，造成算法的不收斂。

5 早熟收斂的防止

知道早熟產生的原因之后，怎樣防止早熟收斂現(xiàn)象，尋找到滿意解或最優(yōu)解呢？解決的方法主要有：

5.1 配對策略

通常，在物種的形成過程中有目的地選擇配對個體，合理的選擇配對策略，能有效地保持群體的多樣性，防止不相似的個體進行配對[6]。不同種族在生物界一般不會雜交的，原因是基因結構不同，會發(fā)生互斥作用。因此，大多數(shù)是同種或近種相配，保存和發(fā)揚一個種族的優(yōu)良特性。Goldberg的共享函數(shù)是一種間接匹配策略，在一定程度上限制了占統(tǒng)治地位的物種內相互匹配。Eshelman提出一種防止相似個體配對的策略，隨機配對參與交配的個體，對參與配對的個體而言，只有它們間的海明距離超設定的閾值時，參與的交配的個體才允許進行交配[7]。在交配時，可將初始群體海明距離的期望平均值作為閾值初值時，隨著迭代過程的不斷深入，可以逐步減小閾值。在某種程度上，匹配策略雖然可以維護群體的多樣性，但在交叉操作中會破壞很多模板，因此也有一定的副作用。

5.2 重新啟動法

當遺傳算法在搜索過程中由于碰到早熟收斂問題而停滯不前時，可隨機選擇一組初始值重新進行遺傳算法操作，即重新啟動法。如果每次執(zhí)行遺傳算法后陷入早熟收斂的概率為M（0≤M<1），那么經過n次獨立的遺傳算法操作后，可避免早熟收斂的概率為F（n）=1-Mn，隨著n的不斷增大，F(xiàn)（n）將漸近于1。但是，在收斂概率M很大的情況下，每次執(zhí)行時間都很長和優(yōu)化對象很復雜時，則不宜采用重新啟動法。

5.3 重組策略

重組策略就是利用交叉操作產生與其父輩不同的個體，在某種程度上，使產生的群體更具有多樣性。一種方法是動態(tài)改變適應度函數(shù)和增加交叉操作的使用頻率，如共享函數(shù)方法，使交叉操作更具有活力；另一種方法是把交叉點選在具有不同值的位的個體上實現(xiàn)群體多樣性。當父輩個體存在兩位以上不同時，新產生的子代個體就與父輩不相同。遺傳算法中使用具有破壞性的交叉算子時能較好地維持群體的多樣性，如均勻交叉算子。由于該算子交叉近一半的不同位，因此保留的模板比單點或兩點交叉要少得多?？傊?，重組策略是通過交叉操作使用頻率和交叉點來維持群體的多樣性，對采用隨機選擇配對個體進行交叉操作有著特定的意義，但對成比例選擇方式，則效果不一定明顯。

5.4 替代策略

匹配策略是在復制階段通過某種策略來維持群體的多樣性，重組策略是交叉階段性按照某種策略來維持群體的多樣性，而替代策略則是由復制，交叉產生的個體中選擇某個個體進入新一代群體。De Jong用新產生的個體去替代父輩中類似的個體，采用的是排擠模式。Syscuda和Whiteley是把父輩各個個體均不相似的新個體添加到群體中[8]，與De Jong的策略類似。這種替換策略不足之處是在交叉操作很多模板被破壞，有一定的負面影響，不過與重組策略相比較，這種影響還是非常小的。

早熟收斂是遺傳算法迭代過程中可能發(fā)生的問題，在實際應用中，需結合具體問題分析，采用一種或多種方法來設計遺傳算法，消除早熟收斂現(xiàn)象，使遺傳算法的搜索能力得到更好的保證，在實際應用得到更好地效果。

參考文獻

[1] Holland J H. Adaptation in Nature and Artificial Systems[J]. 2nd ed .Cambridge：MIT Press，1992：91-92.

[2] Goncalves J F.A hybrid genetic algorithm for job shop scheduling problem[J].European Journal of Operational Research，2005，167（1）：77-95.

[3] 陳國良，王煦法，莊鎮(zhèn)全.遺傳算法及其應用[M].北京：人民郵電出版社，1996：121-125.

[4] 曾建潮，崔志華.自然計算[M].北京：國防工業(yè)出版社，2012：12-18.

[5] 曳永芳，杜永清，行小帥.一種抑制早熟收斂的改進遺傳算法[J].山西師范大學學報（自然科學版），2010（2）：24-27.

[6] 譚丹丹，曹斌，劉俊.一種基于配對的改進遺傳算法[J].計算機應用，2007，（12）：45-48.

[7] 王春水，肖學柱，陳漢明.遺傳算法的應用舉例[J].計算機仿真，2005：155-157.

[8] 高艷霞，劉峰，王道洪.改進型遺傳算法及其應用研究[J].上海大學學報， 2004（10）：249-251.

作者簡介：

聶 軍（1976-），男，碩士，講師，高級工程師.研究領域：計算機及應用技術的開發(fā).