從遺傳算法到OpenAI新方向:進化策略工作機制全解

 2017-11-11 11:08:00.0

原標題:從遺傳算法到OpenAI新方向:進化策略工作機制全解

選自otoro.net

參與:陳韻竹、劉曉坤

在這篇文章中,作者用一些簡單的視覺案例解釋了進化策略(Evolution Strategies)的工作方式,其中包括了簡單進化策略、簡單遺傳算法、CMA-ES、自然進化策略以及 OpenAI 的進化策略,並給出了形象的動態圖過程展示。

「適者生存」

我儘量簡化了公式,如果讀者想理解更多的細節,我提供了原始文章的鏈接。這是這一系列文章的第一篇,在文章中,我將展現如何將這些算法應用到諸如 MNIST、OPENAI Gym、Roboschool 和 PyBullet 等多種環境中。

簡介

神經網絡模型具有高度的表達性和靈活性。如果能找到一系列合適的模型參數,我們就可以運用神經網絡去解決許多有挑戰性的問題。深度學習的成功主要來源於反向傳播算法,因爲它可以有效地使用每個模型的參數去計算目標函數的梯度。有了這些梯度,我們就能有效地在參數空間中選取好的解,來解決我們的神經網絡解決難題。

然而,也有許多反向傳播算法無法應用的問題。舉個例子,在強化學習(reinforcement learning)當中,我們同樣可以訓練一個神經網絡,從而形成一系列的行動決策,去完成環境中的某些任務。然而,特別是在未來多個時間步才能實現回報的情況下,通過當下的動作去估計未來獎勵信號的梯度是非常重要的。退一步說,即使我們可以計算準確的梯度,在強化學習中也有許多陷入局部最優的情況。

「陷入局部最優」

整個強化學習領域都致力於研究這個信度分配問題(credit-assignment problem),近年來也有很大的進展。然而,當獎勵信號非常稀疏時,信度分配問題仍非常困難。在真實世界裏,獎勵可能是稀疏且有噪聲的。有時候,我們只是得到了一個簡單的獎勵,比如一張年終獎金支票,而且其數目取決於我們的僱傭者,我們可能很難確切地知道爲什麼獎金如此之低。對於這些問題,與其依賴這些高噪聲、且很有可能無意義的未來梯度信號估計,我們不如直接忽略任何的梯度信號,並嘗試着使用一些黑箱優化技術(black-box optimization),例如遺傳算法(genetic algorithms)或進化策略。

