幾天前，我著手解決一個(gè)實(shí)際問(wèn)題——大型超市銷(xiāo)售問(wèn)題。在使用了幾個(gè)簡(jiǎn)單模型做了一些特征工程之后，我在排行榜上名列第 219 名。

雖然結(jié)果不錯(cuò)，但是我還是想做得更好。于是，我開(kāi)始研究可以提高分?jǐn)?shù)的優(yōu)化方法。結(jié)果我果然找到了一個(gè)，它叫遺傳算法。在把它應(yīng)用到超市銷(xiāo)售問(wèn)題之后，最終我的分?jǐn)?shù)在排行榜上一下躍居前列。

沒(méi)錯(cuò)，僅靠遺傳算法我就從 219 名直接跳到 15 名，厲害吧！相信閱讀完本篇文章后，你也可以很自如地應(yīng)用遺傳算法，而且會(huì)發(fā)現(xiàn)，當(dāng)把它用到你自己正在處理的問(wèn)題時(shí)，效果也會(huì)有很大提升。

目錄

1、遺傳算法理論的由來(lái)

2、生物學(xué)的啟發(fā)

3、遺傳算法定義

4、遺傳算法具體步驟

• 初始化

• 適應(yīng)度函數(shù)

• 選擇

• 交叉

• 變異

5、遺傳算法的應(yīng)用

• 特征選取

• 使用TPOT庫(kù)實(shí)現(xiàn)

6、實(shí)際應(yīng)用

7、結(jié)語(yǔ)

1、遺傳算法理論的由來(lái)

我們先從查爾斯·達(dá)爾文的一句名言開(kāi)始：

能夠生存下來(lái)的往往不是最強(qiáng)大的物種，也不是最聰明的物種，而是最能適應(yīng)環(huán)境的物種。

你也許在想：這句話(huà)和遺傳算法有什么關(guān)系？其實(shí)遺傳算法的整個(gè)概念就基于這句話(huà)。

讓我們用一個(gè)基本例子來(lái)解釋?zhuān)?/span>

我們先假設(shè)一個(gè)情景，現(xiàn)在你是一國(guó)之王，為了讓你的國(guó)家免于災(zāi)禍，你實(shí)施了一套法案：

• 你選出所有的好人，要求其通過(guò)生育來(lái)擴(kuò)大國(guó)民數(shù)量。

• 這個(gè)過(guò)程持續(xù)進(jìn)行了幾代。

• 你將發(fā)現(xiàn)，你已經(jīng)有了一整群的好人。

這個(gè)例子雖然不太可能，但是我用它是想幫助你理解概念。也就是說(shuō)，我們改變了輸入值（比如：人口），就可以獲得更好的輸出值（比如：更好的國(guó)家）。現(xiàn)在，我假定你已經(jīng)對(duì)這個(gè)概念有了大致理解，認(rèn)為遺傳算法的含義應(yīng)該和生物學(xué)有關(guān)系。那么我們就快速地看一些小概念，這樣便可以將其聯(lián)系起來(lái)理解。

2、生物學(xué)的啟發(fā)

相信你還記得這句話(huà)：「細(xì)胞是所有生物的基石。」由此可知，在一個(gè)生物的任何一個(gè)細(xì)胞中，都有著相同的一套染色體。所謂染色體，就是指由 DNA 組成的聚合體。

傳統(tǒng)上看，這些染色體可以被由數(shù)字0和 1 組成的字符串表達(dá)出來(lái)。

一條染色體由基因組成，這些基因其實(shí)就是組成 DNA 的基本結(jié)構(gòu)，DNA 上的每個(gè)基因都編碼了一個(gè)獨(dú)特的性狀，比如，頭發(fā)或者眼睛的顏色。希望你在繼續(xù)閱讀之前先回憶一下這里提到的生物學(xué)概念。結(jié)束了這部分，現(xiàn)在我們來(lái)看看所謂遺傳算法實(shí)際上指的是什么？

3、遺傳算法定義

首先我們回到前面討論的那個(gè)例子，并總結(jié)一下我們做過(guò)的事情。

1. 首先，我們?cè)O(shè)定好了國(guó)民的初始人群大小。

2. 然后，我們定義了一個(gè)函數(shù)，用它來(lái)區(qū)分好人和壞人。

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

4. 最后，這些后代們從原來(lái)的國(guó)民中替代了部分壞人，并不斷重復(fù)這一過(guò)程。

遺傳算法實(shí)際上就是這樣工作的，也就是說(shuō)，它基本上盡力地在某種程度上模擬進(jìn)化的過(guò)程。

