遺傳算法綜述

摘要：本文主要回顧了遺傳算法的發展歷程，并對遺傳算法的基本原理及特點作了簡要闡述。進一步指出了遺傳算法存在的問題及相應的改進措施，討論了遺傳算法在實際中的應用。

關鍵詞：遺傳算法

選擇

交叉

變異

適應度函數

中圖分類號：TF273

文獻標識碼：A

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

遺傳算法廣泛應用于自動控制、計算科學、模式識別、工程設計、智能故障診斷管理科學和社會科學領域，適用于解決復雜的非線性和多維空間尋優問題。

1遺傳算法的特點

遺傳算法作為具有系統優化、適應和學習的高性能計算和建模方法的研究漸趨成熟。遺傳算法具有進化計算的所有特征，同時又具有自身的特點：

(1)搜索過程既不受優化函數的連續性約束，也沒有優化函數導數必須存在的要求。

(2)遺傳算法采用多點搜索或者說是群體搜索，具有很高的隱含并行性，因而可以提高計算速度。

(3)遺傳算法是一種自適應搜索技術，其選擇、交叉、變異等運算都是以一種概率方式來進行，從而增加了搜索過程的靈活性，具有較好的全局優化求解能力。

(4)遺傳算法直接以目標函數值為搜索信息，對函數的性態無要求。具有較好的普適性和易擴充性。

(5)遺傳算法更適合大規模復雜問題的優化。

2遺傳算法的基本原理

GA研究的問題是搜索候選假設空間并確定“最佳假設”。在GA中，“最佳假設”被定義為是使適應度最優的假設，適應度是為當前問題預先定義的數字度量。

2，1遺傳算法的原型

John Holland教授通過模擬生物進化過程設計了最初的遺傳算法，稱之為標準遺傳算法。標準遺傳算法給出了遺傳算法的基本框架，以后對于遺傳算法的改進，都是基于此種算法。盡管遺傳算法的實現在細節上有所不同，但都具有以下的共同結構：算法迭代更新一個假設池，這個假設池稱為群體。在每一次的迭代中，根據適應度函數評估群體中的所有成員，然后從當前群體中用概率方法選取適應度最高的個體產生新一代群體。在這些選中的個體中，一部分保持原樣地進入下一代群體，其他的被用作產生后代個體的基礎，其中應用象交叉和變異這樣的遺傳方法。標準遺傳算法的流程如表1。

2，2選擇算子

選擇是用來確定交叉個體，以及被選個體將產生多少個子代個體。常用的方法有：

(1)適應度比例方法，各個個體的選擇概率和其適應度值成比例。

(2)最佳個體保存方法，把群體中適應度最高的個體不進行配對交叉而直接復制到下一代中。

(3)排序選擇方法，指在計算每個個體的適應度后，根據適應度大小對群體中個體排序，并把事先設計好的概率表按序分配給個體，作為各自的選擇概率。所有個體按適應度排序，而選擇概率和適應度無直接關系而僅與序號有關。

(4)聯賽選擇方法，其操作思想是從群體中任意選擇一定數目的個體，其中適應度最高的個體保存到下一代。并反復執行，直到保存到的個體數達到預先設定的數目為止。

2，3交叉算子

交叉指把兩個父代個體的部分結構加以替換重組而生成新個體的操作。交叉操作的作用是組合出新的個體，是GA區別于其它進化算法的重要特征，遺傳算法中起核心作用的是遺傳操作。各種交叉算子都包括兩個基本內容：

(1)從由選擇操作形成的群體中，對個體隨機配對并按預先設定的交叉概率來決定每對是否需要進行交叉操作。

(2)設定配對個體的交叉點，并對這些點前后的配對個體的部分結構進行相互交換。常用的交叉操作方法有一點交叉、二點交叉、一致交叉、二維交叉、樹結構交叉等等。

2，4變異算子

變異即對群體中個體串的某些基因座上的基因值作變動。變異的目的有兩個：

(1)使遺傳算法具有局部的隨機搜索能力。

(2)保持群體的多樣性。

變異算子的操作一般分兩步：

(1)在群體中所有個體的碼串范圍內隨機確定基因座。

(2)以事先設定的變異概率來對這些基因座的基因值進行變異。變異算子有很多方式，如基本變異算子、逆轉算子、自適應變異算子等等。

3遺傳算法存在的問題

(1)編碼表示：Holland在運用模式定理分析編碼機制時建議使用二進制編碼。但二進制編碼不能直接反映問題的固有結構、精度不高、個體長度大和占用計算機內存多。

解決這個問題的措施有：

①動態編碼即在保持串長不變的前提下減小搜索區域，當算法收斂到某局部最優時增加搜索的精度，從而使得在全局最優點附近可以進行更精確的搜索。

②對于問題的變量是實向量的情形，可以直接采用實數進行編碼，便于引入與問題領域相關的啟發式信息以增加算法的搜索能力。

③復數編碼本是為了描述和解決二維問題，還可以推廣到多維問題的描述中。

(2)適應度函數：適應度函數是用來區分群體中個體好壞的標準，選擇的好壞直接影響算法的優劣，選擇的不好容易引起兩種不利于優化的現象：

①異常個體引起早熟收斂，影響求得全局最優解。這種現象常出現在小規模群體中。

②個體差距不大引起搜索成為隨機漫游，特別是平均適應度已接近最佳適應度時，最佳個體與其他許多個體在選擇過程中就會有大體相等的選擇機會，影響求得最優解。

(3)選擇策略：優勝劣汰的選擇機制使得適應值大的個體有較大的存活機會，不同的選擇策略對算法性能有較大的影響。輪盤賭法是使用最多的選擇策略，但這種策略可能會產生較大的抽樣誤差，對此提出了很多的改進方法，如繁殖池選擇、非線性排名選擇、基于局部競爭機制的選擇等。

(4)控制參數：群體大小、交換概率、變異概率等這些參數對遺傳算法性能影響較大，會影響算法的全局最優性和收斂性。Davis提出自適應算子概率的方法，用自適應機制把算子概率與算子產生的個體適應性結合。而且高適應性值被分配高算子概率這種方法較好地解決了這一問題。