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

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

概念和定義：

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

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

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

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

框架與術(shù)語：

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

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

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

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

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

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

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

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

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

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

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

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