演化策略是一種求解參數(shù)優(yōu)化問(wèn)題的方法，所以我先介紹一下什么是優(yōu)化。

(資料圖片)

1. 優(yōu)化（Optimization）

優(yōu)化就是計(jì)算一個(gè)函數(shù)的最大值或者最小值的問(wèn)題，下面以求解單變量的最小值為例進(jìn)行介紹。

假設(shè)函數(shù)f(x)的具體表達(dá)式是未知的，把它看作一個(gè)黑盒函數(shù)，我們只能通過(guò)向盒子輸入得到輸出。它可能存在局部最小點(diǎn)和全局最小點(diǎn)，很顯然進(jìn)行坐標(biāo)點(diǎn)窮舉然后對(duì)比出最小值的方法是不可行的，這時(shí)就需要我們根據(jù)一定的策略一步步地向我們的最小值逼近，不同策略就對(duì)應(yīng)著不同的優(yōu)化算法。

因?yàn)?，在機(jī)器學(xué)習(xí)的過(guò)程中，根據(jù)我們搭建的模型并不是一開(kāi)始就能根據(jù)輸入獲得我們想要的結(jié)果，所以就需要對(duì)我們的模型進(jìn)行優(yōu)化，以使誤差函數(shù)值（loss）達(dá)到最小或者適應(yīng)度函數(shù)值（fitness）達(dá)到最大。優(yōu)化分為黑盒優(yōu)化和白盒優(yōu)化。

黑盒優(yōu)化：所謂的黑盒優(yōu)化就是指尋找黑盒函數(shù)的全局最優(yōu)化解。非形式化的來(lái)說(shuō)，一個(gè)黑盒函數(shù)F 可以理解為從 輸入 X(x1,x2,x3...) 到 輸出 的一個(gè)映射.但是映射關(guān)系F的具體表達(dá)式及梯度信息均未知，我們只能通過(guò)不斷地將數(shù)據(jù)輸入到黑盒函數(shù)中然后通過(guò)得到的輸出值來(lái)猜測(cè)黑盒函數(shù)的結(jié)構(gòu)信息。下圖表示一個(gè)黑盒問(wèn)題的映射關(guān)系。

1.2 黑盒優(yōu)化方法

介紹超參數(shù)優(yōu)化之前先介紹一下參數(shù)的概念。模型中的參數(shù)分為模型參數(shù)和超參數(shù)，模型參數(shù)就是我們的模型根據(jù)訓(xùn)練數(shù)據(jù)訓(xùn)練學(xué)習(xí)到的參數(shù)，不需要人為設(shè)定；而超參數(shù)是模型開(kāi)始訓(xùn)練前人為設(shè)定的參數(shù)，通過(guò)不斷調(diào)整超參數(shù)使模型最后的輸出越來(lái)越復(fù)合我們的預(yù)期，下面三種是常見(jiàn)的超參數(shù)優(yōu)化方法（屬于黑盒優(yōu)化）。

1.2.1 網(wǎng)格搜索（Grid Search）

以機(jī)器學(xué)習(xí)中的分類(lèi)問(wèn)題為例，在模型訓(xùn)練過(guò)程中，我們通常需要多次調(diào)整超參數(shù)以使我們的輸出準(zhǔn)確率更高，如果涉及到參數(shù)過(guò)多就需要多次的人工修改，這時(shí)我們可以采用網(wǎng)格搜索---也就是多參數(shù)的交叉組合，從而在所有組合中一次性找出最優(yōu)超參數(shù)，比如我們有兩個(gè)超參數(shù)，設(shè)定超參數(shù)x的范圍(0,1),步長(zhǎng)0.3，y的范圍(0,1),步長(zhǎng)0.3，那么兩個(gè)超參數(shù)的組合方式有3*3=9種。

1.2.2 隨機(jī)搜索（Random Search）

與網(wǎng)格搜索相比，隨機(jī)搜索并未嘗試所有參數(shù)值，而是從指定的分布中采樣固定數(shù)量的參數(shù)設(shè)置。它的理論依據(jù)是，如果隨機(jī)樣本點(diǎn)集足夠大，那么也可以找到最優(yōu)的超參數(shù)，或它的近似值。通過(guò)對(duì)搜索范圍的隨機(jī)取樣，隨機(jī)搜索一般會(huì)比網(wǎng)格搜索要快一些，以了sklearn中的RandomizedSearchCV接口通過(guò)設(shè)定n_iter 的值來(lái)決定采樣的數(shù)量。

1.3 網(wǎng)格搜索和隨機(jī)搜索遇到的問(wèn)題

1.2.3貝葉斯優(yōu)化（Bayesian Optimization）

