導讀：人們一提到遺傳算法（GA），就會聯(lián)想到達爾文的生物進化論。遺傳算法（GA）是一類借鑒生物界的進化規(guī)律演化而來的隨機化搜索方法。

今天我們重點探討一下遺傳算法（GA）。＾＿＾

人們一提到遺傳算法（GA），就會聯(lián)想到達爾文的生物進化論。遺傳算法（GA）是一類借鑒生物界的進化規(guī)律演化而來的隨機化搜索方法。它是由美國的J．Holland教授1975年首先提出。目前，遺傳算法（GA）已成為進化計算研究的一個重要分支。

遺傳算法（GeneTIcAlgorithm）是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的方法。

遺傳算法（GA）是從代表問題可能潛在的解集的一個種群（populaTIon）開始，而一個種群則由經(jīng)過基因（gene）編碼的一定數(shù)目的個體（individual）組成。每個個體實際上是染色體（chromosome）帶有特征的實體。染色體作為遺傳物質的主要載體，即多個基因的集合，其內部表現(xiàn)（即基因型）是某種基因組合，它決定了個體的形狀的外部表現(xiàn)。因此，在一開始需要實現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作。

由于仿照基因編碼的工作很復雜，往往進行簡化，初代種群產生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代（generaTIon）演化產生出越來越好的近似解，在每一代，根據(jù)問題域中個體的適應度（fitness）大小選擇（selecTIon）個體，并借助于自然遺傳學的遺傳算子（geneticoperators）進行組合交叉（crossover）和變異（mutation），產生出代表新的解集的種群。這個過程將導致種群像自然進化一樣的后生代種群比前代更加適應于環(huán)境，末代種群中的最優(yōu)個體經(jīng)過解碼（decoding），可以作為問題近似最優(yōu)解。

遺傳操作是模擬生物基因遺傳的做法。在遺傳算法中，通過編碼組成初始群體后，遺傳操作的任務就是對群體的個體按照它們對環(huán)境適應度（適應度評估）施加一定的操作，從而實現(xiàn)優(yōu)勝劣汰的進化過程。從優(yōu)化搜索的角度而言，遺傳操作可使問題的解，一代又一代地優(yōu)化，并逼近最優(yōu)解。

1）編碼—把問題空間的參數(shù)轉換成遺傳空間的由基因按一定結構組成的染色體或個體的操作過程。目前的幾種常用的編碼技術有二進制編碼，浮點數(shù)編碼，字符編碼，變成編碼等，最常用的是二進制編碼。評估編碼策略有3個規(guī)范：a）完備性（completeness）；b）健全性（soundness）；c）非冗余性（nonredundancy）。

2）適應度函數(shù)—表示某一個體對環(huán)境的適應能力，也表示該個體繁殖后代的能力。遺傳算法的適應度函數(shù)也叫評價函數(shù)，是用來判斷群體中的個體的優(yōu)劣程度的指標，它是根據(jù)所求問題的目標函數(shù)來進行評估的。遺傳算法在搜索進化過程中一般不需要其他外部信息，僅用評估函數(shù)來評估個體或解的優(yōu)劣，并作為以后遺傳操作的依據(jù)。適應度函數(shù)設計直接影響到遺傳算法的性能，因此適應度函數(shù)的設計需要滿足以下條件：a）單值、連續(xù)、非負、最大化；b） 合理、一致性；c）計算量小；d）通用性強。

3）初始群體選取—初始群體中的個體是隨機產生的。初始群體的設定可采取如下策略：a）根據(jù)問題固有知識，設法把握最優(yōu)解所占空間在整個問題空間中的分布范圍，然后，在此分布范圍內設定初始群體。b）先隨機生成一定數(shù)目的個體，然后從中挑出最好的個體加到初始群體中。這種過程不斷迭代，直到初始群體中個體數(shù)達到了預先確定的規(guī)模。

4）染色體—又叫做基因型個體（individuals），一定數(shù)量的個體組成了群體（population），群體中個體的數(shù)量叫做群體大小。

5）基因—串中的元素，基因用于表示個體的特征。

6）基因位置—簡稱基因位，在算法中表示一個基因在串中的位置稱為基因位置（Gene Position）。

7）特征值—在用串表示整數(shù)時，基因的特征值與二進制數(shù)的權一致。

8）選擇—從群體中選擇優(yōu)勝的個體，淘汰劣質個體的操作。選擇算子有時又稱為再生算子（reproduction operator）。選擇的目的是把優(yōu)化的個體（或解）直接遺傳到下一代或通過配對交叉產生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的。目前常用的選擇算子有：適應度比例方法、隨機遍歷抽樣法、局部選擇法、錦標賽選擇和輪盤賭選擇法（最簡單、最常用）等。

9）交叉—把兩個父代個體的部分結構加以替換重組而生成新個體的操作。遺傳算法中起核心作用的是遺傳操作的交叉算子。交叉算子根據(jù)交叉率將種群中的兩個個體隨機地交換某些基因，能夠產生新的基因組合，期望將有益基因組合在一起。通過交叉，遺傳算法的搜索能力得以飛躍提高。最常用的交叉算子為單點交叉（one－point crossover）。

10）變異—變異算子是對群體中的個體串的某些基因座上的基因值作變動。利用變異算子的局部隨機搜索能力可以加速向最優(yōu)解收斂；利用變異算子可維持群體多樣性，防止出現(xiàn)未成熟收斂現(xiàn)象。依據(jù)個體編碼表示方法的不同，可以有：a）實值變異；b）二進制變異。變異率的選取一般受種群大小、染色體長度等因素的影響，通常選取很小的值。

11）終止條件—當最優(yōu)個體的適應度達到給定的閾值，或者最優(yōu)個體的適應度和群體適應度不再上升時，或者迭代次數(shù)達到預設的代數(shù)時，算法終止。

遺傳操作進行的是高效有向的搜索。遺傳操作包括3個基本遺傳算子（genetic operator）：選擇（selection）；交叉（crossover）；變異（mutation）。遺傳操作的效果和3個遺傳算子所取的操作概率、編碼方法、群體大小、初始群體以及適應度函數(shù)的設定密切相關。3個基本遺傳算子的作用：a）選擇的作用：優(yōu)勝劣汰，適者生存；b）交叉的作用：保證種群的穩(wěn)定性，朝著最優(yōu)解的方向進化；c）變異的作用：保證種群的多樣性，避免交叉可能產生的局部收斂。