雷鋒網(wǎng)AI科技評論按：如果你是一名機(jī)器學(xué)習(xí)從業(yè)者，一定不會(huì)對基于梯度下降的優(yōu)化方法感到陌生。對于很多人來說，有了 SGD，Adam，Admm 等算法的開源實(shí)現(xiàn)，似乎自己并不用再過多關(guān)注優(yōu)化求解的細(xì)節(jié)。然而在模型的優(yōu)化上，梯度下降并非唯一的選擇，甚至在很多復(fù)雜的優(yōu)化求解場景下，一些非梯度優(yōu)化方法反而更具有優(yōu)勢。而在眾多非梯度優(yōu)化方法中，演化策略可謂最耀眼的那顆星！

對于深度學(xué)習(xí)模型的優(yōu)化問題來說，隨機(jī)梯度下降（SGD）是一種被廣為使用方法。然而，實(shí)際上 SGD 并非我們唯一的選擇。當(dāng)我們使用一個(gè)「黑盒算法」時(shí)，即使不知道目標(biāo)函數(shù) f(x):Rn→R 的精確解析形式（因此不能計(jì)算梯度或 Hessian 矩陣）你也可以對 f(x) 進(jìn)行評估。經(jīng)典的黑盒優(yōu)化方法包括「模擬退火算法」、「爬山法」以及「單純形法」。演化策略（ES）是一類誕生于演化算法（EA）黑盒優(yōu)化算法。在本文中，我們將深入分析一些經(jīng)典的演化策略方法，并介紹演化策略在深度強(qiáng)化學(xué)習(xí)中的一些應(yīng)用。

目錄

一、演化策略是什么？

二、 簡單的高斯演化策略

三、協(xié)方差矩陣自適應(yīng)演化策略（CMA-ES）

1、均值更新

2、步長控制

3、協(xié)方差自適應(yīng)

四、自然演化策略（NES）

1、自然梯度

2、使用費(fèi)舍爾（Fisher）信息矩陣進(jìn)行估計(jì)

3、NES 算法

五、應(yīng)用：深度強(qiáng)化學(xué)習(xí)中的演化策略

1、OpenAI 用于強(qiáng)化學(xué)習(xí)的演化策略

2、演化策略的探索方式

3、 CEM-RL：結(jié)合演化策略和梯度下降方法的強(qiáng)化學(xué)習(xí)策略搜索

六、擴(kuò)展：深度學(xué)習(xí)中的演化策略

1、超參數(shù)調(diào)優(yōu)：PBT

2、網(wǎng)絡(luò)拓?fù)鋬?yōu)化：WANN

七、參考文獻(xiàn)

一、演化策略是什么？

演化策略（ES）從屬于演化算法的大家族。ES 的優(yōu)化目標(biāo)是實(shí)數(shù)向量 x∈Rⁿ。

演化算法（EA）指的是受自然選擇啟發(fā)而產(chǎn)生的一類基于種群的優(yōu)化算法。自然選擇學(xué)說認(rèn)為，如果某些個(gè)體具有利于他們生存的特性，那么他們就可能會(huì)繁衍幾代，并且將這種優(yōu)良的特性傳給下一代。演化是在選擇的過程中逐漸發(fā)生的，整個(gè)種群會(huì)漸漸更好地適應(yīng)環(huán)境。

圖 1：自然選擇工作原理示意圖（圖片來源：可汗學(xué)院「達(dá)爾文、進(jìn)化與自然選擇」：https://www.khanacademy.org/science/biology/her/evolution-and-natural-selection/a/darwin-evolution-natural-selection）。

（左）一群老鼠移動(dòng)到了一個(gè)巖石顏色非常暗的地區(qū)。由于自然遺傳的變異，有些老鼠毛色是黑色，有的則是棕褐色。（中）相較于黑色的老鼠來說，棕褐色的老師更容易被肉食性鳥類發(fā)現(xiàn)。因此，褐色老鼠比黑色老鼠更頻繁地被鳥類捕食。只有存活下來的老鼠到了生育年齡后會(huì)留下后代。（右）由于黑色老鼠比褐色老鼠留下后代的機(jī)會(huì)更大，在下一代老鼠中黑色的占比上一代更高。

我們可以通過以下方式將演化算法概括為一種通用的優(yōu)化方案：

假設(shè)我們想要優(yōu)化一個(gè)函數(shù) f(x)，而且無法直接計(jì)算梯度。但是，我們在給定任意 x 的情況下仍然可以評估 f(x)，而且得到確定性的結(jié)果。我們認(rèn)為隨機(jī)變量 x 的概率分布 p_θ(x) 是函數(shù) f(x) 優(yōu)化問題的一個(gè)較優(yōu)的解，θ 是分布 p_θ(x) 的參數(shù)。目標(biāo)是找到 θ 的最優(yōu)設(shè)置。