網(wǎng)格搜索窮舉地搜索整個(gè)超參數(shù)空間，隨著待優(yōu)化超參數(shù)的增加計(jì)算量呈指數(shù)增長(zhǎng)，速度非常慢。而對(duì)于隨機(jī)搜索來(lái)說(shuō)，進(jìn)行稀疏的簡(jiǎn)單隨機(jī)抽樣并不會(huì)遇到該問(wèn)題，但采樣過(guò)少很難找到全局最優(yōu)解。貝葉斯優(yōu)化算法能很好地解決前兩種搜索算法遇到的問(wèn)題。貝葉斯優(yōu)化能利用先驗(yàn)知識(shí)動(dòng)態(tài)縮小超參數(shù)搜索空間，并且迭代次數(shù)少，速度更快。

下面簡(jiǎn)單介紹一下貝葉斯優(yōu)化：

首先明確我們的目標(biāo)，通過(guò)不斷調(diào)整輸入（超參數(shù)）來(lái)最大化目標(biāo)函數(shù)值（比如對(duì)于線(xiàn)性回歸調(diào)優(yōu)時(shí)的評(píng)估函數(shù)是均方誤差（fitness），我們的目標(biāo)就是最大化 -1*fitness），也即我們的目標(biāo)并不是使用盡可能多的數(shù)據(jù)點(diǎn)完全推斷未知的目標(biāo)函數(shù)，而是希望能求得最大化目標(biāo)函數(shù)值的參數(shù)。

貝葉斯優(yōu)化用于機(jī)器學(xué)習(xí)調(diào)參的主要思想是：給定優(yōu)化的目標(biāo)函數(shù)(廣義的函數(shù)，只需指定輸入和輸出即可，無(wú)需知道具體的函數(shù)形式)，根據(jù)已知的樣本點(diǎn)在函數(shù)上的分布（先驗(yàn)知識(shí)）不斷地添加樣本點(diǎn)來(lái)更新目標(biāo)函數(shù)的最大值。

上圖可以直觀地解釋貝葉斯優(yōu)化。其中紅色的曲線(xiàn)為實(shí)際的目標(biāo)函數(shù)，并且我們并不知道該函數(shù)確切的表達(dá)式。所以我們希望使用高斯過(guò)程逼近該目標(biāo)函數(shù)。把采樣點(diǎn)（上圖有 4 個(gè)抽樣點(diǎn)）根據(jù)高斯過(guò)程我們能夠得出綠色的置信區(qū)間，即目標(biāo)曲線(xiàn)最有可能處于的區(qū)域。從上面的先驗(yàn)知識(shí)中，我們確定了第二個(gè)點(diǎn)（f+）為最大的樣本觀察值，所以下一個(gè)最大點(diǎn)應(yīng)該要比它大或至少與之相等。因此，我們繪制出一條藍(lán)線(xiàn)，并且下一個(gè)最大點(diǎn)應(yīng)該位于這一條藍(lán)線(xiàn)之上。因此，下一個(gè)采樣在交叉點(diǎn) f+和置信域之間，我們能假定在 f+點(diǎn)以下的樣本是可以丟棄的，因?yàn)槲覀冎恍枰阉髁钅繕?biāo)函數(shù)取極大值的參數(shù)。所以現(xiàn)在我們就縮小了觀察區(qū)域，我們會(huì)迭代這一過(guò)程，直到搜索到最優(yōu)解。（有關(guān)網(wǎng)格搜索、隨機(jī)搜索、貝葉斯優(yōu)化的具體實(shí)例代碼及函數(shù)可以跳轉(zhuǎn)https://www.jianshu.com/p/5378ef009cae）

1.4 梯度優(yōu)化

在高數(shù)課本中我們可以找到梯度這個(gè)概念， 梯度是一個(gè)矢量，是函數(shù)一個(gè)點(diǎn)上導(dǎo)數(shù)最大值的方向，也就是函數(shù)值在該方向上變化最快，因此只要隨著梯度的方向，便能最快的到達(dá)極值點(diǎn)。梯度下降（gradient descent）的方法就是這么得來(lái)的。梯度下降法的基本思想可以類(lèi)比為一個(gè)下山的過(guò)程：想象我們?cè)谏巾?，只要我們每一步都沿著最陡的方向邁出下一步，那么我們一定可以最快到達(dá)山腳。因此，找到了梯度，我們也需要小心注意步長(zhǎng)值，若步長(zhǎng)值太大，我們可能一步邁出過(guò)大，錯(cuò)過(guò)了極值點(diǎn)，若步長(zhǎng)值太小，我們到達(dá)極值點(diǎn)的次數(shù)會(huì)增加。

1.4.1 隨機(jī)梯度下降（SAG）

在模型訓(xùn)練的過(guò)程中，梯度下降是常用的最小化誤差函數(shù)loss的方法。一般而言，梯度下降需要在遍歷所有的數(shù)據(jù)后才進(jìn)行梯度計(jì)算然后更新參數(shù)。假設(shè)現(xiàn)有數(shù)據(jù)集有10,000條數(shù)據(jù)，那么在這10,000條數(shù)據(jù)都進(jìn)行訓(xùn)練之后才會(huì)確定梯度，這樣的計(jì)算會(huì)耗時(shí)很長(zhǎng)。

