現有演算法優化

① 常用優化器演算法歸納介紹

優化器是神經網路訓練過程中，進行梯度下降以尋找最優解的優化方法。不同方法通過不同方式（如附加動量項，學習率自適應變化等）側重於解決不同的問題，但最終大都是為了加快訓練速度。

這里就介紹幾種常見的優化器，包括其原理、數學公式、核心思想及其性能；

核心思想： 即針對每次輸入的訓練數據，計算輸出預測與真值的Loss的梯度；

從表達式來看，網路中參數的更新，是不斷向著最小化Loss函數的方向移動的：

優點:
簡單易懂，即對於相應的最優解（這里認為是Loss的最小函數），每次變數更新都是沿著局部梯度下降最快的方向，從而最小化損失函數。

缺點:

不同於標准梯度下降法（Gradient Descent）一次計算所有數據樣本的Loss並計算相應的梯度，批量梯度下降法（BGD, Batch Gradient Descent）每次只取一個小批次的數據及其真實標簽進行訓練，稱這個批次為mini-batch；

優點：

缺點：
隨機梯度下降法的 batch size 選擇不當可能導致模型難以收斂；由於這種方法是在一次更新中，就對整個數據集計算梯度，所以計算起來非常慢，遇到很大量的數據集也會非常棘手，而且不能投入新數據實時更新模型。

我們會事先定義一個迭代次數 epoch，首先計算梯度向量 params_grad，然後沿著梯度的方向更新參數 params，learning rate 決定了我們每一步邁多大。

Batch gradient descent 對於凸函數可以收斂到全局極小值，對於非凸函數可以收斂到局部極小值。

和 BGD 的一次用所有數據計算梯度相比，SGD 每次更新時對每個樣本進行梯度更新，對於很大的數據集來說，可能會有相似的樣本，這樣 BGD 在計算梯度時會出現冗餘，而 SGD 一次只進行一次更新，就沒有冗餘，而且比較快，並且可以新增樣本。

即訓練時，每次只從一批訓練樣本中隨機選取一個樣本進行梯度下降；對隨機梯度下降來說，只需要一次關注一個訓練樣本，一點點把參數朝著全局最小值的方向進行修改了。

整體數據集是個循環，其中對每個樣本進行一次參數更新

缺點：

梯度下降速度比較慢，而且每次梯度更新時往往只專注與局部最優點，而不會恰好指向全局最優點；

單樣本梯度更新時會引入許多雜訊（跟訓練目標無關的特徵也會被歸為該樣本分類的特徵）；

SGD 因為更新比較頻繁，會造成 cost function 有嚴重的震盪。

BGD 可以收斂到局部極小值，當然 SGD 的震盪可能會跳到更好的局部極小值處。

當我們稍微減小 learning rate，SGD 和 BGD 的收斂性是一樣的。

優點：

當處理大量數據時，比如SSD或者faster-rcnn等目標檢測模型，每個樣本都有大量候選框參與訓練，這時使用隨機梯度下降法能夠加快梯度的計算。

隨機梯度下降是通過每個樣本來迭代更新一次，如果樣本量很大的情況，那麼可能只用其中部分的樣本，就已經將 迭代到最優解了，對比上面的批量梯度下降，迭代一次需要用到十幾萬訓練樣本，一次迭代不可能最優，如果迭代10次的話就需要遍歷訓練樣本10次。缺點是SGD的噪音較BGD要多，使得SGD並不是每次迭代都向著整體最優化方向。所以雖然訓練速度快，但是准確度下降，並不是全局最優。雖然包含一定的隨機性，但是從期望上來看，它是等於正確的導數的。

梯度更新規則：

MBGD 每一次利用一小批樣本，即 n 個樣本進行計算，這樣它可以降低參數更新時的方差，收斂更穩定，另一方面可以充分地利用深度學習庫中高度優化的矩陣操作來進行更有效的梯度計算。

和 SGD 的區別是每一次循環不是作用於每個樣本，而是具有 n 個樣本的批次。

超參數設定值: n 一般取值在 50～256

缺點：（兩大缺點）

鞍點就是：一個光滑函數的鞍點鄰域的曲線，曲面，或超曲面，都位於這點的切線的不同邊。例如這個二維圖形，像個馬鞍：在x-軸方嚮往上曲，在y-軸方嚮往下曲，鞍點就是（0，0）。

為了應對上面的兩點挑戰就有了下面這些演算法

核心思想：

不使用動量優化時，每次訓練的梯度下降方向，都是按照當前批次訓練數據計算的，可能並不能代表整個數據集，並且會有許多雜訊，下降曲線波動較大：

