局部最優演算法

❶ 怎樣解決遺傳演算法的局部最優問題

這個看看遺傳演算法的專著吧。
局部收斂，就是所謂的「早熟現象」是遺傳演算法的一個很讓人頭疼的問題。對應的措施，我舉個例子，可以是提高變異運算元的變異概率。變異運算元是跳出局部收斂的重要操作運算元，當然，遺傳演算法有很多的改進類型。這里不多說了，我介紹本書，叫《MATLAB遺傳演算法工具箱及應用》，雷英傑，西安電子科技大學出版社

❷ matlab全局優化與局部優化

在實際的工作和生活過程中，優化問題無處不在，比如資源如何分配效益最高，擬合問題，最小最大值問題等等。優化問題一般分為尺核局部最優和全局最優，局部最優，就是在函數值空間的一個有限區域內尋找最小值；而全局最優，是在函數值空間整個區域尋找最小值問題。

matlab中的提供的傳統優化工具箱（Optimization Tool），能實現局部最優，但要得全局最優，則要用全局最優化演算法（Global Optimization Tool），主要包括：
GlobalSearch 全局搜索和 MultiStart 多起點方法產生若干起始點，然後它們用局部求解器去找到起始點吸引盆處的最優點。

ga 遺傳演算法用一組起始點（稱為種群），通過迭代從種群中產生更好的點，只要初始種群覆蓋幾個盆，GA就能檢查幾個盆。

simulannealbnd 模擬退火完成一個隨機搜索，通常，模擬退火演算法接受一個點，只要這個點比前面那個好，它也偶而接受一個比較糟的點，目的是轉向不同的盆。

patternsearch 模式搜索演算法在接受一個點之前要看看其附近的一組點。假如附近的某些點屬於不同的盆，模式搜索演算法本質上時同時搜索若干個盆。

下面我就一些具體例子，來說明各種優化方法：

可以看出，初值x0不同，得到的結果侍孫截然不同，這說明這種求解器，能尋找局部最優，但不一定是全局最優，在起點為8時，取得全局最優。
我們換一種求解器：fminbound,這種求解器不需要給點初值。

因此全局最優的方法能夠獲取全局最優。

結果：最小二乘擬合結果誤差較大

可以陵談掘看出全局優化結果較好，誤差較小。
這種演算法的運行時間：Elapsed time is 6.139324 seconds.
使用並行計算的方式解決

結果：14 out of 100 local solver runs converged with a positive local solver exit flag.
Elapsed time is 4.358762 seconds.Sending a stop signal to all the labs ... stopped.可以看出，運行時間減少，提高了效率。

這種方法只能尋找局部最優。
現在用全局優化演算法：

❸ 請大神解釋一下在醫學圖像配准中，什麼叫做局部優化演算法，什麼叫做全局優化演算法

