ML領域的生物進化論，進化策略圖文詳解

編者按：進化策略是德國的I. Rechenberg和HP. Schwefel於1963年提出的參數優化方法，它模仿生物進化原理，不論參數發生何種變化，它的特徵總遵循零均值、某一方差的高斯分布。日前，機器學習開發者大トロ（谷歌大腦）在博客中圖文並茂地對進化策略進行了詳解，並授權論智把成果分享給中國讀者。

註：本文為作者授權論智（公眾號：jqr_ai）編譯，轉載請聯繫公眾號。

介紹

神經網路模型具有高度的表達性和靈活性，如果我們能找到一組合適的模型參數，它能幫助我們解決許多具有挑戰性的的問題。近年來，深度學習的成功主要來源於它能利用反向傳播演算法高效計算每個模型參數上目標函數的梯度。通過這些梯度，我們能更高效地搜索參數空間，從中找出最合適的解。

然而，反向傳播演算法也有諸多局限，如在強化學習（RL）問題中，我們可以訓練一個神經網路來對下一步動作執行做出決策，以實現最終目標。但我們無法判斷沿著當前agent梯度發展，模型在下一階段是否能獲得獎勵信號，尤其是在時間步長較長的情況下。換個角度說，即使最後算出了精確的梯度，那也可能只是局部最優值或局部極小值。

信用分配問題（ credit assignment problem），即在建立模型前，你需要知道哪些動作會觸發獎勵信號及它們的獎勵貢獻大小。它至今仍是RL一大關鍵挑戰，雖然近年來取得了巨大進展，但在獎勵信號稀疏時，信用分配依然十分棘手。現實世界中的獎勵可能是稀疏的、嘈雜的，有時甚至只有一次獎勵，如年底公司發的年終獎，你可能永遠沒法知道它為什麼那麼低，因為那是由你的老闆決定的。對於這類問題，我們不能把結果依賴於在嘈雜數據中進行無意義的梯度計算，一種更合適的解決方法是使用黑盒優化技術，如遺傳演算法（GA）和進化策略（ES）。

今年3月，OpenAI曾發表了一篇名為Evolution Strategies as a Scalable Alternative to Reinforcement Learning（進化策略：可代替強化學習）的文章，指出進化策略只需少量計算就能在效率上比肩標準的強化學習，同時還能克服後者的諸多不便。放棄梯度計算意味著進化策略能進行更有效的評估，可以把任務分配給上千台計算機並行計算。根據實驗，他們得出的一大推論是：和強化學習相比，進化策略產生的結果往往更加多樣化。

什麼是進化策略

下面兩幅圖代表用於測試黑盒優化技術的兩個玩具問題 ，前者是Schaffer函數圖，後者是Rastrigin函數圖，圖中的淺色區域代表空間高值F(x,y)。正如你所看到的，圖中有許多局部最優值，因此我們的任務是找到一組模型參數(x, y)，使得F(x,y)無限接近空間極大值。

儘管進化策略已經有很多官方定義，但在本文中，我們暫且把它簡單解釋為一種為用戶提供一組候選解來評估問題的方法。演算法評估基於一個目標函數，它採用給定的候選解，並返回一個單一的適應值。基於當前解的適應值，演算法會產生下一代候選解，而下一代的適應值結果比上代更佳。如此循環往複，直到用戶得到了滿意的解，整個迭代過程才會終止。

如果想創建一個名為EvolutionStrategy的進化策略演算法，你可以這麼寫：

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

雖然每一代種群規模是不變的，但其實它也沒必要變化，因為進化策略可以根據需要生成儘可能多的候選解，並從每一代更新參數的分布中採樣。以下是一個簡單的例子。

進化策略簡單示例

進化策略最簡單的應用之一就是從一組服從高斯分布的隨機數中抽取一組解，我們用μ來表示均值，用σ來表示固定標準差。以之前提到的玩具問題為例，在那兩個問題中，μ=(μx ,μy )，σ=(σx ,σy)。剛開始的時候，我們把μ設置在圖像原點，隨著進化迭代，它不斷找到最佳解決解並圍繞這個新的均值進行抽樣。

以上動圖是函數經過20次迭代的變化情況，其中綠點表示每一代的新均值，藍色圖塊是候選解，紅點則是演算法得到的最優值。

