1簡介

遺傳演算法（Genetic Algorithm, GA）來源於進化論和群體遺傳學，由美國的 Holland 教授於 1975 年在他的專著《自然界和人工系統的適應性》[1]中首先提出。遺傳演算法作為一種非確定性的擬自然演算法，為複雜系統的最佳化提供了一種新思路，對於諸多NP-Hard問題，遺傳演算法都有不錯的表現。相對於傳統演算法而言，遺傳演算法有四大突出優點[2]：

1.遺傳演算法不需要描述問題的全部特點，不需要描述全部需要處理的情況。

2.遺傳演算法僅需要對引數編碼集進行處理，無需針對問題本身進行約束。

3.相對於傳統演算法對模型線性、連續、可導的限制，遺傳演算法不存在這些限制條件。

4.快速求解。

遺傳演算法的相對不足：

1. 遺傳演算法的本質是隨機搜尋，不能保證所得解為全域性最優解（引數足夠大的情況下是可以求出全域性最優解，但失去了演算法本身的意義）。

2演算法的發展與重心

經過多年的發展，遺傳演算法的研究熱點及發展方向可以由圖1進行展示[3]：

圖1 遺傳演算法研究進展

遺傳演算法的搜尋核心是遺傳運算元的選擇，因此對於遺傳演算法的研究，其中最常見的內容與方向是遺傳運算元，遺傳運算元的選擇多樣性也導致了演算法表現的多樣性，常見的選擇方式如圖2所示：

圖2 遺傳運算元的研究

遺傳演算法作為一種搜尋演算法，在諸多領域均有很好的表現[4]，如函式最佳化、組合最佳化、生產排程、自動控制、機器學習、影象處理、人工生命、遺傳程式設計、機器學習、資料探勘等。

3例項說明

為了更通俗地理解遺傳演算法，下面將透過一些例項進行描述：

如果想在一座連綿的大山上找到其最高點，正常情況下你需要爬遍整座山才可以找到最高峰，但大多數的智慧演算法並不需要搜尋整個山峰，不同的智慧演算法有不同的求解思路，舉幾個簡單例子：

1. 爬山演算法（也稱為貪心演算法）。假設有一隻猴子從山的任意一點出發，當它爬到第一個高峰值點的時候便停止前進，並認為當前的山峰為整座山最高的點。這種情況下，運氣好可能會到達最高點，但是大機率情況下都不會是最高點。

2. 模擬退火演算法。假設有一隻神志不清的猴子，當它爬到山峰的時候，它有一定的機率繼續出發，也有機率停止前進。這種情況下它也有可能透過有限的時間找到整座山的最高點。

3. 遺傳演算法。假設山上有一群猴子，猴子生存的食物只有在山峰處才有，而且山峰越高食物量越充裕。那麼這些猴子為了生存，會不斷聚集在各個山頭上，而這些山峰可以理解為各種區域性最優解（圖3中類似綠色和藍色的地方），如果種群規模足夠大，勢必會有一群猴子聚集在了整座山的最高點，也就是全域性最優解（圖3中紅色位置）。

圖3 山體示意圖

基於以上三種演算法的描述，我們可以對智慧演算法有一個簡單的瞭解：無論是哪種演算法，都具有一定的隨機性，都不能保證最終選擇的山峰為整座山的最高點。但是在實際生活中，有諸多類似的問題，如果要考慮所有的情況可能會花費大量的時間，而恰巧我們並不需要一個最好的結果，我們只需要快速找到一個相對較好的結果便可以滿足要求的時候，智慧演算法的意義便得到了體現。

智慧演算法的核心：犧牲精度，保證效率。

通俗瞭解後，雖然心裡有大概思路，但還是雲裡霧裡，這個時候我們可以考慮結合一些實際的例子來理解遺傳演算法。

結語

雖然遺傳演算法有著一定的弊端和不足，但是遺傳演算法在諸多領域(特別是運籌學)還是有著很不錯的表現並已經運用到實際生活中。為了不斷適應各種問題，近年來不斷有學者提出改進策略，以使遺傳演算法有更廣泛的應用領域。