在給定固定分布形式（例如，高斯分布）的情況下，參數(shù) θ 包含了最優(yōu)解的知識(shí)，在一代與一代間進(jìn)行迭代更新。

假設(shè)初始值為 θ，我們可以通過循環(huán)進(jìn)行下面的三個(gè)步驟持續(xù)更新 θ：

• 1. 生成一個(gè)樣本的種群 D={(x_i,f(x_i)}，其中 x_i～p_θ(x)。

• 2. 估計(jì) D 中樣本的「適應(yīng)度」。

• 3. 根據(jù)適應(yīng)度或排序，選擇最優(yōu)的個(gè)體子集，并使用它們來更新 θ。

在遺傳算法（GA，另一種流行的演化算法子類）中，x 是二進(jìn)制編碼的序列，其中 x∈{0,1}ⁿ。但是在演化策略中，x 僅僅是一個(gè)實(shí)數(shù)向量，x∈Rⁿ。

二、簡單的高斯演化策略

高斯演化策略是最基礎(chǔ)、最經(jīng)典的演化策略（相關(guān)閱讀可參考：http://blog.otoro.net/2017/10/29/visual-evolution-strategies/）。它將 p_θ(x) 建模為一個(gè) n 維各向同性的高斯分布，其中 θ 僅僅刻畫均值 μ 和標(biāo)準(zhǔn)差 σ。

給定 x∈Rⁿ，簡單的高斯演化策略的過程如下：

1. 初始化 θ=θ⁽⁰⁾ 以及演化代數(shù)計(jì)數(shù)器 t=0。

2. 通過從高斯分布中采樣生成大小為 Λ 的后代種群： 

其中，

3. 選擇出使得 f(x_i) 最優(yōu)的 λ 個(gè)樣本組成的子集，該子集被稱為「精英集」。為了不失一般性，我們可以考慮 D^(t+1) 中適應(yīng)度排名靠前的 k 個(gè)樣本，將它們放入「精英集」。我們可以將其標(biāo)注為： 

4. 接著，我們使用「精英集」為下一代種群估計(jì)新的均值和標(biāo)準(zhǔn)差：

 

5. 重復(fù)步驟 2—步驟 4，直到結(jié)果滿足要求。

三、協(xié)方差矩陣自適應(yīng)演化策略（CMA-ES）

標(biāo)準(zhǔn)差 σ 決定了探索的程度：當(dāng) σ 越大時(shí)，我們就可以在更大的搜索空間中對后代種群進(jìn)行采樣。在簡單高斯演化策略中，σ^(t+1) 與 σ^(t) 密切相關(guān)，因此算法不能在需要時(shí)（即置信度改變時(shí)）迅速調(diào)整探索空間。

「協(xié)方差矩陣自適應(yīng)演化策略」（CMA-ES）通過使用協(xié)方差矩陣 C 跟蹤分布上得到的樣本兩兩之間的依賴關(guān)系，解決了這一問題。新的分布參數(shù)變?yōu)榱耍?/p>

其中，σ 控制分布的整體尺度，我們通常稱之為「步長」。

在我們深入研究 CMA-ES 中的參數(shù)更新方法前，不妨先回顧一下多元高斯分布中協(xié)方差矩陣的工作原理。作為一個(gè)對稱陣，協(xié)方差矩陣 C 有下列良好的性質(zhì)（詳見「Symmetric Matrices and Eigendecomposition」：http://s3.amazonaws.com/mitsloan-php/wp-faculty/sites/30/2016/12/15032137/Symmetric-Matrices-and-Eigendecomposition.pdf；以及證明：http://control.ucsd.edu/mauricio/courses/mae280a/lecture11.pdf）：

• C 始終是對角陣

• C 始終是半正定矩陣

• 所有的特征值都是非負(fù)實(shí)數(shù)

• 所有特征值都是正交的

• C 的特征向量可以組成 Rn 的一個(gè)標(biāo)準(zhǔn)正交基

令矩陣 C 有一個(gè)特征向量 B=[b₁,...,b_n] 組成的標(biāo)準(zhǔn)正交基，相應(yīng)的特征值分別為 λ₁²,…,λ_n²。令 D=diag(λ₁,…,λ_n)。

C 的平方根為：

相關(guān)的符號(hào)和意義如下：

x_i^(t)∈Rⁿ：第 t 代的第 i 個(gè)樣本

y_i^(t)∈Rⁿ：x_i^(t)=μ^(t?1)+σ^(t?1)y_i^(t)

μ^(t)：第 t 代的均值

σ^(t)：步長

C^(t)：協(xié)方差矩陣

B^(t)：將 C 的特征向量作為行向量的矩陣

D^(t)：對角線上的元素為 C 的特征值的對角矩陣

p_σ^(t)：第 t 代中用于 σ 的演化路徑