添加動量項之後，能夠有效減小波動，從而加快訓練速度：

當我們將一個小球從山上滾下來時，沒有阻力的話，它的動量會越來越大，但是如果遇到了阻力，速度就會變小。
加入的這一項，可以使得梯度方向不變的維度上速度變快，梯度方向有所改變的維度上的更新速度變慢，這樣就可以加快收斂並減小震盪。

優點：

通過動量更新，參數向量會在有持續梯度的方向上增加速度；
使梯度下降時的折返情況減輕，從而加快訓練速度；

缺點：

如果數據集分類復雜，會導致 和 時刻梯度 向量方向相差較大；在進行向量求和時，得到的 會非常小，反而使訓練速度大大下降甚至模型難以收斂。

這種情況相當於小球從山上滾下來時是在盲目地沿著坡滾，如果它能具備一些先知，例如快要上坡時，就知道需要減速了的話，適應性會更好。

目前為止，我們可以做到，在更新梯度時順應 loss function 的梯度來調整速度，並且對 SGD 進行加速。

核心思想：

自適應學習率優化演算法針對於機器學習模型的學習率，採用不同的策略來調整訓練過程中的學習率，從而大大提高訓練速度。

這個演算法就可以對低頻的參數做較大的更新，對高頻的做較小的更新，也因此，對於稀疏的數據它的表現很好，很好地提高了 SGD 的魯棒性，例如識別 Youtube 視頻裡面的貓，訓練 GloVe word embeddings，因為它們都是需要在低頻的特徵上有更大的更新。

Adagrad 的優點是減少了學習率的手動調節

式中， 表示第 個分類， 表示第 迭代同時也表示分類 累計出現的次數。 表示初始的學習率取值（一般為0.01）

AdaGrad的核心思想： 縮放每個參數反比於其所有梯度歷史平均值總和的平方根。具有代價函數最大梯度的參數相應地有較大的學習率，而具有小梯度的參數又較小的學習率。

缺點：

它的缺點是分母會不斷積累，這樣學習率就會收縮並最終會變得非常小。

這個演算法是對 Adagrad 的改進，

和 Adagrad 相比，就是分母的 換成了過去的梯度平方的衰減平均值，指數衰減平均值

這個分母相當於梯度的均方根 root mean squared (RMS)，在數據統計分析中，將所有值平方求和，求其均值，再開平方，就得到均方根值 ，所以可以用 RMS 簡寫：

其中 的計算公式如下， 時刻的依賴於前一時刻的平均和當前的梯度：

梯度更新規則:

此外，還將學習率 換成了 RMS[Δθ]，這樣的話，我們甚至都不需要提前設定學習率了：

超參數設定值: 一般設定為 0.9

RMSprop 是 Geoff Hinton 提出的一種自適應學習率方法。

RMSprop 和 Adadelta 都是為了解決 Adagrad 學習率急劇下降問題的，

梯度更新規則:

RMSprop 與 Adadelta 的第一種形式相同：（使用的是指數加權平均，旨在消除梯度下降中的擺動，與Momentum的效果一樣，某一維度的導數比較大，則指數加權平均就大，某一維度的導數比較小，則其指數加權平均就小，這樣就保證了各維度導數都在一個量級，進而減少了擺動。允許使用一個更大的學習率η）

超參數設定值:

Hinton 建議設定 為 0.9, 學習率 為 0.001。

這個演算法是另一種計算每個參數的自適應學習率的方法。相當於 RMSprop + Momentum

除了像 Adadelta 和 RMSprop 一樣存儲了過去梯度的平方 vt 的指數衰減平均值 ，也像 momentum 一樣保持了過去梯度 mt 的指數衰減平均值：

如果 和 被初始化為 0 向量，那它們就會向 0 偏置，所以做了偏差校正，通過計算偏差校正後的 和 來抵消這些偏差：

梯度更新規則:

超參數設定值:
建議

示例一

示例二

示例三

上面情況都可以看出，Adagrad, Adadelta, RMSprop 幾乎很快就找到了正確的方向並前進，收斂速度也相當快，而其它方法要麼很慢，要麼走了很多彎路才找到。

由圖可知自適應學習率方法即 Adagrad, Adadelta, RMSprop, Adam 在這種情景下會更合適而且收斂性更好。

如果數據是稀疏的，就用自適用方法，即 Adagrad, Adadelta, RMSprop, Adam。

RMSprop, Adadelta, Adam 在很多情況下的效果是相似的。

Adam 就是在 RMSprop 的基礎上加了 bias-correction 和 momentum，

