1
雷鋒網(wǎng) AI 科技評(píng)論按：這是 otoro.net 的系列技術(shù)博客之一，以通俗可視化的方法講解了進(jìn)化策略（Evolution Strategies）中的諸多概念。雷鋒網(wǎng) AI 科技評(píng)論全文編譯如下。
本文將通過(guò)一些可視化的案例向大家解釋進(jìn)化策略是如何工作的。為了方便更多入門(mén)讀者理解本文，我將對(duì)相關(guān)公式做簡(jiǎn)化處理。同時(shí)，我也為希望理解更多數(shù)學(xué)細(xì)節(jié)的讀者提供了相關(guān)數(shù)學(xué)公式的原始論文。這是本系列的第一篇文章，在本系列中，我會(huì)向大家介紹如何在諸如 MNIST、OpenAI Gym、Roboschool、PyBullet 等任務(wù)中應(yīng)用這些算法。
神經(jīng)網(wǎng)絡(luò)模型是非常靈活的，有著強(qiáng)大的數(shù)據(jù)表示能力。如果我們能夠找到合適的模型參數(shù)，我們可以使用神經(jīng)網(wǎng)絡(luò)解決許多困難的問(wèn)題。深度學(xué)習(xí)的成功在很大程度上歸功于使用反向傳播算法，它可以高效地計(jì)算目標(biāo)函數(shù)梯度的能力，而這個(gè)目標(biāo)函數(shù)中包含著所有的模型參數(shù)。通過(guò)這些基于梯度的計(jì)算，我們能高效地在參數(shù)空間中尋找到有利于神經(jīng)網(wǎng)絡(luò)完成任務(wù)的解。
然而，仍然有很多問(wèn)題是反向傳播算法所不適用的。例如，在強(qiáng)化學(xué)習(xí)（reinforcement learning）問(wèn)題中，我們同樣可以訓(xùn)練一個(gè)神經(jīng)網(wǎng)絡(luò)去做一系列的行動(dòng)決策，從而在環(huán)境中完成某些任務(wù)。但是，根據(jù)當(dāng)前訓(xùn)練個(gè)體（agent）做出的操作去估計(jì)未來(lái)給予該訓(xùn)練個(gè)體的獎(jiǎng)勵(lì)信號(hào)的梯度是十分復(fù)雜的，尤其是在未來(lái)的許多時(shí)間步驟上都會(huì)獲得獎(jiǎng)勵(lì)的情況下。更何況即使我們能夠計(jì)算出準(zhǔn)確的梯度，我們?nèi)匀豢赡茉谟?xùn)練過(guò)程中陷入局部最優(yōu)，這是普遍存在于很多強(qiáng)化學(xué)習(xí)任務(wù)中的現(xiàn)象。
在強(qiáng)化學(xué)習(xí)研究中，有一個(gè)領(lǐng)域?qū)ｉT(mén)致力于研究這個(gè)歸因分配問(wèn)題，并且在近年來(lái)取得了很大的進(jìn)展。然而，但獎(jiǎng)勵(lì)信號(hào)十分稀疏時(shí)，歸因分配仍然是很困難的。在現(xiàn)實(shí)世界中，獎(jiǎng)勵(lì)確實(shí)可能是很稀疏而且有噪聲的。有時(shí)，我們僅僅得到了一個(gè)簡(jiǎn)單的獎(jiǎng)勵(lì)，而不知道它是如何做出的。就像一張年終獎(jiǎng)金的支票，它的金額取決于我們的雇主，想確切地弄清楚為什么它如此之低可能是很困難的。對(duì)于這些問(wèn)題，與其依賴(lài)于一個(gè)充斥著噪聲的、并且很可能毫無(wú)意義的對(duì)未來(lái)的我們的策略的梯度估計(jì)，我們不妨大膽地直接忽略掉所有的梯度信息，嘗試使用黑盒的優(yōu)化技術(shù)，例如遺傳算法（genetic algorithms）或進(jìn)化策略（evolution strategies）。
OpenAI 就曾發(fā)表一篇名為《Evolution Strategies as a Scalable Alternative to Reinforcement Learning 》 (https://blog.openai.com/evolution-strategies/ ) 的博文。在這篇文章中，他們認(rèn)為，盡管進(jìn)化策略比強(qiáng)化學(xué)習(xí)利用數(shù)據(jù)的效率較低一些，它仍然有許多的優(yōu)勢(shì)。進(jìn)化策略摒棄了對(duì)于梯度的計(jì)算，這使得對(duì)于進(jìn)化策略的估計(jì)將更加高效。與此同時(shí)，進(jìn)化策略的計(jì)算任務(wù)能夠被很容易地部署到由上千臺(tái)機(jī)器組成的分布式環(huán)境中進(jìn)行并行計(jì)算。實(shí)際上，在OpenAI從頭開(kāi)始多次運(yùn)行了這個(gè)算法后，他們發(fā)現(xiàn)：使用進(jìn)化策略算法發(fā)現(xiàn)的策略相對(duì)于使用強(qiáng)化學(xué)習(xí)發(fā)現(xiàn)的策略，種類(lèi)更多！
在這里，我要指出，即便是對(duì)于確定一個(gè)機(jī)器學(xué)習(xí)模型的問(wèn)題，例如設(shè)計(jì)一個(gè)神經(jīng)網(wǎng)絡(luò)架構(gòu)，我們也是不能直接計(jì)算梯度的。盡管強(qiáng)化學(xué)習(xí)、進(jìn)化策略、遺傳算法這樣的方法都能被用于在解空間中搜索能夠達(dá)到任務(wù)要求的模型參數(shù)，在本文中，我將僅僅著眼于將這些算法應(yīng)用到為一個(gè)預(yù)定義的模型搜索參數(shù)的問(wèn)題中。
下圖為轉(zhuǎn)換后的二維的 Schaffer 函數(shù)和 Rastrigin 函數(shù)的俯視圖，這兩種函數(shù)常常被用作測(cè)試連續(xù)的黑盒優(yōu)化算法的用例。在圖片中，更亮的區(qū)域代表 F(x, y) 有更大的函數(shù)值。如你所見(jiàn)，這個(gè)函數(shù)有許多的局部最優(yōu)點(diǎn)。我們要做的就是找到一系列的模型參數(shù) (x, y)，從而使 F(x, y) 盡可能地接近全局最大值。
盡管人們對(duì)于進(jìn)化策略的定義版本不一。在這里，我們將其定義為：一個(gè)為用戶(hù)提供一系列用于評(píng)估一個(gè)問(wèn)題的候選解決方案的算法。這里的評(píng)估方法是基于一個(gè)給定了解決方案的目標(biāo)函數(shù)，并且會(huì)返回單個(gè)適應(yīng)度。根據(jù)當(dāng)前的解決方案的適應(yīng)度結(jié)果，進(jìn)化策略接著會(huì)生成下一代的候選解決方案，新的方案會(huì)更有可能得到更好的結(jié)果。一旦提出的最佳方案令用戶(hù)滿(mǎn)意，迭代的進(jìn)程就會(huì)被終止。
我們可以通過(guò)類(lèi)似下面這樣的偽碼實(shí)現(xiàn)一個(gè)叫做 EvolutionStrategy 的進(jìn)化策略算法：
solver = EvolutionStrategy()
while True:
# ask the ES to give us a set of candidate solutions
solutions = solver.ask()# create an array to hold the fitness results.
fitness_list = np.zeros(solver.popsize)# evaluate the fitness for each given solution.
for i in range(solver.popsize):
fitness_list[i] = evaluate(solutions[i])# give list of fitness results back to ES
solver.tell(fitness_list)# get best parameter, fitness from ES
best_solution, best_fitness = solver.result()if best_fitness > MY_REQUIRED_FITNESS:
break
盡管我們通常在每一代的迭代進(jìn)程中將種群的規(guī)模設(shè)置為一個(gè)常量，但是實(shí)際上本可以不必這樣做。進(jìn)化策略可以根據(jù)我們的要求生成相應(yīng)數(shù)目的候選方案，這是因?yàn)檫M(jìn)化策略給出的解決方案是從一個(gè)概率分布中抽樣而來(lái)的，這些分布函數(shù)的參數(shù)會(huì)在每一次的迭代中被進(jìn)化策略所更新。我將通過(guò)一個(gè)簡(jiǎn)單的進(jìn)化策略來(lái)解釋這個(gè)抽樣過(guò)程。
我們可以想象到的最簡(jiǎn)單的進(jìn)化策略，可能是直接從一個(gè)均值為 μ、標(biāo)準(zhǔn)差為 σ 的正態(tài)分布中抽樣得到一系列的解。在我們二維的問(wèn)題中，μ=（μx，μy）并且 σ=（σx，σy）。一開(kāi)始，μ 被設(shè)置在原點(diǎn)。在適應(yīng)結(jié)果被評(píng)估之后，我們將 μ 設(shè)置為這一次迭代中在種群中最優(yōu)解，并且在這個(gè)新的均值周?chē)M(jìn)行抽樣得到下一代的解決方案。下圖為這個(gè)簡(jiǎn)單的進(jìn)化策略在之前提到的兩個(gè)問(wèn)題中進(jìn)行20次迭代之后的表現(xiàn)：
在上面的可視化示例中，綠色的點(diǎn)代表每一代分布函數(shù)的均值，藍(lán)色的點(diǎn)是被抽樣到的解，紅色的點(diǎn)是目前我們的算法找到的最優(yōu)解。
這個(gè)簡(jiǎn)單的算法通常只適用于簡(jiǎn)單的問(wèn)題。由于這個(gè)算法本身是一個(gè)貪婪算法，它會(huì)拋棄當(dāng)前的最優(yōu)解之外的所有解。因此，在更加復(fù)雜的問(wèn)題中，這個(gè)算法可能更易于陷入局部最優(yōu)點(diǎn)。（因?yàn)閺?fù)雜問(wèn)題解空間更大，全局最優(yōu)解可能被隱藏在這種簡(jiǎn)單算法拋棄掉的空間里）如果能夠從代表更多的解決方法的概率分布中對(duì)下一次迭代進(jìn)行抽樣，而并非僅僅從當(dāng)前這一代的最優(yōu)解附近抽樣，可能更為有利。
遺傳算法是最經(jīng)典的黑盒優(yōu)化算法之一。對(duì)于遺傳算法來(lái)說(shuō)，它有許多不同程度復(fù)雜的變種，在這里，我只為大家介紹最簡(jiǎn)單的版本。
遺傳算法的思路是十分簡(jiǎn)單的：僅僅將目前這一代最好的前 10% 的解保留下來(lái)，讓種群中其他的解被淘汰掉（類(lèi)似于自然界中的優(yōu)勝劣汰）。在下一代中，我們隨機(jī)選擇上一代幸存下來(lái)的兩個(gè)解作為父親和母親，將他們的參數(shù)進(jìn)行重組，從而得到新的解。這個(gè)較差重組的過(guò)程使用投擲硬幣（隨機(jī)化）的方法來(lái)決定從上一代的父親母親中的哪一方來(lái)繼承當(dāng)前位置上的參數(shù)。在我們使用的這兩個(gè)簡(jiǎn)單的二維測(cè)試函數(shù)中，我們新的解可能以百分十50的概率從雙親其中的一方繼承 x 或 y。在這個(gè)交叉重組的過(guò)程結(jié)束后，帶固定標(biāo)準(zhǔn)差的高斯噪聲也會(huì)被加入到新的解中。（作為正則項(xiàng)）
上圖向大家展示了這個(gè)簡(jiǎn)單的遺傳算法是如何工作的。綠色的點(diǎn)代表棕群眾上一代被保留下來(lái)的「精英」（即用于當(dāng)代交叉重組的雙親），藍(lán)色的點(diǎn)代表用于產(chǎn)生候選解的后代，紅色的點(diǎn)代表最優(yōu)解。
遺傳算法通過(guò)與多種候選解保持聯(lián)系（交叉重組）保證了生成的解的多樣性。然而，實(shí)際上，種群中大多數(shù)幸存下來(lái)的「精英」會(huì)漸漸地易于收斂到局部最優(yōu)點(diǎn)。此外，遺傳算法還有很多復(fù)雜的變形，例如 CoSyNe、ESP 以及 NEAT，它們希望通過(guò)將種群中相似的解聚類(lèi)到不同的物種子集中，從而保證生成解的多樣性。
簡(jiǎn)單的進(jìn)化策略和遺傳算法有一個(gè)共同的缺點(diǎn)，即我們?cè)肼暤臉?biāo)準(zhǔn)差參數(shù)是固定的。有時(shí)，我們會(huì)希望在更大的解空間中探索更好的解，因此我們需要增加我們搜索空間的標(biāo)準(zhǔn)差。此外，我們有時(shí)十分確信我們已經(jīng)探索到最優(yōu)解附近了，那么我們只想對(duì)當(dāng)前的解進(jìn)行微調(diào)。我們主要希望我們的搜索過(guò)程能夠有下圖這樣的表現(xiàn)：
多么神奇啊！上圖所示的搜索過(guò)程是通過(guò)協(xié)方差矩陣自適應(yīng)進(jìn)化策略（Covariance-Matrix Adaptation Evolution Strategy , CMA-ES）得到的。CMA-ES 算法可以得到每一次迭代的結(jié)果，并且自適應(yīng)地在下一代的搜索中增大或者減小搜索空間。他不僅僅會(huì)自適應(yīng)地調(diào)整參數(shù) μ 和 σ，同時(shí)還會(huì)計(jì)算整個(gè)參數(shù)空間的協(xié)方差矩陣。在每一次迭代中，CMA-ES 會(huì)提供一個(gè)多元正態(tài)分布的參數(shù)，并從這個(gè)多元正態(tài)分布中抽樣得到新的解。那么，這個(gè)算法如何知道該增大還是減小搜索空間呢？
在我們討論該算法做到自適應(yīng)的方法之前，我將先帶大家復(fù)習(xí)一下如何對(duì)協(xié)方差矩陣做估計(jì)。這對(duì)于我們之后理解 CMA-ES 算法所使用的自適應(yīng)方法十分重要。如果我們想要對(duì)一個(gè)我們整個(gè)抽樣得到的大小為 N 的協(xié)方差矩陣進(jìn)行參數(shù)估計(jì)，我們可以使用下面列出的公式去計(jì)算協(xié)方差矩陣C的最大似然估計(jì)。我們首先計(jì)算我們的種群中 xi 和 yi 的均值：
2*2的協(xié)方差矩陣中的元素可以表示為：
當(dāng)然，這樣得出的 μx 和μy 的均值估計(jì)，以及協(xié)方差項(xiàng) σx、σy 和 σxy 僅僅是實(shí)際的原始抽樣協(xié)方差矩陣的參數(shù)估計(jì)，對(duì)我們來(lái)說(shuō)并不是特別有用。
CMA-ES 巧妙地修正了上面的協(xié)方差計(jì)算公式，從而使得它能夠適用于最優(yōu)化問(wèn)題。我會(huì)詳細(xì)說(shuō)明它是如何做到這一點(diǎn)的。首先，它的主要任務(wù)是找出當(dāng)前這一代最優(yōu)秀的 N 個(gè)解 Nbest 。為了方便起見(jiàn)，我們規(guī)定 Nbest 為最優(yōu)秀的前 25% 的解。在根據(jù)適應(yīng)情況將得出的解排序后，我們將僅僅通過(guò)當(dāng)代（g）最優(yōu)秀的前25%的解去計(jì)算下一代（g+1）的均值 μ（g+1），換句話(huà)說(shuō)，我們的計(jì)算過(guò)程可以被表示為下面的公式：
接下來(lái)，我們僅僅使用最優(yōu)的前 25% 的解去估計(jì)下一代的協(xié)方差矩陣 C（g+1）。在這里，我們想到了一個(gè)聰明的計(jì)算方法：使用當(dāng)代的均值 μg，而不是我們剛剛更新的 μ（g+1）。具體的計(jì)算公式如下：
在我們得到了下一代（g+1）的 μx、μy、σx、σy、σxy 等參數(shù)后，我們現(xiàn)在可以抽樣得到下一代的候選解。
這一連串圖片形象地解釋了這個(gè)算法如何根據(jù)當(dāng)代（g）的計(jì)算結(jié)果去構(gòu)造下一代（g+1）的解：
計(jì)算第 g 代中每一個(gè)解的適應(yīng)程度
將第 g 代的最優(yōu)的前 25% 的解挑選出來(lái)，如圖中紫色的點(diǎn)所示
僅僅使用這些最優(yōu)的前 25% 的解和當(dāng)代的均值 μg（如圖中綠色的點(diǎn)所示），來(lái)計(jì)算下一代的協(xié)方差矩陣C（g+1）
使用更新后的均值μ（g+1）和協(xié)方差矩陣C（g+1）得到的分布函數(shù)，抽樣得出新的候選解集。
下面，讓我們?cè)僖淮螌⒃趦蓚€(gè)問(wèn)題中的整個(gè)搜索過(guò)程可視化地呈現(xiàn)在大家面前：
由于 CMA-ES 算法可以利用最優(yōu)解的信息調(diào)整其均值和協(xié)方差矩陣，它可以在還距離最優(yōu)解很遠(yuǎn)時(shí)對(duì)較大的空間進(jìn)行搜索，在距離最優(yōu)解較近時(shí)對(duì)較小的搜索空間進(jìn)行探索。為了便于理解，我這里通過(guò)一個(gè)簡(jiǎn)單的 2 維問(wèn)題對(duì) CMA-ES 的介紹是高度簡(jiǎn)化的。如果想了解更多的細(xì)節(jié)，我建議你去閱讀 CMA-ES 的作者為大家準(zhǔn)備的教程 CMA-ES Tutorial (https://arxiv.org/abs/1604.00772)。
CMA-ES 算法是如今最流行的無(wú)需梯度計(jì)算的優(yōu)化算法之一，并且已經(jīng)被許多研究者和實(shí)際工程人員選用。它真正的唯一的缺點(diǎn)是：當(dāng)模型中的參數(shù)過(guò)多時(shí)候，算法的性能如何。通過(guò)計(jì)算，我們發(fā)現(xiàn)計(jì)算協(xié)方差的時(shí)間復(fù)雜度是 O(N2)，盡管最近人們已經(jīng)將時(shí)間復(fù)雜度降到了近似于 O(N)。對(duì)我來(lái)說(shuō)，當(dāng)搜索空間內(nèi)的參數(shù)少于 1000 時(shí)，我往往會(huì)選擇 CMA-ES 算法。如果我足夠有耐心，我發(fā)現(xiàn)在高達(dá) 10000 個(gè)參數(shù)的搜索空間中使用該算法也是同樣可行的。
假設(shè)你已經(jīng)構(gòu)建了一個(gè)人工生命模擬器，并且你想從中抽取出一個(gè)神經(jīng)網(wǎng)絡(luò)去控制一群中每個(gè)螞蟻的行為。而如果我們使用簡(jiǎn)單的進(jìn)化策略，這種優(yōu)化方式會(huì)讓螞蟻的特性和行為朝著使每個(gè)螞蟻個(gè)體各自受益的方向演變。這樣一來(lái)，我們的種群中會(huì)充滿(mǎn)只顧自己死活的自私的螞蟻。
在這里我們不再使用讓最適應(yīng)環(huán)境的螞蟻生存下來(lái)的準(zhǔn)則。如果我們改變策略，使用整個(gè)種群中所有個(gè)體適應(yīng)程度的總和作為度量標(biāo)準(zhǔn)，并且轉(zhuǎn)而優(yōu)化這個(gè)總和使得整個(gè)種群的康樂(lè)指數(shù)最大，結(jié)果會(huì)如何呢？哈哈，你最終將會(huì)創(chuàng)造一個(gè)馬克思主義的螞蟻烏托邦！
對(duì)于上述的這些信息算法，人們已經(jīng)意識(shí)到它們都有一個(gè)缺點(diǎn)：它們會(huì)拋棄掉大多數(shù)的解而僅僅保留最優(yōu)解。然而，那些較差的解往往包含「不要做」什么的信息，這種信息對(duì)于更好的計(jì)算出下一代的參數(shù)估計(jì)是十分有價(jià)值的。
許多研究強(qiáng)化學(xué)習(xí)的研究者對(duì)于這篇名為 REINFORCE 的論文（http://www-anw.cs.umass.edu/~barto/courses/cs687/williams92simple.pdf ）十分熟悉。在這篇1992年發(fā)表的論文中，Williams 概述了一個(gè)用于估計(jì)關(guān)提出了于策略神經(jīng)網(wǎng)絡(luò)模型的參數(shù)的期望獎(jiǎng)勵(lì)的方法。在這篇論文的第 6 章中，作者也提出了使用強(qiáng)化學(xué)習(xí)作為一種進(jìn)化策略的方式。這個(gè)強(qiáng)化學(xué)習(xí)和進(jìn)化策略相結(jié)合的特例在 Parameter-Exploring Policy Gradients (PEPG, 2009) and Natural Evolution Strategies (NES, 2014)這兩篇文章中得到了進(jìn)一步的討論和擴(kuò)展。
在這個(gè)計(jì)算方法中，我們希望利用種群中所有個(gè)體的信息，無(wú)論是好是壞。這么做是為了估計(jì)出能夠使整個(gè)種群在下一代朝著更好的方向發(fā)展的梯度信號(hào)。由于我們?cè)谶@里需要對(duì)梯度進(jìn)行估計(jì)，我們同樣可以使用被廣泛應(yīng)用于深度學(xué)習(xí)的標(biāo)準(zhǔn)的隨機(jī)梯度下降（SGD）法則來(lái)更新梯度。如果需要，我們甚至可以使用動(dòng)量隨機(jī)梯度下降法（Momentum SGD）、均方根傳播法（RMSProp）以及自適應(yīng)動(dòng)量估計(jì)算法（Adam）來(lái)求解模型參數(shù)。
在這里，我們的思路是最大化抽取出的解的適應(yīng)程度到的期望值。如果期望的結(jié)果足夠好，那么抽樣得到的種群中表現(xiàn)最好的個(gè)體甚至?xí)?，因此?duì)期望進(jìn)行優(yōu)化是一個(gè)很合乎情理的方案。最大化抽樣得到的解的期望適應(yīng)程度，可以近似地被看作最大化整個(gè)種群的適應(yīng)程度。
假設(shè)z是從概率分布函數(shù) π（z，θ）中抽樣得到的解向量，我們可以將目標(biāo)函數(shù)F的期望值定義為：
其中，θ是概率分布函數(shù)的參數(shù)。例如，假設(shè) π 是一個(gè)正態(tài)分布，那么相應(yīng)地，θ 就是 μ 和 σ。對(duì)于我們簡(jiǎn)單的二維問(wèn)題而言，每一個(gè) z 都是一個(gè)二維向量（x，y）的整體。
論文 Natural Evolution Strategies (NES, 2014) 很詳細(xì)地說(shuō)明了 J（θ）關(guān)于 θ 的梯度是如何計(jì)算得來(lái)的。我們可以使用和 REINFORCE 算法相同的對(duì)數(shù)似然方法計(jì)算 J（θ）的梯度，具體公式如下：
在一個(gè)規(guī)模為 N 的種群中，我們將解表示為 z1、z2...zn，我們可以通過(guò)下面的和式估計(jì)梯度：
在得到了梯度之后，我們可以使用參數(shù) α（例如 0.01）來(lái)表示學(xué)習(xí)率，并且開(kāi)始優(yōu)化概率分布函數(shù) π 的參數(shù) θ，從而使得我們抽樣得到的解能夠更有可能在目標(biāo)函數(shù) F 上取得更高的適應(yīng)度。使用隨機(jī)梯度下降法（或者 Adam 算法），我們可以按照如下的方式更新下一代的參數(shù)θ：
之后，我們從這個(gè)更新后的概率分布函數(shù)中抽樣得到新的候選解集。我們會(huì)循環(huán)迭代以上的操作，直到我們找到了一個(gè)令人滿(mǎn)意的解。
在論文 REINFORCE 的第六章中，Williams 推導(dǎo)出了梯度
的通用解法的公式，他考慮了 π（z，θ）是分解后的多元正態(tài)分布的特例（換而言之，參數(shù)的相關(guān)系數(shù)為 0）。在這個(gè)特例中，θ是 μ 和 σ 向量。因此，解的每一個(gè)元素可以從單元正態(tài)分布中抽樣得到：
對(duì)于每一個(gè)解 i 的 θ 向量中每一個(gè)獨(dú)立元素，通用的梯度公式
可以按照如下的方式進(jìn)行推導(dǎo)：
為了更清楚地向大家說(shuō)明，我使用角標(biāo) j 在參數(shù)空間中進(jìn)行計(jì)數(shù)，而我們使用上標(biāo) i 來(lái)對(duì)總種群抽樣得到的個(gè)體進(jìn)行計(jì)數(shù)，這二者不會(huì)被混淆。在我們的二維問(wèn)題中，z1=x, z2 = y, μ1=μx, μ2=μy, σ1=σx, σ2=σy。
上面這兩個(gè)公式可以被帶回到梯度近似公式中，并且推導(dǎo)出明確的對(duì) μ 和 σ 進(jìn)行更新。本文之前提到的論文都推導(dǎo)出了更明確的更新規(guī)則，包含了一個(gè)用于比較的基線(xiàn)，并且可以引入其他的類(lèi)似于 PEPG 中對(duì)偶抽樣的蒙特卡羅技巧，這也是我們賴(lài)以執(zhí)行算法的基礎(chǔ)。舉例而言，論文 Natural Evolution Strategies (NES, 2014) 提出了將 Fisher 信息矩陣的逆矩陣引入梯度更新規(guī)則的方法。然而，這個(gè)思想與其他的進(jìn)化策略算法是相同的，它們都在每一代中更新了多元正態(tài)分布的均值和標(biāo)準(zhǔn)差，并且從更新后的概率分布中進(jìn)行抽樣得到新的解集。下圖是這兩個(gè)公式執(zhí)行動(dòng)作的可視化圖解：
如圖所示，這種算法能夠按需動(dòng)態(tài)地改變 σ，用以探索或者微調(diào)解的空間。與 CMA-ES 不同，本算法的實(shí)現(xiàn)并不涉及相關(guān)性結(jié)構(gòu)（如協(xié)方差）的計(jì)算。因此在這里，我們并沒(méi)有得到對(duì)角型的橢圓樣本，僅僅得到了垂直或者水平的樣本。當(dāng)然，如果需要的話(huà)，我們也可以在以機(jī)選效率為代價(jià)的情況下，引入整個(gè)協(xié)方差矩陣，從而推導(dǎo)出新的更新規(guī)則。
另外一個(gè)我喜歡這個(gè)算法的原因是，它能像 CMA-ES 那樣，動(dòng)態(tài)調(diào)整標(biāo)準(zhǔn)差，以致于我們可以逐漸增大或減小我們的搜索空間。因?yàn)樵谶@個(gè)算法中，我們沒(méi)有使用刻畫(huà)相關(guān)性的參數(shù)，所以這個(gè)算法的時(shí)間復(fù)雜度為 O（N），那么當(dāng)搜索空間較大，以致于 CMA-ES 性能比較差的時(shí)候，我會(huì)選擇使用 PEPG。通常，當(dāng)模型參數(shù)超過(guò)幾千時(shí)，我會(huì)選擇 PEPG。
在 OpenAI 的論文中，他們實(shí)現(xiàn)的算法是之前提到的強(qiáng)化學(xué)習(xí)和進(jìn)化策略相結(jié)合的那個(gè)特例。特別地，σ被固定為一個(gè)常量，只有參數(shù) μ 會(huì)在每一代中被更新。下圖所示為將σ固定為常量后這個(gè)進(jìn)化策略工作的過(guò)程示例：
除了對(duì)這個(gè)原始算法進(jìn)行簡(jiǎn)化，本文也提出了一個(gè)新的更新規(guī)則的修正，使其能夠在不同的工作站機(jī)器組成的集群中進(jìn)行并行計(jì)算。在這個(gè)更新規(guī)則中，大量的基于固定種子的隨機(jī)數(shù)被事先與計(jì)算了出來(lái)。由此，每個(gè)工作站可以復(fù)制其他機(jī)器的參數(shù)，并且它只需要與其他機(jī)器進(jìn)行一個(gè)數(shù)字的通信，即最終的適應(yīng)度結(jié)果。如果我們想將進(jìn)化策略擴(kuò)展到數(shù)以千計(jì)、甚至數(shù)以百萬(wàn)計(jì)的不同的計(jì)算節(jié)點(diǎn)中去，這個(gè)修正的更新規(guī)則就顯得十分重要了。因?yàn)?，在每一次迭代的更新中每次都將整個(gè)解向量傳輸百萬(wàn)次是不切實(shí)際的。但如果每次值傳輸最終的適應(yīng)度結(jié)果就應(yīng)該是可行的了。在這篇論文中，他們展示了：使用亞馬遜 EC2 平臺(tái)上的 1440 個(gè)工作站可以在大約十分鐘內(nèi)解決 Mujoco 人形機(jī)器人行走的問(wèn)題。
我認(rèn)為，理論上來(lái)說(shuō)，這個(gè)并行更新規(guī)則應(yīng)該也對(duì)那些同樣能夠調(diào)整標(biāo)準(zhǔn)差 σ 的算法奏效。然而，實(shí)際的情況是，他們只是為了大規(guī)模的并行計(jì)算，希望將需要傳輸?shù)牟糠纸档阶钌佟＿@篇頗具啟發(fā)意義的文章同時(shí)也討論了許多其他的將進(jìn)化策略部署到強(qiáng)化學(xué)習(xí)領(lǐng)域的任務(wù)中的實(shí)踐工作。我強(qiáng)烈推薦你們仔細(xì)研讀這篇文章，進(jìn)行深入探究。
上面提到的大部分算法通常都會(huì)與構(gòu)造適應(yīng)度的方法結(jié)合起來(lái)，例如接下來(lái)我要討論「基于排序的適應(yīng)度構(gòu)造方法」。對(duì)適應(yīng)度的構(gòu)造可以讓我們避免之前提到的種群中的離群點(diǎn)對(duì)于近似梯度計(jì)算的控制。具體的公式如下：
如果一個(gè)特殊的點(diǎn) F（zm）比種群中其它的點(diǎn) F（zi）都大得多，那么梯度可能被這個(gè)離群點(diǎn)控制，并且增加算法陷入局部最優(yōu)的概率。為了緩解這個(gè)問(wèn)題，我們可以使用適應(yīng)度的排序轉(zhuǎn)換。我們?cè)谶@里不使用適應(yīng)度函數(shù)的真實(shí)值，轉(zhuǎn)而使用一個(gè)與解在種群中的排序成正比的增強(qiáng)適應(yīng)度函數(shù)對(duì)結(jié)果進(jìn)行排序。下圖是分別使用原始的適應(yīng)度和基于排序的適應(yīng)度函數(shù)的效果對(duì)比圖：
如圖所示，假如我們有一個(gè)包含 101 個(gè)樣本的種群，我們會(huì)估計(jì)種群中每個(gè)個(gè)體的真實(shí)適應(yīng)度函數(shù)值，并且根據(jù)他們的適應(yīng)度將解排序。在這里，我們將會(huì)給表現(xiàn)最差的個(gè)體賦予一個(gè)值為 -0.50 的強(qiáng)化適應(yīng)度函數(shù)值，給倒數(shù)第二的解賦予 -0.49，...，賦予0.49 給表現(xiàn)第二好的解，賦予0.50給最好的解。這個(gè)強(qiáng)化適應(yīng)度的集合會(huì)被用來(lái)計(jì)算梯度的更新。從某種程度上來(lái)說(shuō)，這類(lèi)似于在深度學(xué)習(xí)中直接使用批量歸一化（batch-normalization）處理結(jié)果，但我們這種方式更為直接。還有一些其它的構(gòu)造適應(yīng)度的方法，但是他們最終基本上都會(huì)給出一個(gè)相似的結(jié)果。
我發(fā)現(xiàn)，當(dāng)策略網(wǎng)絡(luò)的目標(biāo)函數(shù)是非確定性函數(shù)時(shí)，適應(yīng)度構(gòu)造在強(qiáng)化學(xué)習(xí)任務(wù)中是十分有用的。而由于隨機(jī)生成的映射關(guān)系和各種各樣的隨機(jī)策略，這種情況是十分常見(jiàn)的。對(duì)于那些確定性的、性能良好的函數(shù)而言，使用適應(yīng)度構(gòu)造方法的用處不大，而且有時(shí)還會(huì)使找到最優(yōu)解的速度變慢。
盡管相較于基于梯度的算法，進(jìn)化策略可能是一種能夠找到更多有奇效的解的方法。它仍然在很多能夠計(jì)算出高質(zhì)量的梯度的問(wèn)題上，比基于梯度的算法效果差。就好比，用遺傳算法做圖像分類(lèi)是十分荒謬的事情！但是，有時(shí)候，還真有人這么做，而且竟然有時(shí)這種嘗試還挺有效！
由于目前幾乎所有的機(jī)器學(xué)習(xí)算法都會(huì)在 MNIST 數(shù)據(jù)集上進(jìn)行測(cè)試，我在這里也試著去將這些各種各樣的進(jìn)化策略算法應(yīng)用到一個(gè)簡(jiǎn)單的、兩層的用于對(duì) MNIST 手寫(xiě)數(shù)字進(jìn)行分類(lèi)的卷積網(wǎng)絡(luò)中。我只想看看我們的算法與隨機(jī)梯度下降（SGD）相比，性能如何。由于這個(gè)卷積網(wǎng)絡(luò)只有大約 11000 個(gè)參數(shù)，所以我們可以使用較為慢一點(diǎn)的 CMA-ES 算法。相關(guān)的代碼和實(shí)驗(yàn)信息可以在下面的鏈接中找到。（https://github.com/hardmaru/pytorch_notebooks/tree/master/mnist_es）
以下是使用不同的進(jìn)化策略得到的結(jié)果，我們使用了一個(gè)包含 101 個(gè)個(gè)體的種群，迭代計(jì)算了 300 次。我們持續(xù)記錄了每一代結(jié)束時(shí)表現(xiàn)最好的模型的參數(shù)，并且在 300 次迭代后評(píng)估了這個(gè)模型。有趣的是，這個(gè)模型有時(shí)在測(cè)試集上的準(zhǔn)確率大大高于那些得分較低的訓(xùn)練集的模型。
我們應(yīng)該批判地看的這個(gè)實(shí)驗(yàn)結(jié)果，這是因?yàn)槲覀冎贿\(yùn)行了一次代碼，而不是取 5-10 次運(yùn)行結(jié)果的平均值。這個(gè)基于一次實(shí)驗(yàn)的結(jié)果似乎說(shuō)明了，CMA-ES 模型在 MNIST 手寫(xiě)數(shù)字任務(wù)中是表現(xiàn)最好的，但是PEPG 算法也并沒(méi)有差太遠(yuǎn)。這兩個(gè)算法都達(dá)到了大約 98% 的測(cè)試準(zhǔn)確率，比用作對(duì)比的基線(xiàn) SGD 和Adam 低大約 1%。也許，能夠動(dòng)態(tài)地在每一次迭代中調(diào)整協(xié)方差矩陣和標(biāo)準(zhǔn)差參數(shù)的能力使得它能夠微調(diào)權(quán)重，這比 OpenAI 提出的更簡(jiǎn)單的進(jìn)化策略的變體要更好。
我們之前在文章中提到的所有這些算法都可能有開(kāi)源的實(shí)現(xiàn)。CMA-ES的作者 Nikolaus Hansen 已經(jīng)維護(hù)了一個(gè)基于 numpy 庫(kù)的帶有許多附加功能的 CMA-ES 的實(shí)現(xiàn)。他的 CMA-ES 的 python 實(shí)現(xiàn)版本使我在之前接觸到了循環(huán)訓(xùn)練借口。因?yàn)檫@個(gè)接口十分易于使用，我也使用這個(gè)接口實(shí)現(xiàn)了一些其他的算法，例如簡(jiǎn)單的遺傳算法、PEPG 以及 OpenAI 的進(jìn)化策略算法。我將這些實(shí)現(xiàn)放在了一個(gè)小的名為 es.py 的 python 文件中，并且將原始的 CMA-ES 算法庫(kù)也打包了進(jìn)來(lái)。由此，我可以通過(guò)改變代碼中的一行進(jìn)行切換，從而快速比較不同的進(jìn)化策略算法：
import es
#solver = es.SimpleGA(...)
#solver = es.PEPG(...)
#solver = es.OpenES(...)
solver = es.CMAES(...)while True:
solutions = solver.ask()
fitness_list = np.zeros(solver.popsize)
for i in range(solver.popsize):
fitness_list[i] = evaluate(solutions[i])solver.tell(fitness_list)
result = solver.result()
if result[1] > MY_REQUIRED_FITNESS:
break
你可以在 Github 和 Ipython notebook 上看到使用不同進(jìn)化策略的 es.py 文件：https://github.com/hardmaru/estool/blob/master/simple_es_example.ipynb
在這個(gè)包含 es.py文件的 Ipython notebook ( https://github.com/hardmaru/estool/blob/master/simple_es_example.ipynb ) 中，展示了在 es.py 中使用進(jìn)化策略去解決解決具有更多局部最優(yōu)的一百維 Rastrigin 函數(shù)優(yōu)化問(wèn)題。這個(gè)一百維的版本比上述用與生成可視化圖解的二維版本更加具有挑戰(zhàn)性。下圖是我們之前討論過(guò)的那些算法在這個(gè)問(wèn)題上的性能對(duì)比圖：
在這個(gè) 100 維的 Rastrigin 函數(shù)優(yōu)化問(wèn)題中，沒(méi)還有一個(gè)優(yōu)化算法達(dá)到了全局最優(yōu)解，其中使用 CMA-ES 算法得到的結(jié)果是最接近全局最優(yōu)的，比其他算法都好多得多。PEPG 算法的性能排在第二位，OpenAI 的進(jìn)化策略算法和遺傳算法的性能則相對(duì)較差一些。這讓我不得不用一個(gè)模擬退火方法去漸漸減小標(biāo)準(zhǔn)差 σ，讓它在這個(gè)任務(wù)中表現(xiàn)得好一些。
使用CMA-ES算法在100維的Ras函數(shù)優(yōu)化問(wèn)題中最終得到的解，全局最優(yōu)解應(yīng)該是一個(gè)100維的元素的值為10的向量
在接下來(lái)的文章中，我會(huì)嘗試將進(jìn)化策略應(yīng)用到其它的實(shí)驗(yàn)和有趣的問(wèn)題中。歡迎大家持續(xù)關(guān)注本系列文章！
via otoro，雷鋒網(wǎng) AI 科技評(píng)論編譯
雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見(jiàn)轉(zhuǎn)載須知。