拓展閱讀:

https://zhuanlan.zhihu.com/p/36212065

https://zhuanlan.zhihu.com/p/30140008

https://zhuanlan.zhihu.com/p/25579864

參考文獻

[1] HOLLAND J H． Adaptation in natural and artificial systems: an introductory analysis with applications to biology，control，and artificial intelligence［M］．2nd ed．Cambridge: MIT Press，1992．

[2]葛繼科,邱玉輝,吳春明,蒲國林.遺傳演算法研究綜述[J].計算機應用研究,2008(10):2911-2916.

[3]馬永傑,雲文霞.遺傳演算法研究進展[J].計算機應用研究,2012,29(04):1201-1206+1210.

[4]吉根林.遺傳演算法研究綜述[J].計算機應用與軟體,2004(02):69-73.

[5] Nix A E , Vose M D . Modeling genetic algorithms with Markov chains[J]. Annals of Mathematics & Artificial Intelligence, 1992, 5(1):79-88.

我們可以透過自然界的遺傳原理來理解遺傳演算法。

簡單來說，遺傳演算法是一種隨機搜尋演算法，主要目的是用來最佳化。和自然界的遺傳一樣，遺傳演算法秉持的是適者生存、優勝劣汰的原則。透過選擇、交叉和變異，不斷迭代出更優秀的解法。

透過編碼，將解空間變成編碼空間，從中選擇當前較為優秀的解當作“父母”，下一步則是將多種解的特徵進行交叉，誕生下一代，最後經過變異成為“子嗣”。如果“子嗣”還是不能符合要求，那就再進行一次上述步驟，直到滿足要求。過程中，較差的基因就會一步步被淘汰。總之，這是一個列舉的過程。就像長頸鹿的進化一樣，樹葉長在高處，每一隻鹿都去嘗試吃樹葉，只有符合“標準”的長頸鹿能夠吃到食物、生存下來並誕生後代。

但要注意的是，這種演算法很多時候不會給出一個“最優解”，而是給出一些較為接近的次優解，從矮子裡面拔將軍。

有一款非常有趣的小遊戲——Boxcar 2D，可以幫你理解遺傳演算法：

這款遊戲的主要內容是用幾何圖形和圓形的輪子組成小汽車，不斷走過一條有上下波動的“路”，看什麼形狀的小車可以走得更遠。但和大部分遊戲不一樣的是，不用玩家自己手動拼裝小車，整個過程完全由演算法自動進行，每次隨機生成小車，卡到路上了就重新來過。最後小車會越走越遠，整個過程中小車的形狀會越來越合適，一開始可能只是個“獨輪車”，到後期則會很接近我們生活中摩托車的樣子。

還可以透過實際場景中的應用來理解遺傳演算法的特點：

遺傳演算法可以解決排程類問題，比如確定車間工作流程、飛機航線等。它是將工程、航行中所需要的資源消耗、時間等權值看作“染色體”，幾種染色體排列組合，最終選擇其中的較優方案。機器人中也會用到遺傳演算法，尤其是快速定位、路徑規劃等。就像 Boxcar 這個遊戲一樣，機器人在模擬環境中不斷嘗試接近目標，路線的優越度隨著路線的長度增加，結合機器人對自身位置的感知，最後得出較優解。遺傳演算法也可以被應用於幫助神經網路調整引數，只是這種方式需要的時間太長、運算量太大，屬於價效比較低的引數調整方式。遺傳演算法可以用來增強遊戲體驗。很多遊戲會有在同一場景面對多輪敵人的“生存模式”，在這一模式中，敵人的屬性是會不斷增強的，有了遺傳演算法，就可以根據你自身屬性的變化不斷改變敵人的屬性，以增強遊戲的難度。比如說你的法術強度高，敵人就會增加法術防禦度；你的攻擊穿透性高，敵人就會增加血量。這樣一來相比直接增加屬性，可以有更好的遊戲體驗。

