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