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

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

先說(shuō)一說(shuō) 數(shù)據(jù)驅(qū)動(dòng)進(jìn)化優(yōu)化的 Motivation

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

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

數(shù)據(jù)驅(qū)動(dòng)進(jìn)化優(yōu)化算法

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

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

圖 1. 數(shù)據(jù)驅(qū)動(dòng)的進(jìn)化優(yōu)化算法流程(來(lái)自文獻(xiàn) 1)

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

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

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

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

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

圖 3. 選擇代理模型最不確定的解(來(lái)自文獻(xiàn) 2)

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

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

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

進(jìn)化算法 VS 數(shù)學(xué)優(yōu)化(以下的討論均基于單目標(biāo)優(yōu)化問(wèn)題)

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

Round1 求解效果

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

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

Round2 求解速率

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

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

小結(jié)

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