數(shù)據(jù)驅(qū)動的進化優(yōu)化是什么，僅僅就是數(shù)據(jù) + 優(yōu)化算法嗎?數(shù)據(jù)驅(qū)動的進化優(yōu)化適用于哪些應(yīng)用場景?傳統(tǒng)的數(shù)學(xué)優(yōu)化方法是否迎來了新一輪的挑戰(zhàn)。本文將為您深入淺出的解答以上問題。文末我們還附上了相關(guān)資料與參考文獻的大禮包，這些資料并非一個簡單的書單，是經(jīng)過本文兩位作者多年的研究經(jīng)驗和學(xué)習歷程精心挑選整理的，有***期刊的優(yōu)質(zhì)論文，也有科普大眾的通俗講義。

我們會收集相關(guān)的數(shù)據(jù)驅(qū)動優(yōu)化經(jīng)典文獻和進化計算相關(guān)的課程 PPT 等資料做成網(wǎng)盤鏈接放到后邊。

先說一說 數(shù)據(jù)驅(qū)動進化優(yōu)化的 Motivation

簡單來說，數(shù)據(jù)驅(qū)動的進化優(yōu)化(Data-driven evolutionary computation)就是借助數(shù)據(jù)和進化算法求解優(yōu)化問題。首先為什么用進化算法呢?舉幾個例子，一些優(yōu)化問題很難獲取其數(shù)學(xué)優(yōu)化模型的，如仿真實驗軟件，可以看成是黑箱的優(yōu)化問題。另有一些問題，雖然知道數(shù)學(xué)表達式，但是表達式存在非凸，不可導(dǎo)，不可微等性質(zhì)。這些問題很難用基于梯度的傳統(tǒng)數(shù)學(xué)優(yōu)化方法求解的，這時，智能優(yōu)化算法就隆重上場了，如遺傳算法，粒子群算法，差分算法等。

那為什么還要借助數(shù)據(jù)呢?我們知道，智能優(yōu)化算法都是基于種群迭代的優(yōu)化算法的，種群包含幾十個甚至幾百個的個體(每個個體就是一個解)，并且需要迭代幾百代才能找出比較好的解，這種情況下優(yōu)化問題就需要進行很多次評估(計算解的函數(shù)值)。比如說對于種群是 100，迭代次數(shù) 100 代的智能優(yōu)化算法，優(yōu)化問題就需要評估 10000 次!然而，有些優(yōu)化問題評估代價是很高的，比如風洞實驗評估一次就需要好幾個小時;又比如制藥工程，一次試藥過程需要話費昂貴的代價(一次試藥就關(guān)系到小白鼠的生命)。對于智能優(yōu)化算需要上千次及上萬次的評估，優(yōu)化問題是無法承受的，這種情況下，學(xué)者們就想出了利用優(yōu)化問題的歷史數(shù)據(jù)來輔助優(yōu)化過程，以減少優(yōu)化問題的評估次數(shù)，從而降低優(yōu)化問題評估的代價。

數(shù)據(jù)驅(qū)動進化優(yōu)化算法

那么，數(shù)據(jù)驅(qū)動的進化優(yōu)化是怎樣進行的呢?過程如圖 1 所示(來自文獻 [1])。先用優(yōu)化過程優(yōu)化問題(圖中的 Exact function evaluation，以下稱為真實優(yōu)化問題)產(chǎn)生的數(shù)據(jù)建立個模型，這個模型稱為代理模型(Surrogate)，所以以前數(shù)據(jù)驅(qū)動的進化優(yōu)化算法也叫代理模型輔助的進化優(yōu)化算法(Surrogate-Assisted Evolutionary Algorithm，SAEA)。代理模型的目的就是逼近真實問題。