隨機(jī)梯度下降也稱(chēng)小批量梯度下降（mini-batch gradient decent），它解決了需要遍歷所有數(shù)據(jù)才更新一次參數(shù)的問(wèn)題。隨機(jī)梯度下降根據(jù)每一個(gè)小批量數(shù)據(jù)進(jìn)行更新參數(shù)。也就是說(shuō)，10,000個(gè)數(shù)據(jù)，假設(shè)分成10個(gè)批量，每個(gè)批量是1,000個(gè)數(shù)據(jù)，那么在遍歷完每個(gè)批量后，計(jì)算這個(gè)小批量的梯度然后進(jìn)行更新參數(shù)，這樣在遍歷完10,000個(gè)多有數(shù)據(jù)后，梯度下降實(shí)際上已經(jīng)進(jìn)行了十次，相比于普通梯度下降而言，速度快了10倍。實(shí)驗(yàn)結(jié)果表明，在數(shù)據(jù)打亂情況下，隨機(jī)梯度下降的每一個(gè)批量是可以很好近似整個(gè)數(shù)據(jù)集的。隨機(jī)梯度下降的參數(shù)更新公示如下,gt為目標(biāo)函數(shù)關(guān)于參數(shù)w的梯度：

1.4.2  SAG + Momentum

SGD最大的缺點(diǎn)是下降速度慢，而且可能會(huì)在溝壑的兩邊持續(xù)震蕩，停留在一個(gè)局部最優(yōu)點(diǎn)。為了抑制SGD的震蕩，Momentum 通過(guò)保持前一步的行動(dòng)勢(shì)頭從而加速誤差函數(shù)loss的收斂過(guò)程。如果當(dāng)前一步與前一步的方向保持一致，那么即將邁出的步伐就會(huì)大一些，如果方向不一致則會(huì)因?yàn)槭艿缴弦徊降臋?quán)值影響減小反方向的步伐，從而對(duì)傳統(tǒng)的梯度下降產(chǎn)生優(yōu)化。

α表示的是學(xué)習(xí)率（learning rate），也就是下山例子中的步長(zhǎng)值，所以學(xué)習(xí)率的設(shè)置影響著優(yōu)化過(guò)程，通常設(shè)為0-0.1之間。v是實(shí)際邁出的步長(zhǎng)，w是待優(yōu)化的目標(biāo)函數(shù)。

1.4.3 自適應(yīng)矩估計(jì)（Adam）

Adam （ adaptive moment estimation）自適應(yīng)矩估計(jì)算法是目前比較流行的一種優(yōu)化算法 ，于2015 年在ICLR論文 Adam: A Method for Stochastic Optimisation被提出。Adam 算法根據(jù)梯度grad的一階動(dòng)量和二階動(dòng)量動(dòng)態(tài)調(diào)整步長(zhǎng)。動(dòng)量我理解為歷史上每一代t 的梯度對(duì)下一步步長(zhǎng)的影響程度。Adam算法的步驟如下：

首先定義：待優(yōu)化參數(shù)： w，目標(biāo)函數(shù)： f(w) ，初始學(xué)習(xí)率 α。

而后，開(kāi)始進(jìn)行迭代優(yōu)化。對(duì)每一代 t ：

1.計(jì)算目標(biāo)函數(shù)關(guān)于當(dāng)前參數(shù)的梯度：

2.根據(jù)歷史梯度計(jì)算一階動(dòng)量和二階動(dòng)量：

3.

4.計(jì)算當(dāng)前時(shí)刻的下降梯度:

5.根據(jù)下降梯度進(jìn)行更新：

當(dāng)優(yōu)化的參數(shù)w只有一個(gè)時(shí)梯度就是函數(shù)的導(dǎo)數(shù)，當(dāng)參數(shù)有多個(gè)時(shí)梯度就變成了了向量，上面四步所求的也均為向量。算法中的一階動(dòng)量mt就是參考的momentum防止產(chǎn)生震蕩，最原始的二階動(dòng)量形式為，對(duì)于經(jīng)常更新的參數(shù)，我們已經(jīng)積累了大量關(guān)于它的知識(shí)，不希望被單個(gè)樣本影響太大，希望學(xué)習(xí)速率慢一些；對(duì)于偶爾更新的參數(shù)，我們了解的信息太少，希望能從每個(gè)偶然出現(xiàn)的樣本身上多學(xué)一些，即學(xué)習(xí)速率大一些。但是因?yàn)閂t 是單調(diào)遞增的，會(huì)使得學(xué)習(xí)率單調(diào)遞減至0，可能會(huì)使得訓(xùn)練過(guò)程提前結(jié)束，所以我們參考momentum關(guān)于一階動(dòng)量的公式對(duì)Vt進(jìn)行修改，避免了二階動(dòng)量持續(xù)累積、防止訓(xùn)練過(guò)程提前結(jié)束。 第三步的目的是解決訓(xùn)練剛開(kāi)始初始化Mt=0，Vt=0時(shí)梯度變化很小的問(wèn)題。可以將第四步的看做學(xué)習(xí)率，β1、β2為衰減參數(shù)、epos（=1e-10）為防止動(dòng)量為0導(dǎo)致除0操作。