因此，為了形式化定義一個(gè)遺傳算法，我們可以將它看作一個(gè)優(yōu)化方法，它可以嘗試找出某些輸入，憑借這些輸入我們便可以得到最佳的輸出值或者是結(jié)果。遺傳算法的工作方式也源自于生物學(xué)，具體流程見(jiàn)下圖：

那么現(xiàn)在我們來(lái)逐步理解一下整個(gè)流程。

4、遺傳算法具體步驟

為了讓講解更為簡(jiǎn)便，我們先來(lái)理解一下著名的組合優(yōu)化問(wèn)題「背包問(wèn)題」。如果你還不太懂，這里有一個(gè)我的解釋版本。

比如，你準(zhǔn)備要去野游 1 個(gè)月，但是你只能背一個(gè)限重 30公斤的背包。現(xiàn)在你有不同的必需物品，它們每一個(gè)都有自己的「生存點(diǎn)數(shù)」（具體在下表中已給出）。因此，你的目標(biāo)是在有限的背包重量下，最大化你的「生存點(diǎn)數(shù)」。

4.1初始化

這里我們用遺傳算法來(lái)解決這個(gè)背包問(wèn)題。第一步是定義我們的總體。總體中包含了個(gè)體，每個(gè)個(gè)體都有一套自己的染色體。

我們知道，染色體可表達(dá)為二進(jìn)制數(shù)串，在這個(gè)問(wèn)題中，1 代表接下來(lái)位置的基因存在，0意味著丟失。（譯者注：作者這里借用染色體、基因來(lái)解決前面的背包問(wèn)題，所以特定位置上的基因代表了上方背包問(wèn)題表格中的物品，比如第一個(gè)位置上是 Sleeping Bag，那么此時(shí)反映在染色體的『基因』位置就是該染色體的第一個(gè)『基因』。）

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

4.2適應(yīng)度函數(shù)

接下來(lái)，讓我們來(lái)計(jì)算一下前兩條染色體的適應(yīng)度分?jǐn)?shù)。對(duì)于 A1 染色體[100110]而言，有：

類(lèi)似地，對(duì)于 A2 染色體[001110]來(lái)說(shuō)，有：

對(duì)于這個(gè)問(wèn)題，我們認(rèn)為，當(dāng)染色體包含更多生存分?jǐn)?shù)時(shí)，也就意味著它的適應(yīng)性更強(qiáng)。

因此，由圖可知，染色體 1 適應(yīng)性強(qiáng)于染色體 2。

4.3選擇

現(xiàn)在，我們可以開(kāi)始從總體中選擇適合的染色體，來(lái)讓它們互相『交配』，產(chǎn)生自己的下一代了。這個(gè)是進(jìn)行選擇操作的大致想法，但是這樣將會(huì)導(dǎo)致染色體在幾代之后相互差異減小，失去了多樣性。因此，我們一般會(huì)進(jìn)行「輪盤(pán)賭選擇法」（Roulette Wheel Selection method）。

想象有一個(gè)輪盤(pán)，現(xiàn)在我們將它分割成 m 個(gè)部分，這里的 m 代表我們總體中染色體的個(gè)數(shù)。每條染色體在輪盤(pán)上占有的區(qū)域面積將根據(jù)適應(yīng)度分?jǐn)?shù)成比例表達(dá)出來(lái)。

基于上圖中的值，我們建立如下「輪盤(pán)」。

現(xiàn)在，這個(gè)輪盤(pán)開(kāi)始旋轉(zhuǎn)，我們將被圖中固定的指針（fixed point）指到的那片區(qū)域選為第一個(gè)親本。然后，對(duì)于第二個(gè)親本，我們進(jìn)行同樣的操作。有時(shí)候我們也會(huì)在途中標(biāo)注兩個(gè)固定指針，如下圖：

通過(guò)這種方法，我們可以在一輪中就獲得兩個(gè)親本。我們將這種方法成為「隨機(jī)普遍選擇法」（Stochastic Universal Selection method）。

4.4交叉

在上一個(gè)步驟中，我們已經(jīng)選擇出了可以產(chǎn)生后代的親本染色體。那么用生物學(xué)的話(huà)說(shuō)，所謂「交叉」，其實(shí)就是指的繁殖。現(xiàn)在我們來(lái)對(duì)染色體 1 和 4（在上一個(gè)步驟中選出來(lái)的）進(jìn)行「交叉」，見(jiàn)下圖：