其實，目前遺傳演算法已經慢慢淡出了主流演算法舞臺。雖然主旨是為了避開區域性最優誤區，為無限解集問題尋找答案，可在實際應用時相比梯度和蒙特卡洛演算法都沒有明顯的差異和優勢，常常被視作“玄學演算法”。比如計算結果的穩定性差、求解過程沒有可複製性等都是遺傳演算法的缺點。很長一段時間裡，遺傳演算法都被看作只能用來湊論文的演算法。不過理論也和技術一樣，會隨著實踐和研究不斷髮展，神經網路也曾被打入冷宮。DeepMind還提出了把神經網路和遺傳演算法結合，應用到遷移學習中的案例。或許，有朝一日遺傳演算法還會重新進入我們的視野。

內容選自《未來學徒 讀懂人工智慧飛馳時代》

幾天前，我著手解決一個實際問題——大型超市銷售問題。在使用了幾個簡單模型做了一些特徵工程之後，我在排行榜上名列第219名。

雖然結果不錯，但是我還是想做得更好。

於是，我開始研究可以提高分數的最佳化方法。結果我果然找到了一個，它叫遺傳演算法。在把它應用到超市銷售問題之後，最終我的分數在排行榜上一下躍居前列。

沒錯，僅靠遺傳演算法我就從219名直接跳到15名，厲害吧！相信閱讀完本篇文章後，你也可以很自如地應用遺傳演算法，而且會發現，當把它用到你自己正在處理的問題時，效果也會有很大提升。

目錄

1、遺傳算法理論的由來

2、生物學的啟發

3、遺傳演算法定義

4、遺傳演算法具體步驟

初始化

適應度函式

選擇

交叉

變異

5、遺傳演算法的應用

特徵選取

使用TPOT庫實現

6、實際應用

7、結語

1、遺傳算法理論的由來

我們先從查爾斯·達爾文的一句名言開始：

不是最強大、也不是最聰明的物種才能生存，而是最能對變化作出迴應的那一個。

你也許在想：這句話和遺傳演算法有什麼關係？其實遺傳演算法的整個概念就基於這句話。讓我們用一個基本例子來解釋 ：

我們先假設一個情景，現在你是一國之王，為了讓你的國家免於災禍，你實施了一套法案：

你選出所有的好人，要求其透過生育來擴大國民數量。

這個過程持續進行了幾代。

你將發現，你已經有了一整群的好人。

這個例子雖然不太可能，但是我用它是想幫助你理解概念。也就是說，我們改變了輸入值（比如：人口），就可以獲得更好的輸出值（比如：更好的國家）。

現在，我假定你已經對這個概念有了大致理解，認為遺傳演算法的含義應該和生物學有關係。那麼我們就快速地看一些小概念，這樣便可以將其聯絡起來理解。

2、生物學的啟發

相信你還記得這句話：

“細胞是所有生物的基石。”

由此可知，在一個生物的任何一個細胞中，都有著相同的一套染色體。所謂染色體，就是指由DNA組成的聚合體。

傳統上看，這些染色體可以被由數字0和1組成的字串表達出來。

一條染色體由基因組成，這些基因其實就是組成DNA的基本結構，DNA上的每個基因都編碼了一個獨特的性狀，比如，頭髮或者眼睛的顏色。

希望你在繼續閱讀之前先回憶一下這裡提到的生物學概念。結束了這部分，現在我們來看看所謂遺傳演算法實際上指的是什麼？

3、遺傳演算法定義

1. 首先，我們設定好了國民的初始人群大小。

2. 然後，我們定義了一個函式，用它來區分好人和壞人。

3. 再次，我們選擇出好人，並讓他們繁殖自己的後代。

4. 最後，這些後代們從原來的國民中替代了部分壞人，並不斷重複這一過程。

遺傳演算法實際上就是這樣工作的，也就是說，它基本上盡力地在某種程度上模擬進化的過程。因此，為了形式化定義一個遺傳演算法，我們可以將它看作一個最佳化方法，它可以嘗試找出某些輸入，憑藉這些輸入我們便可以得到最佳的輸出值或者是結果。遺傳演算法的工作方式也源自於生物學，具體流程見下圖：

