遺傳算法的收斂性研究

汪民樂

摘 要：遺傳算法的收斂性分析是遺傳算法研究中的重要問題，直接關系到遺傳算法的實際應用價值。給出遺傳算法全局收斂性的定義，描述當前遺傳算法收斂性分析的主要模型，對自適應遺傳算法、并行遺傳算法、小生境遺傳算法等典型遺傳算法的收斂性進行分析，給出相關的研究結果，并指出遺傳算法收斂性研究的未來發展方向。研究結果對提高遺傳算法收斂性具有參考價值。

關鍵詞：遺傳算法；全局收斂性；自適應遺傳算法；并行遺傳算法；小生境遺傳算法

中圖分類號：TP18 文獻標識碼：A

Abstract：The convergence analysis is an important problem in research on Genetic Algorithm. In this paper， the new definition of Genetic Algorithms convergence was given，the main models for Genetic Algorithms convergence were described， and the typical Genetic Algorithms convergence were analyzed， the conclusions were given. Finally，the future efforts were put forward. The results can offer support for improving Genetic Algorithms convergence .

Key words：genetic algorithm；convergence；adaptive genetic algorithm；parallel genetic algorithm；niche genetic algorithm

1 引 言

作為一種普遍適用的隨機大范圍搜索策略，遺傳算法（Genetic Algorithm—GA）的收斂性研究[1-10]，是遺傳算法隨機搜索機理研究的核心內容。建立公理化的收斂性理論體系，不但可以提高現有遺傳算法的收斂速度，克服陷于局部極值和出現過早收斂，同時可以探討判定當前解是否達到最優解的合理準則，從而給出合理的停機準則。因此，通過遺傳算法收斂性的研究，可為遺傳算法的發展提供堅實可靠的理論依據及正確的方向。目前，關于遺傳算法的收斂性研究主要有兩種方法：一種是將種群數目推廣到無窮，研究其概率密度[11]；一種是以馬氏鏈理論作為工具研究有限種群收斂性[12]。由于GA實際應用中，均只能構造有限種群，故在此主要研究有限種群GA的全局收斂性。

2 遺傳算法收斂性研究的主要方法

遺傳算法的收斂性通常是指遺傳算法所生成的迭代種群收斂到某一穩定狀態，或其適應值函數的最大或平均值隨迭代趨于優化問題的最優值。依據不同的研究方法及所用的數學工具，已有的遺傳算法收斂性研究方法可大致分為四類[13]：VoseLiepins模型、Markov模型、公理化模型和連續（積分算子）模型。

2.1 VoseLiepins 模型

這類模型大致可以分為兩種情形， 即針對無限種群和有限種群的模型。 首先由Vose 和Liepins在1991 年提出了針對無限種群的模型， 其核心思想是： 用兩個矩陣算子分別刻畫比例選擇與組合算子（即雜交算子與變異算子的復合）， 通過研究這兩個算子不動點的存在性與穩定性來刻畫GA 的漸近行為。VoseLiepins 模型在種群規模無限的假設下可精確刻畫GA ， 但在有限規模情形下卻只能描述GA 的平均性態。 為了克服這一缺陷， Nix 和Vose 在1992 年結合VoseLiepins 模型與Markov 鏈描述， 發展了GA 的一個精確Markov 鏈模型， 稱為NixVose 模型， 它針對的是有限種群的情形， 該模型恰好描述了GA 的實際演化過程， 但是由于NixVose 的有限種群模型概率轉移矩陣的復雜性， 故直接基于該模型分析GA 收斂性是困難的， 而VoseLiepins 的無限種群模型雖然只能描述實際GA 演化的平均性態， 但它卻精確預報了GA收斂性態隨種群規模的變化。

2.2 Markov 鏈模型

由于遺傳算法下一代種群的狀態通常完全依賴當前種群信息， 而不依賴于以往狀態， 故可自然地用Markov鏈描述，這也是遺傳算法收斂性研究中最常采用的工具。這種方法一直被用于研究不同形式GA 的漸近行為， 并得出一些典型的結果， 如：用Markov 鏈描述其動態行為；從更一般的等價類層次表述種群等。當然， 還有很多其它的分析結果充分體現了使用Markov 鏈模型描述遺傳算法具有直接、精確的優點， 但由于所采用有限狀態Markov鏈理論本身的限制， 該模型只能用于描述通常的二進制編碼或特殊的非二進制編碼GA。