p_c^(t)：第t 代中用于 C 的演化路徑

α_μ：用于更新 μ 的學(xué)習(xí)率

α_σ：p_σ 的學(xué)習(xí)率

d_σ：σ 更新的衰減系數(shù)

Α_cp：p_c 的學(xué)習(xí)率

α_cλ：矩陣 C 的秩 min(λ, n) 更新的學(xué)習(xí)率

α_c1：矩陣 C 的秩 1 更新的學(xué)習(xí)率

1、更新均值

 

CMA-ES 使用 α_μ≤1 的學(xué)習(xí)率控制均值 μ 更新的速度。通常情況下，該學(xué)習(xí)率被設(shè)置為 1，從而使上述等式與簡單高斯演化策略中的均值更新方法相同：

 

2、控制步長

采樣過程可以與均值和標(biāo)準(zhǔn)差的更新解耦：

參數(shù) σ 控制著分布的整體尺度。它是從協(xié)方差矩陣中分離出來的，所以我們可以比改變完整的協(xié)方差更快地改變步長。步長較大會(huì)導(dǎo)致參數(shù)更新較快。為了評估當(dāng)前的步長是否合適，CMA-ES 通過將連續(xù)的移動(dòng)步長序列相加 ，構(gòu)建了一個(gè)演化路徑（evolution path）p_σ。通過比較該路徑與隨機(jī)選擇（意味著每一步之間是不相關(guān)的）狀態(tài)下期望會(huì)生成的路徑長度，我們可以相應(yīng)地調(diào)整 σ（詳見圖 2）。

圖 2：將每一步演化以不同的方式關(guān)聯(lián)起來的三種情況，以及它們對步長更新的影響。（左）每個(gè)步驟之間互相抵消，因此演化路徑很短。（中）理想情況：每個(gè)步驟之間并不相關(guān)。（右）每個(gè)步驟指向同一個(gè)方向，因此演化路徑較長。（圖片來源：CMA-ES 教程論文中圖 5 的附加注釋，https://arxiv.org/abs/1604.00772）

每次演化路徑都會(huì)以同代中的平均移動(dòng)步長 y_i 進(jìn)行更新。

通過與 C^-1/2 相乘，我們將演化路徑轉(zhuǎn)化為與其方向相獨(dú)立的形式。的工作原理如下：

1. B^(t) 包含 C 的特征向量的行向量。它將原始空間投影到了正交的主軸上。

2. 將各主軸的長度放縮到相等的狀態(tài)。

3. B^(t)?將空間轉(zhuǎn)換回原始坐標(biāo)系。

為了給最近幾代的種群賦予更高的權(quán)重，我們使用了「Polyak平均 」算法（平均優(yōu)化算法在參數(shù)空間訪問軌跡中的幾個(gè)點(diǎn)），以學(xué)習(xí)率 α_σ 更新演化路徑。同時(shí)，我們平衡了權(quán)重，從而使p_σ 在更新前和更新后都為服從 N(0,I)  的共軛分布（更新前后的先驗(yàn)分布和后驗(yàn)分布類型相同）。

隨機(jī)選擇得到的Pσ 的期望長度為 E‖N(0,I)‖，該值是服從 N(0,I) 的隨機(jī)變量的 L2 范數(shù)的數(shù)學(xué)期望。按照圖 2 中的思路，我們將根據(jù) ‖p_σ^(t+1)‖/E‖N(0,I)‖ 的比值調(diào)整步長：

 

其中，d_σ≈1 是一個(gè)衰減參數(shù)，用于放縮 ln^σ 被改變的速度。

3、自適應(yīng)協(xié)方差矩陣

我們可以使用精英樣本的 y_i 從頭開始估計(jì)協(xié)方差矩陣（y_i～N(0,C)）

只有當(dāng)我們選擇出的種群足夠大，上述估計(jì)才可靠。然而，在每一代中，我們確實(shí)希望使用較小的樣本種群進(jìn)行快速的迭代。這就是 CMA-ES 發(fā)明了一種更加可靠，但同時(shí)也更加復(fù)雜的方式去更新 C 的原因。它包含兩種獨(dú)立的演化路徑：

1. 秩 min(λ, n) 更新：使用 {C_λ} 中的歷史，在每一代中都是從頭開始估計(jì)的。

2. 秩 1 更新：根據(jù)歷史估計(jì)移動(dòng)步長 y_i 以及符號(hào)信息

第一條路徑根據(jù) {C_λ} 的全部歷史考慮 C 的估計(jì)。例如，如果我們擁有很多代種群的經(jīng)驗(yàn)，

 

就是一種很好的估計(jì)方式。類似于 p_σ，我們也可以使用「polyak」平均，并且通過學(xué)習(xí)率引入歷史信息：

通常我們選擇的學(xué)習(xí)率為：

 