下面為大家介紹三種演化策略領(lǐng)域（ES）比較流行的黑盒優(yōu)化方法：協(xié)方差矩陣自適應(yīng)策略（CMA-ES）、自然進(jìn)化策略（NES）、強(qiáng)化學(xué)習(xí)（RL-ES）。

2.演化策略（Evolution Strategy , ES）

演化策略是一種在搜索空間中尋找最優(yōu)的解決方案的優(yōu)化技術(shù)，屬于演化算法大家庭中的一員，另外三個(gè)成員分別是遺傳算法(Genetic Algorithms)、遺傳編程（Genetic Programming）和演化編程(Evolution Programming)，他們當(dāng)中的靈感大多來(lái)自于自然界中的生物進(jìn)化。

在介紹演化策略的變體之前先講解一下ES的實(shí)現(xiàn)步驟：

1.生成由候選解決方案組成的種群。

2.依據(jù)適應(yīng)度函數(shù)評(píng)估種群中的每一個(gè)個(gè)體。

3.篩選出適應(yīng)度高的個(gè)體作為繁衍后代的父代。

4.通過(guò)重組和變異的方式產(chǎn)生下一代個(gè)體。

5.重復(fù)上述過(guò)程直到滿(mǎn)足進(jìn)化的終止條件（比如：達(dá)到指定迭代次數(shù) 或者找到適應(yīng)度值滿(mǎn)足要求的個(gè)體 或者種群進(jìn)化不再使使適應(yīng)度值變大）

這是一張演化策略與遺傳算法的差異對(duì)比，截?cái)噙x擇就是指從當(dāng)前種群個(gè)個(gè)體中將適應(yīng)度值較高的前個(gè)個(gè)體保留，其余淘汰。重組就是將選中的2或4個(gè)父體的均值作為新個(gè)體，變異一般是以選中的父體基準(zhǔn)隨機(jī)產(chǎn)生后代，父體與其后代符合均值為父體，某一方差的正態(tài)分布。

上圖是GA的框架流程圖，ES的流程圖只需將GA的遺傳操作部分進(jìn)行替換即可

下面以求解 黑盒函數(shù)f(x)的最小值 為例介紹Basic ES：

如果對(duì)截?cái)噙x擇、重組、變異的原理理解不太深刻，可以參考一下外文中針對(duì)多個(gè)自變量的目標(biāo)函數(shù)最小值問(wèn)題（25張幻燈片，就不往這里放了）

https://www.slideshare.net/OsamaSalaheldin2/cmaes-presentation

2.1 協(xié) 方 差 矩 陣 自 適 應(yīng) 進(jìn) 化 策 略 （CMA-ES）

CMA-ES（Covariance Matrix Adaptation-Evolutionary Strategies）是 在 演化策略 ( Evolution Strategy，ES) 的基礎(chǔ)上發(fā)展起來(lái)的一種高效搜索算法，它將 ES 的可靠性、全局性與自適應(yīng)協(xié)方差矩陣的高引導(dǎo)性結(jié)合起來(lái)，對(duì)求解非凸非線(xiàn)性?xún)?yōu)化問(wèn)題具有較強(qiáng)的適應(yīng)性，目前以其良好的尋優(yōu)性能在優(yōu)化領(lǐng)域備受關(guān)注。并且，在對(duì)全局優(yōu)化問(wèn)題（與進(jìn)化算法相比） 的求解中，CMA-ES 對(duì)步長(zhǎng)的優(yōu)化可以避免種群過(guò)早收斂以及在種群很大的情況下避免局部最優(yōu)，并且它是一種黑盒優(yōu)化算法。

2.1.1基本概念

協(xié)方差 是一種用來(lái)度量?jī)蓚€(gè)隨機(jī)變量關(guān)系的統(tǒng)計(jì)量：結(jié)果>0表示兩個(gè)變量正相關(guān)（比如身高越高的人往往體重越大） ，<0表示兩個(gè)變量負(fù)相關(guān)， =0表示兩個(gè)變量獨(dú)立，方差是指變量關(guān)于其均值的偏離程度。公式如下：

均值（期望）：

協(xié)方差：       cov(X,Y)=cov(Y,X)

方差：D(X)=cov(X,X)=VAR(X)