2.3 公理化模型

這種模型既可用于分析時齊GA，又可用于分析非時齊GA。其核心思想是： 通過公理化描述GA的選擇算子與演化算子， 并利用所引進的參量分析GA的收斂性。 對于常見的選擇算子與演化算子， 所引進的參量能方便地確定， 因而這一模型具有重要的理論意義與應用價值。該模型通過詳細估計常見選擇算子與演化算子的選擇壓力、選擇強度、保存率、 遷入率、遷出率等參數， 導出了一系列具有重要應用價值的GA 收斂性結果。此外， 該模型也可用于非遺傳算法類的其它模擬演化算法的收斂性分析。

2.4 連續（積分算子）模型

大量數值試驗表明：為了有效解決高維連續問題和GA 實現中的效率與穩健性問題， 直接使用原問題的浮點表示而不進行編碼轉換具有許多優點，由此形成的遺傳算法稱為連續變量遺傳算法或浮點數編碼遺傳算法。對于這類連續變量遺傳算法收斂性的分析方法，已有一些研究成果，如： 浮點數編碼模式定理，用以描述進化過程中模式的變化規律，特別是優良模式的產生及變化（保持或被破壞）規律，從而有助于分析連續變量遺傳算法的收斂性；通過研究大樣本行為， 分別導出了連續變量GA 在使用比例選擇、均勻雜交和變異以及三個遺傳算子聯合作用等情形下， 當種群規模趨于無窮時， 種群的概率分布所對應的密度函數應滿足的遞歸公式，但該結果只是在種群規模趨于無窮的條件下得到的種群迭代序列分布的估計， 故只能看作是對GA 漸近行為的大樣本近似，并不能直接應用于改進一般GA 的實際執行策略。

3 典型遺傳算法的收斂性

3.1 標準遺傳算法（Canonical Genetic Algorithm—CGA）的全局收斂性

實數編碼遺傳算法的產生是遺傳算法研究的一大進步，相關的理論與應用成果不斷出現。實數編碼遺傳算法除了具有二進制編碼遺傳算法的所有特點，如：簡單、通用、魯棒性強、適于并行分布處理等之外，在算法的收斂性方面還有以下優勢[16]：

1）直接使用實數作為染色體參與遺傳操作，無需特定的編碼與解碼過程，因此降低了算法實現的復雜度，提高了算法的執行效率，尤其是當處理大規模復雜問題、高維數值優化問題或子目標個數較多的多目標優化問題時，實數編碼遺傳算法的效率更能得到體現。

2）用實數編碼可以消除二進制編碼存在的海明懸崖（Hamming cliffs）問題。

3）實數編碼遺傳算法中可以利用連續變量函數的漸變性（Graduality）。這里的“漸變性”是指變量值的微小變化所引起的對應函數值的變化也是微小的，由于這一特點，使實數編碼遺傳算法具有較強的局部調節功能，例如實數編碼遺傳算法的非一致變異算子（Non uniform mutation）相比二進制編碼遺傳算法的變異算子，能更好地實現種群的局部調節，從而更有利于逼近最優解。

4）在染色體長度一定的條件下，實數編碼遺傳算法具有比二進制編碼遺傳算法更大的搜索空間，甚至是無窮搜索空間，而不會影響其搜索精度，但在二進制編碼遺傳算法中，由于其本質是將一切尋優問題均轉化為組合優化問題進行離散尋優，且由于染色體長度的限制，二進制染色體所能表達的個體數是有限的（等價于在問題的解空間所能遍歷的點是有限個），如果擴大搜索空間，個體間的距離將被拉大，導致種群空間里個體分布的稀疏性，從而降低搜索精度，不利于獲取全局最優解，尤其對于欺騙問題（Deceptive problem）更是如此。因此，實數編碼遺傳算法比二進制編碼遺傳算法具有更好的全局收斂性。

5）對于具有非平凡約束條件的問題，實數編碼遺傳算法更易吸取問題域知識，指導種群朝正確的搜索方向進化。

6）實數編碼遺傳算法繁殖新個體的方式更加靈活。對于二進制編碼遺傳算法，由于編碼的限制，可供使用的交叉和變異算子的種類十分有限，而實數編碼遺傳算法可使用的交叉和變異算子則相對豐富，因而實數編碼遺傳算法在尋優時能夠在解空間中進行更好的探索和開發。