第二條路徑試圖解決 y_iy_i^?=(?y_i)(?y_i)^? 丟失符號(hào)信息的問題。與我們調(diào)整步長 σ 的方法相類似，我們使用了一個(gè)演化路徑 p_c 來記錄符號(hào)信息，p_c 仍然是種群更新前后都服從于 N(0,C) 的共軛分布。

我們可以認(rèn)為 p_c 是另一種計(jì)算 avg_i(y_i) 的（請注意它們都服從于 N(0,C)），此時(shí)我們使用了完整的歷史信息，并且能夠保留符號(hào)信息。請注意，在上一節(jié)中，我們已經(jīng)知道了，p_c的計(jì)算方法如下：

接下來，我們可以根據(jù)通過 p_c 更新協(xié)方差矩陣：

當(dāng) k 較小時(shí)，秩 1 更新方法相較于秩 min(λ, n) 更新有很大的性能提升。這是因?yàn)槲覀冊谶@里利用了移動(dòng)步長的符號(hào)信息和連續(xù)步驟之間的相關(guān)性，而且這些信息可以隨著種群的更新被一代一代傳遞下去。

最后，我們將兩種方法結(jié)合起來： 

在上面所有的例子中，我們認(rèn)為每個(gè)優(yōu)秀的樣本對于權(quán)重的貢獻(xiàn)是相等的，都為 1/λ。該過程可以很容易地被擴(kuò)展至根據(jù)具體表現(xiàn)為抽樣得到的樣本賦予不同權(quán)重 w₁,…,w_λ 的情況。詳情請參閱教程：「The CMA Evolution Strategy: A Tutorial」（https://arxiv.org/abs/1604.00772）

圖 3：CMA-ES 在二維優(yōu)化問題上的工作原理示意圖（顏色越亮的部分性能越好）。黑點(diǎn)是當(dāng)前代中的樣本。樣本在初始階段較分散，但當(dāng)模型在后期較有信心找到較好的解時(shí)，樣本在全局最優(yōu)上變得非常集中。樣本在初始階段較分散，但當(dāng)模型在后期以更高的置信度找到較好的解時(shí)，樣本會(huì)集中于全局最優(yōu)點(diǎn)。

四、自然演化策略

自然演化策略（Wierstra 等人于 2008 年發(fā)表的 NES，論文地址：https://arxiv.org/abs/1106.4487）在參數(shù)的搜索分布上進(jìn)行優(yōu)化，并將分布朝著自然梯度所指向的高適應(yīng)度方向移動(dòng)。

1、自然梯度

給定一個(gè)參數(shù)為 θ 的目標(biāo)函數(shù) J(θ)，我們的目標(biāo)是找到最優(yōu)的 θ，從而最大化目標(biāo)函數(shù)的值。樸素梯度會(huì)以當(dāng)前的 θ 為起點(diǎn)，在很小的一段歐氏距離內(nèi)找到最「陡峭」的方向，同時(shí)我們會(huì)對參數(shù)空間施加一些距離的限制。換而言之，我們在 θ 的絕對值發(fā)生微小變化的情況下計(jì)算出樸素梯度。優(yōu)化步驟如下：

不同的是，自然梯度用到了參數(shù)為 θ, p_θ(x)（在 NES 的原始論文中被稱為「搜索分布」，論文鏈接：https://arxiv.org/abs/1106.4487）的概率分布空間。它在分布空間中的一小步內(nèi)尋找最「陡峭」（變化最快）的方向，其中距離由 KL 散度來度量。在這種限制條件下，我們保證了每一步更新都是沿著分布的流形以恒定的速率移動(dòng)，不會(huì)因?yàn)槠淝识鴾p速。 

2、使用 Fisher 信息矩陣進(jìn)行估計(jì)

但是，如何精確地計(jì)算出 KL[p_θ‖p_θ+Δθ] 呢？通過推導(dǎo)  log_pθ+d 在 θ 處的泰勒展式，我們可以得到：

其中，

 

請注意，p_θ(x) 是概率分布。最終，我們得到了：

其中，F(xiàn)θ 被稱為 Fisher 信息矩陣。由于E[?_θlogp_θ]=0，所以 Fθ 也是 ?_θlogp_θ 的協(xié)方差矩陣：

針對以下的優(yōu)化問題： 

我們可以通過拉格朗日乘子法找到上述問題的解：

其中 d_N^?僅僅提取了忽略標(biāo)量 β^?1 的情況下，在 θ 上最優(yōu)移動(dòng)步長的方向。

圖 4：右側(cè)的自然梯度樣本（黑色實(shí)箭頭）是左側(cè)的樸素梯度樣本（黑色實(shí)箭頭）乘以其協(xié)方差的逆的結(jié)果。這樣一來，可以用較小的權(quán)重懲罰具有高不確定性的梯度方向（由與其它樣本的高協(xié)方差表示）。因此，合成的自然梯度（紅色虛箭頭）比原始的自然梯度（綠色虛箭頭）更加可信（圖片來源：NES 原始論文中圖 2 的附加說明，https://arxiv.org/abs/1106.4487）