這個示例的簡單演算法通常只適用於簡單問題，鑒於其貪婪的本質，它會拋棄除了最優解外的其他所有解，並且可能在面對複雜問題時生成局部最優值。因此，比起在具體某一代中尋找最優值，從多樣性更豐富的上一代中根據概率分布採樣進化出下一代會是一個更理想的方法。

遺傳演算法簡介

談到黑盒優化技技術，遺傳演算法是其中歷史比較悠久的演算法之一。隨著研究的不斷突破，如今遺傳演算法已經衍生出了許多複雜的版本，但在這裡我們只討論其中最簡單的一種。

遺傳演算法的思路很簡單，就是只保留當前這一代中一定比例，如前10%的最優解，然後捨去剩下的90%。在下一代，演算法從上一代遺留下來的解中隨機選擇一對父本，並重組它們的參數形成一個新個體。這個從父本抽調參數的交叉重組過程類似拋硬幣，是完全隨機的（其實需要考慮近親繁殖因素，但本文不涉及）。在我們的玩具問題中，這個新解繼承父本x、y參數的概率各佔50%，因此帶有固定標準差σ的高斯雜訊也會隨著重組過程進入每個新的解。

上圖簡單演示了遺傳演算法的工作情況，其中綠點表示上一代遺留下來的父本，藍點是父本集的後代，而紅點則是演算法的到的最優值。

遺傳演算法通過跟蹤不同解的參數來重建下一代，雖然一定程度上有利於解的多樣性但在具體實踐中，這種篩選最優解的做法也會面臨最後結果收束到局部最優值的問題。因此，許多專家學者曾對它做過不少優化補充，如CoSyNe，ESP和NEAT，這些版本的想法是把種群中類似解的參數聚合到其他解中，以保持更優質的多樣性。

協方差矩陣自適應演化策略（CMA-ES）

由以上實踐可知，在我們的簡單問題中，進化策略是遺傳演算法的缺點在於設定的標準差是固定的。有時候，我們想要探索更多空間，並上調標準差；有時候，我們認為演算法已經接近了最佳值，希望能微調一下解。簡單來說，我們心目中的演算法搜索過程應該是這樣的：

這樣的效果令人驚嘆！要想自己動手實現這一幕，你需要學習協方差矩陣自適應演化策略。協方差矩陣自適應演化策略是一種能夠把握每一代結果，並自適應增加或減少下一代搜索空間的演算法，它不僅能適應均值μ和標準差σ，還能計算整個參數空間的協方差矩陣。在每一代，CMA-ES提供了一個多變數正態分布參數的解的樣本。那它是怎麼做的呢？

在開始討論它的方法前，一些簡單的數學計算不可或缺。首先，我們要計算xi和yi：

其次，計算2x2協方差矩陣C：

當然以上得出的解只是個估計值，只能作為參考。為了簡化計算，我們暫時把Nbest定為25%，即取前25%來更新參數，由g代進化出的下一代（g+1）的均值μg+1為：

最後，我們用25%來估計協方差矩陣Cg+1，需要注意的是，這裡我們用的均值是μg，而不是μg+1：

有了μx、μy、σx、σy、σxy，我們就可以從（g+1）的參數中採樣下一代解了。

1. 計算出每一代（g）每個候選值的適應值；
2. 從當前代（g）中分離出25%的最優值，在圖中用紫色點表示；
3. 選取經分離後的最優值，結合當前代的均值μg，計算下一代矩陣Cg+1；
4. 用Cg+1和μg+1對新一代候選解抽樣。

讓我們再看一遍玩具問題中的整個搜索過程：

因為CMA-ES可以使用最佳值的信息自適應調整均值和協方差矩陣，所以當演算法距離最佳值過遠/過近時，它可以擴大/縮小搜索範圍。我在上文中介紹了似然估計的計算方法，但考慮到入門新手還會有一些問題，在此我推薦CMA-ES發明人Nikolaus Hansen撰寫的教程：arxiv.org/abs/1604.00772。

這個演算法是現在最流行的無梯度優化演算法之一，而且廣受研究人員和數據科學從業者歡迎。如果要說缺點，那它唯一一點會被詬病的是性能。CMA-ES適合用於1000個參數以下的搜索空間，當然你如果願意等，根據我的測試，10000個也是可以用的~

