人工智慧–遺傳演算法

人工智慧之遺傳演算法(GA)

前言: 人工智慧之機器學習有關演算法內容，請參見公眾號「科技優化生活」之前相關文章。

今天我們重點探討一下遺傳演算法（GA）。^_^

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

概念和定義：

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

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

由於仿照基因編碼的工作很複雜，往往進行簡化，初代種群產生之後，按照適者生存和優勝劣汰的原理，逐代（generation）演化產生出越來越好的近似解，在每一代，根據問題域中個體的適應度（fitness）大小選擇（selection）個體，並藉助於自然遺傳學的遺傳運算元（geneticoperators）進行組合交叉（crossover）和變異（mutation），產生出代表新的解集的種群。這個過程將導致種群像自然進化一樣的後生代種群比前代更加適應於環境，末代種群中的最優個體經過解碼（decoding），可以作為問題近似最優解。

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

框架與術語：

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

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

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

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

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

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

7）特徵值—在用串表示整數時，基因的特徵值與二進位數的權一致。

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

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

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

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

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

遺傳演算法中，交叉運算元因其全局搜索能力而作為主要運算元，變異運算元因其局部搜索能力而作為輔助運算元。遺傳演算法通過交叉和變異這對相互配合又相互競爭的操作而使其具備兼顧全局和局部的均衡搜索能力。如何有效地配合使用交叉和變異操作，是目前遺傳演算法的一個重要研究內容。

運算過程：

1）初始化：設置進化代數計數器t=0，設置最大進化代數T，隨機生成M個個體作為初始群體P(0)。

2）個體評價：計算群體P(t)中各個個體的適應度。

3）選擇運算:將選擇運算元作用於群體。選擇的目的是把優化的個體直接遺傳到下一代或通過配對交叉產生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的。

4）交叉運算：將交叉運算元作用於群體。遺傳演算法中交叉運算元起核心作用。

5）變異運算：將變異運算元作用於群體。對群體中的個體串的某些基因座上的基因值作變動。群體P(t)經過選擇、交叉、變異運算之後得到下一代群體P(t+1)。

6）終止條件判斷:若t=T,則以進化過程中所得到的具有最大適應度個體作為最優解輸出，終止計算。

可把遺傳演算法的運算過程看作是一個在多元函數裡面求最優解的過程。如下圖所示，這個多維曲面裡面有數不清的「山峰」，而這些「山峰」所對應的就是局部最優解。而其中也會有一個「山峰」的海拔最高的，那麼這個就是全局最優解。而遺傳演算法的任務就是盡量爬到最高峰，而不是陷落在一些小山峰。

演算法優點：

1）遺傳演算法從問題解的串集開始搜索，而不是從單個解開始。這是遺傳演算法與傳統優化演算法的極大區別。遺傳演算法從串集開始搜索，覆蓋面大，利於全局擇優。

2）遺傳演算法同時處理群體中的多個個體，即對搜索空間中的多個解進行評估，減少了陷入局部最優解的風險，同時演算法本身易於實現並行化。

3）遺傳演算法不用搜索空間的知識或其它輔助信息，而僅用適應度函數值來評估個體，在此基礎上進行遺傳操作。適應度函數不僅不受連續可微的約束，而且其定義域可以任意設定。這一特點使得遺傳演算法的應用範圍大大擴展。

4）遺傳演算法不是採用確定性規則，而是採用概率的變遷規則來指導它的搜索方向。

5）具有自組織、自適應和自學習性。遺傳演算法利用進化過程獲得的信息自行組織搜索時，適應度大的個體具有較高的生存概率，並獲得更適應環境的基因結構。

6）演算法本身也可以採用動態自適應技術，在進化過程中自動調整演算法控制參數和編碼精度，比如使用模糊自適應法。

簡而言之，主要優點是直接對結構對象進行操作，不存在求導和函數連續性的限定；具有內在的隱並行性和更好的全局尋優能力；採用概率化的尋優方法，能自動獲取和指導優化的搜索空間，自適應地調整搜索方向，不需要確定的規則。可以把搜索空間擴展到整個問題空間，因而具有全局優化性能。同時也縮短了整個搜尋額時間，整體上效率更高、結果更接近最優解。實現簡單，沒有複雜的數學計算。

演算法缺點：

1）遺傳演算法編碼和解碼比較複雜，在進化前需要做複雜的編碼工作，而在得到最優解後還要做複雜的解碼工作，比較繁瑣和複雜；

2）編碼不規範及編碼存在表示的不準確性，在遺傳操作過程中，遺傳演算法編、解碼不易掌控，容易出錯；

3）遺傳演算法對初始種群的選擇有一定的依賴性；

4）遺傳演算法通常的效率比其他傳統的優化方法低；

5）遺傳演算法在適應度函數選擇不當的情況下有可能收斂於局部最優，而不能達到全局最優；也容易過早收斂；

6）遺傳演算法對演算法的精度、可行度、計算複雜性等方面，還沒有有效的定量分析方法。

研究動向與應用前景：

遺傳演算法的應用研究已從初期的組合優化求解擴展到了許多更新、更工程化的應用方面。隨著應用領域的擴展，遺傳演算法的研究出現了幾個引人注目的新動向：

1）基於遺傳演算法的機器學習，這是把遺傳演算法從歷來離散的搜索空間的優化搜索演算法擴展到具有獨特的規則生成功能的機器學習演算法。這一新的學習機制對於解決人工智慧中知識獲取和知識優化精鍊的瓶頸難題帶來了希望。

2）遺傳演算法正日益和神經網路、模糊推理以及混沌理論等其它智能計算方法相互滲透和結合，這對開拓21世紀中新的智能計算技術將具有重要的意義。

3）並行處理的遺傳演算法的研究十分活躍。這一研究不僅對遺傳演算法本身的發展，而且對於新一代智能計算機體系結構的研究都是十分重要的。

4）遺傳演算法和人工生命的嶄新研究領域正不斷滲透。

5）遺傳演算法和進化規劃（EP）以及進化策略（ES）等進化計算理論日益結合。這三者之間的比較研究和彼此結合的探討正形成熱點。

由於遺傳演算法的整體搜索策略和優化搜索方法在計算時不依賴於梯度信息或其它輔助知識，而只需要影響搜索方向的目標函數和相應的適應度函數，所以遺傳演算法提供了一種求解複雜系統問題的通用框架，它不依賴於問題的具體領域，對問題的種類有很強的魯棒性，適用於非常複雜和困難的環境。所以廣泛應用於許多科學和領域。

目前，遺傳演算法已被人們廣泛地應用於生產調度、組合優化、通信網路設計、機器學習、機器人學、圖象處理與模式識別、運動估計、信號處理、遺傳編碼、自適應控制和人工生命等領域。遺傳演算法也是人工智慧領域中用於解決最優化的一種搜索啟發式演算法，是進化演算法的一種。這種啟發式通常用來生成有用的解決方案來優化和搜索問題。

結語:

遺傳演算法模擬生物繁殖的突變、交換和達爾文的自然選擇（適者生存）。它把問題可能的解編碼為一個向量（個體），向量的每一個元素稱為基因，並利用目標函數（選擇標準）對群體（個體集合）中的每一個個體進行評價，根據評價值（適應度）對個體進行選擇、交換、變異等遺傳操作，從而得到新的群體。遺傳演算法提供了一種求解複雜系統問題的通用框架，它不依賴於問題的具體領域，對問題的種類有很強的魯棒性，適用於非常複雜和困難的環境。所以廣泛應用於許多科學和領域。遺傳演算法特別在人工智慧領域有突出表現，對推動人工智慧發展具有重要意義！

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！