演算法GA把問題的解表示成「染色體」，在演算法中也即是以二進制編碼的串。並且，在執行遺傳演算法之前，給出一群「染色體」，也即是假設解。然後，把這些假設解置於問題的「環境」中，並按適者生存的原則，從中選擇出較適應環境的「染色體」進行復制，再通過交叉，變異過程產生更適應環境的新一代「染色體」群。這樣，一代一代地進化，最後就會收斂到最適應環境的一個「染色體」上，它就是問題的最優解。
一、遺傳演算法的目的
典型的遺傳演算法CGA(Canonical Genetic Algorithm)通常用於解決下面這一類的靜態最優化問題：
考慮對於一群長度為L的二進制編碼bi，i＝1，2，…，n；有
bi∈{0,1}L (3-84)
給定目標函數f，有f(bi)，並且
0<f(bi)<∞
同時
f(bi)≠f(bi+1)
求滿足下式
max{f(bi)|bi∈{0,1}L} (3-85)
的bi。
很明顯，遺傳演算法是一種最優化方法，它通過進化和遺傳機理，從給出的原始解群中，不斷進化產生新的解，最後收斂到一個特定的串bi處，即求出最優解。
二、遺傳演算法的基本原理
長度為L的n個二進制串bi(i＝1，2，…，n)組成了遺傳演算法的初解群，也稱為初始群體。在每個串中，每個二進制位就是個體染色體的基因。根據進化術語，對群體執行的操作有三種：
1．選擇(Selection)
這是從群體中選擇出較適應環境的個體。這些選中的個體用於繁殖下一代。故有時也稱這一操作為再生(Reproction)。由於在選擇用於繁殖下一代的個體時，是根據個體對環境的適應度而決定其繁殖量的，故而有時也稱為非均勻再生(differential reproction)。
2．交叉(Crossover)
這是在選中用於繁殖下一代的個體中，對兩個不同的個體的相同位置的基因進行交換，從而產生新的個體。
3．變異(Mutation)
這是在選中的個體中，對個體中的某些基因執行異向轉化。在串bi中，如果某位基因為1，產生變異時就是把它變成0；反亦反之。
遺傳演算法的原理可以簡要給出如下：
choose an intial population
determine the fitness of each indivial
perform selection
repeat
perform crossover
perform mutation
determine the fitness of each indivial
perform selection
until some stopping criterion applies
這里所指的某種結束准則一般是指個體的適應度達到給定的閥值；或者個體的適應度的變化率為零。
三、遺傳演算法的步驟和意義
1．初始化
選擇一個群體，即選擇一個串或個體的集合bi，i=1，2，...n。這個初始的群體也就是問題假設解的集合。一般取n＝30-160。
通常以隨機方法產生串或個體的集合bi,i＝1，2，...n。問題的最優解將通過這些初始假設解進化而求出。
2．選擇
根據適者生存原則選擇下一代的個體。在選擇時，以適應度為選擇原則。適應度准則體現了適者生存，不適應者淘汰的自然法則。
給出目標函數f，則f(bi)稱為個體bi的適應度。以

(3-86)
為選中bi為下一代個體的次數。
顯然．從式(3—86)可知：
(1)適應度較高的個體，繁殖下一代的數目較多。
(2)適應度較小的個體，繁殖下一代的數目較少；甚至被淘汰。
這樣，就產生了對環境適應能力較強的後代。對於問題求解角度來講，就是選擇出和最優解較接近的中間解。
3．交叉
對於選中用於繁殖下一代的個體，隨機地選擇兩個個體的相同位置，按交叉概率P。在選中的位置實行交換。這個過程反映了隨機信息交換；目的在於產生新的基因組合，也即產生新的個體。交叉時，可實行單點交叉或多點交叉。
例如有個體
S1=100101
S2=010111
選擇它們的左邊3位進行交叉操作，則有
S1=010101
S2=100111
一般而言，交叉幌宰P。取值為0.25—0.75。
4．變異
根據生物遺傳中基因變異的原理，以變異概率Pm對某些個體的某些位執行變異。在變異時，對執行變異的串的對應位求反，即把1變為0，把0變為1。變異概率Pm與生物變異極小的情況一致，所以，Pm的取值較小，一般取0.01-0.2。
例如有個體S＝101011。
對其的第1，4位置的基因進行變異，則有
S'=001111
單靠變異不能在求解中得到好處。但是，它能保證演算法過程不會產生無法進化的單一群體。因為在所有的個體一樣時，交叉是無法產生新的個體的，這時只能靠變異產生新的個體。也就是說，變異增加了全局優化的特質。
5．全局最優收斂(Convergence to the global optimum)
當最優個體的適應度達到給定的閥值，或者最優個體的適應度和群體適應度不再上升時，則演算法的迭代過程收斂、演算法結束。否則，用經過選擇、交叉、變異所得到的新一代群體取代上一代群體，並返回到第2步即選擇操作處繼續循環執行。
圖3—7中表示了遺傳演算法的執行過程。

❹ 如何判斷螢火蟲演算法陷入局部最優