3、NES 算法

我們將與一個(gè)樣本相關(guān)聯(lián)的適應(yīng)度標(biāo)記為 f(x)，關(guān)于 x 的搜索分布的參數(shù)為 θ。我們希望 NES 能夠優(yōu)化參數(shù) θ，從而得到最大的期望適應(yīng)度：

在這里，我們使用與蒙特卡洛策略梯度強(qiáng)化中相同的似然計(jì)算技巧：

除了自然梯度，NES 還采用了一些重要的啟發(fā)式方法讓算法的性能更加魯棒。

• NES 應(yīng)用了基于排序的適應(yīng)度塑造（Rank-Based Fitness Shaping）算法，即使用適應(yīng)度值單調(diào)遞增的排序結(jié)果，而不是直接使用 f(x)。它也可以是對「效用函數(shù)」進(jìn)行排序的函數(shù)，我們將其視為 NES 的一個(gè)自由參數(shù)。

• NES 采用了適應(yīng)性采樣（Adaptation Sampling）在運(yùn)行時(shí)調(diào)整超參數(shù)。當(dāng)進(jìn)行 θ→θ′ 的變換時(shí)，我們使用曼-惠特尼 U 檢驗(yàn)（ [Mann-Whitney U-test）對比從分布 p_θ 上采樣得到的樣本以及從分布 p_θ′ 上采樣得到的樣本。如果出現(xiàn)正或負(fù)符號(hào)，則目標(biāo)超參數(shù)將減少或增加一個(gè)乘法常數(shù)。請注意，樣本 x_i′～p_θ′(x) 的得分使用了重要性采樣權(quán)重 w_i′=p_θ(x)/p_θ′(x)。

五、應(yīng)用：深度強(qiáng)化學(xué)習(xí)中的演化策略

1、OpenAI 用于強(qiáng)化學(xué)習(xí)的演化策略

將演化算法應(yīng)用于強(qiáng)化學(xué)習(xí)的想法可以追溯到很久以前的論文「Evolutionary Algorithms for Reinforcement Learning」（論文地址：https://arxiv.org/abs/1106.0221），但是由于計(jì)算上的限制，這種嘗試僅僅止步于「表格式」強(qiáng)化學(xué)習(xí)（例如，Q-learning）。

受到 NES 的啟發(fā)，OpenAI 的研究人員（詳見 Salimans 等人于 2017 年發(fā)表的論文「Evolution Strategies as a Scalable Alternative to Reinforcement Learning」，論文鏈接：https://arxiv.org/abs/1703.03864）提出使用 NES 作為一種非梯度黑盒優(yōu)化器，從而尋找能夠最大化返回函數(shù) F(θ) 的最優(yōu)策略參數(shù) θ。

這里的關(guān)鍵是，為模型參數(shù) θ 加入高斯噪聲 ε，并使用似然技巧將其寫作高斯概率密度函數(shù)的梯度。最終，只剩下噪聲項(xiàng)作為衡量性能的加權(quán)標(biāo)量。

假設(shè)當(dāng)前的參數(shù)值為 θ^（區(qū)別于隨機(jī)變量 θ）。我們將 θ 的搜索分布設(shè)計(jì)為一個(gè)各向同性的多元高斯分布，其均值為 θ^，協(xié)方差矩陣為 σ²I 

θ 更新的梯度為：

 

其中，高斯分布為。

是我們用到的似然計(jì)算技巧。

在每一代中，我們可以采樣得到許多 ε_i，i=1,…,n，然后并行地估計(jì)其適應(yīng)度。一種優(yōu)雅的設(shè)計(jì)方式是，無需共享大型模型參數(shù)。只需要在各個(gè)工作線程之間傳遞隨機(jī)種子，就足以事主線程節(jié)點(diǎn)進(jìn)行參數(shù)更新。隨后，這種方法又被拓展成了以自適應(yīng)的方試學(xué)習(xí)損失函數(shù)。詳情請查閱博文「Evolved Policy Gradient」：

• https://lilianweng.github.io/lil-log/2019/06/23/meta-reinforcement-learning.html#meta-learning-the-loss-function

圖 5：使用演化策略訓(xùn)練一個(gè)強(qiáng)化策略的算法（圖片來源：論文「ES-for-RL」，https://arxiv.org/abs/1703.03864）

為了使算法的性能更加魯棒，OpenAI ES 采用了虛擬批量歸一化（Virtual BN，用于計(jì)算固定統(tǒng)計(jì)量的 mini-batch 上的批量歸一化方法），鏡面采樣（Mirror Sampling，采樣一對 (??,?) 用于估計(jì)），以及適應(yīng)度塑造（Fitness Shaping）技巧。

2、使用演化策略進(jìn)行探索

在強(qiáng)化學(xué)習(xí)領(lǐng)域，「探索與利用」是一個(gè)很重要的課題。上述演化策略中的優(yōu)化方向僅僅是從累積返回函數(shù) F(θ) 中提取到的。在不進(jìn)行顯式探索的情況下，智能體可能會(huì)陷入局部最優(yōu)點(diǎn)。

新穎性搜索（Novelty-Search）演化策略（NS-ES，詳見 Conti 等人于 2018 年發(fā)表的論文「Improving Exploration in Evolution Strategies for Deep Reinforcement Learning via a Population of Novelty-Seeking Agents」，論文地址：https://arxiv.org/abs/1712.06560）通過朝著最大化「新穎性得分」的方向更新參數(shù)來促進(jìn)探索。

「新穎性得分」取決于一個(gè)針對于特定領(lǐng)域的行為特征函數(shù) b(π_θ)。對 b(π_θ) 的選擇取決于特定的任務(wù)，并且似乎具有一定的隨機(jī)性。例如，在論文里提到的人形機(jī)器人移動(dòng)任務(wù)中，b(π_θ) 是智能體最終的位置 (x,y)。

1. 將每個(gè)策略的 b(π_θ) 加入一個(gè)存檔集合 A。

2. 通過 b(π_θ) 和 A 中所有其它實(shí)體之間的 K 最近鄰得分衡量策略 π_θ 的新穎性。（文檔集合的用例與「情節(jié)記憶」很相似）

在這里，演化策略優(yōu)化步驟依賴于新穎性得分而不是適應(yīng)度：

 

NS-ES 維護(hù)了一個(gè)由 M 個(gè)獨(dú)立訓(xùn)練的智能體組成的集合（「元-種群」），M={θ₁,…,θ_M}。然后選擇其中的一個(gè)智能體，將其按照與新穎性得分成正比的程度演化。最終，我們選擇出最佳策略。這個(gè)過程相當(dāng)于集成，在 SVPG 中也可以看到相同的思想。

 

其中，N 是高斯擾動(dòng)噪聲向量的數(shù)量，α 是學(xué)習(xí)率。

NS-ES 完全舍棄了獎(jiǎng)勵(lì)函數(shù)，僅僅針對新穎性進(jìn)行優(yōu)化，從而避免陷入極具迷惑性的局部最優(yōu)點(diǎn)。為了將適應(yīng)度重新考慮到公式中，研究人員又提出了兩種變體。

NSR-ES:

 

NSRAdapt-ES (NSRA-ES)：自適應(yīng)的權(quán)重參數(shù)初始值為 w=1.0。如果算法的性能經(jīng)過了很多代之后沒有變化，我們就開始降低 w。然后，當(dāng)性能開始提升時(shí)，我們停止降低 w，反而增大 w。這樣一來，當(dāng)性能停止提升時(shí)，模型更偏向于提升適應(yīng)度，而不是新穎性。

 

圖 6：（左圖）環(huán)境為人形機(jī)器人移動(dòng)問題，該機(jī)器人被困在一個(gè)三面環(huán)繞的強(qiáng)中，這是一個(gè)具有迷惑性的陷阱，創(chuàng)造了一個(gè)局部最優(yōu)點(diǎn)。（右圖）實(shí)驗(yàn)對比了 ES 基線和另一種促進(jìn)探索的變體。（圖片來源，論文「NS-ES」，https://arxiv.org/abs/1712.06560）

3、CEM-RL

圖 7：CEM-RL 和 ERL 算法（https://papers.nips.cc/paper/7395-evolution-guided-policy-gradient-in-reinforcement-learning.pdf）的架構(gòu)示意圖（圖片來源：論文「CEM-RL」，https://arxiv.org/abs/1810.01222）

CEM-RL 方法（詳見 Pourchot 和 Sigaud 等人于 2019 年發(fā)表的論文「CEM-RL: Combining evolutionary and gradient-based methods for policy search」，論文地址：https://arxiv.org/abs/1810.01222）結(jié)合了交叉熵方法（CEM）和 DDPG 或 TD3。

在這里，CEM 的工作原理與上面介紹的簡單高斯演化策略基本相同，因此可以使用 CMA-ES 替換相同的函數(shù)。CEM-RL 是基于演化強(qiáng)化學(xué)習(xí)（ERL，詳見 Khadka 和 Tumer 等人于 2018 年發(fā)表的論文「Evolution-Guided Policy Gradient in Reinforcement Learning」，論文地址：https://papers.nips.cc/paper/7395-evolution-guided-policy-gradient-in-reinforcement-learning.pdf）的框架構(gòu)建的，它使用標(biāo)準(zhǔn)的演化算法選擇并演化「Actor」的種群。隨后，在這個(gè)過程中生成的首次展示經(jīng)驗(yàn)也會(huì)被加入到經(jīng)驗(yàn)回放池中，用于訓(xùn)練強(qiáng)化學(xué)習(xí)的「Actor」網(wǎng)絡(luò)和「Critic」網(wǎng)絡(luò)。

工作流程：

1. π_μ 為 CEM 種群的「Actor」平均值，使用隨機(jī)的「Actor」網(wǎng)絡(luò)對其進(jìn)行初始化。

2. 「Critic」網(wǎng)絡(luò) Q 也將被初始化，通過 DDPG/TD3 算法對其進(jìn)行更新。

3. 重復(fù)以下步驟直到滿足要求：

• 在分布 N(π_μ,Σ) 上采樣得到一個(gè)「Actor」的種群。

• 評估一半「Actor」的種群。將適應(yīng)度得分用作累積獎(jiǎng)勵(lì) R，并將其加入到經(jīng)驗(yàn)回放池中。

• 將另一半「Actor」種群與「Critic」一同更新。

• 使用性能最佳的優(yōu)秀樣本計(jì)算出新的 π_mu 和 Σ。也可以使用 CMA-ES 進(jìn)行參數(shù)更新。

六、拓展：深度學(xué)習(xí)中的演化算法

（本章并沒有直接討論演化策略，但仍然是非常有趣的相關(guān)閱讀材料。）

演化算法已經(jīng)被應(yīng)用于各種各樣的深度學(xué)習(xí)問題中?！窹OET」（詳見 Wang 等人于 2019 年發(fā)表的論文「Paired Open-Ended Trailblazer (POET): Endlessly Generating Increasingly Complex and Diverse Learning Environments and Their Solutions」，論文地址：https://arxiv.org/abs/1901.01753）就是一種基于演化算法的框架，它試圖在解決問題的同時(shí)生成各種各樣不同的任務(wù)。關(guān)于 POET 的詳細(xì)介紹請參閱下面這篇關(guān)于元強(qiáng)化學(xué)習(xí)的博文：https://lilianweng.github.io/lil-log/2019/06/23/meta-reinforcement-learning.html#task-generation-by-domain-randomization。

另一個(gè)例子則是演化強(qiáng)化學(xué)習(xí)（ERL），詳見圖 7（b）。

下面，我將更詳細(xì)地介紹兩個(gè)應(yīng)用實(shí)例：基于種群的訓(xùn)練（PBT），以及權(quán)重未知的神經(jīng)網(wǎng)絡(luò)（WANN）

1、超參數(shù)調(diào)優(yōu)：PBT

圖 8：對比不同的超參數(shù)調(diào)優(yōu)方式的范例（圖片來源：論文「Population Based Training of Neural Networks」，https://arxiv.org/abs/1711.09846）

基于種群的訓(xùn)練（PBT，詳見 Jaderberg 等人于 2017 年發(fā)表的論文「Population Based Training of Neural Networks」，論文地址：https://arxiv.org/abs/1711.09846）將演化算法應(yīng)用到了超參數(shù)調(diào)優(yōu)問題中。它同時(shí)訓(xùn)練了一個(gè)模型的種群以及相應(yīng)的超參數(shù)，從而得到最優(yōu)的性能。

PBT 過程起初擁有一組隨機(jī)的候選解，它們包含一對模型權(quán)重的初始值和超參數(shù) {(θ_i,h_i)∣i=1,…,N}。我們會(huì)并行訓(xùn)練每個(gè)樣本，然后周期性地異步評估其自身的性能。當(dāng)一個(gè)成員準(zhǔn)備好后（即該成員進(jìn)行了足夠的梯度更新步驟，或當(dāng)性能已經(jīng)足夠好），就有機(jī)會(huì)通過與整個(gè)種群進(jìn)行對比進(jìn)行更新：

• 「exploit()」：當(dāng)模型性能欠佳時(shí)，可以用性能更好的模型的權(quán)重來替代當(dāng)前模型的權(quán)重。

• 「explore()」：如果模型權(quán)重被重寫，「explore」步驟會(huì)使用隨機(jī)噪聲擾動(dòng)超參數(shù)。

在這個(gè)過程中，只有性能良好的模型和超參數(shù)對會(huì)存活下來，并繼續(xù)演化，從而更好地利用計(jì)算資源。

圖 9：基于種群的訓(xùn)練算法示意圖。（圖片來源，論文「Population Based Training of Neural Networks」，https://arxiv.org/abs/1711.09846）

2、網(wǎng)絡(luò)拓?fù)鋬?yōu)化：WANN