那麼現在我們來逐步理解一下整個流程。

4、遺傳演算法具體步驟

為了讓講解更為簡便，我們先來理解一下著名的組合最佳化問題“揹包問題”。如果你還不太懂，這裡有一個我的解釋版本。

比如，你準備要去野遊1個月，但是你只能背一個限重30公斤的揹包。現在你有不同的必需物品，它們每一個都有自己的“生存點數”（具體在下表中已給出）。因此，你的目標是在有限的揹包重量下，最大化你的“生存點數”。

4.1 初始化

這裡我們用遺傳演算法來解決這個揹包問題。第一步是定義我們的總體。總體中包含了個體，每個個體都有一套自己的染色體。

我們知道，染色體可表達為2進位制數串，在這個問題中，1代表接下來位置的基因存在，0意味著丟失。（譯者注：作者這裡借用染色體、基因來解決前面的揹包問題，所以特定位置上的基因代表了上方揹包問題表格中的物品，比如第一個位置上是Sleeping Bag，那麼此時反映在染色體的‘基因’位置就是該染色體的第一個‘基因’。）

現在，我們將圖中的4條染色體看作我們的總體初始值。

4.2 適應度函式

接下來，讓我們來計算一下前兩條染色體的適應度分數。

對於A1染色體[100110]而言，有：

類似地，對於A2染色體[001110]來說，有：

對於這個問題，我們認為，當染色體包含更多生存分數時，也就意味著它的適應性更強。因此，由圖可知，染色體1適應性強於染色體2。

4.3 選擇

現在，我們可以開始從總體中選擇適合的染色體，來讓它們互相‘交配’，產生自己的下一代了。

這個是進行選擇操作的大致想法，但是這樣將會導致染色體在幾代之後相互差異減小，失去了多樣性。

因此，我們一般會進行“輪盤賭選擇法”（Roulette Wheel Selection method）。

想象有一個輪盤，現在我們將它分割成m個部分，這裡的m代表我們總體中染色體的個數。每條染色體在輪盤上佔有的區域面積將根據適應度分數成比例表達出來。

基於上圖中的值，我們建立如下“輪盤”。

現在，這個輪盤開始旋轉，我們將被圖中固定的指標（fixed point）指到的那片區域選為第一個親本。然後，對於第二個親本，我們進行同樣的操作。

有時候我們也會在途中標註兩個固定指標，如下圖：

透過這種方法，我們可以在一輪中就獲得兩個親本。我們將這種方法成為“隨機普遍選擇法”（Stochastic Universal Selection method）。

4.4 交叉

在上一個步驟中，我們已經選擇出了可以產生後代的親本染色體。那麼用生物學的話說，所謂“交叉”，其實就是指的繁殖。

現在我們來對染色體1和4（在上一個步驟中選出來的）進行“交叉”，見下圖：

這是交叉最基本的形式，我們稱其為“單點交叉”。這裡我們隨機選擇一個交叉點，然後，將交叉點前後的染色體部分進行染色體間的交叉對調，於是就產生了新的後代。

如果你設定兩個交叉點，那麼這種方法被成為“多點交叉”，見下圖：

4.5 變異

如果現在我們從生物學的角度來看這個問題，那麼請問：由上述過程產生的後代是否有和其父母一樣的性狀呢？答案是否。在後代的生長過程中，它們體內的基因會發生一些變化，使得它們與父母不同。

這個過程我們稱為“變異”，它可以被定義為染色體上發生的隨機變化，正是因為變異，種群中才會存在多樣性。

下圖為變異的一個簡單示例：

變異完成之後，我們就得到了新為個體，進化也就完成了，整個過程如下圖：

在進行完一輪“遺傳變異”之後，我們用適應度函式對這些新的後代進行驗證，如果函式判定它們適應度足夠，那麼就會用它們從總體中替代掉那些適應度不夠的染色體。

這裡有個問題，我們最終應該以什麼標準來判斷後代達到了最佳適應度水平呢？