協(xié)方差矩陣：兩個(gè)向量（多個(gè)參數(shù)）之間的相關(guān)性統(tǒng)計(jì)，協(xié)方差矩陣的維度等于待優(yōu)化參數(shù)的個(gè)數(shù)。假設(shè)有兩個(gè)待優(yōu)化參數(shù)A，B。對(duì)應(yīng)協(xié)方差矩陣為C = 由方差和協(xié)方差的定義可以確定：協(xié)方差矩陣中D(X)增大會(huì)使得樣本點(diǎn)在X軸的方向上更分散（樣本點(diǎn)在X軸的方向被拉伸，圖片中的橫坐標(biāo)由原來(lái)的[-3,3]變成了[-5,5]），D(Y)增大會(huì)使得樣本點(diǎn)在Y軸的方向上更分散；cov(X,Y)大于0 會(huì)使得樣本點(diǎn)成正相關(guān)性偏移，也即隨樣本點(diǎn)X值的增大Y值也會(huì)增大。下面是協(xié)方差矩陣各個(gè)位置變化對(duì)樣本分布的影響：

通過(guò)上面的講解，相信你對(duì)協(xié)方差矩陣各個(gè)位置的變幻 對(duì)樣本點(diǎn)進(jìn)化方向的改變有了一個(gè)初步的認(rèn)識(shí)，下面再介紹一下步長(zhǎng)（step-size）：

參數(shù)σ控制分布的總體規(guī)模。它是從協(xié)方差矩陣中分離出來(lái)的，這樣我們就可以比完全計(jì)算出協(xié)方差矩陣更快地改變步長(zhǎng)。步長(zhǎng)越大，參數(shù)更新越快，新產(chǎn)生的個(gè)體（樣本）是在步長(zhǎng)內(nèi)進(jìn)行隨機(jī)選取的。

累計(jì)步長(zhǎng)適應(yīng)（cumulative step-size adaptation，CSA）是指綜合考慮本代樣本均值的大小和方向與歷史步長(zhǎng)的進(jìn)化方向相同或者相反，決定下一代步長(zhǎng)的變化。由下圖可見(jiàn)，當(dāng)代樣本的更新方向與歷史進(jìn)化方向相同則會(huì)加速步長(zhǎng)的增加，從而擴(kuò)大種群的搜索范圍，反之則會(huì)減小步長(zhǎng)甚至改變進(jìn)化的方向，從而使得下一代個(gè)體更加密集，更利于找到全局最優(yōu)的樣本點(diǎn)。

下面開(kāi)始步入正軌，我們參考basic ES的流程來(lái)介紹CMA-ES的優(yōu)化流程：

首先介紹需要初始化的參數(shù)，設(shè)待優(yōu)化的參數(shù)個(gè)數(shù)為n個(gè)，則樣本點(diǎn)x，均值m都是n維的向量,目標(biāo)函數(shù)為f(x),值越小越好，最小為0：

：每一代的種群規(guī)模

：通過(guò)截?cái)噙x擇截取個(gè)最優(yōu)的個(gè)體作為產(chǎn)生下一代的父體。

C=I（協(xié)方差矩陣初始為n*n維單位陣）

m：人為猜測(cè)的一個(gè)n維初始樣本均值

：人為猜測(cè)的一個(gè)n*1步長(zhǎng)矩陣

：第i個(gè)個(gè)體所占的更新權(quán)重

1.產(chǎn)生新個(gè)體：通過(guò)對(duì)m進(jìn)行變異產(chǎn)生個(gè)后代，他服從均值為m，協(xié)方差為^2*C的多元正態(tài)分布，即從這個(gè)分布中隨機(jī)取樣。

等價(jià)于

2.適應(yīng)度評(píng)估：根據(jù)適應(yīng)度函數(shù)或者誤差函數(shù)對(duì)個(gè)體進(jìn)行評(píng)估，然后排序，使得f(x1)<=f(x2)<=f(x3)...<=f()

3.更新均值：通過(guò)最優(yōu)的個(gè)個(gè)體更新均值，當(dāng)代最優(yōu)的個(gè)體所占權(quán)重最大，使均值更偏向于最優(yōu)個(gè)體的方向：

4.更新步長(zhǎng)，采用上面提到的累計(jì)步長(zhǎng)適應(yīng)策略進(jìn)行更新，相應(yīng)的也需要對(duì)每一代的累計(jì)步長(zhǎng)進(jìn)行更新：

是累計(jì)步長(zhǎng)的衰減率， =  - m，

5，更新協(xié)方差矩陣：

（1）      （2）

為協(xié)方差矩陣?yán)鄯e路徑的衰減率，、分別為rank-1、rank-u更新策略的學(xué)習(xí)率， =  - m

