遺傳演算法寫的這麼厲害。。為什麼在最優化理論裡面罕見有應用，還是以梯度下降為主呢？

03-01

所謂遺傳演算法適合搜索空間大的問題是誤導性的，有必要做澄清。

遺傳演算法，或者更廣泛的說，隨機搜索演算法最主要的問題就是收斂性差，收斂速度慢。做進化計算常常聲稱的優勢就是馬爾可夫鏈證明的全局收斂性，當演算法運行時間趨於無窮的時候，以概率一趨於全局最優。即使是完全隨機搜索，比如從標準正態分布產生一個點，好的話就作為均值，不做任何步長之類的參數調整，一樣滿足這一條件。這種理論保障這在實際中是完全沒有意義的，有誰跑程序的時候把運行時間設置成無窮？

對於神經網路的訓練一類的問題來說，真正重要的是收斂速率。上面那種隨機演算法收斂速率是subLinear的，在普通單峰函數（如球函數）上搜索到 $epsilon$ 精度所需的迭代次數是 $O(({1}/{epsilon})^n)$ ，n是變數個數。這樣即使是非常低的維度比如n=10，所需的時間也是不可接受的。

如果從收斂速率方面考慮，隨機搜索、進化計算、或者無梯度優化的收斂速率不可能超過 $Oleft({1}/{n} ight)$ ，搜索到 $epsilon$ 精度所需的迭代次數（目標函數評估次數）不可能少於 $O({1}/{epsilon})$ ，即收斂速率隨著變數個數增加而下降。這對於神經網路一類的優化問題是不可接受的，因為那裡的變數個數動輒都達到 $10^6$ ，這樣的收斂速度實在是太慢了。這才是這一大類演算法沒有被廣泛應用的原因。

與此相對應的，梯度下降法的收斂速率是和維度（變數個數）無關的， dimension-free。這其實很好理解，從有限差分的角度來說，計算一次梯度需要n次有限差分進行估計，這樣就退回到了無梯度的情形，收斂速率與維度成反比。這樣dimension-free的演算法才能用到變數個數非常多的，空間維度很高的優化問題。

Random Gradient-Free Minimization of Convex Functions

Our experiments confirm the following conclusion. If the computation of the gradient is feasible, then the cost of the iteration of random methods, and the cost of iteration of the gradients methods are the same. In this situation, the total time spent by the random methods is typically in O(n) times bigger than the time of the gradient schemes. Hence, the random gradient-free methods should be used only if creation of the code for computing the gradient is too costly or just impossible.

Linear Convergence of Comparison-based Step-size Adaptive Randomized Search via Stability of Markov Chains

Comparison based adaptive evolution strategies converge linearly. The convergence rate is inverse proportional to the dimension of search space $lim_{t ightarrow infty} frac{|x_{t + 1}-x^* |}{|x_t -x^*|} = expleft(- frac{c}{n} ight)$ .

從這個角度來說，進化計算適合的實際上是搜索空間不那麼大的問題。尤其是所謂的複雜優化問題，這種時候（變數個數不多）進化計算的優勢在相當大程度上來自於搜索的隨機性，相對於梯度每次迭代只搜索一個點來說，EAs每次迭代都會評估一整個種群的解。而這是通過犧牲搜索的效率得到的（從初始化到找到一個局部極值所需的評估/迭代的步數更多了），只是變數個數不多的時候影響不大。

另外，進化計算所指的優化的難點通常就是指多峰問題，有很多局部極值。神經網路領域在很大程度上早已拋棄了這種看法，神經網路並沒有那麼多局部極值。

幾個相關問題

關於無梯度優化收斂性方面的一些資料：Some Comments on Gradient-Free Optimization

在這個回答裡面涉及部分關於進化計算和梯度法的對比：有哪些學術界都搞錯了，忽然間有人發現問題所在的事情？

啟發式優化演算法中，如何使之避免陷入局部最優解？

聽一個面試官講的，二者適用的情況往往解空間的大小是不同的。遺傳演算法和梯度下降這類最優化方法都可以用來求最優解，也都有收斂到局部最優的現象。但是梯度的方法更適用於解空間較小的情況，這樣使用梯度下降能夠更快速準確的收斂到最優解，而遺傳演算法更適用於解空間很大的情況，這種情況下，根據特定概率來獲得更優的結果，保留適應度高的子集，不斷迭代，往往比梯度的方法能夠更快速的得到滿足我們指定條件的結果。也就是說在解空間相對較小的情況下，適合用梯度來找到最優結果，而在解空間很大的情況下，並且對於結果的精度要求沒有那麼苛刻，只需找到滿足條件的解即可時，遺傳演算法能夠更快速的得到我們想要的結果。

拉馬克進化論和達爾文進化論的區別，注意看下迭代次數

佛系玩法和常規玩法

佛系玩法讓人覺得很厲害，明明看著很扯卻常常能完美通關.然而佛系玩法隨機性太大而且一般人去玩要花很長很長的時間才能偶然通關，對於一般人遊戲體驗太差

因此大家通常選擇常規玩法，循規蹈矩也能通關

誰說的，gradient free optimization一直被寄予厚望。

SGD更適合干這個。