一般來說，有如下幾個終止條件：

在進行X次迭代之後，總體沒有什麼太大改變。

我們事先為演算法定義好了進化的次數。

當我們的適應度函式已經達到了預先定義的值。

好了，現在我假設你已基本理解了遺傳演算法的要領，那麼現在讓我們用它在資料科學的場景中應用一番。

5、遺傳演算法的應用

5.1 特徵選取

試想一下每當你參加一個數據科學比賽，你會用什麼方法來挑選那些對你目標變數的預測來說很重要的特徵呢？你經常會對模型中特徵的重要性進行一番判斷，然後手動設定一個閾值，選擇出其重要性高於這個閾值的特徵。

那麼，有沒有什麼方法可以更好地處理這個問題呢？其實處理特徵選取任務最先進的演算法之一就是遺傳演算法。

我們前面處理揹包問題的方法可以完全應用到這裡。現在，我們還是先從建立“染色體”總體開始，這裡的染色體依舊是二進位制數串，“1”表示模型包含了該特徵，“0表示模型排除了該特徵”。

不過，有一個不同之處，即我們的適應度函式需要改變一下。這裡的適應度函式應該是這次比賽的的精度的標準。也就是說，如果染色體的預測值越精準，那麼就可以說它的適應度更高。

現在我假設你已經對這個方法有點一概念了。下面我不會馬上講解這個問題的解決過程，而是讓我們先來用TPOT庫去實現它。

5.2 用TPOT庫來實現

這個部分相信是你在一開始讀本文時心裡最終想實現的那個目標。即：實現。

那麼首先我們來快速瀏覽一下TPOT庫（Tree-based Pipeline Optimisation Technique，樹形傳遞最佳化技術），該庫基於scikit-learn庫建立。

下圖為一個基本的傳遞結構。

圖中的灰色區域用TPOT庫實現了自動處理。實現該部分的自動處理需要用到遺傳演算法。

我們這裡不深入講解，而是直接應用它。

為了能夠使用TPOT庫，你需要先安裝一些TPOT建立於其上的python庫。下面我們快速安裝它們：

# installing DEAP, update_checker and tqdm pip install deap update_checker tqdm# installling TPOT pip install tpot

這裡，我用了Big Mart Sales（資料集地址：https://datahack.analyticsvidhya.com/contest/practice-problem-big-mart-sales-iii/）資料集，為實現做準備，我們先快速下載訓練和測試檔案，以下是python程式碼：

# import basic libraries

import numpy as np

import pandas as pd

import matplotlib.pyplot as plt

%matplotlib inline

from sklearn import preprocessing

from sklearn.metrics import mean_squared_error

## preprocessing

### mean imputations

train["Item_Weight"].fillna((train["Item_Weight"].mean()), inplace=True)

test["Item_Weight"].fillna((test["Item_Weight"].mean()), inplace=True)

### reducing fat content to only two categories

train["Item_Fat_Content"] = train["Item_Fat_Content"].replace(["low fat","LF"], ["Low Fat","Low Fat"])

train["Item_Fat_Content"] = train["Item_Fat_Content"].replace(["reg"], ["Regular"])

test["Item_Fat_Content"] = test["Item_Fat_Content"].replace(["low fat","LF"], ["Low Fat","Low Fat"])

test["Item_Fat_Content"] = test["Item_Fat_Content"].replace(["reg"], ["Regular"])

train["Outlet_Establishment_Year"] = 2013 - train["Outlet_Establishment_Year"]

test["Outlet_Establishment_Year"] = 2013 - test["Outlet_Establishment_Year"]

train["Outlet_Size"].fillna("Small",inplace=True)

test["Outlet_Size"].fillna("Small",inplace=True)

train["Item_Visibility"] = np.sqrt(train["Item_Visibility"])

test["Item_Visibility"] = np.sqrt(test["Item_Visibility"])

col = ["Outlet_Size","Outlet_Location_Type","Outlet_Type","Item_Fat_Content"]

test["Item_Outlet_Sales"] = 0

combi = train.append(test)