此公式結(jié)合了rank-u-update和rank-1-update對(duì)協(xié)方差矩陣進(jìn)行更新，一方面，當(dāng)代種群的所有信息通過(guò)rank-u策略被充分利用，另一方面，進(jìn)化過(guò)程中每代種群間的相關(guān)性信息通過(guò)rank-one的演化路徑策略充分探索，前一種策略對(duì)種群規(guī)模很大時(shí)重要（考慮種群中最優(yōu)的u個(gè)個(gè)體），后者對(duì)種群規(guī)模小時(shí)重要（類(lèi)似于步長(zhǎng)的更新方式，使用累計(jì)路徑策略來(lái)兼顧之前的種群信息），這樣在不同種群規(guī)模下的評(píng)估結(jié)果會(huì)更加準(zhǔn)確。

6.重復(fù)上述過(guò)程直到滿(mǎn)足進(jìn)化的終止條件（比如：達(dá)到指定迭代次數(shù) 或者找到適應(yīng)度值滿(mǎn)足要求的個(gè)體 或者種群進(jìn)化不再使使適應(yīng)度值變大）

除了協(xié)方差矩陣C的自適應(yīng)規(guī)則外，我們引入步長(zhǎng)控制來(lái)對(duì)后代樣本點(diǎn)更新，還有兩個(gè)原因： 1.最佳步長(zhǎng)不能用步驟5中的公式（2）很好地逼近。 2.公式（2）中協(xié)方差矩陣更新的最大可靠學(xué)習(xí)率太慢，無(wú)法實(shí)現(xiàn)總體步長(zhǎng)的競(jìng)爭(zhēng)性變化率。

2.2自然進(jìn)化策略 (Natural Evolution Strategies，NES)

NES的重點(diǎn)是自然梯度，所以先介紹一下常規(guī)梯度（見(jiàn)上面1.4節(jié)介紹）與自然梯度的區(qū)別：

給定一個(gè)參數(shù)為 θ 的目標(biāo)函數(shù) J (θ)，我們的目標(biāo)是找到最優(yōu)的 θ，從而最大化目標(biāo)函數(shù)的值。

常規(guī)梯度會(huì)以當(dāng)前的 θ 為起點(diǎn)，在很小的一段歐氏距離內(nèi)找到最陡峭的方向，也就是J(θ)相對(duì)于θ的負(fù)梯度方向，而樣本的分布是無(wú)規(guī)律的；

而在演化策略中，第一代種群個(gè)體的生成是在當(dāng)前的分布空間（高斯分布）中進(jìn)行抽樣產(chǎn)生的，所以在NES中每一代的個(gè)體進(jìn)化過(guò)程可以理解為概率分布空間的優(yōu)化過(guò)程：θ的優(yōu)化-->種群分布空間的變化-->在分布空間中隨機(jī)采樣的個(gè)體的變化

自然梯度考慮的是參數(shù)的變化引起樣本分布空間的變化，比如p(xi;)-->p(xi;),而這一概率屬性距離（無(wú)法用Euclidean distance來(lái)度量）可以用Kullback-Lubler差離度來(lái)度量，自然梯度是按KL距離度量來(lái)進(jìn)行梯度下降過(guò)程的。自然梯度法采用分布空間距離約束 —> KL散度二階泰勒級(jí)數(shù)展開(kāi)—> Fisher信息矩陣近似—> 拉格朗日乘數(shù)法計(jì)算KL散度約束下的目標(biāo)函數(shù)最大值—>自然梯度：

完整的自然梯度推導(dǎo)過(guò)程如下：

下面步入正題：

NES 也是一種黑箱式優(yōu)化算法。Wirestra等人提出了將進(jìn)化算法和神經(jīng)網(wǎng)絡(luò)中的梯度下降思路結(jié)合在一起的想法。傳統(tǒng)的進(jìn)化算法包含突變和重組這兩個(gè)步驟。 我們通過(guò)這兩個(gè)步驟， 期待找到更好的解法。 然而， 突變和重組是完全隨機(jī)的，不會(huì)根據(jù)已知的數(shù)據(jù)集特征產(chǎn)生 進(jìn)化的傾向性，所以多數(shù)情況下，他們不會(huì)產(chǎn)生比當(dāng)前這一代更優(yōu)的解法。 因此, 我們想引入梯度下降或者梯度上升的思想, 從而使得突變總是能夠朝著使個(gè)體適應(yīng)度更好的方向（比如誤差更小的方向）邁進(jìn)。換句話(huà)說(shuō),我們用梯度下降替代了進(jìn)化算子中的突變和重組步驟，官方定義 為 NES是一類(lèi)利用分布參數(shù)上的估計(jì)梯度策略迭代更新搜索分布的進(jìn)化策略。具體的實(shí)現(xiàn)步驟如圖（類(lèi)比遺傳編程中的種群進(jìn)化過(guò)程）：