這是交叉最基本的形式，我們稱(chēng)其為「單點(diǎn)交叉」。這里我們隨機(jī)選擇一個(gè)交叉點(diǎn)，然后，將交叉點(diǎn)前后的染色體部分進(jìn)行染色體間的交叉對(duì)調(diào)，于是就產(chǎn)生了新的后代。

如果你設(shè)置兩個(gè)交叉點(diǎn)，那么這種方法被成為「多點(diǎn)交叉」，見(jiàn)下圖：

4.5變異

如果現(xiàn)在我們從生物學(xué)的角度來(lái)看這個(gè)問(wèn)題，那么請(qǐng)問(wèn)：由上述過(guò)程產(chǎn)生的后代是否有和其父母一樣的性狀呢？答案是否。在后代的生長(zhǎng)過(guò)程中，它們體內(nèi)的基因會(huì)發(fā)生一些變化，使得它們與父母不同。這個(gè)過(guò)程我們稱(chēng)為「變異」，它可以被定義為染色體上發(fā)生的隨機(jī)變化，正是因?yàn)樽儺悾N群中才會(huì)存在多樣性。

下圖為變異的一個(gè)簡(jiǎn)單示例：

變異完成之后，我們就得到了新為個(gè)體，進(jìn)化也就完成了，整個(gè)過(guò)程如下圖：

在進(jìn)行完一輪「遺傳變異」之后，我們用適應(yīng)度函數(shù)對(duì)這些新的后代進(jìn)行驗(yàn)證，如果函數(shù)判定它們適應(yīng)度足夠，那么就會(huì)用它們從總體中替代掉那些適應(yīng)度不夠的染色體。這里有個(gè)問(wèn)題，我們最終應(yīng)該以什么標(biāo)準(zhǔn)來(lái)判斷后代達(dá)到了最佳適應(yīng)度水平呢？

一般來(lái)說(shuō)，有如下幾個(gè)終止條件：

1. 在進(jìn)行 X 次迭代之后，總體沒(méi)有什么太大改變。

2. 我們事先為算法定義好了進(jìn)化的次數(shù)。

3. 當(dāng)我們的適應(yīng)度函數(shù)已經(jīng)達(dá)到了預(yù)先定義的值。

好了，現(xiàn)在我假設(shè)你已基本理解了遺傳算法的要領(lǐng)，那么現(xiàn)在讓我們用它在數(shù)據(jù)科學(xué)的場(chǎng)景中應(yīng)用一番。

5、遺傳算法的應(yīng)用

5.1特征選取

試想一下每當(dāng)你參加一個(gè)數(shù)據(jù)科學(xué)比賽，你會(huì)用什么方法來(lái)挑選那些對(duì)你目標(biāo)變量的預(yù)測(cè)來(lái)說(shuō)很重要的特征呢？你經(jīng)常會(huì)對(duì)模型中特征的重要性進(jìn)行一番判斷，然后手動(dòng)設(shè)定一個(gè)閾值，選擇出其重要性高于這個(gè)閾值的特征。

那么，有沒(méi)有什么方法可以更好地處理這個(gè)問(wèn)題呢？其實(shí)處理特征選取任務(wù)最先進(jìn)的算法之一就是遺傳算法。

我們前面處理背包問(wèn)題的方法可以完全應(yīng)用到這里。現(xiàn)在，我們還是先從建立「染色體」總體開(kāi)始，這里的染色體依舊是二進(jìn)制數(shù)串，「1」表示模型包含了該特征，「0表示模型排除了該特征」。

不過(guò)，有一個(gè)不同之處，即我們的適應(yīng)度函數(shù)需要改變一下。這里的適應(yīng)度函數(shù)應(yīng)該是這次比賽的的精度的標(biāo)準(zhǔn)。也就是說(shuō)，如果染色體的預(yù)測(cè)值越精準(zhǔn)，那么就可以說(shuō)它的適應(yīng)度更高。

現(xiàn)在我假設(shè)你已經(jīng)對(duì)這個(gè)方法有點(diǎn)一概念了。下面我不會(huì)馬上講解這個(gè)問(wèn)題的解決過(guò)程，而是讓我們先來(lái)用 TPOT 庫(kù)去實(shí)現(xiàn)它。

5.2用TPOT庫(kù)來(lái)實(shí)現(xiàn)