自然進化策略

試想一下，如果你已經建立了一個人工生命模擬器，並且選取了一系列不同的神經網路控制蟻群內每隻螞蟻的行為。通過簡單的進化策略演算法，你篩選出最有利於螞蟻的特徵和行為，並利用一代代演化過程鞏固、優化這些特徵。最後，你得到的只會是一群只想著自己如何更優秀的螞蟻。

反之，如果把蟻群看做一個整體，計算整體的適應值來進行優化，那會產生更好的結果嗎？答案顯而易見，由於這些螞蟻都沒有經歷「物競天擇，適者生存」，它們最後接受的只會是一個及時止損的「烏托邦」式結局，並不會嚮往比上一代更進一步。

結合上述所提及的演算法，可以發現它們都有一個弱點，即放棄了大多數解，只保留最優值。其實那些不那麼「優秀」的解中也包含了一些否定信息，它能提示not to do，這對於下一代得出一個更具價值的值是有意義的。

研究強化學習的人應該會對1992年的那篇經典論文Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning印象深刻，在文中，Williams推薦了一種通過預估神經網路梯度推測獎勵的方法，在文章第六節，他還提出將強化用於進化策略。從那以後，相關研究持續推進，而Parameter-exploring Policy Gradients和Natural Evolution Strategies這兩篇論文都是對REINFORCE-ES的經典擴展。

這種方法旨在使用來自每個成員的所有信息，無論好壞，它們都可以被用來估計一個梯度信號，並使整個種群在進化到下一代時能朝著更好的方向前進。由於需要預估梯度，我們可以靈活借用深度學習中隨機梯度下降演算法（SGD）的參數更新規則，讓它服務於更精確的梯度計算。如果願意，我們甚至可以用Momentum SGD、RMSProp或Adam。

它的思路是使候選解適應值的期望最大化，如果期望足夠好，那麼種群樣本中最優值的期望應該更好，因此對期望進行優化可能是一個明智的做法。而實踐也證明，最大化的樣本期望和整個種群的總體適應值幾乎相同。

如果樣本z的概率密度函數為π(z,θ)，則可定義目標函數期望F為：

θ是函數的參數。當π為高斯分布時，θ即μ和σ。在我們的二維玩具問題中，每個z都是向量(x,y)。論文Natural Evolution Strategies對θ和J(θ)的梯度推導做了具體解釋，借用REINFORCE的對數似然法，可計算J(θ)：

在一個大小為N的種群中，已知z1，z2，...zN，可用求和估計梯度：

有了?θJ(θ)，則可用學習率（如0.01）開始優化參數。利用SGD（或Adam），我們可以計算θ的迭代：

這樣即完成了一輪函數更新，在此基礎上進行抽樣迭代，最終我們會獲得最優值。

在Williams論文的第六節，他還對梯度公式?θ logπ(zi ,θ)進行推導，這主要是針對π(z,θ)是多變數高斯分布函數的情況（即參數為0）。在這種情況下，θ是μ和σ的向量，所有解都可從zj～N(μj ,σj)中抽樣得到。

對?θ logπ(zi ,θ)求導：

其中j為參數空間，i為單個樣本。在玩具問題中，z1 =x， z2 = y，μ1 =μx，μ2 =μy，σ1 =σx，σ2 =σy。利用上述公式，整個演算法的運行狀態如下圖所示：

可以發現，這個演算法能自適應調整搜索空間和對解進行微調，和CMA-ES不同，這個實現沒有相關結構，因此我們無法得到對角橢圓樣本，只有垂直或水平的樣本。如果願意降低計算效率，原則上我們可以導出更新規則來包含整個協方差矩陣。

OpenAI的進化策略

在OpenAI的論文中，他們實現了一個進化策略，這是之前提到的REINFORCE-ES演算法中的一個特例，尤其是它的σ是個固定的常數，只有μ參數隨著迭代更新。下圖是OpenAI進化策略的大致情況：

除了簡化外，該文還提出對參數更新規則進行了修改，以適應不同機器並行計算。在這個新規則中，OpenAI用一個固定seed生成了一大堆隨機數，這之後，機器間可以互相複製參數，它們只需進行簡單的數字交流，即交換單個解的最終適應值。要知道，這對於用進化策略處理涉及上百甚至上千台機器並行計算的任務至關重要，因為如果要計算當前一代中的最佳函數向量，你可能需要進行上百萬次數據傳輸，這在實際操作中並不可行。在論文中，OpenAI租用Amazon EC2雲伺服器上的1440個CPU在短短十分鐘內就完成了MuJoCo訓練。