OpenAI 發表了一篇名爲「用作強化學習的可擴展替代的進化策略」(Evolution Strategies as a Scalable Alternative to Reinforcement Learning (https://blog.openai.com/evolution-strategies/))的論文,(機器之心文章:深度 | 谷歌和 OpenAI 新研究:如何使用達爾文進化論輔助設計人工智能算法?)其中表示,儘管進化策略比強化學習的數據效率低,它仍然有許多優勢。進化策略擯棄梯度計算的方法,從而能更有效地評價這些算法。同時,利用進化策略算法,很容易將計算分配到上千臺機器中完成並行計算。研究發現,通過多次運行進化策略算法,相較於強化學習算法,使用進化策略算法發現的策略種類更多。

我想指出,即使是對那些識別機器學習模型的問題,如設計一個神經網絡的架構,我們也無法直接計算梯度。儘管諸如強化學習、進化策略、遺傳算法,能夠被應用於搜索模型空間以及用於解決實際問題的模型參數,這篇文章只會關注一部分,即將這些算法應用到預定義的模型中,並找尋模型參數。

什麼是進化策略?

「二維 Rastrign 函數有許多局部最優(來源:維基百科)」

下面的圖片是轉換的二維 Schaffer 函數和 Rastrigin 函數的俯視圖,作爲簡單的工具常常被用於測試連續的黑箱優化算法。圖中顏色更淺的區域代表了更大的函數值 F(x, y) 。正如你所見,這個函數中有許多的局部最優。我們的工作就是去尋找一系列的模型參數 (x, y),使得 F(x, y) 能夠儘量接近全局最大值。

進化策略的定義多種多樣。我們可以將之定義爲,一種爲用戶提供多個競爭方案以評估問題的算法。這個評估是基於一個給定解決方案的目標函數,並會返回單個擬合(fitness)值。基於當下解決方案的擬合結果,算法會接着提供下一代的競爭方案,與當前代的方案相比,這些方案更有可能會得到更好的結果。一旦提出了用戶滿意的最佳方案,迭代進程就會結束。

假設我們的算法命名爲 EvolutionStrategy,我們可以運用如下的方式:

  1. solver = EvolutionStrategy()

  2. whileTrue:

  3. # ask the ES to give us a set of candidate solutions

  4. # 使用進化策略(ES)給出多個競爭方案

  5. solutions = solver.ask()

  6. # create an array to hold the solutions.

  7. # 創建一個數組,保存這些方案

  8. fitness_list = np.zeros(solver.popsize)

  9. # evaluate the fitness for each given solution.

  10. # 評估每個方案的擬合度

  11. fori inrange(solver.popsize):

  12. fitness_list[i] = evaluate(solutions[i])

  13. # give list of fitness results back to ES

  14. # 將擬合結果返回給ES

  15. solver.tell(fitness_list)

  16. # get best parameter, fitness from ES

  17. # 從ES得到最佳參數和擬合度

  18. best_solution, best_fitness = solver.result()

  19. ifbest_fitness > MY_REQIRED_FITNESS:

  20. break

通常來說,會將每一代競爭方案的規模保持爲常量,但其實這並不必要。進化策略可以根據所需,形成許多競爭方案。這是因爲這些由進化策略給出的方案是從一個分佈函數中抽樣的,而這些分佈函數將會在每一代被進化策略更新。我會使用一個簡單進化策略的例子解釋這個抽樣的過程。

簡單進化策略

可以想象,一種最簡單的進化策略,就是單純地從正態分佈(平均值爲 μ,標準差爲 σ)中直接抽樣。在我們的二維問題中,有 μ=(μ_x,μ_y) 以及 σ = (σ_x, σ_y)。首先初始化一個μ值。在擬合度結果被評估之後,我們將平均值μ設定爲本代競爭方案中最優解,並且在這個新的均值周圍進行下一代解決方法的抽樣。以下就是把這個算法用於之前提過的兩個問題的 20 代的表現:

在上述的可視化表示中,綠色圓點表示每代分佈的平均值,藍色圓點表示被抽樣的方案,而紅色圓點就是當前被我們的算法找到的最佳方案。

這個簡單的算法通常只對簡單的問題有效。因爲它貪婪的本性,算法會拋棄除了最佳方案外的一切方案,所以可能在更困難的問題中傾向於陷入局部最優。如果能夠從一個表示更多種方案的概率分佈中爲下一代抽樣,而不是隻從當前代的最優解附近抽樣,可能更爲有利。

簡單遺傳算法

遺傳算法是最古老的黑箱優化算法之一。遺傳算法有許多的變形和不同程度的複雜度,但在此只闡明最簡單的版本。

這個遺傳算法的思想非常簡單:只保留當前代最佳的前 10% 的方案,捨棄其他方案。在下一代中,抽樣一個新的方案的辦法是,隨機選取前一代的兩個方案作爲雙親,並重新組合這些參數,從而形成一個新的方案。這種交叉重新組合的方法使用了擲硬幣的辦法,決定從雙親中的哪一方獲取每一個參數。在我們的二維函數中,我們的新方案會以 50% 的機率從雙親的任何一方中繼承 x 或 y。在重新組合之後,有着固定標準差的高斯噪聲也會出現在每一個新的方案中。

上面的圖片闡述了簡單遺傳算法是如何工作的。綠色圓點表示了上一代中的精英方案,藍色圓點便是競爭方案的子代,而紅色圓點是最優解。

遺傳算法通過與不同種類的競爭方案保持聯繫的方法生成下一代,從而保證了多樣性。然而,在實際過程中,大部分留存下來的精英方案傾向於逐漸收斂到局部最優。遺傳算法有許多複雜的變形,比如 CoSyNe、ESP 和 NEAT,它們的想法主要是將類似的解決方案集聚到不同的種類中,從而更好地在過程中更好地保持多樣性。

協方差矩陣適應性進化策略(CMA-ES)

簡單進化策略和遺傳算法的一個共同缺點是,標準差的噪聲參數是固定的。有時候,我們會想探索更多可能,並增加我們的搜索空間的標準差;有時候,我們有自信正在一個最優值附近,只是想微調這個方案。基本上來說,我們希望我們的研究進程像下圖這樣展現:

是不是很神奇?上述圖像所展示的研究策略,就運用了協方差矩陣自適應進化策略(Covariance-Matrix Adaptation Evolution Strategy , 以下簡稱 CMA-ES)。CMA-ES 是這樣一種算法,它可得到每一代的結果,並且適應性的增加或減小下一代的搜索範圍。它不只是根據 μ 和 σ 調整適應性,還會計算整個參數空間的協方差矩陣。在每一代中,CMA-ES 會提供一個多變量的正態分佈的參數,用於下一代的抽樣。那麼,它是如何增加或減少搜索範圍的呢?

在我們討論它使用的方法之前,讓我們複習一下如何評估一個協方差矩陣。這對於之後研究 CMA-ES 的方法非常重要。如果我們想評估一個大小爲 N 的樣本的協方差矩陣,我們可以使用下面的方程去計算協方差矩陣 C 的最大似然估計。我們首先計算了樣本中 x_i 和 y_i 的平均值:

一個 2x2 的協方差矩陣 C 的元素是這樣的:

當然,產生的平均值 μ_x 和 μ_y 以及協方差σ_x、σ_y 和σ_xy 只是對於實際的、原始抽樣的協方差矩陣的一個估計,對我們而言並不是非常有用。

CMA-ES 聰明地修改了上述的協方差計算公式,使得它能夠適應一個優化問題。我會一步一步地講解這是怎麼做的。首先,它關注的是當前代的 N_best 個最優解。爲了簡化,我們取 N_best 爲解中的前 25%。在根據擬合度挑選出方案之後,我們僅通過當前代(g)樣本的 25% 的解去計算下一代(g+1)的平均值μ^(g+1),比如:

接下來,我們僅僅使用解中最佳的 25% 去估計下一代的協方差矩陣 C^(g+1),但我們用了一個聰明的辦法:在計算中沒有使用更新的 μ^(g+1),而使用當前代的 μ^(g):

在有了下一代(g+1)的一系列參數μ_x, μ_y, σ_x, σ_y, 和 σ_xy 之後,我們現在可以抽樣出下一代的競爭方案了。

下面是一系列視覺圖像,清晰地展現瞭如何使用當前代(g)的結果去構建下一代的方案:

1. 計算第 g 代中每一個競爭方案的擬合度;

2. 挑選出第 g 代的最佳 25% 的方案,如圖中紫色圓點所示;

3. 僅僅使用這些最優解,以及當前代的平均值μ^g(圖中綠色圓點),計算下一代的協方差矩陣 C^(g+1);

4. 使用更新的平均值μ^(g+1) 和協方差矩陣 C^(g+1) 進行新一組的競爭方案抽樣。

讓我們把這些策略再一次在整個搜索過程中可視化,以下是這兩個問題的可視化結果:

因爲 CMA-ES 可以使用最優解的信息對它的平均值和方差同時進行調整,所以它可以在最優解距離很遠時擴大搜索範圍,或在最優解很近的時候縮小搜索範圍。爲了便於理解,我對於這個簡單二維問題的 CMA-ES 算法的解釋進行了高度簡化。如果你想了解更多的細節,建議閱讀 CMA-ES 作者 Nikolaus Hansen 所準備的 CMA-ES 教程(https://arxiv.org/abs/1604.00772)。

CMA-ES 算法,作爲無梯度優化算法中最流行的算法之一,已經成爲許多研究者和實踐者的選擇。它真正唯一的缺點是,當我們需要解決的模型參數太多時,協方差的計算複雜度將變成 O(N^2),儘管現在已經將其近似成爲 O(N)。在參數的數量小於 1000 時,我會選用 CMA-ES。當然,如果足夠耐心,我發現此算法也可以用於上至 10000 個參數的情形。

自然進化策略

假設你建立了一個人造生存模擬器,並抽取一些神經網絡去控制一個蟻羣中每個螞蟻的行爲。如果我們使用簡單進化策略,螞蟻的行爲和特性將會朝着獨自受益的方向發展。因此在每一代中,我們的蟻羣裏將充滿着只管自己死活的「精英」螞蟻。

如果我們不使用上述只考慮自我擬合度的法則,轉而使用擬合度的總和作爲變量,並且在每一代中對於整個蟻羣的整體幸福感做優化,結果會如何呢?好吧,你最終將會創造一個馬克思主義的理想蟻國了。

迄今,上述算法的直觀缺點在於,拋棄了大部分的方案,只保留了部分最佳的方案。其實,那些不好的方案保留了關於「不要做什麼」的關鍵信息,對於更好地計算、評估下一代有重要作用。許多研究強化學習的人會對於這篇 REINFORCE 論文(http://www-anw.cs.umass.edu/~barto/courses/cs687/williams92simple.pdf)比較熟悉。在這篇 1992 年發表的論文當中,關於策略神經網絡的模型參數,作者 Williams 簡單概述了一種評估期望獎勵的方案。同時,在論文的第六部分,文章提議使用強化學習(REINFORCE)作爲進化策略的手段。隨後 Policy Exploring Policy Gradients (PEPG, 2009) 和 Natural Evolution Strategies(NES,2014) 兩篇文章,將本論文中使用強化學習-進化策略(REINFORCE-ES)的特例進行了擴充和發展。

在這種方案當中,我們想使用每一代中每個方案的全部信息,無論是好是壞。這樣,有了這些梯度信號的評估,我們就能將全部方案在下一代中朝着更好的方向發展。既然我們需要評估梯度,我們就可以使用應用於深度學習的標準隨機梯度下降算法(SGD)。當然,我們也可以使用動量隨機梯度下降算法(Momentum SGD),均方根傳播算法(RMSProp),或 Adam 算法進行優化。

我們需要的是對於一個抽樣方案進行期望擬合度評分(fitness score)的優化。如果期望結果足夠好,那麼在抽樣的一代中,表現最佳的方案可能表現更好,所以對期望進行優化是一個明智的方案。將某個抽樣方案的期望擬合度評分最大化,其實幾乎等同於將全體的擬合度評分進行最大化。

假設 z 是概率分佈函數 π(z,θ) 的抽樣方案向量,我們可以將目標函數 F 的期望值定義爲:

其中θ表示概率分佈函數的參數。舉例來說,如果 π 是一個正態分佈,那麼 θ 就是指 μ 和 σ。對於我們的簡單二維問題,每一個 z 的整體都是一個二維向量 (x,y)。

在「自然進化策略」(http://www.jmlr.org/papers/volume15/wierstra14a/wierstra14a.pdf)這篇論文中,說明了關於 θ 的 J(θ) 的梯度的來歷。使用與 REINFORCE 算法中同樣的對數似然法,我們可以計算 J(θ) 的梯度:

在一個大小爲 N 的樣本中,我們有方案 z^1, z^2, ...... z^N,從而可以用求和的方式估計這個梯度:

有了上述的梯度,我們可以使用一個學習率 α(比如 0.01),並且開始我們關於概率分佈函數π的θ參數優化,從而使得我們的抽樣方案在目標函數 F 上獲得更高的擬合度評分。使用 SGD 或 Adam 算法,我們可以將 θ 在下一代進行更新:

在概率分佈函數更新之後,我們可以進行新的競爭方案 z 的抽樣,直到我們得到一個適當的解。

在 REINFORCE 論文的第六部分,Williams 還推導了封閉型的梯度公式 ∇_θlogπ(z^i,θ),這主要是爲了那些向量化多變量正態分佈的 π(z,θ) 所設計的(即,相關參數是零)。在這種特殊情況下,θ是μ和σ向量。因此,解的每一個元素可以從一個單變量的正態分佈 z_j∼N(μ_j,σ_j) 中抽樣而來。

對於每一個方案 i 的θ向量中每一個獨立元素,這個封閉的梯度公式∇_θ logN(z^i,θ) 可以被推導成:

爲了清楚地表示,我使用角標 j 表示參數空間,而上標 i 表示羣體中的每一個樣本,它們不應該被混淆。對於本文的二維問題來說,z_1 = =x, z_2 = y, μ_1=μ_x, μ_2=μ_y, σ_1=σ_x, σ_2=σ_y。

我們可以把這兩個公式放回到兩個近似梯度公式中,對 μ 和 σ 進行清晰的更新。上文提及的論文中有着更加明晰的更新規則,包含了一個基準,並且可以引入例如 PEPG 中的對立抽樣等其他技巧,而這正是我的執行方案的基礎。但是,這個概念基本與其他進化策略算法相同,即,在每一代更新多變量正態分佈的平均值和標準差,並從新的分佈之中進行取樣。下面是使用上述公式的本算法圖解:

我們可以看到,這種算法可以根據需要動態地改變 σ,以繼續探索或者調整解的空間。不像 CMA-ES,我們的實現中並沒有相關結構,所以我們只是沒有得到對角型的橢圓樣本,而是得到了垂直或水平的樣本,儘管理論上來說,如有需要,我們能夠以計算效率爲代價,推導出更新規則,從而納入整個協方差矩陣。

我喜歡這個算法。因爲它正如 CMA-ES 那樣,這裏的標準差可以調整,然後搜索空間可以在過程中增大或者縮小。由於並沒有使用相關參數,這個算法的效率是 O(N),所以在 CMA-ES 的表現不太好時,我會使用 PEPG。我經常在參數超過幾千的時候使用 PEPG。

OpenAI 的進化策略

在 OpenAI 的論文中,他們使用了一種新的遺傳策略,是上面提到的 REINFORCE-ES 算法的特例。特別地,σ 被定爲一個常量,只有 μ 在每一代中被更新。下面就是將 σ 定義爲常量之後這個策略執行的樣子:

在這個簡化之外,該論文同樣提出了更新規則的修正,從而適用於不同工作機器的並行計算。該更新規則使用一個固定值種子預計算一大羣隨機數。這樣的話,每個工作機器可以複製其他機器的參數,並且每個機器只需要與其他機器進行一個數字的簡單通信,這個數字也就是最終的擬合度結果。如果我們想將進化策略擴展到成千上萬個不同的工作機器中去,這就顯得非常重要了。因爲在每一代的更新中,每次都將一整個解向量傳輸上百萬次並不太現實,但是隻傳輸最終的擬合度結果卻也許可行。這篇論文展示,通過利用亞馬遜 EC2 的 1440 個機器,他們可以使用十幾分鐘的時間解決 Mujoco 仿真機器人步行問題。

在理論上,我以爲這個並行更新規則對那些同樣可以調整 σ 的原始算法也有效。但也許在實際上,他們只是想在大型並行計算實驗中,把可變的部分減小到最小值。這篇富有啓發性的論文同樣討論了許多其他將進化策略應用到強化學習方面的實際案例。我非常推薦大家繼續深入學習。

擬合度塑造

上述大部分算法通常會與擬合度塑造(fitness shaping)方法相結合。下面我想說說基於等級的擬合度塑造方法(rank-based fitness shaping method)。擬合度塑造會避免當前樣本中的異常值主導(上文提到的)近似梯度計算:

如果一個特殊的 F(z^m) 比當前樣本中其他 F(z^i) 都大得多,梯度就可能被這個異常值所主導,從而增大了算法陷入局部最優的可能性。爲了減輕這個問題,可以應用擬合度的等級轉化。我們將給結果進行評級,不使用實際的擬合度函數,而是使用一個與解的等級成比例的增強擬合度函數(augmented fitness function)。下面就是原始擬合度和基於等級的擬合度的結果對比:

假設我們有一個大小爲 101 的樣本。我們會根據實際擬合度函數評價每一個樣本,然後根據擬合度挑選解。比如,我們會給最差的方案提供一個增強擬合度函數值,-0.50,然後給第二差的方案標值爲 -0.49,……,給次優方案標值 0.49,給最優方案標值 0.50。這個增強擬合度值的集合將會取代實際的擬合度值,被用於計算下一次梯度更新。從某種程度上,這有點類似於用更直接一點的辦法,即對結果使用批標準化(Batch Normalization)。也有一些擬合度塑造的其他類似方法,不過它們最後都基本會給出一個類似的結論。

我發現擬合度塑造在這種強化學習中非常有用:在策略神經網絡中,並具有非確定性目標函數。此外,它同時作用於這樣的情況——地圖是隨機形成且競爭方案有隨機策略;而這也是強化學習環境常常會出現的情況。對於那些確定性的、表現良好的函數而言,使用擬合度塑造塑形用處不大,而且有時會拖慢找到優化解的時間。

MNIST 數據集

比起基於梯度的算法,進化策略可能是一個發現更多新穎解決方案的算法。然而,進化策略在許多可計算高質量梯度的問題中,比基於梯度的算法仍然要差得多。比如,只有傻子纔會用遺傳算法做圖像分類。但是,有時候這種人真的存在,並且有時候這種探索還是富有成效的呢!

既然所有的機器學習算法都應該在 MNIST 上進行測試,我也嘗試着用這些進化策略算法,使用一個 2 層的用於分類 MNIST 的卷積網絡尋找權重。當然,這只是想看看我們跟隨機梯度下降相比處在什麼位置。因爲這個卷積網絡只有約 1.1 萬個參數,所以我們使用了較慢一點的 CMA-ES 算法。在 https://github.com/hardmaru/pytorch_notebooks/tree/master/mnist_es 中,可以獲得相關代碼和實驗過程。

下面是使用了不同進化策略的結果。我們用大小爲 101 的樣本計算了 300 代。我們持續追蹤了每一代結束時表現最好的模型參數,並且在進行 300 代計算之後在測試集中評估了這個模型。有趣的是,有時候測試集的精確度比那些得分較低的訓練集模型的精確度高。

不過,我們要懷着懷疑的眼光看待這個結果,因爲我們只運行了一次,而不是對 5-10 次實驗取了平均。這個基於一次運行的結果表明,CMA-ES 在 MNIST 訓練集任務當中表現得最好,不過 PEPG 算法也緊隨其後。兩者都達到了近 98% 的準確度,比 SGD 或 Adam 算法的基準線大約低 1%。也許那種動態改變協方差矩陣的能力,以及逐代改變標準差參數的能力,使得它能較好地調節權重,這比簡單的 OpenAI 的 ES 算法要略勝一籌。

自己動手

文章提到的上述算法很有可能有開源執行方案。CMA-ES 的作者,Nikolaus Hansen, 已經在維護一個基於 numpy 的 CMA-ES 方案,這個方案還有許多附加功能。他的這個 python 方案,使我之前接觸了訓練循環的接口。因爲這個接口非常容易使用,我使用這個接口執行了一些其他的算法,比如簡單遺傳算法、PEPG 算法,還有 OpenAI 的 ES 算法等等。我把它們放在了一個簡單的 python 文件中,名爲 es.py,並且把原始的 CMA-ES 也放了進去。這樣的話,我就可以只通過改變代碼中的一兩行,快速比較不同的 ES 算法:

  1. importes

  2. #solver = es.SimpleGA(...)

  3. #solver = es.PEPG(...)

  4. #solver = es.OpenES(...)

  5. solver = es.CMAES(...)

  6. whileTrue:

  7. solutions = solver.ask()

  8. fitness_list = np.zeros(solver.popsize)

  9. fori inrange(solver.popsize):

  10. fitness_list[i] = evaluate(solutions[i])

  11. solver.tell(fitness_list)

  12. result = solver.result()

  13. ifresult[1] > MY_REQIRED_FITNESS:

  14. break

你可以在 Github 和 Ipython notebook 上看到使用不同進化策略的實例:https://github.com/hardmaru/estool/blob/master/simple_es_example.ipynb

在這個攜帶有 es.python 的 Ipython notebook ( https://github.com/hardmaru/estool/blob/master/simple_es_example.ipynb) 上,我向你展示了使用 es.py 中的進化策略,解決具有更多局部最優的十維 Ras 函數優化問題的辦法。這個十維版本的問題比上述用於可視化的二維版本的問題更難。以下是上述討論過的算法的性能比較:

在這個十維 Ras 問題中,沒有一個優化方案達到了全局最優解。不過 CMA-ES 比較接近,遠遠超過了其他任何算法。PEPG 和 NES 在第二位,OpenAI-ES 以及遺傳算法落在後面。我不得不使用退火辦法減小 OpenAI-ES 的 σ 值,讓它在這個任務中表現得好一些。

原文鏈接:http://blog.otoro.net/2017/10/29/visual-evolution-strategies/

點擊【閱讀原文】報名參賽,美國賽區報名請點擊大賽首頁 US 進入美國賽區報名通道

責任編輯:

文章來源:機器之心