遺傳演算法簡介
遺傳演算法是受自然進化理論啟發的一系列搜尋演算法。透過模仿自然選擇和繁殖的過程，遺傳演算法可以為涉及搜尋，最佳化和學習的各種問題提供高質量的解決方案。同時，它們類似於自然進化，因此可以克服傳統搜尋和最佳化演算法遇到的一些障礙，尤其是對於具有大量引數和複雜數學表示形式的問題。
類比達爾文進化論
達爾文進化理論
遺傳演算法是類比自然界的達爾文進化實現的簡化版本。達爾文進化論的原理概括總結如下：
變異：種群中單個樣本的特徵（性狀，屬性）可能會有所不同，這導致了樣本彼此之間有一定程度的差異。
遺傳：某些特徵可以遺傳給其後代。導致後代與雙親樣本具有一定程度的相似性。
選擇：種群通常在給定的環境中爭奪資源。更適應環境的個體在生存方面更具優勢，因此會產生更多的後代。
換句話說，進化維持了種群中個體樣本彼此不同。那些適應環境的個體更有可能生存，繁殖並將其性狀傳給下一代。這樣，隨著世代的更迭，物種變得更加適應其生存環境。而進化的重要推動因素是交叉（crossover）或重組（recombination）或雜交——結合雙親的特徵產生後代。交叉有助於維持人口的多樣性，並隨著時間的推移將更好的特徵融合在一起。此外，變異（mutations）或突變（特徵的隨機變異）可以透過引入偶然性的變化而在進化中發揮重要作用。
遺傳演算法對應概念
遺傳演算法試圖找到給定問題的最佳解。達爾文進化論保留了種群的個體性狀，而遺傳演算法則保留了針對給定問題的候選解集合（也稱為）。這些候選解經過迭代評估（evaluate），用於建立下一代解。更優的解有更大的機會被選擇，並將其特徵傳遞給下一代候選解集合。這樣，隨著代際更新，候選解集合可以更好地解決當前的問題。
基因型（Genotype）
在自然界中，透過基因型表徵繁殖，繁殖和突變，基因型是組成染色體的一組基因的集合。在遺傳演算法中，每個個體都由代表基因集合的染色體構成。例如，一條染色體可以表示為二進位制串，其中每個位代表一個基因：
種群（Population）
遺傳演算法保持大量的個體（individuals）——針對當前問題的候選解集合。由於每個個體都由染色體表示，因此這些種族的個體（individuals）可以看作是染色體集合：
適應度函式（Fitness function）
在演算法的每次迭代中，使用適應度函式（也稱為目標函式）對個體進行評估。目標函式是用於最佳化的函式或試圖解決的問題。適應度得分更高的個體代表了更好的解，其更有可能被選擇繁殖並且其性狀會在下一代中得到表現。隨著遺傳演算法的進行，解的質量會提高，適應度會增加，一旦找到具有令人滿意的適應度值的解，終止遺傳演算法。
選擇（Selection）
在計算出種群中每個個體的適應度後，使用選擇過程來確定種群中的哪個個體將用於繁殖併產生下一代，具有較高值的個體更有可能被選中，並將其遺傳物質傳遞給下一代。仍然有機會選擇低適應度值的個體，但機率較低。這樣，就不會完全摒棄其遺傳物質。
交叉（Crossover）
為了建立一對新個體，通常將從當前代中選擇的雙親樣本的部分染色體互換（交叉），以建立代表後代的兩個新染色體。此操作稱為交叉或重組：
突變（Mutation）
突變操作的目的是定期隨機更新種群，將新模式引入染色體，並鼓勵在解空間的未知區域中進行搜尋。突變可能表現為基因的隨機變化。變異是透過隨機改變一個或多個染色體值來實現的。例如，翻轉二進位制串中的一位：
遺傳算法理論
構造遺傳演算法的理論假設——針對當前問題的最佳解是由多個要素組成的，當更多此類要素組合在一起時，將更接近於問題的最優解。種群中的個體包含一些最優解所需的要素，重複選擇和交叉過程將個體將這些要素傳達給下一代，同時可能將它們與其他最優解的基本要素結合起來。這將產生遺傳壓力，從而引導種群中越來越多的個體包含構成最佳解決方案的要素。
圖式定理（schema theorem）
要素假設的一個更形式化的表達是Holland圖式定理，也稱為遺傳演算法的基本定理。該定理是指圖式是可以在染色體內找到的模式（或模板）。每個圖式代表染色體中具有一定相似性的子集。例如，如果一組染色體用長度為4的二進位制串表示，則圖式101表示所有這些染色體，其中最左邊的位置為1，最右邊的兩個位置為01，從左邊數的第二個位置為1或0，其中表示萬用字元。對於每個圖式，具有以下兩個度量：
階（Order）：固定數字的數量
定義長度（Defining length）：最遠的兩個固定數字之間的距離
下表提供了四位二進位制圖式及其度量的幾個示例：
種群中的每個染色體都對應於多個圖式。例如，染色體1101對應於該表中出現的每個圖式，因為它與它們代表的每個模式匹配。如果該染色體具有較高的適應度，則它及其代表的所有圖式都更有可能從選擇操作中倖存。當這條染色體與另一條染色體交叉或發生突變時，某些圖式將保留下來，而另一些則將消失。低階圖式和定義長度短的圖式更有可能倖存。因此，圖式定理指出，低階、定義長度短且適合度高於平均值的圖式頻率在連續的世代中呈指數增長。換句話說，隨著遺傳演算法的發展，代表更有效解決方案的屬性的更小、更簡單的要素基塊將越來越多地出現在群體中。
遺傳演算法與傳統演算法的差異
遺傳演算法與傳統的搜尋和最佳化演算法（例如基於梯度的演算法）之間存在一些重要區別。
基於種群
遺傳搜尋是針對一組候選解決方案（individuals）而不是單個候選方案進行的。在搜尋過程中，演算法會保留當前一代的一組個體。遺傳演算法的每次迭代都會建立下一代個體。相反，大多數其他搜尋演算法都維持單個解決方案，並迭代地修改它以尋找最佳解決方案。例如，梯度下降演算法沿當前最陡下降方向迭代移動當前解，梯度方向為給定函式的梯度的負數。2。 遺傳表徵遺傳演算法不是直接在候選解上執行，而是在它們的表示（或編碼）（通常稱為染色體，chromosomes）上執行。染色體能夠利用交叉和突變的遺傳操作。使用遺傳表示的弊端是使搜尋過程與原始問題域分離。遺傳演算法不知道染色體代表什麼，也不試圖解釋它們。3。 適應度函式適應度函式表示要解決的問題。遺傳演算法的目的是找到利用適應度函式求得的得分最高的個體。與許多傳統的搜尋演算法不同，遺傳演算法僅考慮利用適應度函式獲得的值，而不依賴於導數或任何其他資訊。這使它們適合處理難以或不可能在數學上求導的函式。4。 機率行為儘管許多傳統演算法本質上是確定性的，但是遺傳演算法用來從一代產生下一代的規則是機率性的。例如，選擇的個體將被用來建立下一代，選擇個體的機率隨著個體的適應度得分增加，但仍有可能選擇一個得分較低的個體。儘管此過程具有機率性，但基於遺傳演算法的搜尋並不是隨機的；取而代之的是，它利用隨機將搜尋引向搜尋空間中有更好機會改善結果的區域。
遺傳演算法的優缺點
優點
全域性最優
在許多情況下，最佳化問題具有區域性最大值和最小值。這些值代表的解比周圍的解要好，但並不是最佳的解。大多數傳統的搜尋和最佳化演算法，尤其是基於梯度的搜尋和最佳化演算法，很容易陷入區域性最大值，而不是找到全域性最大值。遺傳演算法更有可能找到全域性最大值。這是由於使用了一組候選解，而不是一個候選解，而且在許多情況下，交叉和變異操作將導致候選解與之前的解有所不同。只要設法維持種群的多樣性並避免過早趨同（premature convergence），就可能產生全域性最優解。2。 處理複雜問題由於遺傳演算法僅需要每個個體的適應度函式得分，而與適應度函式的其他方面（例如導數）無關，因此它們可用於解決具有複雜數學表示、難以或無法求導的函式問題。3。 處理缺乏數學表達的問題遺傳演算法可用於完全缺乏數學表示的問題。這是由於適應度是人為設計的。例如，想要找到最有吸引力顏色組合，可以嘗試不同的顏色組合，並要求使用者評估這些組合的吸引力。使用基於意見的得分作為適應度函式應用遺傳演算法搜尋最佳得分組合。即使適應度函式缺乏數學表示，並且無法直接從給定的顏色組合計算分數，但仍可以執行遺傳演算法。只要能夠比較兩個個體並確定其中哪個更好，遺傳演算法甚至可以處理無法獲得每個個體適應度的情況。例如，利用機器學習演算法在模擬比賽中駕駛汽車，然後利用基於遺傳演算法的搜尋可以透過讓機器學習演算法的不同版本相互競爭來確定哪個版本更好，從而最佳化和調整機器學習演算法。4。 耐噪音一些問題中可能存在噪聲現象。這意味著，即使對於相似的輸入值，每次得到的輸出值也可能有所不同。例如，當從感測器產生異常資料時，或者在得分基於人的觀點的情況下，就會發生這種情況。儘管這種行為可以干擾許多傳統的搜尋演算法，但是遺傳演算法通常對此具有魯棒性，這要歸功於反覆交叉和重新評估個體的操作。5。 並行性遺傳演算法非常適合並行化和分散式處理。適應度是針對每個個體獨立計算的，這意味著可以同時評估種群中的所有個體。另外，選擇、交叉和突變的操作可以分別在種群中的個體和個體對上同時進行。6。 持續學習進化永無止境，隨著環境條件的變化，種群逐漸適應它們。遺傳演算法可以在不斷變化的環境中連續執行，並且可以在任何時間點獲取和使用當前最佳的解。但是需要環境的變化速度相對於遺傳演算法的搜尋速度慢。
侷限性
需要特殊定義：將遺傳演算法應用於給定問題時，需要為它們建立合適的表示形式——定義適應度函式和染色體結構，以及適用於該問題的選擇、交叉和變異運算元。
超引數調整：遺傳演算法的行為由一組超引數控制，例如種群大小和突變率等。將遺傳演算法應用於特定問題時，沒有標準的超引數設定規則。
計算密集：種群規模較大時可能需要大量計算，在達到良好結果之前會非常耗時。可以透過選擇超引數、並行處理以及在某些情況下快取中間結果來緩解這些問題。
過早趨同：如果一個個體的適應能力比種群的其他個體的適應能力高得多，那麼它的重複性可能足以覆蓋整個種群。這可能導致遺傳演算法過早地陷入區域性最大值，而不是找到全域性最大值。為了防止這種情況的發生，需要保證物種的多樣性。
無法保證的解的質量：遺傳演算法的使用並不能保證找到當前問題的全域性最大值（但幾乎所有的搜尋和最佳化演算法都存在此類問題，除非它是針對特定型別問題的解析解）。通常，遺傳演算法在適當使用時可以在合理的時間內提供良好的解決方案。
遺傳演算法應用場景
數學表示複雜的問題：由於遺傳演算法僅需要適應度函式的結果，因此它們可用於難以求導或無法求導的目標函式問題，大量引數問題以及引數混合問題型別。
沒有數學表示式的問題：只要可以獲得分數值或有一種方法可以比較兩個解，遺傳演算法就不需要對問題進行數學表示。
涉及噪聲資料問題：遺傳演算法可以應對資料可能不一致的問題，例如源自感測器輸出或基於人類評分的資料。
隨時間而變化的環境所涉及的問題：遺傳演算法可以透過不斷建立適應變化的新一代來響應較為緩慢的環境變化。
但是當問題具有已知的和專業的解決方法時，使用現有的傳統方法或分析方法可能是更有效的選擇。
遺傳演算法的組成要素
遺傳演算法的核心是迴圈——依次應用選擇，交叉和突變的遺傳運算元，然後對個體進行重新評估——一直持續到滿足停止條件為止
演算法的基本流程
以下流程圖顯示了基本遺傳演算法流程的主要階段：
no
yes
開始
建立初始種群
計算種群中每個個體的適應度
選擇
交叉
突變
計算種群中每個個體的適應度
滿足終止條件？
選擇適應度最高的個體
結束
建立初始種群
初始種群是隨機選擇的一組有效候選解（個體）。由於遺傳演算法使用染色體代表每個個體，因此初始種群實際上是一組染色體。
計算適應度
適應度函式的值是針對每個個體計算的。對於初始種群，此操作將執行一次，然後在應用選擇、交叉和突變的遺傳運算元後，再對每個新一代進行。由於每個個體的適應度獨立於其他個體，因此可以平行計算。由於適應度計算之後的選擇階段通常認為適應度得分較高的個體是更好的解決方案，因此遺傳演算法專注於尋找適應度得分的最大值。如果是需要最小值的問題，則適應度計算應將原始值取反，例如，將其乘以值（-1）。
選擇、交叉和變異
將選擇，交叉和突變的遺傳運算元應用到種群中，就產生了新一代，該新一代基於當前代中較好的個體。選擇（selection）操作負責當前種群中選擇有優勢的個體。交叉（crossover，或重組，recombination）操作從選定的個體建立後代。這通常是透過兩個被選定的個體互換他們染色體的一部分以建立代表後代的兩個新染色體來完成的。變異（mutation）操作可以將每個新建立個體的一個或多個染色體值（基因）隨機進行變化。突變通常以非常低的機率發生。
演算法終止條件
在確定演算法是否可以停止時，可能有多種條件可以用於檢查。兩種最常用的停止條件是：
已達到最大世代數。這也用於限制演算法消耗的執行時間和計算資源。
在過去的幾代中，個體沒有明顯的改進。這可以透過儲存每一代獲得的最佳適應度值，然後將當前的最佳值與預定的幾代之前獲得的最佳值進行比較來實現。如果差異小於某個閾值，則演算法可以停止。
其他停止條件：
自演算法過程開始以來已經超過預定時間。
消耗了一定的成本或預算，例如CPU時間和/或記憶體。
最好的解已接管了一部分種群，該部分大於預設的閾值。
其他
精英主義（elitism）
儘管遺傳演算法群體的平均適應度通常隨著世代的增加而增加，但在任何時候都有可能失去當代的最佳個體。這是由於選擇、交叉和變異運算子在建立下一代的過程中改變了個體。在許多情況下，丟失是暫時的，因為這些個體（或更好的個體）將在下一代中重新引入種群。但是，如果要保證最優秀的個體總是能進入下一代，則可以選用精英主義策略。這意味著，在我們使用透過選擇、交叉和突變建立的後代填充種群之前，將前n個個體（n是預定義引數）複製到下一代。複製後的的精英個體仍然有資格參加選擇過程，因此仍可以用作新個體的親本。Elitism策略有時會對演算法的效能產生重大的積極影響，因為它避免了重新發現遺傳過程中丟失的良好解決方案所需的潛在時間浪費。
小生境與共享
在自然界中，任何環境都可以進一步分為多個子環境或小生境，這些小生境由各種物種組成，它們利用每個小生境中可用的獨特資源，例如食物和庇護所。例如，森林環境由樹梢，灌木，森林地面，樹根等組成；這些可容納不同物種，它們生活在該小生境中並利用其資源。當幾種不同的物種共存於同一個小生境中時，它們都將爭奪相同的資源，從而形成了尋找新的，無人居住的生態位並將其填充的趨勢。在遺傳演算法領域，這種小生境現象可用於維持種群的多樣性以及尋找幾個最佳解決方案，每個解決方案均被視為小生境。例如，假設遺傳演算法試圖最大化具有幾個不同峰值的適應度函式：
由於遺傳演算法的趨勢是找到全域性最大值，因此一段時間後大多數個體集中在最高峰附近。在圖中透過使用×標記的位置表示這一點，×代表了當前代的個體。但是有時，除了全域性最大值外，我們還希望找到其他部分（或全部）峰值。為此，可以將每個峰視為小生境，以與其高度成比例的方式提供資源。然後，找到一種在佔用資源的個體之間共享（或分配）這些資源的方法，理想情況下，這將促使物種進行相應的分配，最高峰會吸引最多的人，因為它提供的獎勵最多，而其他峰由於提供較少的獎勵而相應減少物種數量：
實現共享機制的一種方法是將每個個體的原始適應度值除以（與之相關的）其他所有個體的距離之和。另一種選擇是將每個個體的原始適應度除以周圍某個半徑內的其他個體的數量。
遺傳演算法實踐
採用deap框架實現遺傳演算法的Hello world——OneMax問題，程式碼實現連結。
