⑴ 能不能簡單的給我解釋一下蒙特卡羅演算法
以概率和統計的理論、方法為基礎的一種計算方法，將所求解的問題同一定的概率模型相聯系，用電子計算機實現統計模擬或抽樣，以獲得問題的近似解，故又稱統計模擬法或統計試驗法。
蒙特卡羅是摩納哥的一個城市，以賭博聞名於世界。蒙特卡羅法借用這一城市的名稱是為了象徵性地表明該方法的概率統計的特點。
蒙特卡羅法作為一種計算方法，是由S.M.烏拉姆和J.馮·諾伊曼在20世紀40年代中葉為研製核武器的需要而首先提出來的。在此之前，該方法的基本思想實際上早已被統計學家所採用了。例如，早在17世紀，人們就知道了依頻數來決定概率的方法。
20世紀40年代中葉，出現了電子計算機，使得用數學方法模擬大量的試驗成為可能。另外，隨著科學技術的不斷發展，出現了越來越多的復雜而困難的問題，用通常的解析方法或數值方法都很難加以解決。蒙特卡羅法就是在這些情況下，作為一種可行的而且是不可缺少的計算方法被提出和迅速發展起來的。
基本原理 考慮一個射擊運動員的射擊成績 G。令x表示彈著點到靶心的距離，g(x)表示得分，而�0�6(x)表示該運動員的彈著點的分布密度，則
。
另一方面，如果該運動員進行了實彈射擊，彈著點依次為X1，X2，…，XN，則平均得分為
。
很明顯，弿N是G 的一個近似估計。蒙特卡羅法正是用弿N作為G 的近似估計。
假設 x不是一維空間的點，而是一個S 維空間的點(x1，x2，…，xs)，則上述積分變為
。
蒙特卡羅法計算此積分是用
作為G 的近似估計，式中(X1n，X2n，…，Xsn)是由�0�6(x1，x2，…，xs)中抽取的第n 個樣本點。同上述一維積分比較，相同點是，都以某隨機變數的N 個獨立抽樣值的算術平均作為近似估計；不同點僅僅是，決定隨機量的樣本點不同，一個是一維空間的點，另一個是S 維空間的點。由上式可見， 決定近似估計 弿N好壞的僅僅是隨機變數g(x)或g(x1，x2，…，xs)的分布情況，而與它們是由怎樣的樣本點對應過來的無關。換言之，如果隨機變數g(x)和g(x1，x2，…，xs)具有相同分布，在不計抽樣，不計計算g(x)和g(x1，x2，…，xs)的差別的情況下，S維情況與一維情況無任何差異。這是其他計算方法所不具有的、一個非常重要的性質。
蒙特卡羅法解題的一般過程是，首先構成一個概率空間；然後在該概率空間中確定一個隨機變數g(x)，其數學期望
正好等於所要求的值G，其中F(x)為x的分布函數；最後，以所確定的隨機變數的簡單子樣的算術平均值
作為G 的近似估計。由於其他原因，如確定數學期望為G 的隨機變數g(x)有困難，或為其他目的，蒙特卡羅法有時也用G 的漸近無偏估計代替一般過程中的無偏估計弿N來作為G 的近似估計。
收斂性、誤差和費用 蒙特卡羅法的近似估計弿N依概率1收斂於G的充分必要條件是隨機變數g(x)滿足
。
如果隨機變數g(x)滿足條件
，
式中1≤r<2，則
，
亦即弿N依概率1收斂於G 的速度為。總之，蒙特卡羅法的收斂性取決於所確定的隨機變數是否絕對可積，而蒙特卡羅法的收斂速度取決於該隨機變數是幾次絕對可積的。
根據中心極限定理，只要隨機變數g(x)具有有限的異於零的方差σ2，當N 足夠大時便有蒙特卡羅法的誤差公式如下：
，
式中1-α為置信水平，x由置信水平所惟一確定。根據上述誤差公式，為滿足問題的誤差和置信水平的要求，子樣容量N必須大於(x/ε)2σ2，其中ε表示誤差。進一步假設每觀察一個樣本所需要的費用是C，則蒙特卡羅法的費用是。這一結果表明，在相同誤差和置信水平要求下，一個蒙特卡羅法的優劣完全取決於σ2C 的值的大小，它的值越小相應的方法越好，或者說，蒙特卡羅法的效率與σ2C 成反比。
提高效率的方法
降低方差技巧 降低方差是提高蒙特卡羅法效率的重要途徑之一。考慮二重積分
，
式中�0�6(x，y)為x和y的分布密度函數，g(x，y)的方差存在。蒙特卡羅法計算Eg的一般技巧是用g=g(x， y)作為所確定的隨機變數，其中x和y服從分布�0�6(x，y)。降低方差的具體辦法有：
① 統計估計技巧用�0�6(x) 和�0�6x(y)分別表示分布�0�6(x，y)的邊緣分布和條件分布。計算Eg的統計估計技巧是用y的統計估計量
作為所確定的隨機變數，其中x服從分布�0�6(x)。g的方差恰好為兩個方差的和，它們分別是對隨機變數x和隨機變數y採用抽樣辦法而產生的。gSE的方差正好等於前者，因此gSE的方差一定比g的方差小。統計估計技巧的一般原理是，對於問題中所出現的諸隨機變數，能夠確定其相應的統計估計量的，就不要再對它們採用隨機抽樣的辦法。
② 重要抽樣技巧引入任意分布密度函數�0�6*(x，y)，則
的數學期望同樣為Eg，其中x和y服從分布�0�6*(x，y)。當�0�6*(x，y)～|g(x，y)|�0�6(x，y)時，gIS的方差達到最小。在g(x，y)≥0時，方差等於零，gIS實際上變成了與其中出現的隨機變數無關的常數。重要抽樣技巧的一般原理是，盡量使所確定的隨機變數與問題中所出現的隨機變數關系不大。
③ 相關抽樣技巧考慮一個新的、積分值已知的二重積分
，
可得知
的數學期望同樣為Eg，式中x和y服從分布�0�6(x，y)，α為任意常數。當為隨機變數g(x，y)和g*(x，y)的均方差σg、λg*之比時，gCS的方差達到最小。此時的方差等於g 的方差 1-ρ2倍，ρ為隨機變數g(x，y)和g*(x，y)的相關系數。當ρ=1時，方差變為零。相關抽樣技巧的一般原理是，尋找一個數學期望已知的且與原確定的隨機變數正相關的隨機變數，使相應的相關系數盡量接近1，然後用這兩個隨機變數的線性組合作為蒙特卡羅法最終所確定的隨機變數。
降低方差的技巧還有對偶變數技巧、系統抽樣技巧和分層抽樣技巧等。對偶變數技巧的一般原理是，除了原確定的隨機變數外，尋找另一個（或多個）具有相同數學期望的隨機變數，使得它們之間盡量是對偶負相關的，然後用它們的線性組合作為蒙特卡羅法最終所確定的隨機變數。系統抽樣技巧的一般原理是，對問題中所出現的某些隨機變數按相應分布所確定的比例進行抽樣，而不是進行隨機抽樣。分層抽樣技巧的一般原理是，對問題中所出現的某些隨機變數進行分層，盡量使所確定的隨機變數在各層中相對平穩，各層間的抽樣按相應分布所確定的比例進行。
其他途徑 為了提高蒙特卡羅法的效率，除了簡單地降低方差外，還有為降低費用設計的分裂和輪盤賭技巧，為逐步降低方差而設計的多極抽樣技巧，為改善收斂速度而設計的擬蒙特卡羅法，為計算條件期望而設計的條件蒙特卡羅法等等。分裂和輪盤賭技巧的一般原理是，將x的積分區域分為重要和非重要兩部分，對於抽樣確定的X，當它屬於重要區域時，對相應的Y 進行多次抽樣；當它屬於非重要區域時，只有在賭獲勝時才對相應的Y 進行抽樣。多級抽樣技巧的一般原理是，在進行某一級抽樣計算的同時，根據它所提供的抽樣觀察值，設計更好的抽樣技巧，用新設計的抽樣技巧進行新的一級的抽樣計算，依次類推，最後用各級的結果的線性組合作為蒙特卡羅法的近似估計。擬蒙特卡羅法與一般蒙特卡羅法的最大區別是，前者不像後者那樣要求子樣 g(X1)，g(X2)，…，g(Xn)是相互獨立的。用一致分布點列替代由隨機數組成的點列的所謂數論方法，實際上就是一種擬蒙特卡羅法。條件蒙特卡羅法的一般原理是，首先將條件期望問題轉化成為非條件期望問題，然後用解非條件期望的一般方法來解決條件期望計算問題。由於條件蒙特卡羅法中引進了任意分布密度函數，因此，可以選取合適的分布密度函數來實現進一步降低方差的目的。
優缺點 蒙特卡羅法的最大優點是，在方差存在的情況下，問題的維數不影響它的收斂速度，而隻影響它的方差；問題幾何形狀的復雜性對它的影響不大；它不象其他數值方法那樣對問題一定要進行離散化處理，而是常可以進行連續處理；它的程序結構簡單，所需計算機存貯單元比其他數值方法少，這對於高維問題差別尤其顯著。蒙特卡羅法的最大缺點是，對於維數少的問題它不如其他數值方法好；它的誤差是概率誤差，而不是一般意義下的誤差。
應用 隨著電子計算機的迅速發展和科學技術問題日趨復雜，蒙特卡羅法的應用越來越廣泛，已經滲透到科學技術的各個領域。
在一些典型數學問題方面的應用主要有：多重積分計算、線性代數方程組求解、矩陣求逆、常微分方程邊值問題求解、偏微分方程求解、非齊次線性積分方程求解、本徵值計算和最優化計算等等。其中的多重積分計算、非齊次線性積分方程求解和齊次線性積分方程本徵值計算等，不僅非常有代表性，而且有很大的實用價值，對於高維問題常比其他數值方法好。
在一些實際問題方面的應用主要有，屏蔽計算、核臨界安全計算、反應堆物理計算、微擾計算、實驗核物理計算、高能物理計算、核物理計算、統計物理計算、真空技術、公用事業、資訊理論、系統模擬、可靠性計算和計算機科學等等。其中的屏蔽計算、核臨界安全計算、微擾計算、實驗核物理計算和統計物理計算等，不僅非常有代表性，而且應用得很廣泛，按蒙特卡羅法解決這些問題的能力講，已經超過了其他計算方法的水平。
⑵ 優化演算法筆記（一）優化演算法的介紹
（以下描述，均不是學術用語，僅供大家快樂的閱讀）
我們常見常用的演算法有排序演算法,字元串遍歷演算法,尋路演算法等。這些演算法都是為了解決特定的問題而被提出。
演算法本質是一種按照固定步驟執行的過程。
優化演算法也是這樣一種過程，是一種根據概率按照固定步驟尋求問題的最優解的過程。與常見的排序演算法、尋路演算法不同的是，優化演算法不具備等冪性，是一種 概率演算法 。演算法不斷的 迭代 執行同一步驟直到結束，其流程如下圖。
等冪性即 對於同樣的輸入，輸出是相同的 。
比如圖1，對於給定的魚和給定的熊掌，我們在相同的條件下一定可以知道它們誰更重，當然，相同的條件是指魚和熊掌處於相同的重力作用下，且不用考慮水分流失的影響。在這些給定的條件下，我們（無論是誰）都將得出相同的結論，魚更重或者熊掌更重。我們可以認為，秤是一個等冪性的演算法（工具）。
現在把問題變一變，問魚與熊掌你更愛哪個，那麼現在，這個問題，每個人的答案可能不會一樣，魚與熊掌各有所愛。說明喜愛這個演算法不是一個等冪性演算法。當然你可能會問，哪個更重，和更喜歡哪個這兩個問題一個是客觀問題，一個是主觀問題，主觀問題沒有確切的答案的。當我們處理主觀問題時，也會將其轉換成客觀問題，比如給喜歡魚和喜歡熊掌的程度打個分，再去尋求答案，畢竟計算機沒有感情，只認0和1（量子計算機我不認識你）。
說完了等冪性，再來說什麼是概率演算法。簡單來說就是看臉、看人品、看運氣的演算法。
有一場考試，考試的內容全部取自課本，同時老師根據自己的經驗給同學們劃了重點，但是因為試卷並不是該老師所出，也會有考試內容不在重點之內，老師估計試卷中至少80%內容都在重點中。學霸和學渣參加了考試，學霸為了考滿分所以無視重點，學渣為了pass，因此只看了重點。這樣做的結果一定是score(學霸)>=score(學渣)。
當重點跟上圖一樣的時候，所有的內容都是重點的時候，學霸和學渣的學習策略變成了相同的策略，則score(學霸)=score(學渣)。但同時，學渣也要付出跟學霸相同的努力去學習這些內容，學渣心裡苦啊。
當課本如下圖時
學霸？學霸人呢，哪去了快來學習啊，不是說學習一時爽，一直學習一直爽嗎，快來啊，還等什麼。
這時，如果重點內容遠少於書本內容時，學渣的學習策略有了優勢——花費的時間和精力較少。但是同時，學渣的分數也是一個未知數，可能得到80分也可能拿到100分，分數完全取決於重點內容與題目的契合度，契合度越高，分數越高。對學渣來說，自己具體能考多少分無法由自己決定，但是好在能夠知道大概的分數范圍。
學霸的學習策略是一種遍歷性演算法，他會遍歷、通讀全部內容，以保證滿分。
學渣的學習策略則是一種概率演算法，他只會遍歷、學習重點內容，但至於這些重點是不是真重點他也不知道。
與遍歷演算法相比，概率演算法的結果具有不確定性，可能很好，也可能很差，但是會消耗更少的資源，比如時間（人生），空間（記憶）。概率演算法的最大優點就是 花費較少的代價來獲取最高的收益 ，在現實中體現於節省時間，使用很少的時間得到一個不與最優解相差較多的結果。
「莊子：吾生也有涯，而知也無涯；以有涯隨無涯，殆矣。」的意思是：人生是有限的，但知識是無限的（沒有邊界的），用有限的人生追求無限的知識，是必然失敗的。
生活中概率演算法（思想）的應用其實比較廣泛，只是我們很少去注意罷了。關於概率演算法還衍生出了一些有趣的理論，比如墨菲定律和倖存者偏差，此處不再詳述。
上面說到，優化演算法就是不停的執行同樣的策略、步驟直到結束。為什麼要這樣呢？因為優化演算法是一種概率演算法，執行一次操作就得到最優結果幾乎是不可能的，重復多次取得最優的概率也會增大。
栗子又來了，要從1-10這10個數中取出一個大於9的數，只取1次，達到要求的概率為10%，取2次，達到要求的概率為19%。
可以看出取到第10次時，達到要求的概率幾乎65%，取到100次時，達到要求的概率能接近100%。優化演算法就是這樣簡單粗暴的來求解問題的嗎？非也，這並不是一個恰當的例子，因為每次取數的操作之間是相互獨立的，第2次取數的結果不受第1次取數結果的影響，假設前99次都沒達到要求，那麼再取一次達到要求的概率跟取一次達到要求的概率相同。
優化演算法中，後一次的計算會依賴前一次的結果，以保證後一次的結果不會差於前一次的結果。這就不得不談到馬爾可夫鏈了。
由鐵組成的鏈叫做鐵鏈，同理可得，馬爾可夫鏈就是馬爾可夫組成的鏈。
言歸正傳, 馬爾可夫鏈（Markov Chain, MC） ,描述的是 狀態轉移的過程中,當前狀態轉移的概率只取決於上一步的狀態,與其他步的狀態無關 。簡單來說就是當前的結果只受上一步的結果的影響。每當我看到馬爾可夫鏈時，我都會陷入沉思，生活中、或者歷史中有太多太多與馬爾可夫鏈相似的東西。西歐封建等級制度中「附庸的附庸不是我的附庸」與「昨天的努力決定今天的生活，今天的努力決定明天的生活」，你的下一份工作的工資大多由你當前的工資決定，這些都與馬爾可夫鏈有異曲同工之處。
還是從1-10這10個數中取出一個大於9的數的這個例子。基於馬爾可夫鏈的概率演算法在取數時需要使當前取的數不小於上一次取的數。比如上次取到了3，那麼下次只能在3-10這幾個數中取，這樣一來，達到目標的概率應該會顯著提升。還是用數據說話。
取1次達到要求的概率仍然是
取2次內達到要求的概率為
取3次內達到要求的概率為
取4次內……太麻煩了算了不算了
可以看出基於馬爾可夫鏈來取數時，3次內能達到要求的概率與不用馬爾可夫鏈時取6次的概率相當。說明基於馬爾可夫鏈的概率演算法求解效率明顯高於隨機概率演算法。那為什麼不將所有的演算法都基於馬爾可夫鏈呢？原因一，其實現方式不是那麼簡單，例子中我們規定了取數的規則是復合馬爾可夫鏈的，而在其他問題中我們需要建立適當的復合馬爾科夫鏈的模型才能使用。原因二，並不是所有的問題都符合馬爾科夫鏈條件，比如原子內電子出現的位置，女朋友為什麼會生（lou）氣，彩票號碼的規律等，建立模型必須與問題有相似之處才能較好的解決問題。
介紹完了優化演算法，再來討論討論優化演算法的使用場景。
前面說了優化演算法是一種概率演算法，無法保證一定能得到最優解，故如果要求結果必須是確定、穩定的值，則無法使用優化演算法求解。
例1，求城市a與城市b間的最短路線。如果結果用來修建高速、高鐵，那麼其結果必定是唯一確定的值，因為修路寸土寸金，必須選取最優解使花費最少。但如果結果是用來趕路，那麼即使沒有選到最優的路線，我們可能也不會有太大的損失。
例2，求城市a與城市b間的最短路線，即使有兩條路徑，路徑1和路徑2，它們從a到b的距離相同，我們也可以得出這兩條路徑均為滿足條件的解。現在將問題改一下，求城市a到城市b耗時最少的線路。現在我們無法馬上得出確切的答案，因為最短的線路可能並不是最快的路線，還需要考慮到天氣，交通路況等因素，該問題的結果是一個動態的結果，不同的時間不同的天氣我們很可能得出不同的結果。
現實生產、生活中，也有不少的場景使用的優化演算法。例如我們的使用的美圖軟體，停車場車牌識別，人臉識別等，其底層參數可能使用了優化演算法來加速參數計算，其參數的細微差別對結果的影響不太大，需要較快的得出誤差范圍內的參數即可；電商的推薦系統等也使用了優化演算法來加速參數的訓練和收斂，我們會發現每次刷新時，推給我們的商品都有幾個會發生變化，而且隨著我們對商品的瀏覽，系統推給我們的商品也會發生變化，其結果是動態變化的；打車軟體的訂單系統，會根據司機和客人的位置，區域等來派發司機給客人，不同的區域，不同的路況，派發的司機也是動態變化的。
綜上我們可以大致總結一下推薦、不推薦使用優化演算法的場景的特點。
前面說過，優化演算法處理的問題都是客觀的問題，如果遇到主觀的問題，比如「我孰與城北徐公美」，我們需要將這個問題進行量化而轉換成客觀的問題，如身高——「修八尺有餘」，「外貌——形貌昳麗」，自信度——「明日徐公來，孰視之，自以為不如；窺鏡而自視，又弗如遠甚」，轉化成客觀問題後我們可以得到各個解的分數，通過比較分數，我們就能知道如何取捨如何優化。這個轉化過程叫做問題的建模過程，建立的問題模型實際上是一個函數，這個函數對優化演算法來說是一個黑盒函數，即不需要知道其內部實現只需要給出輸入，得到輸出。
在優化演算法中這個黑盒函數叫做 適應度函數 ， 優化演算法的求解過程就是尋找適應度函數最優解的過程 ，使用優化演算法時我們最大的挑戰就是如何將抽象的問題建立成具體的模型，一旦合適的模型建立完成，我們就可以愉快的使用優化演算法來求解問題啦。（「合適」二字談何容易）
優化演算法的大致介紹到此結束，後面我們會依次介紹常見、經典的優化演算法，並探究其參數對演算法性能的影響。
——2019.06.20
[目錄]
[下一篇 優化演算法筆記（二）優化演算法的分類]
⑶ 優化演算法
SGD演算法中的一個關鍵參數是學習率。之前，我們介紹的SGD使用固定的學習率。在實踐中，有必要隨著時間的推移逐漸降低學習率，因此我們將第 k 步迭代的學習率記作 ϵ k 。
這是因為SGD中梯度估計引入的雜訊源（m 個訓練樣本的隨機采樣）並不會在極小點處消失。相比之下，當我們使用批量梯度下降到達極小點時，整個代價函數的真實梯度會變得很小，之後為 0，因此批量梯度下降可以使用固定的學習率。保證SGD收斂的一個充分條件是
若 ϵ 0 太大，學習曲線將會劇烈振盪，代價函數值通常會明顯增加。溫和的振盪是良好的，容易在訓練隨機代價函數（例如使用Dropout的代價函數）時出現。如果學習率太小，那麼學習過程會很緩慢。如果初始學習率太低，那麼學習可能會卡在一個相當高的代價值。通常，就總訓練時間和最終代價值而言，最優初始學習率會高於大約迭代 100 次左右後達到最佳效果的學習率。因此，通常最好是檢測最早的幾輪迭代，選擇一個比在效果上表現最佳的學習率更大的學習率，但又不能太大導致嚴重的震盪。
雖然隨機梯度下降仍然是非常受歡迎的優化方法，但其學習過程有時會很慢。動量方法 (Polyak, 1964) 旨在加速學習，特別是處理高曲率、小但一致的梯度，或是帶雜訊的梯度。動量演算法積累了之前梯度指數級衰減的移動平均，並且繼續沿該方向移動。動量的效果如圖8.5所示
受 Nesterov 加速梯度演算法 (Nesterov, 1983, 2004) 啟發，提出了動量演算法的一個變種。這種情況的更新規則如下：
其中參數 α 和 ϵ 發揮了和標准動量方法中類似的作用。Nesterov 動量和標准動量之間的區別體現在梯度計算上。Nesterov 動量中，梯度計算在施加當前速度之後。因此，Nesterov 動量可以解釋為往標准動量方法中添加了一個校正因子。完整的Nesterov動量演算法如演算法3.2所示
初始點能夠決定演算法是否收斂，有些初始點十分不穩定，使得該演算法會遭遇數值困難，並完全失敗。當學習收斂時，初始點可以決定學習收斂得多快，以及是否收斂到一個代價高或低的點。此外，差不多代價的點可以具有區別極大的泛化誤差，初始點也可以影響泛化。
也許完全確知的唯一特性是初始參數需要在不同單元間 『『破壞對稱性』』。如果具有相同激活函數的兩個隱藏單元連接到相同的輸入，那麼這些單元必須具有不同的初始參數。如果它們具有相同的初始參數，然後應用到確定性損失和模型的確定性學習演算法將一直以相同的方式更新這兩個單元。即使模型或訓練演算法能夠使用隨機性為不同的單元計算不同的更新（例如使用Dropout的訓練），通常來說，最好還是初始化每個單元使其和其他單元計算不同的函數。這或許有助於確保沒有輸入模式
丟失在前向傳播的零空間中，沒有梯度模式丟失在反向傳播的零空間中。每個單元計算不同函數的目標促使了參數的隨機初始化。我們可以明確地搜索一大組彼此互不相同的基函數，但這經常會導致明顯的計算代價。例如，如果我們有和輸出一樣多的輸入，我們可以使用 Gram-Schmidt 正交化於初始的權重矩陣，保證每個單元計算彼此非常不同的函數。在高維空間上使用高熵分布來隨機初始化，計算代價小並且不太可能分配單元計算彼此相同的函數。
通常情況下，我們可以為每個單元的偏置設置啟發式挑選的常數，僅隨機初始化權重。額外的參數（例如用於編碼預測條件方差的參數）通常和偏置一樣設置為啟發式選擇的常數。
我們幾乎總是初始化模型的權重為高斯或均勻分布中隨機抽取的值。高斯或均勻分布的選擇似乎不會有很大的差別，但也沒有被詳盡地研究。然而，初始分布的大小確實對優化過程的結果和網路泛化能力都有很大的影響。
更大的初始權重具有更強的破壞對稱性的作用，有助於避免冗餘的單元。它們也有助於避免在每層線性成分的前向或反向傳播中丟失信號——矩陣中更大的值在矩陣乘法中有更大的輸出。如果初始權重太大，那麼會在前向傳播或反向傳播中產生爆炸的值。在循環網路中，很大的權重也可能導致混沌（chaos）（對於輸入中很小的擾動非常敏感，導致確定性前向傳播過程表現隨機）。在一定程度上，梯度爆炸問題可以通過梯度截斷來緩解（執行梯度下降步驟之前設置梯度的閾值）。較大的權
重也會產生使得激活函數飽和的值，導致飽和單元的梯度完全丟失。這些競爭因素決定了權重的理想初始大小。
也有助於避免在每層線性成分的前向或反向傳播中丟失信號——矩陣中更大的值在矩陣乘法中有更大的輸出。如果初始權重太大，那麼會在前向傳播或反向傳播中產生爆炸的值。在循環網路中，很大的權重也可能導致混沌（chaos）（對於輸入中很小的擾動非常敏感，導致確定性前向傳播過程表現隨機）。在一定程度上，梯度爆炸問題可以通過梯度截斷來緩解（執行梯度下降步驟之前設置梯度的閾值）。較大的權重也會產生使得激活函數飽和的值，導致飽和單元的梯度完全丟失。這些競爭因素決定了權重的理想初始大小。
有些啟發式方法可用於選擇權重的初始大小。一種初始化 m 個輸入和 n 輸出的全連接層的權重的啟發式方法是從分布 U(−1/√ m ,
1/√ m ) 中采樣權重，而 Glorot and Bengio 建議使用標准初始化
後一種啟發式方法初始化所有的層，折衷於使其具有相同激活方差和使其具有相同梯度方差之間。這假設網路是不含非線性的鏈式矩陣乘法，據此推導得出。現實的神經網路顯然會違反這個假設，但很多設計於線性模型的策略在其非線性對應中的效果也不錯。
數值范圍准則的一個缺點是，設置所有的初始權重具有相同的標准差，例如1/√ m ，會使得層很大時每個單一權重會變得極其小。Martens (2010) 提出了一種被稱為稀疏初始化（sparse initialization）的替代方案，每個單元初始化為恰好有 k 個非零權重。這個想法保持該單元輸入的總數量獨立於輸入數目 m，而不使單一權重元素的大小隨 m 縮小。稀疏初始化有助於實現單元之間在初始化時更具多樣性。但是，獲得較大取值的權重也同時被加了很強的先驗。因為梯度下降需要很長時間縮小 『『不正確』』 的大值，這個初始化方案可能會導致某些單元出問題，例如maxout單元有幾個過濾器，互相之間必須仔細調整。
Delta-bar-delta 演算法 (Jacobs, 1988) 是一個早期的在訓練時適應模型參數各自學習率的啟發式方法。該方法基於一個很簡單的想法，如果損失對於某個給定模型參數的偏導保持相同的符號，那麼學習率應該增加。如果對於該參數的偏導變化了符號，那麼學習率應減小。當然，這種方法只能應用於全批量優化中。
AdaGrad 演算法，如演算法8.4所示，獨立地適應所有模型參數的學習率，縮放每個參數反比於其所有梯度歷史平方值總和的平方根 (Duchi et al., 2011)。具有損失最大偏導的參數相應地有一個快速下降的學習率，而具有小偏導的參數在學習率上有相對較小的下降。凈效果是在參數空間中更為平緩的傾斜方向會取得更大的進步。
在凸優化背景中，AdaGrad 演算法具有一些令人滿意的理論性質。然而，經驗上已經發現，對於訓練深度神經網路模型而言，從訓練開始時積累梯度平方會導致有效學習率過早和過量的減小。AdaGrad在某些深度學習模型上效果不錯，但不是全部。
RMSProp 演算法 (Hinton, 2012) 修改 AdaGrad 以在非凸設定下效果更好，改變梯度積累為指數加權的移動平均。AdaGrad旨在應用於凸問題時快速收斂。當應用於非凸函數訓練神經網路時，學習軌跡可能穿過了很多不同的結構，最終到達一個局部是凸碗的區域。AdaGrad 根據平方梯度的整個歷史收縮學習率，可能使得學習率在達到這樣的凸結構前就變得太小了。RMSProp 使用指數衰減平均以丟棄遙遠過去的歷史，使其能夠在找到凸碗狀結構後快速收斂，它就像一個初始化於該碗狀結構的 AdaGrad 演算法實例。
RMSProp 的標准形式如演算法8.5所示，結合 Nesterov 動量的形式如演算法8.6所示。相比於 AdaGrad，使用移動平均引入了一個新的超參數ρ，用來控制移動平均的長度范圍。經驗上，RMSProp 已被證明是一種有效且實用的深度神經網路優化演算法。目前它是深度學習從業者經常採用的優化方法之一。
Adam (Kingma and Ba, 2014) 是另一種學習率自適應的優化演算法，最好被看作結合 RMSProp 和具有一些重要區別的動量的變種。首先，在 Adam 中，動量直接並入了梯度一階矩（指數加權）的估計。將動量加入 RMSProp 最直觀的方法是將動量應用於縮放後的梯度。結合縮放的動量使用沒有明確的理論動機。其次，Adam 包括偏置修正，修正從原點初始化的一階矩（動量項）和（非中心的）二階矩的估計（演算法8.7）。RMSProp 也採用了（非中心的）二階矩估計，然而缺失了修正因子。因此，不像 Adam，RMSProp 二階矩估計可能在訓練初期有很高的偏置。Adam 通常被認為對超參數的選擇相當魯棒，盡管學習率有時需要從建議的默認修改。
目前，最流行並且使用很高的優化演算法包括 SGD、具動量的 SGD、RMSProp、具動量的 RMSProp、AdaDelta 和 Adam。
⑷ 優化演算法筆記（十二）煙花演算法
（以下描述，均不是學術用語，僅供大家快樂的閱讀）
煙花演算法（Firework Algorithm,FWA）是一種受煙花爆炸產生火星，並繼續分裂爆炸這一過程啟發而得出的演算法。演算法的思想簡單，但具體實現復雜。演算法提出時間並不長，但是已經有了不少的改進研究和較為全面的應用。
煙花演算法中，每一個煙花的位置都代表了一個可行解。煙花的爆炸產生的火星有兩種，正常的火星與特別的火星。每個火星都會爆炸產生數個正常火星，某些火星有一定的概率產生一個特別的火星。正常的火星根據當前火星的振幅隨機均勻分布在該火星的周圍，而特別的火星將在當前火星附近以正態分布方式產生。每次迭代產生的火星數量多於每一代應有的火星數，演算法將參照火星位置的優劣，隨機留下指定數量的火星，已保持火星數目的穩定。
煙花演算法的主角毫無疑問就是煙花了。
式（1）為適應度值越小越優的情況，而式（2）則是適應度值越大越優的情況。 為一個極小的值，以保證分母不為0。
每個火星產生的正常火星數量也由其適應度值來決定。
其中 表示第i個火星將要產生的正常火星數， 是產生正常火星的總數為一個常數，從式（3）,（4）可以看出適應度值越好的火星能夠產生更多的正常火星，反之，火星適應度越差，能夠產生的火星數越少。
由於式（3），（4）計算出的值為小數，煙花演算法中使用式（5）將其轉化為整數。
從式（3）和式（4）中可以看出，在每一代中將會產生出 個正常火星。產生的正常火星的位置與當前火星的振幅有關，可以從式（1），（2）看出，適應度越優的火星的振幅越小，那麼它產生的正常火星將在它自己周圍，而適應度越差的火星的振幅越大，它產生的正常火星將會出現在離自己較遠的位置。
當前火星每次爆炸會從D維搜索空間內隨機選擇z維進行更新從而產生新的火星。正常火星的位置由如下公式產生。
其中z為取值1-D的均勻隨機正整數，rand(-1,1)表示-1到1內的均勻隨機數。從式(6)中可以看出，正常火星的位置與其振幅有直接關系，振幅越大產生的新火星距當前火星的距離約遠。
每次迭代過程中，會產生m個特別的火星，即在這N個火星中隨機選擇m個火星，每個火星產生一個特別的火星。特別的火星的由下面的公式產生：
由上面的過程可知，在每一代中，有N個火星，將會產生出 個正常火星以及m個特別的火星。但是每一代中只能從這 個火星中選擇N個火星保留至下一代。
每次會先從 個火星中選擇最優的火星保留至下一代，然後再從中選擇N-1個火星。選擇某個火星的概率如下：
其中R(X)表示該火星距其他所有火星的距離之和，即距其它火星越遠的火星，被選擇保留至下一代的概率較大。
個火星，而且
,所有煙花演算法每次迭代的計算復雜度要大於其他演算法，這簡直就是一個作弊行為。別的演算法每次只搜索了N個位置，而煙花演算法卻搜索了 個位置。與其他優化演算法對比時，其他演算法的種群數量應該取 ，否則這將是一場不公正的對決。
適應度函數還是這個簡單的小白鼠
實驗一 ：標准煙花演算法
以上數據來自原論文，現在看一看實驗的圖像以及實驗結果。
從圖像可以看出每次只選擇保留了5個火星，它們的收斂速度很慢，實驗結束時距離目標點還有一段距離。
看看實驗結果
從實驗結果可以看出，演算法的性能很不穩定，而造成這一點的原因很可能是其收斂速度較慢，演算法仍在收斂過程中，所以結果看上去很差。將最大迭代次數修改為100代，重新試驗，其結果如下：
結果好了一些但還是難以接受，為什麼煙花演算法的結果不理想呢？
原因可能是保留機制（2.3節）的問題，煙花演算法中保留火星的概率是根據該火星與其他火星的距離和，距離群體越大的個體被保留下的概率越大。這樣做有什麼好處呢？好處是火星相對分散，這是一個對抗局部最優的策略，但是，距離群體較遠的個體是一個較差的個體的概率非常大，壞處就是，集中於當前最優位置的火星被保留的概率較小，演算法的局部搜索能力將較弱。
實驗二 . 隨機選擇的方式保留火星
為了加快煙花演算法的收斂速度，增強局部搜索能力，我移除了標准煙花演算法的選擇過程，使用隨機選擇的方式保留火星，當然，最優個體依然會被保留至下一代。其他參數保持不變。
可以看出這次的圖像相比實驗一收斂速度快了不少，在迭代結束時已經相對在一個較小的區域。這次的結果也明顯優於實驗一。將選擇過程改為隨機選擇後，由於較優的火星產生的較多且分布在自己周圍，因此選擇到這些較優的火星的概率也相對較大，演算法的收斂速度相對較快。與此同時，演算法跳出局部最優的能力比修改前要弱。
對於較簡單的問題來說當然是隨機選擇收斂較快結果較好，而復雜的問題則需要更強的跳出局部最優能力。問題的關鍵仍然是，我們無法在一開始就知道問題的復雜程度。
實驗三 .增加火星的種群數量，減少每代產生的正常火星總數
為什麼要減少產生的正常火星數，這樣演算法搜索的次數減少了，效果不會更差嗎？其實與直覺相反，減少正常火星總數，增加火星總群數，實際上是讓較優的火星產生的正常火星被保留下來的概率變大了，這樣也可以解決實驗一中的問題，加快演算法的收斂速度。
從圖像中可以看出，演算法在50代之前已經收斂，但是之後只在小范圍內進行搜索。實驗圖像與之前的描述相符，收斂速度加快但是跳出局部最優能力減弱。看看實驗結果，實驗結果好了不少且結果更加穩定。
其實實驗二與實驗三，使用了不同的策略，但都達到了同樣的目的——保留更多的優質火星到下一代，它們促進了局部搜索但是擠佔了較劣火星的位置，削弱了種群的多樣性。
每代留下的火星多了，圖像看上去是不是更像煙花？
煙花演算法的探究遠不止如此，幾年前作為一個較新的演算法來學習時卻已經有了大量的論文和書籍，可見大家對煙花演算法已經有了較為深入的研究，而我能做的只是應用演算法解決問題以及稍作改進讓演算法與問題的適應性更高。
煙花演算法產生正常火星的過程為演算法提供了搜索能力，產生特殊火星的過程和選擇過程為演算法提供了跳出局部最優的能力。但是個人認為選擇過程與其他過程的適應性不是很好。標準的選擇過程會丟失掉許多較優的個體，使之前產生的正常火星得到的成果沒有保留。
煙花演算法其實還有比較多的改進點，對演算法產生最大的參數應該就是正常火星的總數以及振幅了。簡單粗暴的改進：在每一代可以對這兩個參數進行變化或者隨機化，讓演算法的搜索能力與跳出局部最優能力在整個流程中動態變化，以均衡兩種能力。
以下指標純屬個人yy,僅供參考
參考文獻
Tan Y , Zhu Y . Fireworks Algorithm for Optimization[C]// Advances in Swarm Intelligence, First International Conference, ICSI 2010, Beijing, China, June 12-15, 2010, Proceedings, Part I. Springer-Verlag, 2010. 提取碼：yaj0
目錄
上一篇 優化演算法筆記（十一）群搜索演算法
下一篇 優化演算法筆記（十三）鯨魚演算法
優化演算法matlab實現（十二）煙花演算法matlab實現
⑸ 優化演算法筆記（七）差分進化演算法
（以下描述，均不是學術用語，僅供大家快樂的閱讀）
差分進化演算法（Differential Evolution Algorithm，DE）是一種基於群體的進化演算法，它模擬了群體中的個體的合作與競爭的過程。演算法原理簡單，控制參數少，只有交叉概率和縮放比例因子，魯棒性強，易於實現。
差分進化演算法中，每一個個體的基因表示待求問題的一個候選解。每次迭代將先進行變異操作，選擇一個或多個個體的基因作為基，然後選擇不同的個體的差分來構成差分基因，最後將作為基的基因與差分基因相加來得出新的個體。交叉操作將新的個體將於父代的對應個體交叉，然後進行選擇操作，比較交叉後的個體與父代的對應個體，選擇較優的個體保留至下一代。在迭代完成之後將選擇種群中最優個體的基因作為解。
差分進化演算法可以算是我所使用過的優化演算法中大魔王級別的演算法，雖然它每個方面都沒有強到離譜，但是綜合起來的效果好於大多數演算法。它就像一個每個科目都能考到90分（百分制）的學生，雖然沒門課都不是最優秀的，但是論綜合，論總分，它有極大的概率是第一名。
在我研究優化演算法的小路上，我的目標就是找到一個能打敗大魔王或是能在大多數方面壓制魔王的演算法。
這次的主角就選魔王軍吧（或者蟻王軍，為了與蟻群演算法區別還是叫魔王軍吧），個體則稱之為魔王兵。
魔王兵的能力取決於它們的基因，它們可以根據環境或者需要改變自己的基因使得自己更加強大，更方便的處理問題，問題的維度與基因維度相同。
表示第i個魔王兵在進化了第t次後的基因，該個體有D位基因。
與遺傳演算法同為進化演算法的差分進化演算法，它們的操作（運算元）也都非常相似的，都是交叉，變異和選擇，流程也幾乎一樣（遺傳演算法先交叉後變異，差分進化演算法先變異後交叉）。
說到差分進化演算法中的變異，我就想到一句論語 「三人行，必有我師焉。擇其善者而從之，其不善者而改之。」 ，其實這句論語已經向我們說明了差分進化演算法的整個流程：
「三人行，必有我師焉」——變異，交叉。
「擇其善者而從之，其不善者而改之」——選擇。
差分進化演算法中，當一個魔王兵變異時，它會先找來3個小夥伴，當然是隨機找來3個小夥伴，避免同化。在一個小夥伴的基因上加上另外兩個小夥伴基因之差作為自己的目標基因。其變異公式如下：
表示第i個魔王兵找到了編號為r1、r2和r3的三個魔王兵，當然了i、r1、r2、r3為互不相同的整數，F為縮放比例因子，通常 ，一般取F=0.5。 為第i個魔王兵交叉後的目標基因圖紙，不過這是個半成品，再經過交叉後，目標基因圖紙才算完成。
其實現在我們已經有了5個基因圖紙了 ，接下來將進行交叉操作。由於變異操作，差分進化演算法的種群中個體數至少為4，即魔王軍中至少有4個小兵。
交叉操作中，魔王兵i會將目標基因圖紙 進行加工得到 ，加工過程如下：
其中 。 為交叉概率，其值越大，發生交叉的概率越大，一般取 。 為{1,2,…,D}中的隨機整數，其作用是保證交叉操作中至少有一維基因來自變異操作產生的基因，不能讓交叉操作的努力白費。
從公式上可以看出交叉操作實際上是從變異操作得出的基因圖紙上選擇至少一位基因來替換自己的等位基因，得到最終的基因圖紙。
選擇操作相對簡單，魔王兵i拿到了最終的基因圖紙 ，大喊一聲，進化吧，魔王兵i的基因改變了。它拿出了能力測量器fitness function,如果發現自己變強了，那麼就將基因 保留到下一代，否則它選擇放棄進化，讓自己還原成 。
實驗又來啦，還是那個實驗 ，簡單、易算、好畫圖。
實驗1 ：參數如下
圖中可以看出在第20代時，群體已經非常集中了，在來看看最終得出的結果。
這結果真是好到令人發指，惡魔在心中低語「把其他的優化演算法都丟掉吧」。不過別往心裡去，任何演算法都有優缺點，天下沒有免費的午餐，要想獲得某種能力必須付出至少相應的代價。
實驗2：
將交叉率CR設為0,即每次交叉只選擇保留一位變異基因。
看看了看圖，感覺跟實驗1中相比沒有什麼變化，那我們再來看看結果。
結果總體來說比實驗1好了一個數量級。為什麼呢？個人感覺應該是每次只改變一位基因的局部搜索能力比改變多位基因更強。下面我們將交叉率CR設為1來看看是否是這樣。
實驗3：
將交叉率CR設為1,即每次交叉只選擇保留一位原有基因。
實驗3的圖與實驗1和實驗2相比好像也沒什麼差別,只是收斂速度好像快了那麼一點點。再來看看結果。
發現結果比實驗2的結果還要好？那說明了實驗2我得出的結論是可能是錯誤的，交叉率在該問題上對差分進化演算法的影響不大，它們結果的差異可能只是運氣的差異，畢竟是概率演算法。
實驗4：
將變異放縮因子設為0，即變異只與一個個體有關。
收斂速度依然很快，不過怎麼感覺結果不對，而且個體收斂的路徑好像遺傳演算法，當F=0，時，差分進化演算法退化為了沒有變異、選擇操作的遺傳演算法，結果一定不會太好。
果然如此。下面我們再看看F=2時的實驗。
實驗5：
將變異放縮因子設為2。
實驗5的圖可以明顯看出，群體的收斂速度要慢了許多，到第50代時，種群還未完全收斂於一點，那麼在50代時其結果也不會很好，畢竟演算法還未收斂就停止進化了。
結果不算很好但也算相對穩定。
通過上面5個實驗，我們大致了解了差分進化演算法的兩個參數的作用。
交叉率CR，影響基因取自變異基因的比例，由於至少要保留一位自己的基因和變異的基因導致CR在該問題上對演算法性能的影響不大（這個問題比較簡單，維度較低，影響不大）。
變異放縮因子F，影響群體的收斂速度，F越大收斂速度越慢，F絕對值越小收斂速度越快，當F=0是群體之間只會交換基因，不會變異基因。
差分進化演算法大魔王已經如此強大了，那麼還有什麼可以改進的呢？當然有下面一一道來。
方案1 .將3人行修改為5人行，以及推廣到2n+1人行。
實驗6：
將3人行修改為5人行，變異公式如下：
五人行的實驗圖看起來好像與之前並沒有太大的變化，我們再來看看結果。
結果沒有明顯提升，反而感覺比之前的結果差了。反思一下五人行的優缺點，優點，取值范圍更大，缺點，情況太多，減慢搜索速度。
可以看出演算法的收斂速度比之前的變慢了一點，再看看結果。
比之前差。
差分進化演算法的學習在此也告一段落。差分進化演算法很強大，也很簡單、簡潔，演算法的描述都充滿了美感，不愧是大魔王。不過這里並不是結束，這只是個開始，終將找到打敗大魔王的方法，讓新的魔王誕生。
由於差分進化演算法足夠強，而文中實驗的問題較為簡單導致演算法的改進甚至越改越差（其實我也不知道改的如何，需要大量實驗驗證）。在遙遠的將來，也會有更加復雜的問題來檢驗魔王的能力，總之，後會無期。
以下指標純屬個人yy,僅供參考
目錄
上一篇 優化演算法筆記（六）遺傳演算法
下一篇 優化演算法筆記（八）人工蜂群演算法
優化演算法matlab實現（七）差分進化演算法matlab實現
⑹ 優化演算法筆記（十四）水波演算法
（以下描述，均不是學術用語，僅供大家快樂的閱讀）
水波演算法（Water wave optimization）是根據水波理論提出的優化演算法。什麼是水波理論？簡單來說就是水波的寬度越小，其頻率越高，頻率與水波寬度的平方根成反比（具體細節我也不懂，物理方面的）。水波演算法也算是一種受物理現象（理論）啟發而提出的演算法，提出時間並不長，還有大量的研究和應用可以深入進行。
在水波演算法中，水波有三種形式來對空間進行搜索。1.傳播，2.折射，3.碎浪。傳播即水波向周圍擴散開來，折射是水波的高度趨近與0時改變了傳播的方向（我是真的理解不能，光可以折射，水也能折射的咯？），碎浪即水波的高度較高時，水波破碎形成浪花。可以看出水波的傳播是貫穿整個演算法流程的，而折射只會發生在水波高度減少至0時，碎浪則發生在水波過高時。
（強行解釋最為致命，作者開心就好）。
將每一個水波想像成一個獨立的個體，那麼每個水波將擁有3個屬性：位置X，波長 以及波高h。
在每一次迭代過程中，每個水波都會通過傳播的形式來對空間進行搜索同時水波的高度h會減少1。其位置更新公式如下：
其中 為該水波的波長， 為當前搜索空間的上下界。 的值會隨著迭代的進行而改變：
其中 為波長的衰減系數， 為一個較小的數以保證分母不為0。
每次傳播後，如果當前的水波優於傳播前的水波，則傳播到該位置，否則波浪的高度h會減少1，即：
上式中適應度函數值越大，表明位置越優。
在一個水波進行傳播之後，該水波有可能進行折射。每次傳播，水波的高度h會減少1，當h減少到0時，該水波將發生折射，同時其高度和波長也會改變，折射及高度波長改變公式如下：
折射後的位置正態分布在以當前水波和最優水波中點為均值，當前水波與最優水波距離為方差的位置。
在折射後水波的高度將會重新初始化為最大高度：
折射後， 會重新計算該水波的波長 ：
在水波進行傳播之後，到達了一個優於當前最優水波的位置，則該水波將會進行碎浪，並將當前最優水波傳播到碎浪產生的位置。
碎浪位置的產生公式如下：
k為一個隨機數，每次碎浪將會隨機選擇k個維度來進行改變。 為一個常數。如果碎浪得到的結果優於當前最優水波，則改變當前最優水波到碎浪的位置。
是不是感覺流程圖有點復雜，其實演算法沒有那麼復雜，整個過程一共只有三個操作，一個水波在一代中最多隻會執行兩種方式。每個水波可能的搜索方式有三種：1.傳播，2.先傳播後碎浪，3.先傳播後折射。
適應度函數
由於水波演算法收斂較慢，所以最大迭代次數使用100。
實驗一 ：
從圖像中可以看出，個體在向著中心不斷的收斂，其收斂速度不算很快。其結果也相對穩定。
從圖像可以推測出，水波演算法的核心參數其實是水波的最大高度，水波的最大高度決定了演算法的收斂速度和精度，就像人工蜂群演算法中的蜜源最大開采次數一樣。若一個個體連續多代沒有找到優於當前的位置，它將改變自己的策略。
從演算法的具體實現可以看出，傳播是一個在自身周圍的全局搜索的過程，折射則屬於一個大概率局部搜索，小概率跳出局部最優的操作，而碎浪則是進一步的局部搜索。那麼水波的最大高度越高，則水波演算法的全局搜索能力越強，但收斂速度越慢，反正，演算法的收斂速度越快。
實驗二 ：減少演算法的水波最大高度至5
從圖像可以看出演算法的收斂速度明顯比實驗一要快，在第30代時已經快收斂於一個點了。從結果來看，實驗二的結果也優於實驗一，由於水波的最大高度較小，演算法進行碎浪和折射的次數增加了，即演算法的局部搜索能力增強了。
同樣之前的演算法中也提到過多次，收斂速度越快，群體越容易聚集到同一個區域，演算法也越容易陷入局部最優，而適應度函數對優化演算法來說是一個黑盒函數，無法得知其復雜程度。所以對於實驗所使用的較為簡單的測試函數，水波的最大高度越小，結果的精度越高，而面對未知的問題時，應該選取較大的水波高度以避免陷入局部最優。同樣物極必反，水波的最大高度過大可能會使演算法的局部搜索較弱，我們可以選取一個動態的水波最大高度。
實驗三 ：水波最大高度隨迭代次數增加由12遞減至2
看圖像和結果感覺和實驗一差別不大，唯一的區別就是最優值要好於實驗一。在這個簡單的測試函數中無法表現出其應有的特點，由於演算法後期群體已經較為集中，也無法明顯的看出演算法的收斂速度是否隨著迭代次數增加而加快。
水波演算法也是一個新興演算法，演算法的流程較為復雜且可修改參數較多。演算法的流程和思想與蜂群演算法有點類似，但水波演算法更為復雜。水波演算法的三個搜索策略，傳播是一個全局搜索行為，也有一定的跳出局部最優能力；折射則是一個局部搜索過程，由於正態分布的原因，有較小的概率產生跳出局部最優的操作；碎浪則是一個更進一步的局部搜索，只在最優位置附近搜索。
其搜索策略使演算法在整個流程中都擁有全局搜索和局部搜索能力，全局搜索與局部搜索之間的平衡由水波的最大高度決定，最大高度約大，全局搜索能力越強，收斂速度越慢，反之，局部搜索能力越強，收斂速度越快。
以下指標純屬個人yy,僅供參考
參考文獻
Zheng, Yu-Jun. Water wave optimization: A new nature-inspired metaheuristic[J]. Computers & Operations Research, 2015, 55:1-11. 提取碼：fo70
目錄
上一篇 優化演算法筆記（十三）鯨魚演算法
下一篇 優化演算法筆記（十五）蝙蝠演算法
優化演算法matlab實現（十四）水波演算法matlab實現
⑺ PSO優化方向
1. PSO收斂快，特別是在演算法的早期，但存在著精度較低，易發散等缺點。加速系數、最大速度等參數太大，粒子可能錯過最優解--------------->不收斂； 收斂的情況下，由於所有粒子都向最優的方向飛去，所有粒子趨向同一化（失去多樣性）--------->使得 後期收斂速度明顯變慢，搜索能力變弱 ，同時演算法收斂到一定精度時，無法繼續優化。
2. 缺乏數學理論支持，PSO演算法本質上是一種隨機搜索演算法，因此可靠性上讓人存疑；
3. 尋找一種好的拓撲結構，加強PSO演算法的泛化能力；
4. 平衡全局搜索和局部搜索能力；
（1）粒子群初始化：粒子群初始化對演算法性能有一定的影響，分為粒子位置初始化和速度初始化。
粒子群 位置 初始化的理想效果：初始種群盡可能 均勻覆蓋整個 搜索空間。
一、不推薦的初始化 ：a. 均勻分布隨機數
缺點：1. 對搜索空間的覆蓋不夠好；
2. 當維度D增大時候，所有的粒子都傾向於靠近搜索空間的邊緣：
b. 偽隨機數初始化：造成粒子在參數空間的不均勻分布和聚集效應；
二、推薦的初始化 ：a. 基於centroidal voronoi tessellations (CVTs)的種群初始化方法（這東西是啥沒搞懂）；
b. 採用正交設計方法對種群進行初始化；
c. 類隨機采樣方法中的sobol序列：使得粒子群在參數空間更加均勻；
d. Hammersley方法：感覺這個類似於類隨機采樣方法（具體我也沒搞清楚）；
e. 將粒子建立為帶電（positive charged）的模型，通過建立一個平衡方程，求解該方程的最小解獲得粒子初始化位置；
f. 設置偏向的隨機分布（推薦） ：即：我們通過對評價函數等一系列先驗信息進行分析，得出最優解的可能存在空間范圍，然後在這些范圍內，著重撒點。就算再不濟，也可以根據評價函數遵循Nearer is Better class（最優解更加可能在搜索空間的中心位置准則），在搜索空間的中心位置著重撒點。比如：
粒子群 速度 初始化：主要有如下五種方式：（根據實驗表明，One-rand的效果最好。喂！！！這里One-rand的表達式是不是寫錯了啊？）
（2）領域拓撲：粒子的拓撲，決定了粒子所接受到的信息來源。
一、全局模型gbest：最早的粒子群優化版本是全局PSO，使用全局拓撲結構，社會 只能 通過種群中， 最優的那個粒子 ，對每個粒子施加影響。
1. 優點：具有較快的收斂速度。
2. 缺點：粒子間的交流不夠充分，但更容易陷入局部極值。
二、局部模型lbest：採用每個粒子僅在一定的鄰域內進行信息交換，，粒子之間的交流相對比較緩慢。
1. 優點：粒子更容易搜索問題空間中的不同地區。
2. 缺點：信息傳遞緩慢，設計相對復雜。
3. 分類：被動模型：微觀領域、宏觀領域、維度劃分；主動模型。
（1）微觀鄰域：細分到每個粒子。空間鄰域(spatial neighborhood)、性能空間(performance space)鄰域、社會關系鄰域(sociometric neighborhood)。
a. 空間鄰域：直接在搜索空間按粒子間的距離(如歐式距離)進行劃分。在搜索初始階段，將鄰域定義為每個粒子自身；隨著迭代次數的增加，將鄰域范圍逐漸擴展到整個種群。
b. 性能空間領域：根據性能指標(如適應度、目標函數值)劃分的鄰域，如：適應度距離比值(fitness-distance-ratio)來選擇粒子的相鄰粒子。
c. 社會關系鄰域： 按粒子存儲陣列的索引編號進行劃分，主要有：環形拓撲(ring or circle topology)、輪形拓撲(wheel topology)或星形拓撲(star topology)、塔形拓撲(pyramid topology)、馮－諾以曼拓撲(Von Neumann topology)以及隨機拓撲(random topology)等。（隨機拓撲往往對大多數問題能表現出較好的性能，其次是馮－諾以曼拓撲。）
（2）宏觀鄰域：對群體進行劃分。比如：使用簇分析將整個粒子群劃分為多個簇，然後用簇中心代替帶收縮因子PSO中的粒子歷史最佳位置或群體歷史最佳位置；根據粒子相似性動態地將粒子群體按種類劃分為多個子種群，再以每個子種群的最佳個體作為每個粒子的鄰域最佳位置；劃分一個主群體，多個仆群體，仆群體進行獨立的搜索，主群體在仆群體提供的最佳位置基礎上開展搜索；每間隔一定代數將整個群體隨機地重新劃分；每個粒子除了自身和鄰域最佳歷史位置外，還學習鄰域內其他粒子的 成功經驗（只學好的，不學壞的） 等等；
（3）維度劃分：想法源自於：搜索空間維數較高時往往容易遭受「維數災」的困擾。假設粒子群的整體維度為D，則可以將D劃分成不同的部分，比如劃分成k份，使用不同的群體，分別優化不同的維度。
（4）主動模型：主動改變粒子鄰域空間，避免碰撞和擁擠。比如：將粒子分為帶電粒子和自然粒子，帶電粒子接近會產生排斥；為每個粒子引入與鄰近粒子距離成反比的自組織危險度，距離越近危險度越高，當危險度達到一定閾值，對粒子進行重新初始化，或者彈開；為粒子賦一個半徑，以檢測兩個粒子是否會發生碰撞，並且採取碰撞-彈開方式將其分離。
（3）參數選擇：三種參數：慣性權重或收斂因子、最大速度、兩個加速因子。
一、慣性權重：
a. 慣性權重大：加強PSO 全局 搜索能力；慣性權重小：加強PSO 局部 搜索能力；
b. 矛盾點：初始慣性權重大，局部搜索能力差，可能錯過最優點；後期，慣性權重小，全局搜索能力不行，導致整個粒子群就陷入局部最優解。
c. 優化方向：在適當的時候降低權重w，平衡全局和局部搜索能力；
d. 優化建議：w隨著更新代數的增加從0.9線性遞減到0.4；
二、壓縮因子：
a. 優勢：慣性常數方法通常採用慣性權值隨更新代數增加而遞減的策略，演算法後期由於慣性權值過小，會失去探索新區域的能力，而收縮因子方法則不存在此不足
b. 優化建議：通常φ取4.1，χ得0.729。
三、最大速度的選擇：為了抑制粒子更新的無規律的跳動，速度往往被限制在[-Vm,Vm]
a. Vm增大，有利於全局 探索（exploration） ，但可能越過全局最優解；Vm減小，有利於局部 開發（exploitation） ，但可能陷入局部最優；
b. 優化建議：一般設定為問題空間的10%~20%；或者動態調整Vm，比如：根據群體最佳適應和最差適應來進行調整；
四、兩個加速常數：加速常數C1和C2分別用於控制粒子指向自身或鄰域最佳位置的運動。
a. C1增大，粒子全局搜索能力好；C2增大，粒子向著最優靠攏局部能力好，但粒子會過早收斂；
b. 優化建議：C1 = C2 = 2.0，並且C1+C2 <= 4.0;或者根據自適應調整，比如隨著迭代次數增加，減小C1增大C2；
（4）混合法：PSO與其他方法結合。
這點我覺得，主要根據個人的學習積累來操作。考慮方向：增加粒子群的局部搜索能力。
⑻ 有人知道影響自適應LMS演算法收斂性、收斂速度、失調量的因素么
一種具有雙瞬變因子的LMS自適應濾波演算法�
曾召華 劉貴忠 馬社祥
（西安交通大學信息與通信工程研究所 西安710049）
【摘要】 作者在文獻〔4〕中提出了一種改進的瞬變步長SPLMS自適應濾波演算法。本文在SPLMS演算法的基礎上，進一步提出一種基於瞬變步長、瞬變平滑因子的雙瞬變SPLMS演算法—DSPLMS演算法。該演算法除具有常規LMS演算法簡單的優點外，還具有更高的起始收斂速率、更小的權失調雜訊和更大的抑噪能力。文中重點討論瞬變步長、瞬變平滑因子的變化特性。計算機模擬結果支持了理論分析。
【關鍵詞】 自適應濾波器，失調雜訊，收斂速度，最小均方誤差，瞬變因子
1 引言
自適應濾波器及其相應演算法是多年來人們廣泛研究的課題。基於Widrow－Hoff標準的LMS演算法和其相應的自適應濾波器以其演算法和結構簡單，便於實時信號處理等優點，在不同領域得到了最為廣泛的應用。而為克服常規的固定步長LMS或牛頓LMS（Newton LMS，即NLMS）自適應演算法在收斂速率、跟蹤速率與權失調雜訊之間要求上存在的較大矛盾，人們發展了各種各樣的改進型LMS演算法，如基於瞬變步長LMS自適應濾波演算法〔1～6〕、基於正交變換（DCT、FFT、小波變換、子帶濾波）的新型LMS均衡演算法〔7～8〕。基於模糊判斷的自適應LMS系統識別和基於最小四次均方誤差的LMS自適應平穩收斂演算法〔9～10〕。在所有改進型LMS演算法中，瞬變步長LMS自適應濾波演算法是研究最為廣泛的一類LMS自適應濾波演算法。本文演算法也是基於瞬變因子的一種改進LMS自適應濾波演算法。
2 SPLMS演算法分析及問題的提出
在文獻〔4〕中，作者對上述方案進行了大量的計算機模擬和理論分析，結果表明：（1）上述諸種演算法的收斂速率與系統輸入信噪比SNR直接相關，信噪比SNR越高，它們的收斂速率普遍提高；隨著信噪比SNR的降低，它們的收斂速率減慢，甚至出現發散現象，因此它們必須在弱干擾下完成規一化起動，即在起始過程中雜訊要相當小，否則效果不佳。（2）在上述所有演算法中，由於採用瞬時平方誤差性能函數e2k來代替均方誤差性能函數，所以其演算法的權值收斂過程表現為加權矢量的平均值變化規律和由於雜訊引起的隨機起伏項的疊加。因此，雜訊方差越大，則隨機起伏項越大，表現為權值振動也就越大。（3）為了追求更快的收斂性，往往增大μ和M，但濾波器階數越高，步長因子μ和輸入功率越大，就便得失調系數也越大。在有限次數起動迭代過程中，也就很難收斂到較穩態值，所以必須尋求更佳的瞬態步長演算法。
文獻〔4〕在准最小均方（Pseudo－LMS，即PLMS）誤差演算法基礎上通過採用滑動時間窗，減少PLMS演算法起動過程的計算量；同時在權值迭代中加一平滑迭代而使PLMS演算法具備全局較強的抗噪性能，較快速收斂性能而提出了SPLMS演算法，即：
其中rk為M階濾波器輸入信號的功率估值；Wk為濾波器的第k步M維最優權矢量估值；Xk是濾波器輸入信號的M維輸入數據矢量；dk為希望輸出；μk為濾波器第k步瞬態步長。切換條件中，閾值μ類似於LMS演算法的步長因子μL，滿足：
μL＜μ＜1／trR，R＝E〔XkXTk〕（7）
為待定的演算法常數，是μk變化的動態平衡點。而α是一常數為平滑因子，它決定上一次的權值變化對本次權值更新的影響程度。k0是採用式（2）規一化啟動後，演算法收斂到較穩態時的步數。式（4）是μk下降的遞推演算法，式（5）是μk上升的平滑遞推演算法。λ為上升的速度因子，滿足0＜λ＜1。在實際應用中，考慮到學習過程的啟動速度，一般取較大的λ值，即：
0．9＜λ＜1，k0＝25～35，｜α｜＜0．3（8）
SPLMS演算法的實質是：在開始k0步中，採用啟動速度較快的MLMS（Mend LMS）演算法收斂到相對較穩態的狀態；然後在k≥k0＋1過程中，採用瞬態步長μk來訓練演算法。而μk根據不同的切換條件將圍繞μ作升降變化，其迭代計算主要表現為不降即升的動態過程。α主要根據經驗來取值，輸入數據的非平穩性越大，雜訊方差越大時，增大α可明顯抑制振動，從而加速收斂過程；在雜訊小時減小α。
但SPLMS演算法也有一明顯不足，即α主要根據經驗來取值，沒有理論上的確切依據。α取值不當，反而容易造成演算法收斂性能更差，甚至發散的現象。從理論上分析，α與瞬態步長μk和輸出誤差ek（文中定義為：ek＝dk－WTk Xk）應有一定關系。在演算法啟動階段，ek較大，為追求啟動速度而常取較大步長μk，但μk越大，權失調系數也就越大，有時反而起不到應有的作用，這時就應相應增加α值來平滑權失調雜訊；在演算法漸趨穩定，步長μk漸趨於常數，ek漸趨於0，此時α也應漸趨於0。綜合起來就是：α應隨步長μk和誤差ek瞬時變化而變化，也應是一瞬變因子。本文重點就是尋求瞬變因子αk的數學表達式以滿足上述分析的要求。
3 改進的雙瞬變因子SPLMS演算法——DSPLMS演算法
3．1 μk的變化特性
從式（4）和式（5）可以看出，在k≥k0＋1過程中，μk根據不同的切換條件將圍繞μ作升降變化，μk的迭 代計算主要表現為不降即升的動態過程。對於式（5），設k≥kr時，μk＜μ，則在k≥kr＞k0＋1的上升過程中：
即上升速度按指數衰減，使趨於平衡點μ的上升速度迅速減小。其變化過程類似於一電阻電容串聯電路上電容的充電過程。對式（4），由於μk＝μk－1／（1＋Rk），Rk＞0，即使很小的Rk經過一步迭代就足以使μk＜μ，再次切換到上升過程。當rk較大時，下降形成的負脈沖也較大。
綜上所述，在k≥k0＋1的收斂過程中，μk的時變特性等價於幅值極不對稱的隨機正負尖脈沖序列組成的瞬態分量和直流分量μ的線性疊加。瞬態分量的負脈沖強度與rk瞬值對應，有利於抑制局部自激或短暫發散，減小權矢量雜訊，提高穩定度。在rk較小、演算法漸趨於穩定時，瞬變分量趨於0，μk～μ。
3．2 αk的變化特性
定義：ΔWk＝Wk＋1－Wk為自適應濾波器的權系數增量；ξ為均方誤差性能函數，ξ＝E〔ek〕2，ek＝dk－WTk Xk為輸出誤差，則SPLMS演算法的權系數更新公式由式（1）可重寫為：
Wk＋1＝Wk－μk�＾Wξk＋αΔWk－1（10）
其中�Wξ為ξ的梯度函數，＾W為�Wξ的第k步估計。由式（10）的系數更新公式，我們可寫出均方誤差性能函數的表達式：
式中上標T表示矢量的轉置。若用一矢量�＾Wζk＋1去左乘式（10），則可得到：
＾Wξk＋1Wk＋1＝�＾Wζk＋1Wk－μk�＾Wζk＋1�＾Wζk＋�＾Wζk＋1αΔWk－1（13）
利用式（12）的結論，可將式（13）化簡為：
�＾TWζk＋1ΔWk＝0（14）
由於參量μk和α均為實的標量因子，故式（14）又可寫成：
（μk�＾TWζk＋1）（αΔWk）＝0（15）
式（15）清楚地表明：在SPLMS演算法中，自適應濾波器的權系數在迭代過程中，其均方誤差性能函數的梯度估值與權系數增量始終存在一個正交關系。ΔWk－1對ΔWk的調節作用是在當前梯度估值方向上，給出與梯度估值方向正交矢量，並以這兩個矢量所構成的合矢量來改變權系數空間的權重。
對於FIR結構的LMS自適應系統而言，其均方誤差性能函數在平穩輸入時為一個二次型函數，在收斂點附近仍可視為一個二次型函數，故有：
ξ（Wk＋1）＝WTk RWk－2WTk P＋C（16）
式中R＝E〔XTk Xk〕為輸入信號的自相關矩陣，P＝E〔dkXk〕為所需信號與輸入信號的互相關矢量，C＝E〔d2k〕，則由式（16）可得：
將式（17）代入式（18），則式（18）可變形為：
式（19）就是本文給出的瞬變平滑因子αk的數學表達式。顯然，它滿足前面分析時所提出的要求，且在演算法達到穩態收斂時，滿足：
limk→∞αk＝0（20）
3．3 改進的雙瞬變SPLMS演算法——DSPLMS演算法
用式（19）中αk的表達式替換式（1）中的α，就得到本文提出的具有雙瞬變因子的LMS演算法——DSPLMS演算法，即
Wk＋1＝Wk＋2μk（dk－WTk Xk）Xk＋αk（Wk－Wk－1）（21）
μk＝λ／（1＋2λrk），0≤k≤k0（22）
由式（19）、（20）可知，αk是一個與μk成正比且具有衰減性的瞬變因子，從而使本文提出的DSPLMS演算法比SPLMS演算法更能快速穩定收斂；與常規LMS演算法相比，其性能有極大的提高，為實時信號處理提供了一個較好的演算法。
4 計算機模擬
模擬實驗的結構如圖1所示，其中dk為隨機輸入信號，nk為高斯白雜訊，ek為輸出誤差，xk為自適應濾波器的輸入，yk為濾波器輸出，此時xk＝dk＋nk。
在圖2中，dk是均值為0、方差為1的高斯白雜訊；nk是與dk不相關的均值為0、方差為1的高斯白雜訊；濾波器參數：M＝32，λ＝0．9，μL＝0．005，μ＝0．01，α＝0．1。在圖3中，nk為均值為0、方差為0．1的高斯白雜訊，其它參數同圖2。圖2、3為分別採用LMS、SPLMS和DSPLMS演算法進行濾波的學習曲線比較圖。
從圖2（強干擾啟動）和圖3（較弱干擾啟動）中可以看出：在強干擾下，DSPL MS 具有比SPLMS好、比LMS好得多的啟動速度和收斂速度；而在弱干擾下，DSPLMS仍具有比SPLMS快、比LMS快得多的啟動速度。從圖中同時還可看出：DSPLMS與SPLM S具有幾乎相同的收斂速度，它們的收斂速度比LMS快得多。
5 結語
加進瞬變平滑項的規一化起動，使DSPLMS具有更高的起始收斂速度、更小的權失調雜訊和更大的抑噪能力；在平穩連接之後的穩態過程中，該演算法趨於步長為μ的LMS演算法性能，但由於瞬變分量負脈沖的作用，在相近的權失調量下可按式（7）取較大的μ值，增強演算法對時變參數過程的跟蹤處理能力；輸入數據的非平穩性越大，雜訊方差越大時，加進的瞬變平滑項使權失調雜訊減小，從而使本文提出的DSPLMS演算法比SPLMS演算法更能快速穩定地收斂；與常規LMS演算法相比，其性能有極大的提高，可以明顯抑制振動，從而加速收斂過程。
網址：http://www.bjx.com.cn/files/WX/XDLD/2000-1/14.htm