遺傳算法是由美國密西根大學的 Holland教授創立於20世紀六七十年代，受達爾文「進化論」思想的啟發而設計實現。遺傳算法不是通過暴力搜索解的方法，而是通過模擬種群的基因交叉和突變，經過種群一代一代的適者生存的方式尋找問題優解的方法，這在解決組合優化時解空間組合爆炸中應用廣泛。
一、如何理解遺傳算法
我們可以這樣形象地理解遺傳算法，假設我們現在需要找到一個最能抵抗寒冷的人類，那麼遺傳算法是這樣設計的：首次創造一個較寒冷生活環境(問題的限制條件)，在這個環境中投入一批各種各樣的人類(初始種群)，讓人類在這種寒冷的環境中生存。人類一代一代的生活，周圍環境也設置得越來越寒冷，同時人類在產生下一代的時候也伴隨著基因的交叉和變異(遺傳算法的迭代過程)。正是隨著基因交叉和突變，慢慢的產生了極少數可以抵抗寒冷的基因，慢慢的擁有可以抵抗寒冷基因的人更加適應環境而得以發展，慢慢的能夠適應寒冷的人類生存了下來，其它不適應環境的被淘汰了，這個過程就是解空間的慢慢趨於優的過程，遺傳算法就是模擬這一過程 。
遺傳算法很好理解，但是需要說明一下，遺傳算法是一種尋優的方案，一種算法思想，所以遺傳算法針對具體的問題需要具體的設計。
二、遺傳算法
遺傳算法按照其進化的思想，將算法的實施分為四個部分，編碼、選擇、交叉和變異。
2.1編碼
編碼問題是遺傳算法首先要解決的問題，這是一個從基因向表現型的表達過程，是模仿基因表達的過程。如雙眼皮\單眼皮由某一段基因控制，那麼就說這段基因表達到了眼皮這個表現型上。編碼就是建立基因與表現型的映射，編碼形式主要有三種：二進位編碼、整數編碼和浮點數編碼，三種編碼各有特點。
二進位編碼採用0/1數字串代表基因，如果011011中每兩個0/1數字串代表一個表現型，那麼表現型就是1,2,3，如果用來解決TSP問題的話，就代表選擇1->2->3這條路徑。
二進位編碼使用方便，能夠輕鬆處理基因交叉和變異過程，但是，二進位編碼容易造成編碼過剩和在交叉與變異過程中產生不穩定的新數據導致搜索結果難以收斂。
整數編碼的基因和表現型一致，在TSP問題中，基因串1,2,3的表現型就是1,2,3，就代表了1->2->3這條路徑。因此，整數編碼很方便處理TSP問題，但是，基因交叉的過程中會帶來路線中站點重複的問題。浮點數編碼適應於浮點數問題，涉及較少。
2.2選擇
選擇的作用是將適應環境能力強的個體挑選出來，對於算法來說就是將更加滿足優化條件的解挑選出來，並且在下一代中保留更多優解，這就是對搜索的啟發。適應環境能力就對應著優化條件，越優的條件越強的適應能力。對於TSP問題的優化條件就是希望路徑最短，即：
arg Min(distance(X))，對應arg Max(1/distance(X))
將適應函數取為：f(X)=1/distance(X)，X代表一條路徑。對於適應度函數，當f(X)越大，適應度越大，distance(X)也越小，這是我們所期望的。
在選擇的過程中希望，適應環境能力強能夠更多的選擇，常常會採用輪盤賭的方式來按照體個的適應能力，按比例的選擇下一代的個體。輪盤賭的方式需要求出一下概率矩陣：
輪盤賭的實施過程為：當要進行選擇時，隨機的產生一個概率，假如概率為0.4，那麼這個處於個體1和個體2的累計概率之間，那麼個體2將被選中。按照輪盤賭的方式可以按照個體的適應度的比例挑選下一代。
輪盤賭中，適應度高，對應的選擇的面積大，被選中的概率高。
2.3交叉和變異
交叉和變異是模擬生物基因行為的方法，是產生新物種的途徑，對應到算法中就是跳出局部最優向其它解空間搜索的方式。交叉是指兩條染色體的部分片段交叉互換，變異是指染色體中的基因發生了變化，改變了原來的結構。
如果採用二進位編碼的基因發生交叉的話，就是如下表中的兩端基因的加粗部分的基因串交換，同時，兩端基因的表現型也將發生變化。
如果採用整數編碼的基因發生交叉的話，還需要考慮是否需要通過映射去重。
同樣，如果採用二進位編碼的基因發生變異的話，基因串中的某一個0變成1，或者1變成0，其表現型也將發生變化。
三、解決什麼問題
在實際的生活中常常會遇到NP難問題，尤其是組合優化問題，隨著組合的增加解的空間也指數的增加。因為無法在可接受的時間內搜索得到問題最優解，這時就需要採用啟發式搜索優解的方法，在可接受的時間範圍內得到較優解甚至最優解。遺傳算法可以派上用場了，可以解決組合優化問題，如：排課問題、生產計劃規劃、旅行商問題等。
本文的版權歸算法卡農所有，抄襲等侵權行為必究！
喜歡我的話，加個關注吧，有更加精彩的內容等著大家。