FA主要是利用螢火蟲發光的特點進行隨機優化。利用螢火蟲個體模擬解空間的可行解，目標函數值表示螢火蟲的亮度，較亮的螢火蟲會吸引其他個體向這個方向進行位置移動，他們之間的吸引力與距離成反比，如果某個螢火蟲周圍沒有更亮的個體，它選擇不移動或者隨機變換位置。兩只螢火蟲之間的吸引力計算公式如下： 貝塔0是指距離為0時的吸引力值，rij表示兩只螢火蟲之間的歐式距離，拉姆塔一般表示對光的吸收率，通常取1. 螢火蟲會飛向更亮的螢火蟲位置處，其位置更新公式為：
其中阿爾法是[0,1]之間的隨機數，另一個因子是服從均勻分布的隨機因子。 演算法流程如下 1、初始化各個參數和每隻螢火蟲的位置 2、計算每對螢火蟲之間的吸引力，選取螢火蟲移動的方向 3、更新整個種群中螢火蟲的位置，更新螢火蟲的最優位置 4、判斷是否達到終止條件，是就結束演算法，否則就返回步驟2繼續進行

❺ 優化演算法總結

本文介紹一下機器學習和深度學習中常用的優化演算法和優化器以及一些其他我知道的優化演算法,部分演算法我也沒有搞懂,就先記錄下來以後慢慢研究吧.*_*.

1.梯度下降演算法(Gradient Descent)

梯度下降法可以參考我另一篇文章 機器學習-線性回歸 里的講解,這里就不在重復敘述.這里需要強調一下,深度學習里常用的SGD,翻譯過來是隨機梯度下降,但是實質是mini-batch梯度下降(mini-batch-gd),或者說是兩者的結合更准確一些.

SGD的優點是,演算法簡單,計算量小,在函數為凸函數時可以找到全局最優解.所以是最常用的優化演算法.缺點是如果函數不是凸函數的話,很容易進入到局部最優解而無法跳出來.同時SGD在選擇學習率上也是比較困難的.

2.牛頓法

牛頓法和擬牛頓法都是求解無約束最優化問題的常用方法,其中牛頓法是迭代演算法,每一步需要求解目標函數的海森矩陣的逆矩陣,計算比較復雜.

牛頓法在求解方程根的思想:在二維情況下,迭代的尋找某一點x,尋找方法是隨機一個初始點x_0,目標函數在該點x_0的切線與x坐標軸的交點就是下一個x點,也就是x_1.不斷迭代尋找x.其中切線的斜率為目標函數在點x_0的導數(梯度),切必過點(x_0,f(x_0)).所以迭代的方程式如圖1,為了求該方程的極值點,還需要令其導數等於0,也就是又求了一次導數,所以需要用到f(x)的二階導數.

在最優化的問題中,牛頓法提供了一種求解的辦法. 假設任務是優化一個目標函數f, 求函數ff的極大極小問題, 可以轉化為求解函數f導數等於0的問題, 這樣求可以把優化問題看成方程求解問題(f的導數等於0). 剩下的問題就和牛頓法求解方程根的思想很相似了.

目標函數的泰勒展開式:

化簡後:

這樣就得到了與圖1相似的公式,這里是二維的,在多維空間上,求二階導數就是求海森矩陣,因為是分母,所以還需要求海森矩陣的逆矩陣.

牛頓法和SGD的區別:

牛頓法是二階求導,SGD是一階求導,所以牛頓法要收斂的更快一些.SGD只考慮當前情況下梯度下降最快的方向,而牛頓法不僅考慮當前梯度下降最快,還有考慮下一步下降最快的方向.

牛頓法的優點是二階求導下降速度快,但是因為是迭代演算法,每一步都需要求解海森矩陣的逆矩陣,所以計算復雜.

3.擬牛頓法(沒搞懂,待定)

考慮到牛頓法計算海森矩陣比較麻煩,所以它使用正定矩陣來代替海森矩陣的逆矩陣,從而簡化了計算過程.

常用的擬牛頓法有DFP演算法和BFGS演算法.

4.共軛梯度法(Conjugate Gradient)