3.4 并行遺傳算法（Parallel Genetic Algorithm—PGA）的全局收斂性

在求解大規模甚至超大規模問題時，采用并行遺傳算法（PGA）是一種行之有效的策略，能獲得較高的計算效率。并行遺傳算法主要分為三種類型[26]，其收斂性各有特點，詳細分析如下：

1）主從式并行模型

這種并行模型由一個主處理器和若干個從處理器構成，主處理器的工作是監控整個染色體種群，并基于全局統計執行操作；各個從處理器接受來自主處理器的個體然后進行重組、交叉、變異，產生新一代個體，并計算適應度，再把計算結果回傳給主處理器。由于存在主處理機忙而從處理機空閑的情況，而且從處理機計算完成后要向主處理機發送結果，造成瓶頸和通信延遲，從而導致效率的低下，在很大程度上限制了此類模型的應用。如果個體適應度評價很費時，并且在時間上遠遠超過通信時間，主從式并行遺傳算法將能夠獲得很高的效率。

2）粗粒度并行模型

粗粒度并行遺傳算法模型將種群劃分為多個子種群，并分配給不同的處理器，每個處理器相互獨立并發運行一個進化過程。為了減少通信量，進化若干代后通信一次，互相傳遞最佳個體或以一定比例交換個體。雖然最佳個體的多次遷移會造成一定的通信開銷，但正是由于粗粒度并行遺傳算法允許子種群之間根據預定的通訊拓撲關系按一定比例交換個體，通過新個體的加入，增加了個體的差異，維持了種群的多樣性，并且每個子種群同時搜索種群空間的不同區域，提高了全局搜索能力，從而有利于避免早熟收斂現象。粗粒度并行遺傳算法模型是目前應用最為廣泛的一種并行遺傳算法，一方面是由于它容易實現，只需要在串行遺傳算法中增加個體遷移子例程，在并行計算機的節點上各自運行一個算法的副本，定期交換最佳個體即可；另一方面是它容易模擬，即使在沒有并行計算機的情況下，也可在串行機網絡或者單臺串行機上執行粗粒度并行遺傳算法，有較高的加速比。雖然在串行計算機上實現的粗粒度并行遺傳算法不具有并行計算的速度優勢，但仍具有避免早熟收斂的特性。因此，粗粒度并行遺傳算法作為遺傳算法的一種特殊變形，能有效克服遺傳算法在全局搜索能力方面的固有不足。

3）細粒度并行模型

細粒度并行模型又稱為鄰域模型，是將遺傳算法與細胞自動機結合起來的模型。細粒度模型可以看作是一種細胞狀的自動機網絡，群體劃分為多個小的子群體，分配到給定空間環境（一般是排列成環形陣列的二維網格的形狀，以防止邊界效應的問題發生）中的處理機中（在理想情況下每個處理機單獨處理一個個體，稱為細胞）。網格中的鄰域關系限定了個體空間上的關系，遺傳操作被看作隨機的局部更新規則，這樣模型是完全分布而無需任何全局控制結構的。對每個細胞而言，選擇僅僅是在賦給該細胞的個體及其鄰域的個體上進行，交叉也僅交配鄰近的個體。通過比較細粒度模型與標準遺傳算法，可以發現細粒度模型能提供對搜索空間更徹底的搜索，因為它的局部選擇機制減輕了選擇壓力。對困難的問題，細粒度遺傳算法比標準算法的求解效果好，也更不容易陷人局部最優。考慮到參數的設置，細粒度遺傳算法的魯棒性較好，但是細粒度并行模型要求有盡可能多的處理機，所以此類模型的應用范圍不廣，一般只運行于大規模系統。細粒度模型和粗粒度模型的根本區別就是算法框架中的結構的控制次數的不同，前者是群體中個體的個數，而后者則是子群體規模，即處理器的個數。

3.5 小生境遺傳算法（Niche Genetic Algorithm—NGA）的全局收斂性

在生物學中 ，小生境 （Niche）是指特定的生存環境。生物在其進化過程中 ，一般總是與自己相同的物種生活在一起，這就是一種小生境的自然現象。在遺傳算法中引進小生境的概念 ，讓種群中的個體在不同特定的生存環境中進化 ，而不是全部聚集在一種環境中，這樣可以使算法在整個解空間中搜索 ，以找到更多的最優個體，避免了在進化后期適應度高的個體大量繁殖 ，充斥整個解空間 ，導致算法停止在局部最優解上。