權(quán)重未知的神經(jīng)網(wǎng)絡(luò)（WANN，詳見 Gaier 和 Ha 等人于 2019 年發(fā)表的論文「Weight Agnostic Neural Networks」，論文地址：https://arxiv.org/abs/1906.04358）在不訓(xùn)練網(wǎng)絡(luò)權(quán)重的情況下，通過搜索最小的網(wǎng)絡(luò)拓?fù)鋪慝@得最優(yōu)性能。

由于不需要考慮網(wǎng)絡(luò)權(quán)值的最佳配置，WANN 更加強(qiáng)調(diào)網(wǎng)絡(luò)架構(gòu)本身，這使得它的重點(diǎn)與神經(jīng)網(wǎng)絡(luò)架構(gòu)搜索（NAS）不同。WANN 在演化網(wǎng)絡(luò)拓?fù)涞臅r(shí)候深深地受到了一種經(jīng)典的遺傳算法「NEAT」（增廣拓?fù)涞纳窠?jīng)演化，詳見 Stanley 和 Miikkulainen 等人于 2002 年發(fā)表的論文「Efficient Reinforcement Learning through Evolving Neural Network Topologies」，論文地址：http://nn.cs.utexas.edu/downloads/papers/stanley.gecco02_1.pdf）的啟發(fā)。