在優(yōu)化過程中，這個代理模型和真實問題相互合作評估個體，這個相互合作就是所謂的模型管理(Surrogate Management)。代理模型和真實優(yōu)化問題相互合作有兩個方面的原因，一方面是代理模型由真實問題的數(shù)據(jù)訓(xùn)練得到，和真實問題有著相似性，用代理模型代替優(yōu)化問題對解進行評估，預(yù)選出真實問題的比較好的解，以減少真實問題的評估次數(shù)。另一方面是代理模型和真實問題存在偏差，用真實問題對解進行評估以防止代理模型誤導(dǎo)解偏離真實問題，將真實問題評估的解加入訓(xùn)練數(shù)據(jù)集(就是圖中的虛線那塊)修正代理模型。那么代理模型是怎么建立的?模型管理是什么呢?

圖 1. 數(shù)據(jù)驅(qū)動的進化優(yōu)化算法流程(來自文獻 1)

一般來說，機器學(xué)習的那些建模方法都可以拿來訓(xùn)練代理模型，如高斯過程，神經(jīng)網(wǎng)絡(luò)，SVM，RBF 還有各種集成模型。不過用的比較多的是高斯過程(講到后面模型管理就知道了)。

模型管理常用的方法在學(xué)術(shù)上稱為基于代和個體的混合方法。意思就是算法先以代理模型為優(yōu)化問題進行優(yōu)化若干代，然后從***一代中選取一部分個體重新送給真實問題重新評估。 這里的重點和難點(也是 SAEA 問題)是從代理模型中選擇出哪些解能夠快速輔助真實問題的收斂，也就是前面提到的怎樣預(yù)選出好的解。如何從代理模型中選擇真實問題評估解的策略在 SAEA 中有個專業(yè)名詞叫 Infill Sampling Criteria.

一個想法是選擇代理模型***的一部分解給真實問題重新評估，在這種情況下，如果代理模型足夠準確，也是就代理模型和真實優(yōu)化問題很近似，那么選擇出的這些解更有助于真實問題的收斂。如圖 2 所示。

圖 2. 選擇代理模型的***解