1. 利用參數(shù)化分布空間隨機(jī)抽樣產(chǎn)生個(gè)個(gè)體，對(duì)每一個(gè)個(gè)體求適應(yīng)度函數(shù)值。

2. 沿著自然梯度執(zhí)行梯度下降步驟更新分布空間參數(shù)θ。

3. 整個(gè)過(guò)程迭代進(jìn)行，直到滿(mǎn)足停止條件。

NES引入了一些新技術(shù)并解決了很多問(wèn)題：(以下技術(shù)的原理推導(dǎo)及實(shí)驗(yàn)證明詳見(jiàn)14年 Wierstra 等人發(fā)表的論文Natural Evolution Strategies)

1. 引入 自然梯度 解決 常規(guī)梯度 存在的過(guò)早收斂和尺度不變性問(wèn)題。

2. 引入Fitness shaping使NES算法不受適應(yīng)度保序變換的影響，增強(qiáng)算法的魯棒性

3. 適應(yīng)性抽樣調(diào)整了在線(xiàn)學(xué)習(xí)率，在基準(zhǔn)上產(chǎn)生了高績(jī)效的結(jié)果

4. 指數(shù)參數(shù)化是維持正定協(xié)方差矩陣的關(guān)鍵

5. 自然坐標(biāo)系保證了計(jì)算的可行性。

2.3強(qiáng)化學(xué)習(xí)（ Reinforcement Learing，RL）

2.3.1基本概念

眾所周知，當(dāng)AlphaGO戰(zhàn)勝了世界圍棋冠軍李世石之后，整個(gè)工業(yè)界都為之振奮，而AlphaGO背后的技術(shù)原理正是強(qiáng)化學(xué)習(xí)。現(xiàn)如今強(qiáng)化學(xué)習(xí)因其普適性在越來(lái)越多的領(lǐng)域得到了應(yīng)用。

首先我們來(lái)看一下強(qiáng)化學(xué)習(xí)所屬的分支，如圖所示：

RL與有監(jiān)督學(xué)習(xí)、無(wú)監(jiān)督學(xué)習(xí)的比較：

（1）有監(jiān)督的學(xué)習(xí)是從一個(gè)已經(jīng)給出正確結(jié)果的訓(xùn)練集中進(jìn)行學(xué)習(xí)，訓(xùn)練集中每一個(gè)樣本的特征可以視為是對(duì)該situation的描述，而其label可以視為是應(yīng)該執(zhí)行的正確的action，但是有監(jiān)督的學(xué)習(xí)不能學(xué)習(xí)交互的情景，因?yàn)樵诮换サ膯?wèn)題中獲得期望行為的樣例是非常不實(shí)際的，agent只能從自己的經(jīng)歷（experience）中進(jìn)行學(xué)習(xí)，而experience中采取的行為并不一定是最優(yōu)的。這時(shí)利用RL就非常合適，因?yàn)镽L不是利用正確的行為來(lái)指導(dǎo)，而是利用已有的訓(xùn)練信息來(lái)對(duì)行為進(jìn)行評(píng)價(jià)。

（2）因?yàn)镽L利用的并不是采取正確行動(dòng)的experience，從這一點(diǎn)來(lái)看和無(wú)監(jiān)督的學(xué)習(xí)確實(shí)有點(diǎn)像，但是還是不一樣的，無(wú)監(jiān)督的學(xué)習(xí)的目的可以說(shuō)是從一堆未標(biāo)記樣本中發(fā)現(xiàn)隱藏的結(jié)構(gòu)，而RL的目的是最大化reward signal。

（3）總的來(lái)說(shuō)，RL與其他機(jī)器學(xué)習(xí)算法不同的地方在于：其中沒(méi)有監(jiān)督者，只有一個(gè)reward信號(hào)；反饋是延遲的，不是立即生成的；時(shí)間對(duì)于RL具有重要的意義；agent的行為會(huì)影響之后一系列的data。這三種不同訓(xùn)練方式的核心區(qū)別在于loss的設(shè)計(jì)，三者可以用于同一task，就像黑貓白貓，能抓耗子的都是好貓。具體選擇哪一種工具要看哪一種模型會(huì)使最終的loss最小或者fitness 達(dá)到最優(yōu)。

強(qiáng)化學(xué)習(xí) 是一種通過(guò)交互的目標(biāo)導(dǎo)向?qū)W習(xí)方法，旨在找到連續(xù)時(shí)間序列的最優(yōu)策略。

這個(gè)定義比較抽象，舉個(gè)栗子方便大家理解：在你面前有兩條路，但是只有一條路到達(dá)目的地，有個(gè)前提條件是你不知道目的地在它們當(dāng)中的哪個(gè)方向。是不是感覺(jué)很抓瞎，但是如果給你個(gè)機(jī)會(huì)，讓你在兩個(gè)不同方向都去嘗試一下，你是不是就知道哪一個(gè)方向是正確的。