WANN 的工作流程看上去與標(biāo)準(zhǔn)的遺傳算法基本一致：

1. 初始化：創(chuàng)建一個(gè)最小網(wǎng)絡(luò)的種群。

2. 評估：使用共享的權(quán)重值進(jìn)行測試。

3. 排序和選擇：根據(jù)性能和復(fù)雜度排序。

4. 變異：通過改變最佳的網(wǎng)路來創(chuàng)建新的種群。

圖 10:：WANN 中用于搜索新網(wǎng)絡(luò)拓?fù)涞淖儺惒僮?。（從左到右分別為）最小網(wǎng)絡(luò)，嵌入節(jié)點(diǎn)，增加連接，改變激活值，節(jié)點(diǎn)的激活。

在「評估」階段，我們將所有網(wǎng)絡(luò)權(quán)重設(shè)置成相同的值。這樣一來，WANN 實(shí)際上是在尋找可以用最小描述長度來描述的網(wǎng)絡(luò)。在「選擇」階段，我們同時(shí)考慮網(wǎng)絡(luò)連接和模型性能。

圖 11：將 WANN 發(fā)現(xiàn)的網(wǎng)絡(luò)拓?fù)湓诓煌瑥?qiáng)化學(xué)習(xí)任務(wù)上的性能與常用的基線 FF 網(wǎng)絡(luò)進(jìn)行了比較?！笇蚕頇?quán)重調(diào)優(yōu)」只需要調(diào)整一個(gè)權(quán)重值。

