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