共軛梯度法是介於最速下降法與牛頓法之間的一個方法,它僅需利用一階導數信息,但克服了最速下降法收斂慢的缺點,又避免了牛頓法計算海森矩陣並求逆的缺點.共軛梯度法不僅是解決大型線性方程組最有用的方法之一,也是解大型非線性最優化最有效的演算法之一.

5.拉格朗日法

參考SVM里的講解 機器學習-SVM

6.動量優化法(Momentum)

動量優化法主要是在SGD的基礎上,加入了歷史的梯度更新信息或者說是加入了速度更新.SGD雖然是很流行的優化演算法,但是其學習過程很慢,因為總是以同樣的步長沿著梯度下降的方向.所以動量是為了加速學習的方法.

其中第一行的減號部分是計算當前的梯度,第一行是根據梯度更新速度v,而α是新引進的參數,在實踐中,α的一般取值為 0.5,0.9 和 0.99.和學習率 一樣,α 也會隨著時間不斷調整.一般初始值是一個較小的值,隨後會慢慢變大.

7.Nesterov加速梯度(NAG, Nesterov accelerated gradient)

NAG是在動量優化演算法的基礎上又進行了改進.根據下圖可以看出,Nesterov 動量和標准動量之間的區別體現在梯度計算上, Nesterov 動量中,梯度計算在施加當前速度之後.因此,Nesterov 動量可以解釋為往標准動量方法中添加了一個校正因子

8.AdaGrad演算法

AdaGrad演算法,自適應優化演算法的一種,獨立地適應所有模型參數的學習率,縮放每個參數反比於其所有梯度歷史平均值總和的平方根.具有代價函數最大梯度的參數相應地有個快速下降的學習率,而具有小梯度的參數在學習率上有相對較小的下降.通俗一點的講,就是根據實際情況更改學習率,比如模型快要收斂的時候,學習率步長就會小一點,防止跳出最優解.

其中g是梯度,第一行的分母是計算累計梯度的平方根, 是為了防止分母為0加上的極小常數項,α是學習率.

Adagrad的主要優點是不需要人為的調節學習率,它可以自動調節.但是依然需要設置一個初始的全局學習率.缺點是隨著迭代次數增多,學習率會越來越小,最終會趨近於0.

9.RMSProp演算法

RMSProp修改 AdaGrad 以在非凸設定下效果更好,改變梯度積累為指數加權的移動平均.AdaGrad旨在應用於凸問題時快速收斂.

10.AdaDelta演算法

11.Adam演算法

Adam是Momentum和RMSprop的結合體,也就是帶動量的自適應優化演算法.

12.Nadam演算法

13.模擬退火演算法

14.蟻群演算法

15.遺傳演算法

動量是為了加快學習速度,而自適應是為了加快收斂速度,注意學習速度快不一定收斂速度就快,比如步長大學習速度快,但是很容易跳出極值點,在極值點附近波動,很難達到收斂.

未完待定....

參考:

《統計學習方法》  李航    著

《深度學習》  花書

❻ 優化演算法筆記（二十五）飛蛾撲火演算法

（以下描述，均不是學術用語，僅供大家快樂的閱讀）
飛蛾撲火演算法（Moth-Flame Optimization）是受飛蛾圍繞火焰飛行啟發而提出的演算法。演算法提出於2015年5月（投稿日期），雖可算作一個新演算法，不過無數研究者就像飛蛾見了火一樣，發表了如此之多的論文，驚了。
飛蛾撲火演算法中有兩種個體，飛蛾和火焰，飛蛾選擇並圍繞火焰以螺線方式飛行搜索，搜索完後，火焰將移動位置，以保持火焰是飛蛾和火焰群體中最優的位置。
演算法的流程簡單，螺線搜索在之前的鯨魚演算法中也出現過，這里會較為詳細的記錄記錄螺線搜索的具體情況。