但是訓(xùn)練足夠準確的代理模型是不太現(xiàn)實的，特別是在 SAEA 中收集到的小數(shù)據(jù)。因此，另一種選擇重新評估解的方法就是選擇代理模型認為不確定的解(簡單的理解是離其它個體比較遠的那些個體)，如圖 3 所示(來自文獻 2)。這時就能體現(xiàn)出高斯過程的優(yōu)勢了，既能直接給出解的評估值還能給出評估值的確定性(一個講解高斯過程的網(wǎng)址http://www.ppvke.com/Blog/archives/24049)。選擇這些不確定的解有兩方面好處：這些個體所在的區(qū)域還很少被搜索(圖 3a)，傳遞給真實問題能夠提高真實問題的探索能力。另一個好處是由于這些個體分布在稀疏的區(qū)域，用真實問題評估過后加入訓(xùn)練集提高了訓(xùn)練集的多樣性，從而在在代理模型修正過程能很大程度提高代理模型的準確度(圖 3b)。

圖 3. 選擇代理模型最不確定的解(來自文獻 2)

***一種方法，也是最常用的方法是選擇那些兼顧上述兩種情況的個體。如高斯過程模型常用的 LCB 指標，ExI 指標如公式(1)和(2)。

對于其它不能給出解不準確度的模型，SAEA 研究領(lǐng)域提出了各種各樣的策略。比如說建立局部代理模型，選擇局部代理模型的***解;對于集成模型，用各個子模型評估的差異性代表個體評估的準確性等。

***真實問題的***解(集)就從訓(xùn)練集里面選出(真實問題評估過的解)。以上所述就是數(shù)據(jù)驅(qū)動進化優(yōu)化算法的簡單過程。詳細的介紹推薦綜述 [3] 和挑戰(zhàn)[4]。

進化算法 VS 數(shù)學(xué)優(yōu)化(以下的討論均基于單目標優(yōu)化問題)

上面的章節(jié)對數(shù)據(jù)驅(qū)動的進化優(yōu)化給出了一個簡單介紹，看到這里大家可能想問一下進化算法和數(shù)學(xué)優(yōu)化(如果不熟悉數(shù)學(xué)優(yōu)化是什么可以參考這篇文章https://zhuanlan.zhihu.com/p/25579864)各自的優(yōu)勢和不足是什么。實際上做進化算法和數(shù)學(xué)優(yōu)化都是為了解決優(yōu)化問題，但是出發(fā)的角度是有很大不同的，我們經(jīng)常會見到以下情景。

Round1 求解效果

進化算法只需計算目標函數(shù)的值即可，對優(yōu)化問題本身的性質(zhì)要求是非常低的，不會像數(shù)學(xué)優(yōu)化算法往往依賴于一大堆的條件，例如是否為凸優(yōu)化，目標函數(shù)是否可微，目標函數(shù)導(dǎo)數(shù)是否 Lipschitz continuity 等等。本人還曾經(jīng)研究過帶有偏微分方程約束的優(yōu)化問題，很多時候你根本就不知道那個目標函數(shù)凸不凸，可導(dǎo)不可導(dǎo)。這一點是進化算法相對數(shù)學(xué)優(yōu)化算法來說***的一個優(yōu)勢，實際上同時也是進化算法一個劣勢，因為不依賴問題的性質(zhì)(problem-independent)對所有問題都好使往往意味著沒有充分的利用不同問題的特性去進一步加速和優(yōu)化算法(這里很具有哲學(xué)辯證思想的是有優(yōu)點往往就會派生出缺點)。這樣看來數(shù)學(xué)優(yōu)化算法的條條框框?qū)嶋H上是劃定了，數(shù)學(xué)優(yōu)化算法的適用范圍，出了這個范圍好使不好使不知道，但是在這個范圍內(nèi)數(shù)學(xué)優(yōu)化就能給出一個基本的理論保證。

結(jié)論：對問題結(jié)構(gòu)確定的優(yōu)化問題，有充分的關(guān)于優(yōu)化問題的信息來利用的時候數(shù)學(xué)優(yōu)化一般來說有優(yōu)勢，例如線性規(guī)劃，二次規(guī)劃，凸優(yōu)化等等。反之，可能使用進化算法就會有優(yōu)勢。對于一些數(shù)學(xué)優(yōu)化目前不能徹底解決的問題例如 NP hard 問題，進化算法也有很大的應(yīng)用前景。

Round2 求解速率

進化算法的計算速度比較慢一直是大家的共識，這一點也很好理解，每迭代一次都需要計算 M 次目標函數(shù)，M 是種群規(guī)模一般是 30-50 左右。進化算法的前沿的研究方向其中一個就是針對大規(guī)模優(yōu)化問題的(large-scale), 我也曾查閱過相關(guān)***期刊的論文發(fā)現(xiàn)進化算法里的 large-scale 的規(guī)模對數(shù)學(xué)優(yōu)化算法來講可能根本構(gòu)不成 large-scale。所以側(cè)面反應(yīng)出了進化算法在計算速度的瓶頸限制了其在大規(guī)模優(yōu)化問題上的應(yīng)用。值得一提的是近幾年來隨著深度學(xué)習的崛起，人們對計算力的要求越來越高，基于 GPU 的并行計算和分布式計算的架構(gòu)被廣泛的應(yīng)用到人工智能的各個領(lǐng)域。由于進化算法本身天生具有良好的并行特性，基于 GPU 并行計算的進化算法是否能夠在一定程度上解決進化算法速度慢的問題絕對是一個值得研究的 topic。

綜上所述：進化算法也好，數(shù)學(xué)優(yōu)化也好都只是認識問題解決問題的工具之一，工具本身并不存在絕對的優(yōu)劣之分，每種工具都有其適用的場景，辨別它們的長短，找到它們合適的應(yīng)用場景是我們這些用工具的人應(yīng)該做的。

小結(jié)

數(shù)據(jù)驅(qū)動進化優(yōu)化算法用來解決計算代價昂貴的問題，也有看到應(yīng)用在其它優(yōu)化領(lǐng)域，如魯棒優(yōu)化問題，大規(guī)模優(yōu)化問題等，因為這些問題求解過程也耗費大量計算時間，其本質(zhì)還是減少真實問題的評估次數(shù)。此外，離線的數(shù)據(jù)驅(qū)動優(yōu)化也開始研究(也稱為仿真優(yōu)化)[1]，也就是說優(yōu)化過程中只能使用代理模型，無法用真實問題驗證。