強(qiáng)化學(xué)習(xí)的一個(gè)核心點(diǎn)就是要嘗試，因?yàn)橹挥袊L試了之后，它才能發(fā)現(xiàn)哪些行為會(huì)導(dǎo)致獎(jiǎng)勵(lì)的最大化，而當(dāng)前的行為可能不僅僅會(huì)影響即時(shí)獎(jiǎng)勵(lì)，還會(huì)影響下一步的獎(jiǎng)勵(lì)以及后續(xù)的所有獎(jiǎng)勵(lì)。因?yàn)橐粋€(gè)目標(biāo)的實(shí)現(xiàn)，是由一步一步的行為串聯(lián)實(shí)現(xiàn)的。在上面的場(chǎng)景當(dāng)中，涉及到了強(qiáng)化學(xué)習(xí)的幾個(gè)主要因素：智能體、環(huán)境、狀態(tài)、動(dòng)作、獎(jiǎng)勵(lì)、策略。

智能體（Agent）：強(qiáng)化學(xué)習(xí)的本體，作為學(xué)習(xí)者或者決策者，上述場(chǎng)景是指我們自己。

環(huán)境（Environment）：強(qiáng)化學(xué)習(xí)智能體以外的一切，主要由狀態(tài)集合組成。

狀態(tài)（State）：一個(gè)表示環(huán)境的數(shù)據(jù)，狀態(tài)集則是環(huán)境中所有可能的狀態(tài)。比如，走一步就會(huì)達(dá)到一個(gè)新的狀態(tài)。

動(dòng)作（Action）：智能體可以做出的動(dòng)作，動(dòng)作集則是智能體可以做出的所有動(dòng)作。比如，你可以走第一條路也可以走第二條。

獎(jiǎng)勵(lì)（Reward）：智能體在執(zhí)行一個(gè)動(dòng)作后，獲得的正/負(fù)反饋信號(hào)，獎(jiǎng)勵(lì)集則是智能體可以獲得的所有反饋信息。走正確就獎(jiǎng)勵(lì)，錯(cuò)誤就懲罰。

策略（Policy）：策略就是指智能體的行為，是從狀態(tài)到動(dòng)作的映射，即智能體如何選擇動(dòng)作的思考過(guò)程，分為確定策略和與隨機(jī)策略，確定策略就是某一狀態(tài)下的確定動(dòng)作a=π(s), 隨機(jī)策略以概率來(lái)描述，即某一狀態(tài)下執(zhí)行這一動(dòng)作的概率π(a|s)=P[At=a|St=s]。

RL 的具體步驟為：

1. 智能體嘗試執(zhí)行了某個(gè)動(dòng)作后，環(huán)境將會(huì)轉(zhuǎn)換到一個(gè)新的狀態(tài)，當(dāng)然，對(duì)于這個(gè)新的狀態(tài)，環(huán)境會(huì)給出獎(jiǎng)勵(lì)或者懲罰。

2. 智能體根據(jù)新的狀態(tài)和環(huán)境反饋的獎(jiǎng)勵(lì)或懲罰，執(zhí)行新的動(dòng)作，如此反復(fù)，直至到達(dá)目標(biāo)。

3. 智能體根據(jù)獎(jiǎng)勵(lì)最大值找到到達(dá)目標(biāo)的最佳策略，然后根據(jù)這個(gè)策略到達(dá)目標(biāo)。

下圖列出了各元素之間的作用關(guān)系。要注意的是，智能體要嘗試執(zhí)行所有可能的動(dòng)作，到達(dá)目標(biāo)，最終會(huì)有所有可能動(dòng)作對(duì)應(yīng)所有可能狀態(tài)的一張映射表（Q-table）

2.3.2涉及到的公式

強(qiáng)化學(xué)習(xí)基本上可以總結(jié)為通過(guò)最大化reward來(lái)得到一個(gè)最優(yōu)策略。但是如果只是瞬時(shí)reward最大會(huì)導(dǎo)致每次都只會(huì)從動(dòng)作空間選擇reward最大的那個(gè)動(dòng)作，這樣就變成了最簡(jiǎn)單的貪心策略(Greedy policy)，所以為了使reward是包括未來(lái)的當(dāng)前reward值最大（即使從當(dāng)前時(shí)刻開(kāi)始一直到狀態(tài)達(dá)到目標(biāo)的總reward最大），構(gòu)造了值函數(shù)（value function）來(lái)描述這一變量。表達(dá)式如下：

t表示當(dāng)前時(shí)刻，R是reward，S是狀態(tài)，γ是折扣系數(shù)(取值在[0,1])，折扣系數(shù)與我們的認(rèn)知是一致的，就是在衡量權(quán)重時(shí)我們更看重時(shí)間距離更近時(shí)的Reward影響。

強(qiáng)化學(xué)習(xí)的算法迭代都是基于Bellman方程