這個(gè)部分相信是你在一開(kāi)始讀本文時(shí)心里最終想實(shí)現(xiàn)的那個(gè)目標(biāo)。即：實(shí)現(xiàn)。那么首先我們來(lái)快速瀏覽一下 TPOT 庫(kù)（Tree-based Pipeline Optimisation Technique，樹(shù)形傳遞優(yōu)化技術(shù)），該庫(kù)基于 scikit-learn 庫(kù)建立。下圖為一個(gè)基本的傳遞結(jié)構(gòu)。

圖中的灰色區(qū)域用 TPOT 庫(kù)實(shí)現(xiàn)了自動(dòng)處理。實(shí)現(xiàn)該部分的自動(dòng)處理需要用到遺傳算法。

我們這里不深入講解，而是直接應(yīng)用它。為了能夠使用 TPOT 庫(kù)，你需要先安裝一些 TPOT 建立于其上的 python 庫(kù)。下面我們快速安裝它們：

# installing DEAP, update_checker and tqdm 

pip install deap update_checker tqdm
# installling TPOT 
pip install tpot

這里，我用了 Big Mart Sales（數(shù)據(jù)集地址：https://datahack.analyticsvidhya.com/contest/practice-problem-big-mart-sales-iii/）數(shù)據(jù)集，為實(shí)現(xiàn)做準(zhǔn)備，我們先快速下載訓(xùn)練和測(cè)試文件，以下是 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'] = 0combi = 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')

一旦這些代碼運(yùn)行完成，tpot_exported_pipeline.py 里就將會(huì)放入用于路徑優(yōu)化的 python 代碼。我們可以發(fā)現(xiàn)，ExtraTreeRegressor 可以最好地解決這個(gè)問(wèn)題。

## 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)

如果你提交了這個(gè) csv，那么你會(huì)發(fā)現(xiàn)我一開(kāi)始保證的那些還沒(méi)有完全實(shí)現(xiàn)。那是不是我在騙你們呢？當(dāng)然不是。實(shí)際上，TPOT 庫(kù)有一個(gè)簡(jiǎn)單的規(guī)則。如果你不運(yùn)行 TPOT 太久，那么它就不會(huì)為你的問(wèn)題找出最可能傳遞方式。

所以，你得增加進(jìn)化的代數(shù)，拿杯咖啡出去走一遭，其它的交給 TPOT 就行。此外，你也可以用這個(gè)庫(kù)來(lái)處理分類(lèi)問(wèn)題。進(jìn)一步內(nèi)容可以參考這個(gè)文檔：http://rhiever.github.io/tpot/。除了比賽，在生活中我們也有很多應(yīng)用場(chǎng)景可以用到遺傳算法。

6、實(shí)際應(yīng)用

遺傳算法在真實(shí)世界中有很多應(yīng)用。這里我列了部分有趣的場(chǎng)景，但是由于篇幅限制，我不會(huì)逐一詳細(xì)介紹。

6.1工程設(shè)計(jì)

工程設(shè)計(jì)非常依賴(lài)計(jì)算機(jī)建模以及模擬，這樣才能讓設(shè)計(jì)周期過(guò)程即快又經(jīng)濟(jì)。遺傳算法在這里可以進(jìn)行優(yōu)化并給出一個(gè)很好的結(jié)果。

相關(guān)資源：

• 論文：Engineering design using genetic algorithms

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

6.2交通與船運(yùn)路線（TravellingSalesmanProblem，巡回售貨員問(wèn)題）

這是一個(gè)非常著名的問(wèn)題，它已被很多貿(mào)易公司用來(lái)讓運(yùn)輸更省時(shí)、經(jīng)濟(jì)。解決這個(gè)問(wèn)題也要用到遺傳算法。

6.3機(jī)器人

遺傳算法在機(jī)器人領(lǐng)域中的應(yīng)用非常廣泛。實(shí)際上，目前人們正在用遺傳算法來(lái)創(chuàng)造可以像人類(lèi)一樣行動(dòng)的自主學(xué)習(xí)機(jī)器人，其執(zhí)行的任務(wù)可以是做飯、洗衣服等等。

相關(guān)資源：

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

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

7、結(jié)語(yǔ)

希望通過(guò)本文介紹，你現(xiàn)在已經(jīng)對(duì)遺傳算法有了足夠的理解，而且也會(huì)用 TPOT 庫(kù)來(lái)實(shí)現(xiàn)它了。但是如果你不親身實(shí)踐，本文的知識(shí)也是非常有限的。

所以，請(qǐng)各位讀者朋友一定要在無(wú)論是數(shù)據(jù)科學(xué)比賽或是生活中嘗試自己去實(shí)現(xiàn)它

審核編輯 ：李倩