我認為從原則上說，這個並行更新規則可以適應那個可以對σ做自適應調整的演算法，也許OpenAI的考慮是在計算中儘可能讓搜索更集中。無論如何，這篇文章值得一讀。

Fitness Shaping

上述演算法都結合了一種適應值調整、塑造的方法，即fitness shaping，它能幫我們規避種群中的異常值，避免得出過於相近的梯度，如之前的計算：

如果F(zi)中有一個過大的異常值 F(zm )，它可能會對樣本梯度產生過大影響，使演算法得出局部最優值。為了避免這一點，一種方法是對適應值進行等級變換，也就是說，演算法不包含一個具體的適應值函數，它只對結果做評級，並引入一個和等級成正比的增強適應值函數。下圖展示了兩種操作帶來的不同影響：

假如我們有一個規模為101的種群，我們需要計算其中每一個個體的實際適應值，然後根據適應值挑選解。例如，如果最低適應值的個體的評分是-0.50，倒數第二個體的評分是-0.49……那麼排名第二的個體評分應該是0.49，而最佳的則為0.50。根據這個排名得出的增強適應值會在梯度計算中參與實際計算。

fitness shaping對強化學習問題有時也有奇效。如當給定神經網路中充滿不確定因素，涉及一大堆隨機maps和opponents時，它能顯著提高整體效率。但如果那是一個確定的、行為良好的神經網路，那fitness shaping會拉低計算速率。

MNIST數據集

儘管進化策略能比基於梯度的演算法得出更多樣化的解，但在一些可以計算出高質量梯度的問題上，它還是明顯落了下風。你會進化策略做圖像分類嗎？顯然大多數回答是不會。但這個世界上也確實有一些「獃子」願意吃力不討好，更有甚者，他們還得出了豐碩的成果。

MNIST是機器學習演算法適用的一個經典數據集，我曾利用進化策略在上面試著用一個小型的、只有2層的神經網路訓練一個分類器，事實上這個做法的初衷在於觀察隨機梯度下降程度。由於包含的參數只有11000個，所以我用了效率比較低的CMA-ES演算法。

以下是我得出的結果：種群規模101，迭代300次。我跟蹤了每一代結束時整個訓練集上表現最佳的模型參數，並在完成300次迭代後又對模型進行了評估，在這之中我發現了一件有趣的事，有時測試集的準確率高於評分較低的訓練集模型。

當然這個結果的可信度有待商榷，因為我只跑了一次，不是跑了五六次的平均值。但就這一次的表現來看，CMA-ES在MNIST上的表現很好，它和PEPG不相上下，準確率高達98%。也許正是因為它能對協方差矩陣做自適應調整，所以在權重計算上更精確。而OpenAI的簡化版進化策略則表現一般。

動手試一試

本文提到的CMA-ES演算法已有一些開源工具。據我所知，演算法作者Nikolaus Hansen就有一個基於Numpy的CMA-ES開源工具，而且已經維護了一段時間，Python的他也有。如果你也想對比這幾種演算法的準確率，你可以使用我寫的代碼，並在這一行位置自定義修改：

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

完整代碼地址（es.py）：https://github.com/hardmaru/estool/blob/master/es.py

一些實例：https://github.com/hardmaru/estool/blob/master/simpleesexample.ipynb

Rastrigin函數，是英雄就上100-D：https://github.com/hardmaru/estool/blob/master/simpleesexample.ipynb

註：為避免偷換概念，論智君將原文population一詞譯為「種群」，具體可結合情景理解；計算方法處涉及大量概率論知識，也已做簡化處理。如發現錯誤，歡迎留言指明，謝謝~

最後，再次感謝作者的熱心分享~

原文地址：blog.otoro.net/2017/10/29/visual-evolution-strategies/

正確顯示角標地址：ML領域的生物進化論，進化策略圖文詳解

博主大トロ的其他文章：

零門檻教學：基於循環神經網路的建模思路

如果引進漢字的是循環神經網路，日本文字會是什麼樣