for i in col:

combi[i] = number.fit_transform(combi[i].astype("str"))

combi[i] = combi[i].astype("object")

train = combi[:train.shape[0]]

test = combi[train.shape[0]:]

test.drop("Item_Outlet_Sales",axis=1,inplace=True)

## removing id variables

tpot_train = train.drop(["Outlet_Identifier","Item_Type","Item_Identifier"],axis=1)

tpot_test = test.drop(["Outlet_Identifier","Item_Type","Item_Identifier"],axis=1)

target = tpot_train["Item_Outlet_Sales"]

tpot_train.drop("Item_Outlet_Sales",axis=1,inplace=True)

# finally building model using tpot library

from tpot import TPOTRegressor

X_train, X_test, y_train, y_test = train_test_split(tpot_train, target,

train_size=0.75, test_size=0.25)

tpot = TPOTRegressor(generations=5, population_size=50, verbosity=2)

tpot.fit(X_train, y_train)

print(tpot.score(X_test, y_test))

tpot.export("tpot_boston_pipeline.py")

一旦這些程式碼執行完成，tpot_exported_pipeline.py裡就將會放入用於路徑最佳化的python程式碼。我們可以發現，ExtraTreeRegressor可以最好地解決這個問題。

## predicting using tpot optimised pipeline

tpot_pred = tpot.predict(tpot_test)

sub1 = pd.DataFrame(data=tpot_pred)

#sub1.index = np.arange(0, len(test)+1)

sub1 = sub1.rename(columns = {"0":"Item_Outlet_Sales"})

sub1["Item_Identifier"] = test["Item_Identifier"]

sub1["Outlet_Identifier"] = test["Outlet_Identifier"]

sub1.columns = ["Item_Outlet_Sales","Item_Identifier","Outlet_Identifier"]

sub1 = sub1[["Item_Identifier","Outlet_Identifier","Item_Outlet_Sales"]]

sub1.to_csv("tpot.csv",index=False)

如果你提交了這個csv，那麼你會發現我一開始保證的那些還沒有完全實現。那是不是我在騙你們呢？

當然不是。實際上，TPOT庫有一個簡單的規則。如果你不執行TPOT太久，那麼它就不會為你的問題找出最可能傳遞方式。

所以，你得增加進化的代數，拿杯咖啡出去走一遭，其它的交給TPOT就行。

此外，你也可以用這個庫來處理分類問題。進一步內容可以參考這個文件：http://rhiever.github.io/tpot/

除了比賽，在生活中我們也有很多應用場景可以用到遺傳演算法。

6、 實際應用

遺傳演算法在真實世界中有很多應用。這裡我列了部分有趣的場景，但是由於篇幅限制，我不會逐一詳細介紹。

6.1 工程設計

工程設計非常依賴計算機建模以及模擬，這樣才能讓設計週期過程即快又經濟。遺傳演算法在這裡可以進行最佳化並給出一個很好的結果。

相關資源：

論文：Engineering design using genetic algorithms

地址：http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=16942&context=rtd

6.2 交通與船運路線（Travelling Salesman Problem，巡迴售貨員問題）

這是一個非常著名的問題，它已被很多貿易公司用來讓運輸更省時、經濟。解決這個問題也要用到遺傳演算法。

6.3 機器人

遺傳演算法在機器人領域中的應用非常廣泛。實際上，目前人們正在用遺傳演算法來創造可以像人類一樣行動的自主學習機器人，其執行的任務可以是做飯、洗衣服等等。

相關資源：

論文 Genetic Algorithms for Auto-tuning Mobile Robot Motion Control

地址：https://pdfs.semanticscholar.org/7c8c/faa78795bcba8e72cd56f8b8e3b95c0df20c.pdf

7. 結語

希望透過本文介紹，你現在已經對遺傳演算法有了足夠的理解，而且也會用TPOT庫來實現它了。但是如果你不親身實踐，本文的知識也是非常有限的。

所以，請各位讀者朋友一定要在無論是資料科學比賽或是生活中嘗試自己去實現它。