隨著梯度變的稀疏，Adam 比 RMSprop 效果會好。

整體來講，Adam 是最好的選擇。

很多論文里都會用 SGD，沒有 momentum 等。SGD 雖然能達到極小值，但是比其它演算法用的時間長，而且可能會被困在鞍點。

如果需要更快的收斂，或者是訓練更深更復雜的神經網路，需要用一種自適應的演算法。

各種優化器Optimizer原理：從SGD到AdamOptimizer

深度學習——優化器演算法Optimizer詳解（BGD、SGD、MBGD、Momentum、NAG、Adagrad、Adadelta、RMSprop、Adam）

② 現在哪些智能優化演算法比較新

智能優化演算法是一種啟發式優化演算法，包括遺傳演算法、蟻群演算法、禁忌搜索演算法、模擬退火演算法、粒子群演算法等。·智能優化演算法一般是針對具體問題設計相關的演算法，理論要求弱，技術性強。一般，我們會把智能演算法與最優化演算法進行比較，
最新的智能優化演算法有哪些呢，論文想研究些新演算法，但是不知道哪些演算法...
答：蟻群其實還是算比較新的。 更新的也只是這些演算法的最後改進吧。演化演算法就有很多。隨便搜一篇以這些為標題，看06年以來的新文章就可以了。 各個領域都有的。否則就是到極限，也就沒有什麼研究前景了。

③ 優化演算法有哪些

你好，優化演算法有很多，關鍵是針對不同的優化問題，例如可行解變數的取值（連續還是離散）、目標函數和約束條件的復雜程度（線性還是非線性）等，應用不同的演算法。
對於連續和線性等較簡單的問題，可以選擇一些經典演算法，例如梯度、Hessian
矩陣、拉格朗日乘數、單純形法、梯度下降法等；而對於更復雜的問題，則可考慮用一些智能優化演算法，例如你所提到的遺傳演算法和蟻群演算法，此外還包括模擬退火、禁忌搜索、粒子群演算法等。
這是我對優化演算法的初步認識，供你參考。有興趣的話，可以看一下維基網路。

④ A*演算法優化

A演算法是游戲中路徑搜索的常見演算法。Dijkstra是最短路徑的經典演算法，A演算法的思路基本上和Dijkstra演算法一致，在Dijkstra演算法的基礎上增加了啟發函數，也就是：

f(n) = g(n) + h(n)

其中，n是路徑上某一點，g(n)是從出發點到該點的cost，h(n)是關於該點的啟發函數，通常是對從該點到目標花費的一個估計，例如到目標的直線距離或者曼哈頓距離。 A演算法每次選擇f(n)最小的點，然後更新所有g(n)。
如果你明白Dijkstra演算法，那麼在這里h(n) = 0 的話，A演算法就和Dijkstra演算法一樣了。
本文不詳細講解A演算法，需要詳細了解A演算法的具體過程的，參見以下兩篇文章：

理解A*演算法的具體過程
A*演算法詳解

A*演算法優化的關鍵在於h(n)的選擇。 一個啟發函數h(n)被稱為admissible的，是指h(n)的估計，不會超過節點N到目標的實際花費。
如果h(x)滿足以下條件，h(x)被稱為單調的(monotone, or consistent)。 對於任意一條邊(x,y),
h(x) <= d(x,y) + h(y)
其中d(x,y)是（x,y）的長度

如果滿足這個條件，就意味著沒有任何節點需要被處理多次，也就是說，在Dijkstra演算法中，新加入一個節點會導致已添加節點中cost降低的情況不會存在，也就不需要去更新已添加節點(稱為close set)。

如果一個啟發函數是單調的，那麼該啟發函數一定是admissible的。如果該啟發函數是admissible的，那麼可以證明A*在同類演算法中搜尋到最短的路徑。

問題出在這里：如果我們更在意的是搜索的時間空間花費，而不是最優結果，那麼A*演算法就有優化空間。所以我們放鬆要求，修改我們的啟發函數，使得我們搜尋到的路徑不會比最佳路徑差太多，就是優化演算法，稱為ε-admissible演算法。

有多種ε-admissible演算法，在此只舉例最簡單直接的一種： 加權A*(靜態加權)演算法。

假如ha(n)是一個admissible的啟發函數，我們選取新的啟發函數hw(n) = ε ha(n)，其中ε>1 作為啟發函數。就可以在某種程度上進行優化。 下圖1是使用ha(n)作為啟發式演算法，下圖2是使用hw(n)作為啟發式演算法，其中ε取5.

