人工智能之遺傳算法(GA),搜索最優(yōu)解的方法

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

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

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

概念和定義：

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

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

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

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

框架與術(shù)語：

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

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

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

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

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

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

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

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

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

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

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

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