1 進化算法

在學習最優模型參數的時候，梯度下降并不是唯一的選擇。在我們不知道目標函數的精確解析或者不能直接計算梯度的情況下，進化算法是有效的。

進化算法的靈感來源于自然選擇，具有有利于生存的特征的個體可以世代生存，并將好的特性傳給下一代；具有不利于生存的特正的個體則會被不斷淘汰，最后減少甚至消失。進化是在選擇過程中逐漸發生的，進化使得種群可以更好地適應環境。

下面這張圖可以很好地解釋進化算法的想法，一開始島上有數量相等的白老鼠和黑老鼠，但是因為黑老鼠和土地的顏色相近，所以老鼠的天敵不易于發現這一種類的老鼠。而白老鼠由于過于顯眼，在不斷地被吃掉的過程中，慢慢地被淘汰了。久而久之，最后剩的多的就是黑老鼠。

進化算法旨在優化無法直接建模的函數，核心是采樣和更新。它在在每一代估計基因型的實值，然后保留最佳的基因型，其他的基因型被丟棄，精英基因被保留并產生。

如下圖所示，虛線圓是初始的正態分布，星星表示采樣生成的后代，藍色的星星表示排序后被選中的后代，紅色表示沒有選中的。那么虛線橢圓就是新一代的概率采樣分布。

進化算法作為一種通用的優化方式，可以歸納為：

1，假設我們想優化一個函數f(x)，但f(x)的梯度難以求解。只能得到在特定x下f(x)的確定值。

2，我們認為隨機變量x的概率分布p(θ,x)是函數f(x)優化問題的一個較優的解,θ是分布p(θ,x)的參數。我們最終的目標是找到θ的最優配置。

3，在給定分布形式（例如，高斯分布）的情況下，參數 θ 包含了最優解的知識，在一代與一代間進行迭代更新。

4，

2?簡單高斯進化策略

即 在分布中隨機采樣

4，

5，重復（2）-（4）步直到結果足夠好

3?協方差自適應進化策略CMA-ES

3.1 基本原理

協方差矩陣自適應演化策略（CMA-ES）通過使用協方差矩陣 C 跟蹤分布上得到的樣本兩兩之間的依賴關系，解決了上述這一問題。新的分布參數變為了：

3.1.1 協方差矩陣性質

1，始終都是對角陣

2，始終都是半正定矩陣

3，所有的特征值為非負實數

4，所有的特征向量都是正交的

5，特征向量可以組成一個Rn的標準正交基

3.1.2 本節涉及符號及其意義

是在分布上隨機采樣；是在分布上隨機采樣。

是第t代的平均值；是第t代采樣時候的步長;?是第t代的協方差矩陣。

和是?進行特征值分解的結果（見3.1.1）。

?是第t代步長σ和協方差矩陣C的進化路徑

?分別是μ,σ,pc,C的兩種路徑（后文會涉及）的學習率

是步長σ更新時候的阻尼系數

3.1.3 更新均值

μ的學習率為1的時候，就是

3.1.4 控制步長

即?~N(0,I) （第二行式子是因為每一個yi都是N(0,C)中采樣的）

有了演化路徑之后，我們就可以根據演化路徑來更新我們的σ進化路徑了

注：這里公式有一處筆誤，第二行根號里面第一項為

注：這里調整步長的思想來源于CSA-ES（累積步長調整策略），這種思路使用多代來記錄同一條路徑，即進化路徑。演化路徑是連續幾代路徑的總和，在每次迭代中對多個精英子代的搜索方向做加權平均，相反分量相互抵消，相同分量進行疊加。如果成功的步驟都朝著相同的方向發展累加起來，那么該方向的發展路徑就會相對較長，我們可以用一個較大的步長來代替該方向的總進化距離；反之，則需要簡短步長，即：

3.1.4.1 Polyak算法回憶

3.1.5 調整協方差矩陣

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

注：n是每個樣本的維度，λ是每一代取的精英樣本數

3.2 總體CMA-ES

這是一篇論文里面的CMA-ES的總體方案；第一步取值；第二步挑精英值；第三步，更新均值μ；第四步更新 步長σ需要的演化路徑；第五步更新步長；第六步更新path2 需要的C的演化路徑；第七步我個人覺得不需要？（同時在另一篇論文“基于改進的CMA_ES的仿真足球機器人的行走優化”里面，也是直接第八步的，這個歡迎討論哈！）；第八步更新協方差矩陣

總結

以上是生活随笔為你收集整理的CMA-ES 算法初探的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。