遺傳算法的應用及研究分析

摘要：在介紹遺傳算法的基本原理與方法的基礎上，分析了遺傳算法相對于其它算法的優越性和存在的問題以及遺傳算法的主要應用和研究發展方向。

關鍵詞：遺傳算法

智能控制

算法優化

中圖分類號：TP11

文獻標識碼：A

文章編號：1002-2422(2010)03-0113-03

1遺傳算法的基本原理與方法

1，1編碼

編碼是把一個問題的可行解從其解空間轉換到GA所能處理的搜索空間的轉換方法。而解碼是由GA解空間向問題空間的轉換。編碼機制直接影響著算法的整體性能，也決定了種群初始化和各種遺傳算子的設計等各種過程。常用的編碼方案有：二進制編碼、Gray編碼和實數編碼等。

1，2種群的初始化

種群的初始化是指如何生成第一代初始種群。對于二進制編碼機制，初始化就是生成多個二進制數串；對于實數編碼機制，初始化是指生成多個實數數串。

1，3適應度函數

適應度是用來衡量群體中各個個體在優化計算中能達到或接近于或有助于找到最優解的優良程度。適應度較高的個體遺傳到下一代的概率就較大：反之遺傳到下一代的概率就相對較小。度量個體適應度的函數稱為適應度函數，是根據目標函數確定的，用于區分群體中個體好壞的標準，是算法演化過程的驅動力。

1，4選擇算子

選擇算子是從一個舊種群選擇生命力頑強的個體位串進行復制，從而產生新種群的過程。不同的選擇操作會導致不同的選擇效果，較大的選擇壓力將會使當前種群中的最優個體具有較高的復制數目，算法會以較快的速度收斂，容易出現“早熟”問題。相反，較小的選擇壓力能使種群的保持多樣性，有利于跳出局部最優，收斂于全局最優點，但缺點是收斂速度慢，效率低下。常用的選擇算子有：輪盤賭選擇、基于排序的選擇、局部競爭選擇、最佳個體保存選擇和Boltzmann選擇等。

1，5交叉算子

交叉算子是指兩個相互配對的染色體按照某種方式相互交換自身的部分基因片，從而構成兩個新個體的過程。交叉算子不僅要考慮生成更多不同的個體，保持種群的多樣性；還要避免破壞種群中的優良個體，加快種群的收斂速度，才能使種群的多樣性和收斂性達到和諧的統一。常用的交叉算子有：單點交叉、多點交叉、均勻交叉和算術交叉等。

1，6變異算子

變異是指父代染色體中的某些基因片，以相對較小的概率發生隨機改變的操作過程。變異的概率決定了種群中個體發生變異的機會大小，如果制定過高，容易破壞種群中已有的優良個體結構；如果制定過低，則產生新個體的速度慢，收斂速度慢，甚至可能陷入局部最優。常用的變異算子有：倒位變異、交換變異和插入變異等。研究表明，將多種變異算子在交叉使用或者按照一定的概率進行分配使用，會帶來較好的效果。

2 GA遺傳算法的特點

2，1遺傳算法相對于其它算法的優越性

(1)GA從問題的初始解集開始搜索，而不是從單個解開始，覆蓋面大，有利于全局擇優從而有效地避免局部最優解的干擾。

(2)GA不是對問題的待優化參數本身進行操作，而是通過由這些參數所編碼形成的染色體進行交叉，變異和選擇等操作，參與操作的信息量大，速度快，效果好，比較容易獲得全局最優或逼近全局最優。

(3)GA求解時使用特定問題的信息極少，容易形成通用算法程序，對于有待優化的函數數學限制較少，既不要求可導可微，也不要求函數具有連續性，通用性好，魯棒性強。

(4)GA通過選擇、交叉、變異操作能迅速排除與最優解相差極大的串，這是一個強烈的濾波過程，也是一個并行濾波機制，有極強的容錯能力。

(5)GA中的選擇、交叉和變異都是隨機操作，選擇體現了向最優解的迫近，交叉體現了最優解的產生，變異則體現了全局最優解的覆蓋。

(6)GA具有隱含的并行性，實現簡單，效果良好。

2，2遺傳算法存在的問題

(1)GA在全局最優的搜索上效果良好，而在局部最優的搜索上存在不足。在算法進行的前期，搜索效果良好，而在算法進行的后期，搜索速度緩慢。即使在逼近全局最優時，要獲得全局最優解仍要花費很大的搜索代價。

(2)GA雖然實現簡單，但實現的效果很大程度上取決問題的表示，種群的規模，最大遺傳代數，遺傳算子的選擇，交叉變異概率等參數，如果設置不好，類似以隨機搜索算法。而這些參數又無規律可循，要通過大量的實驗來獲取，參數的選取不具有通用性，當問題本身發生改變時，要重新指定參數，將要花費很大代價。