遺傳算法中模擬小生境的方法主要有以下幾種[27]：

1）基于預選擇的小生境實現方法 其基本思想是：僅當新產生子代個體的適應度超過其父代個體時 ，所產生出的子代個體才能替代其父代個體而遺傳到下一代群體中，否則父代個體仍保留在下一代群體中。由于子代和父代個體之間的編碼結構有相似性 ，所以該方法替代掉的只是一些編碼結構相似的個體 ，故它能有效地維持種群多樣性 ，并造就小生境的生存環境，從而有利于全局收斂。

2）基于排擠的小生境實現方法 其基本思想是：設置一個排擠因子CF，由群體中隨機選擇的 1/CF個個體組成排擠成員，排擠掉一些與其相類似的個體。這里個體之間的相似性可用個體編碼串之間的海明距離來度量。隨著排擠過程的進行 ，群體中的個體逐漸被分類 ，從而形成各個小的生存環境即小生境 ，并維持了群體的多樣性。

3）基于共享（Sharing）函數的小生境實現方法 其基本思想是：通過反映個體之間相似程度的共享函數來調整群體中各個個體的適應度，從而在以后的進化過程中 ，能夠依據調整后的新適應度來進行選擇運算。這種調整適應度的方法能夠限制群體內個別個體的大量增加 ，以維護群體的多樣性 ，并形成了一種小生境的進化環境。

4）基于淘汰相似結構機制的小生境實現方法 該方法是在標準遺傳算法的基礎上增加小生境淘汰運算 ，通過引入罰函數的方法來調整個體的適應度 ，淘汰結構相似的個體 ，使得各個個體之間保持一定的距離 ，從而造就了一種小生境的進化環境 ，維護了群體的多樣性 ，提高了全局搜索能力。

小生境遺傳算法具有更強的全局搜索能力和更高的收斂速度 ，能夠高效地尋找到多個全局最優值 ，是一種尋優能力、搜索效率和全局收斂概率更高的優化算法 ，其綜合性能比標準遺傳算法有顯著提高。

4 遺傳算法收斂性研究的主要發展方向

遺傳算法收斂性研究的主要發展方向包括以下幾個方面：

1）遺傳算法的收斂性與遺傳算子的內在關系研究。主要包括遺傳算子的操作方式對遺傳算法收斂性的影響機制研究、影響結果的定量刻畫與描述，如：對遺傳算法收斂速度的影響、對遺傳算法收斂到全局最優解的影響等。

2）平衡遺傳算法的收斂性與時間復雜性的研究。收斂性與時間復雜性平衡是指在保證遺傳算法收斂的同時預防過度進化，防止出現“漫游”（Roam）現象。在遺傳算法的實際運行中，為提高遺傳算法的收斂性（收斂到全局最優解的概率），往往以增加進化時間為代價，而這在求解大規模問題時是難以接受的。

3）遺傳算法最終收斂到全局最優解的時間復雜度研究。主要是遺傳算法收斂速度的定量估計和提高收斂速度的方法研究。除有關標準遺傳算法時間復雜度的研究外，還包括各種改進遺傳算法時間復雜度的研究。

4）在提高遺傳算法收斂性的同時預防早熟收斂的研究。為提高遺傳算法的收斂速度，降低其時間復雜性，在遺傳算法的實際運行中，往往采用控制參數選擇（如：提高遺傳算法的交叉概率）和改進遺傳操作的方法，但這容易導致“早熟”（Premature）現象的發生，從而降低遺傳算法收斂到全局最優解的概率，這一矛盾至今依然存在。

5）混合遺傳算法的收斂性研究。許多研究表明，采用混合模型可有效提高遺傳算法的局部搜索能力，從而進一步改善其收斂速度和解的品質。通過對混合遺傳算法收斂性的研究，不僅可以增強現有遺傳算法的實用性與可靠性，而且可為正在蓬勃發展的混合遺傳算法提供一定的理論支撐。而關于混合遺傳算法的收斂性分析，卻更加困難。

6）構造高效且全局收斂遺傳算法的方法研究。對遺傳算法的收斂性進行研究的最終目的是構造高效、收斂的遺傳算法，這直接關系到遺傳算法的實際應用價值。要構造高效、收斂的遺傳算法，必須充分運用已有的收斂性分析的研究成果，從算法結構、控制參數選擇、遺傳算子的操作方式等方面進行綜合設計，其中還存在許多尚未解決的問題，如：如何利用遺傳算法的收斂性構造合理的停機準則。