圖1：ha(x)作為啟發演算法

圖2：hn(x)作為啟發演算法

可以看出，ha(n)可以找到最小路徑，但是多了許多無用的搜索；而hw(n)找到的不是最優路徑，但是減少了大量無用搜索。
其他的優化演算法思路類似都是在於啟發函數的選擇。詳見參考文獻。

參考文獻：
https://en.wikipedia.org/wiki/A*_search_algorithm#Admissibility_and_optimality https://en.wikipedia.org/wiki/Consistent_heuristic

⑤ 演算法優化有哪些主要方法和作用

優化演算法有很多，關鍵是針對不同的優化問題，例如可行解變數的取值（連續還是離散）、目標函數和約束條件的復雜程度（線性還是非線性）等，應用不同的演算法。
對於連續和線性等較簡單的問題，可以選擇一些經典演算法，如梯度、Hessian
矩陣、拉格朗日乘數、單純形法、梯度下降法等。
而對於更復雜的問題，則可考慮用一些智能優化演算法，如遺傳演算法和蟻群演算法，此外還包括模擬退火、禁忌搜索、粒子群演算法等。

⑥ Miller Rabin演算法的優化實現

Miller-Rabin演算法最為耗時的步驟在2.2模冪操作和2.3.2 循環。對演算法的優化實現主要集中在對這兩部分運算的優 化。對模冪操作的優化有兩種途徑：減少模冪演算法中的模乘 操作和優化模乘操作。在求模冪的過程中不能先求冪最後一次求模，這樣會產生一個十分巨大的中間結果，造成實際的 不可操作，所以在求模冪的演算法中用模乘代替乘法，使得中 間結果的長度不超過模的長度。對模冪演算法的優化，我們使 用改進的滑動窗口演算法結合Montgomery模乘和模平方演算法。表1給出模冪演算法的比較。 模冪演算法 預先計算 模平方 模乘法 模平方 模乘法 最壞情況 平均情況 平方乘演算法滑動窗口類演算法 改進的滑動窗口演算法 011 02k -32k-1-1 tt-(k-1)≤次數≤t t-(k-1)≤次數≤t t (t/k)-1 (t/k)-1 t/2 t/k(2k-1)/ 2kk≤t/k(2 -1)/ * 模冪演算法比較，其中k是窗口大小，根據情況 選擇以達到最優，t是指數的二進制位數。 優化的模冪演算法描述：輸入： x，e=(e tet-1?e1e0)2，其中et=1，k≥1( 窗口大小)輸出： xe mod n1、預計算1.1、x1← MontMul(x， R2，n)，x2←MontSqu(x 1， n)1.2、對i 從1 到2k-1-1計算x2i+1←MontMul(x2i-1， x2，n)2、A←R，i ←t3、 當i≥ 0時作下面的操作： 3.1、如果ei=0，A←MontSqu(A ，n)，i← i-13.2、否則找到最長的位串eiei-1?es使得i-s+1≤k並且es=1,計算3.2.1、A <－A2i-s+1 ， (利 用MontSqu函數計算)3.2.2、A <－A*X(ee ...e )2 ，(利 用MontMul函數計算)3.2.3、i ←s-14、A←MontMul(A ，1 ，n)5、返回A其中MontMul(x,y,n) 是Montgomery模乘函數，函數輸出 結果為x*y*R-1 mod n，MontSqu(x,n) 是Montgomery模平方函 數，輸出結果為x2R-1 mod n。模乘演算法如果採用大整數乘法 和除法求模乘，因為涉及耗時的除法操作，所以要相對較 慢，結合大整數乘法和Barrett求模演算法可以用2(n2+3n+1) 步 單精度乘法完成。使用Montgomery求模演算法結合大整數乘法 演算法，可以 在 2n(n+1) 步單精度乘法內完成演算法。 Montgomery模平方的操作可以在3n(n+1) /2步單精度乘法內 完成，而Barrett模平方需要(3n(n+3)/2+1) 步單精度乘法。結 合改進的滑動窗口演算法和Montgomery類演算法，可以得到目前 非特殊情況下的最優的模冪演算法。在Miller-Rabin演算法的2.3.2循環中的模平方操作我們沒有 使用Montgomery模平方演算法，因為該演算法給出的結果帶有R-1這個參數，在2.3.2循環中處理掉這個參數將占整個循環運 行時間中的很大部分，尤其是在循環的控制參數s 相對較小的時候。我們在這里使用大整數平方演算法結合Barrett求模算 法，2.3.2的循環最壞情況需要(s-1)(3n(n+3)/2+1)步單精度乘法。