人類通過直覺常識和生活經驗，設計了壹種以尋找最優解為目的，模擬自然規律的算法。該算法能在可接受的成本(計算時間和存儲空間)內找到問題實例的可行解，且可行解與真實最優解之間的誤差壹般無法估計。
目前主要的啟發式算法有遺傳算法、退火法、蟻群算法、人工神經網絡等。本文主要介紹遺傳算法。
遺傳算法的基本原理是模擬達爾文進化論“物競天擇，適者生存”的自然法則，其核心思想如下
(1)將原問題的參數抽象成基因編碼。
(2)將原問題的可行解抽象為基因排列的染色體組合。
(3)將原問題解集的規模抽象為由壹定數量染色體組成的種群。
(4)將尋找可行解的過程抽象為種群的進化過程(染色體選擇、交叉、變異等。)
(5)比較可行方案的優劣，抽象為定量比較不同種群對當前環境的適應能力。
(6)逼近最優解的過程抽象為淘汰適應度差的種群，保留適應度高的種群進行下壹次進化。
(7)問題的最優解抽象為經過多次進化最終存活下來的精英種群。
理論上，通過有限種群進化，存活的種群都是精英染色體，是最適合當前環境條件的種群，可以無限逼近原問題的最優解。
相關生物學術語:
為了更好的理解遺傳算法，在此之前，我們先簡單介紹壹下相關的生物學術語，以便大家理解。
基因型:性狀染色體的內部表達；
表現型:由染色體決定的性狀的外在表現，或根據基因型形成的個體的外在表現；
進化:種群逐漸適應生存環境，質量不斷提高。生物的進化是以種群的形式進行的。
適合度:衡量壹個物種對生活環境的適應能力。
選擇:從群體中以壹定概率選擇幾個個體。總的來說，選拔過程是壹個基於適合度的優勝劣汰過程。
復制:當細胞分裂時，遺傳物質DNA通過復制轉移到新的細胞中，新的細胞繼承了舊細胞的基因。
交叉:兩條染色體的DNA在同壹位置被切割，兩串交叉結合形成兩條新的染色體。也稱為基因重組或雜交；
突變:復制時有可能(小概率)出現壹些復制錯誤，突變會產生新的染色體，表現出新的性狀。
編碼:DNA中的遺傳信息沿著壹條長鏈以壹定的模式排列。遺傳編碼可以看作是從表型到基因型的映射。
解碼:從基因型到表現型的映射。
個體:指具有染色體特征的實體；
群體:個體的集合，這個集合中個體的數量稱為群體。
壹般實現過程
遺傳算法中的每條染色體對應壹個遺傳算法的解。通常，我們用適應度函數來衡量這個解的質量。所以從壹個基因組到它的解的適合度形成了壹個映射。遺傳算法的實現過程其實就像自然界的進化過程。
基本遺傳算法綜述
1.[開始]生成n個染色體的隨機群體(適用於此問題的解決方案)
2.【適應度】評估群體中每個染色體X的適應度f(x)。
3.[新群體]通過重復以下步驟創建新群體，直到新群體完成。
3.1【選擇】根據群體的適應度(適應性更好，選擇機會更大)選擇兩條親本染色體。
3.2【雜交】以雜交概率雜交親本，形成新的後代(子代)。如果沒有交叉，子代就是父代的精確拷貝。
3.3【突變】突變概率對每個基因座(在染色體中的位置)的新後代進行突變。
4.[接受]將新後代放入新群體中[替換]使用新生成的群體進壹步運行算法。
5.[測試]如果滿足結束條件，則停止並返回當前種群中的最佳解。
6。[循環]轉到步驟2
影響遺傳算法的因素
從遺傳算法的概述中，我們可以看到交叉和變異是遺傳算法中最重要的部分。性能主要受這兩個因素影響。在我們解釋更多關於交叉和變異之前，我們將給出壹些關於染色體的信息。
染色體編碼
染色體應該以某種方式包含有關它所代表的解決方案的信息。最常用的編碼方法是二進制字符串。那麽染色體看起來像這樣:
每個染色體由壹個二進制字符串表示。字符串中的每壹位都可以代表解決方案的壹些特征。另壹種可能性是整個字符串可以代表壹個數字——這已經在基本的GA小程序中使用。當然，還有很多其他的編碼方式。編碼主要看要解決的問題。比如可以直接對整數或者實數進行編碼，有時候對壹些排列進行編碼也很有用。
染色體交叉
確定了要使用的編碼後，我們可以繼續交叉操作。交叉操作從父代染色體中選擇的基因並產生新的後代。最簡單的方法是隨機選擇壹些交集，從這個點之前的第壹個父交集開始復制所有內容，然後在交集之後的另壹個父交集之後復制所有內容。交集可描述如下:(|為交集):
還有其他的方式過馬路，比如我們可以選擇更多的路口。交叉可能非常復雜，主要取決於染色體的編碼。針對特定問題的特定交叉可以提高遺傳算法的性能。
4.染色體突變
交叉完成後，變異發生。變異的目的是防止群體中的所有解陷入解決問題的局部最優。變異操作隨機改變交叉產生的後代。在二進制編碼的情況下，我們可以將壹些隨機選擇的位從1切換到0或從0切換到1。突變可能如下:
變異(和交叉)技術主要依賴於染色體的編碼。例如，當我們編碼排列時，我們可以將突變視為兩個基因的交換。
遺傳算法的參數
1.交叉和變異的概率
遺傳算法有兩個基本參數——交叉概率和變異概率。
交叉概率:交叉的頻率。如果沒有交集，後代就是父母的精確拷貝。如果有交叉，後代由父母的部分染色體組成。如果交叉概率是100%，那麽所有後代都是交叉產生的。如果是0%，那麽新壹代就是由老種群的染色體精確復制而成的(但這並不代表新壹代是壹樣的！)。交叉是希望新染色體包含舊染色體的好的部分，所以新染色體會更好。但是，把壹部分老人口留給下壹代也是好的。
突變概率:染色體部分突變的頻率。如果沒有突變，交叉(或直接復制)後會立即產生後代，沒有任何變化。如果發生突變，染色體的壹個或多個部分就會改變。如果突變概率為100%，則整個染色體發生變化，如果為0%，則沒有變化。變異通常可以防止GA陷入局部極值。變異應該不會頻繁出現，因為GA實際上會變成隨機搜索。
2.其他參數
群體大小:群體中有多少染色體(第壹代)。如果染色體太少，GA幾乎不可能交叉，只探索搜索空間的壹小部分。另壹方面，如果染色體太多，GA會變慢。研究表明，在壹定的限制條件下(主要取決於編碼和問題)，使用非常大的群體是沒有用的，因為它不能比中等規模的群體更快地解決問題。
3選擇
從GA的概述中已經知道，從群體中選擇染色體作為交叉親本。問題是如何選擇這些染色體。根據達爾文的進化論，最好的進化可以創造新的後代。有很多方法可以選擇最好的染色體。比如輪盤賭選擇、玻爾茲曼選擇、錦標賽選擇、等級選擇、穩態選擇等等。
1.輪盤賭選擇
家長根據身體狀況選擇。染色體越好，被選中的機會就越大。想象壹個輪盤賭，種群中所有的染色體都被放置在那裏。輪盤賭中橫截面的大小與每個染色體的適應度函數成正比——值越大，橫截面越大。參見下圖中的示例。
在輪盤上放壹個彈珠，選擇停止的染色體。顯然，適應值越大的染色體被選擇的次數就越多。
這個過程可以用下面的算法來描述。
【Sum】計算群體中所有染色體的適應度之和——Sum s。
[選擇]從區間(0，s)-r生成壹個隨機數
[循環]遍歷總體，從0-和開始求和。當總和s大於r時，停下來，回到妳的染色體。當然，步驟1對於每個組只執行壹次。
2.排名選擇
當適應值相差較大時，之前的選擇類型就會出現問題。比如，如果最佳染色體適應度是所有適應度之和的90%，那麽其他染色體被選中的機會就很小。等級選擇首先對種群進行排序，然後每個染色體得到由等級決定的適應度值。最差的將是適應度1，第二差的是2，以此類推，最好的將是適應度n(種群中染色體的數量)。妳可以在下圖中看到，改變適應性和排名決定的數字後，情況是如何變化的。
排名前的情況(健身圖)
排名後(順序號圖)
現在所有的染色體都有機會被選擇。但是這種方法會減慢收斂速度，因為最好的染色體和其他染色體差別不大。
3.穩態選擇
這不是選擇父母的具體方式。選擇新群體的主要思想是很大壹部分染色體可以存活到下壹代。穩態選擇遺傳算法以如下方式工作。在每壹代中，選擇壹些好的(適應性更強的)染色體來創造新的後代。然後去掉壹些不好的染色體(適應度低的)，把新的後代放到它們的位置上。其余的人幸存了下來。
4.精英
精英主義的概念已經被引入。當我們通過交叉和變異創造壹個新的種群時，我們有很大的機會會失去最好的染色體。精英主義是先把最好的染色體(或幾個最好的染色體)復制到壹個新群體的方法的名稱。其余的人是按上述方式構成的。精英主義可以快速提高遺傳算法的性能，因為它可以防止最優解的丟失。
交叉和變異。
交叉和變異是遺傳算法的兩個基本算子。GA的性能非常依賴於它們。運算符的類型和實現取決於編碼和問題。有許多方法來執行交叉和變異。在本章中，我們將簡要介紹壹些關於如何執行多重編碼的例子和建議。
1.二進制編碼
橫斷
單點交集-選擇壹個交集，將染色體中的二進制字符串復制到第壹個父代中的交集，並從另壹個父代中復制其余部分。
選擇兩點相交-兩個相交，將染色體上的二進制串從第壹個父節點復制到第壹個相交，將第壹個相交的部分從第壹個父節點復制到第二個相交，將剩余部分從第壹個父節點再次復制。
均勻交叉-從第壹個父項或第二個父項隨機復制位。
算術交叉-執行壹些算術運算來產生新的後代。
變化
位反轉-選定的位被反轉。
2.置換編碼
橫斷
單點交點-選擇壹個交點，將排列從第壹個父交點復制到交點，然後掃描另壹個父交點，如果編號不在後代中，則添加它。註意:有更多的方法可以在交叉點後創建休止符。
(1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) = (1 2 3 4 5 6 8 9 7)
變化
訂單變更-選擇並交換兩個數字。
(1 2 3 4 5 6 8 9 7) = >(1 8 3 4 5 6 2 9 7)
3.價值編碼
橫斷
二進制編碼的所有雜交都可以使用。
變化
加壹個小數字(用於實數編碼)-將壹個小數字加(或減)到選定的值上。
(1.29 5.68 2.86 4.11 5.55)= >(1.29 5.68 2.73 4.22 5.55)
4.樹形編碼
橫斷
樹交叉——在雙親之間選擇壹個交叉點，在這個交叉點上雙親被分割，交換點以下的部分被交換產生新的後代。
變化
更改運算符，編號-所選節點已更改。
補充:
疑點:
初始人口是多少:
用二進制(通用)表示最終解。
比如妳需要求z = x ^ 2+y ^ 2的最大值，x = {1，5，3，8}，y = {5，4，0，6}。
用六位二進制數表示由x和y組成的解，例如001100表示x=1，y=4。
001100稱為基因序列，代表了這個問題的解決方案。
群體是包含多個基因序列(解決方案/個體)的集合。
什麽是健身功能，它的作用是什麽:
健身功能可以理解為“遊戲規則”。如果問題比較復雜，就需要定義適應度函數來解釋如何區分優秀個體和較差個體。如果問題比較簡單，比如上面提到的求最大值的問題，這個函數可以直接作為適應度函數。功能:評價個體的優劣，從而決定其遺傳機會的大小。
如何選擇:
定義“優勝劣汰，不適合者淘汰”的規則，比如定義適應性高的人更容易被選中。
如何穿越:
使用循環，遍歷群體中的每個個體，並選擇另壹個個體進行交叉。例如，通過遍歷為基因序列A選擇B對，將A的前半部分和B的後半部分組合起來，形成壹個新的個體(基因序列)C。
如何變異:
隨機選擇基因序列上的某個位置，交換0-1。
GA的建議參數
如果妳決定實現遺傳算法，這壹章應該為妳提供壹些基本的建議。這些建議非常籠統。妳可能想嘗試用自己的GA來解決具體問題，因為沒有通用的理論來幫妳針對任何問題調整GA參數。
建議通常是對GA的經驗研究的結果，通常只在二進制編碼上進行。
交叉率
交叉率壹般應該比較高，80%-95%左右。但有研究結果表明，對於某些問題，60%左右的交叉率是最好的。)
突變率
另壹方面，突變率應該很低。最好的利率好像是0.5%-1%左右。
群體大小
也許令人驚訝的是，非常大的群體通常不會提高GA的性能(就找到解的速度而言)。壹個好的種群規模大約是20-30，但有時50-100的規模是最好的。壹些研究還表明，最佳群體大小取決於編碼串(染色體)的大小。這意味著如果妳有32條染色體，那麽群體應該高於16條染色體。
挑選
基本的輪盤輪盤選擇可以，但是有時候排位選擇可以更好。見選擇的利與弊壹章。在GA操作期間，有壹些更復雜的方法來改變選擇參數。基本上，這些行為類似於模擬退火。如果妳不使用其他方法來保存找到的最佳解決方案，妳應該確保使用精英主義。也可以嘗試穩態選擇。
編碼
編碼取決於問題和問題實例的大小。有關壹些建議或其他資源，請參見編碼壹章。
交叉和變異
運算符取決於所選的編碼和問題。查看關於操作符的章節以獲得壹些建議。也可以查看其他網站。
搜索空間
如果我們正在解決問題，我們通常會尋找壹些最佳解決方案。所有可行解的空間(所需解所在的解集)稱為搜索空間(也稱為狀態空間)。搜索空間中的每個點代表壹個可能的解決方案。每個可能的解決方案都可以用來“標記”問題的價值(或適合度)。通過GA，我們在許多可能的解決方案中尋找最佳解決方案——用搜索空間中的壹個點來表示。那麽找到壹個解就相當於在搜索空間中找到壹些極值(最小值或最大值)。有時可以很好地定義搜索空間，但通常我們只知道搜索空間中的幾個點。在使用遺傳算法的過程中，隨著進化，尋找解的過程會產生其他點(可能的解)。
問題是搜索可能非常復雜。人們可能不知道在哪裏尋找解決方案或從哪裏開始。有許多方法可以找到合適的解決方案，但這些方法不壹定提供最佳解決方案。這些方法中的壹些是爬山、禁忌搜索、模擬退火和遺傳算法。用這些方法找到的解通常被認為是好解，因為通常不可能證明是最佳解。
NP難問題
NP問題是壹類無法用傳統方法解決的問題。我們可以快速應用許多任務(多項式)算法。還有壹些問題是算法解決不了的。許多重要問題很難找到解決方案，但壹旦有了解決方案，檢查就很容易了。這壹事實導致了NP完全問題。NP代表非確定性多項式，意思是妳可以“猜測”解(通過壹些非確定性算法)，然後檢查。如果我們有壹個猜測機器，我們也許能在合理的時間內找到解決方案。為了簡單起見，對NP完全問題的研究僅限於那些答案可以是或不是的問題，由於輸出任務復雜，引入了壹類問題，稱為NP難問題。這門課不像NP完全問題那麽局限。NP問題的壹個特點是可以使用簡單的算法，可能壹眼就看出，可以用來尋找可用的解。但是這種方法通常會提供許多可能的解——僅僅嘗試所有可能的解是壹個非常緩慢的過程(例如O (2 n))。對於這類問題的較大實例，這種方法根本不可用。今天，沒有人知道是否有壹些更快的算法來提供NP問題的精確答案。對於研究人員來說，找到這樣的算法仍然是壹項重大任務(可能是妳！:-))。今天，很多人認為這種算法不存在，所以他們在尋找壹種替代方法。替代方法的壹個例子是遺傳算法。NP問題的例子有可滿足性問題、旅行推銷員問題或背包問題。可以獲得NP問題的匯編。
參考:
/p/ae5157c26af9
/p/b36b520bd187