參考文獻

[1] GOLDBERG D E. Genetic algorithm in Search， optimization and machine learning[M]. Reading， AddisonWesley，1989.

[2] MICHALEWICZ Z. Genetic Algorithms+Data Structure=Evolution Program[M]. 3rd edition. Berlin：Springer—Verlag，1996.

[3] BACK T，FORGEL D，Michalewicz Zeds. Handbooks of Evolutionary computation[M]. New York：Oxford university Press，1997.

[4] SANKAR K.Pal，Fellew and C.A.Murthy. GA for generation of class boundaries[J]. IEEE Trans on SMC-Part B：cybemetics，1998，28（6）：816-828.

[5] POTTS JC，et al. The Development and Evaluation of an Improved Genetic Algorithm Based on Migration and Artificial Selection[J]. IEEE Trans on SMC，1994，24（1）：73-86.

[6] 潘正君. 演化計算[M]. 北京：清華大學出版社，1998.

[7] 王嵐. 基于自適應交叉和變異概率的遺傳算法收斂性研究[J]. 云南師范大學學報，2010，30（3）：32-37.

[8] 明亮，王宇平. 關于一類遺傳算法收斂速度的研究[J]. 計算數學，2007，29（1）：15-26.

[9] 應偉勤，李元香. 熱力學遺傳算法計算效率的改進[J]. 軟件學報，2008，19（7）：1613-1622

[10]喻壽益，鄺溯瓊. 保留精英遺傳算法收斂性和收斂速度的鞅方法分析[J]. 控制理論與應用，2010，27（7）：843-848.

[11]Xiao Fang Qi，FRARCESCO P. Theoretical Analysis of Evolutionary Algorithms with on Infinite Population Size in Continuous Space， Part I and PartII： Basic Properties of Selection and Mutation[J]. IEEE Trans on neural network， 1994，5 （1）：102-129.

[12]明亮. 遺傳算法的模式理論及收斂理論[D]. 西安：西安電子科技大學博士學位論文，2006.

[13]曹建文. 遺傳算法收斂性問題研究[J].中南林業科技大學學報，2008，28（3）：163-167.

[14]RUDOLPH G. Convergence Analysis of Canonical GA[J]. IEEE Trans on Neural Networks，1994，5（1）：96-101.

[15]陳國良. 遺傳算法及其應用[M]. 北京：人民郵電出版社，1996.

[16]田小梅，龔靜. 實數編碼遺傳算法的評述[J]. 湖南環境生物職業技術學院學報，2006，11（1）：25-31.

[17]YAO X. A Review of Evolutionary Artificial Neural Networks[J]. Int.J.Intelligent Systems， 1993，8（6）：539-567.

[18]CHIPPERFIELD A J. Multiobjective turbine engine controller design using GA[J]. IEEE trans. Int Electron，1996，4（3）：583-589.

[19]CARLOS M. Multiobjective optimization and multiple constraint handling with evolutionary algorithm[J]. IEEE Trans on SMC，1998，28（1）：26-34.

[20]GLOVFER F. GA and tabu search： hybrids for optimization[J]. Computer Ops. Res.1995，22（1）：111-134.

[21]肖宏峰，譚冠政. 基于單純形的小生境混合遺傳算法[J]. 小型微型計算機系統，2008，29（9）：1719-1725.

[22]KRISTISSON K，DUMENT G A. System identification and control using Genetic Algorithms[J]. IEEE Trans on SMC.1992，22（5）：1033-1046.

[23]FOGEL D.B. A comparison of evolutionary Programming and genetic algorithms on selected constrained Optimization Problems[J]. Simulation，1995， 64 （6）：397-406.

[24]HOMAIFER A，et al. Constrained Optimization Via Genetic Algorithms[J]. Simulation， 1994，62（4）：242-254.

[25]SRINIVAS M，PATNAIK LM. Adaptive Probabilities of Crossover and Mutation in GA[J]. IEEE Trans on SMC，1994，24（4）：656-667.

[26]張旭風，王紀川，牟莉. 并行遺傳算法收斂性分析及優化[J]. 西安工程科技學院學報，2007，21（5）：657-660.

[27]朱筱蓉，張興華. 基于小生境遺傳算法的多峰函數全局優化研究[J]. 南京工業大學學報，2006，28（3）：39-43.