顯然,飛蛾撲火演算法中有兩種角色,飛蛾與火焰。初始時飛蛾與火焰的數量均為N。為了方便查看，將飛蛾的位置表示為XM ，火焰的位置為 XF。
初始化時，會在解空間內初始化N個飛蛾與M(M=N)個火焰。在演算法過程中，飛蛾將會圍繞它所選擇的火焰飛行，之後將這N個飛蛾與M個火焰按優劣排序，並將M個火焰移動到較優的前M個個體的位置。其中火焰的數量M會隨著迭代次數的改變而不斷變化，論文中階梯遞減至1。
演算法的主要步驟如下：
1. 飛蛾選擇火焰（將火焰分配給飛蛾）。
2. 飛蛾圍繞火焰飛行。
3. 移動火焰到相應位置。
從步驟可以看出，演算法中飛蛾的飛行是一種無貪心演算法的操作，而火焰的移動則是一種變相的貪心操作。

初始化時，會有N個飛蛾和N個火焰（M=N）,故每隻飛蛾都可以選擇互不相同的火焰。隨著迭代次數的遞增，火焰的數量會遞減。其數量根據以下公式計算得出：

其圖像如下圖所示：

其實就是將火焰數量M線性遞減到1，由於火焰數量是正數，故圖像呈階梯狀。
隨著迭代次數增加，火焰數量遞減，每隻飛蛾無法選擇互不相同的火焰，此時可以隨機選擇火焰或者飛蛾群體按順序依次往後選取，類似於取模。兩種方式的差別不大。

該步驟是演算法的核心計算步驟。
對於飛蛾 ,它圍繞火焰 飛行後到達的新位置XM_new根據以下公式計算得出：

其圖像如下

而演算法中的飛行軌跡應該是這樣的：

取出一維看看

其中i為計算次數。

圖像就是cos函數圖像的變形。考慮到飛蛾與火焰之間的距離會越來越短，其飛行圖像應該與上圖相反，即振幅越來越小，局部搜索能力越來越強。

N只飛蛾圍繞M個火焰飛行後，會到N個新位置，計算這N個新位置的適應度值，將這N個新位置與M個火焰這（N+M）個位置按優劣排序，並將其中較優的M個位置作為下一輪中火焰的位置。

其飛蛾撲火演算法流程圖如下：

由於飛蛾撲火演算法可以說是對蟻獅演算法和鯨魚演算法的結合，這里就看看演算法的圖像，不再做其他處理了。
適應度函數 。

實驗一：

從結果看來，飛蛾撲火演算法的性能穩定也優於蟻獅演算法，從圖像看演算法收斂性不如蟻獅演算法但局部搜索性能要強於蟻獅演算法。
可見螺線的局部搜索能力還是強於隨機遊走的，不過其全局搜索要弱於隨機遊走。相比蟻獅演算法，飛蛾撲火演算法更容易陷入局部最優（其實與蟻獅差不多，只要火焰/蟻獅陷入局部最優基本完蛋，不過蟻獅數量恆定，火焰數量遞減，所有火焰更容易局部最優）。

飛蛾撲火演算法是根據飛蛾圍繞火焰飛行的行為而提出的演算法。演算法的結構比較簡單，與蟻獅演算法類似，只是搜索步驟將隨機遊走替換成了螺線搜索（當然還有跟多細節上的不同，可以看看原文）。演算法的局部搜索能力非常強，依靠螺線就提供了全局搜索和局部搜索能力，其全局搜索和局部搜索能力強弱由其極半徑決定，演算法中由b決定。不過演算法缺少跳出局部最優的能力，在平滑函數中的效果非常好，在局部最優較多的函數中效果中規中矩。

參考文獻
Mirjalili S . Moth-flame optimization algorithm: A novel nature-inspired heuristic paradigm[J]. Knowledge-Based Systems, 2015, 89(NOV.):228-249.. 提取碼：koy9
以下指標純屬個人yy,僅供參考

目錄
上一篇 優化演算法筆記（二十四）帝王蝶演算法
下一篇 優化演算法筆記（二十六）和聲搜索演算法