如圖 11 所示，WANN 的結(jié)果是同時(shí)使用隨機(jī)權(quán)重和共享權(quán)重（單一權(quán)重）評估得到的。有趣的是，即使在對所有權(quán)重執(zhí)行權(quán)重共享并對于這單個(gè)參數(shù)進(jìn)行調(diào)優(yōu)的時(shí)候，WANN 也可以發(fā)現(xiàn)實(shí)現(xiàn)非常出色的性能的拓?fù)洹?/p>

參考文獻(xiàn)

[1] Nikolaus Hansen. “The CMA Evolution Strategy: A Tutorial” arXiv preprint arXiv:1604.00772 (2016).

[2] Marc Toussaint. Slides: “Introduction to Optimization”

[3] David Ha. “A Visual Guide to Evolution Strategies” blog.otoro.net. Oct 2017.

[4] Daan Wierstra, et al. “Natural evolution strategies.” IEEE World Congress on Computational Intelligence, 2008.

[5] Agustinus Kristiadi. “Natural Gradient Descent” Mar 2018.

[6] Razvan Pascanu & Yoshua Bengio. “Revisiting Natural Gradient for Deep Networks.” arXiv preprint arXiv:1301.3584 (2013).

[7] Tim Salimans, et al. “Evolution strategies as a scalable alternative to reinforcement learning.” arXiv preprint arXiv:1703.03864 (2017).

[8] Edoardo Conti, et al. “Improving exploration in evolution strategies for deep reinforcement learning via a population of novelty-seeking agents.” NIPS. 2018.

[9] Alo?s Pourchot & Olivier Sigaud. “CEM-RL: Combining evolutionary and gradient-based methods for policy search.” ICLR 2019.

[10] Shauharda Khadka & Kagan Tumer. “Evolution-guided policy gradient in reinforcement learning.” NIPS 2018.

[11] Max Jaderberg, et al. “Population based training of neural networks.” arXiv preprint arXiv:1711.09846 (2017).

[12] Adam Gaier & David Ha. “Weight Agnostic Neural Networks.” arXiv preprint arXiv:1906.04358 (2019).

 via https://lilianweng.github.io/lil-log/2019/09/05/evolution-strategies.html 雷鋒網(wǎng) AI 科技評論編譯 雷鋒網(wǎng)

雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。