(3)GA的“早熟”問題，是指在算法早期，種群中出現了超級個體，該個體的適應值大大超過了當前種群的平均個體適應值∑f_i／N，使算法較早收斂于局部最優點，而非全局最優。特別是到了算法進行的后期，超級個體在種群中占據了絕大多數，這時，傳統的交叉操作對于相同的超級個體已經不起作用，而變異操作雖然能夠為算法補充新的個體，但變異在遺傳中畢竟是小概率事件。所以，必須在其他方面對算法進行改進，提高算法的抗干擾能力。

(4)GA對算法的精度、可信度、計算復雜性等方面，還沒有有效的定量分析方法。

3遺傳算法的應用

GA由于具有魯棒性強，實現簡單，對問題依賴性小等優點，為求解復雜系統優化問題提供了通用框架，下面是一些主要應用領域：

(1)函數優化：是GA的經典應用領域，也是對GA進行性能評價的常用算例，對于一些非線性、多模型、多目標的函數優化問題，用其他優化方法較難求解，GA卻可以得到較好的結果。

(2)組合優化：隨問題規模的擴大，搜索空間急劇擴大，對這類復雜問題，實踐證明，GA對于組合優化的NP完全問題非常有效。

(3)生產調度問題：GA已成為解決復雜調度問題的有效工具，在單件生產車間調度、流水線生產車間調度、生產規模、人物分配等方面都得到了有效的應用。

(4)自動控制：GA在自動控制領域中的應用日益增加，并顯示了良好的效果。如在參數辨識、人工神經網絡的結構優化設計和權值學習，都顯示了GA的應用優勢。

(5)機器人智能控制：GA是源自于對人工自適應系統的研究，已經在移動機器人路徑規劃、關節機器人運動軌跡規律、機器人逆運動學求解、細胞機器人的結構優化和行動協調等方面得到研究和應用。

(6)圖像處理和模式識別：在圖像處理過程中，如掃描、特征提取、圖像分割等不可避免的會產生一些誤差。目前，GA已在圖像恢復、圖像邊緣特征提取、幾何形狀識別等方面得到了應用。

(7)人工生命：基于GA的進化模型是研究人工生命現象的重要理論基礎，已在其進化模型、學習模型、行為模型等方面得到應用。

(8)遺傳程序設計：Koza發展了遺傳程序設計，基本思想是：采用樹型結構表示計算機程序，運用遺傳算法的思想，通過自動生成計算機序來解決問題。雖然該理論尚未成熟，應用也有些限制，但已成功地應用于人工智能、機器學習等領域。

(9)機器學習：基于GA的機器學習、特別分類器系統，在調整人工神經網絡的連接權、神經網絡結構的優化設計、和多機器人路徑規劃系統中得到了成功的應用。

4遺傳算法的研究分析

4，1算法自身的改進

GA有著自身所特有的巨大優勢，但在數學基礎、算法結構、實現機理以及算法組成等方面都還存在著不足，為了改善算法的求解性能，擴大算法的應用范圍，必須致力于算法自身的改進的研究工作。

4，2參數的動態自適應

GA中的參數包括種群規模、遺傳代數、交叉概率和變異概率等，參數設置的好壞直接影響到算法性能的優劣。如何對這些參數進行配置，一直是研究的重點。參考文獻中不僅從理論上證明了自然數編碼的前提下存在種群的最優種群規模，而且給出了如何計算最優種群規模的方法。Srlnivaszai提出了對交叉概率和變異概率進行算法動態自適應的思想。Fogarry從整數編碼的角度研究了變異概率對算法性能的影響。

4，3小生境技術的遺傳算法

小生境技術是指將每代種群中的個體按照適應度的大小劃分為多個類，在每個類中選取適應度較大的個體組成一個新的種群，通過這些種群之間的共享機制來完成種群間優秀個體的交流共享，從而達到尋找最優解的搜索過程。不僅能夠保持種群的多樣性，而且對于算法的全局尋優能力和算法的收斂性都能起到良好的改善作用。

4，4混合遺傳算法

GA在全局最優解的搜索上有其獨特的高效性，但局部搜索能力不足。而一些常用的算法，如貪婪算法、模擬退火算法、爬山法等，局部搜索能力很強，通過融合這些算法的優點，彌補GA自身的不足的混合式算法，成為提高算法的效率和求解質量的一個有效途徑。

4，5并行遺傳算法

由于GA存在的隱式并行性的特性，可以用并行技術來提高效率。并行GA主要有主從式模型，粗力度模型和細粒度模型三種主要框架。在主從式模型中，主處理器控制整個GA的運行，其他的從處理器則進行個體的初始化，交叉、變異和選擇操作，然后由主處理器進行總體調控。在粗細粒度模型中，每個處理器進行整體算法的獨立操作，然后備個處理器之間進行個體交流。在細粒度模型中，一個處理器只能夠與其周圍的處理器之間進行個體交換。在并行算法中，處理器之間的個體交換稱之為“遷移”，是并行GA中獨特的操作算子。通過遷移算子，可實現最佳個體在不同子種群之間的流動，從而提高各個子種群的之間，加快子種群的收斂。

5結束語

遺傳算法經過幾十年的發展，其應用從工程科學到社會科學的諸多領域，今后，拓展更加多樣的應用領域將是遺傳算法發展的主流。