局部優化演算法

『壹』 什麼事演算法陷入局部最優化

一般最優化演算法只能求局部最優值，很難求出全局最優值。
許多演算法當找到局部最優點後，就不能再繼續尋找了，這叫陷入局部極值。

『貳』 如何解決貪婪演算法中的局部優化問題

基本思路
1.建立數學模型來描述問題
⒉把求解的問題分成若干個子問題。
⒊對每一子問題求解，得到子問題的局部最優解。
⒋把子問題的解局部最優解合成原來解問題的一個解。
實現該演算法的過程：
從問題的某一初始解出發；
while 能朝給定總目標前進一步 do
求出可行解的一個解元素；
由所有解元素組合成問題的一個可行解。

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

演算法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中表示了遺傳演算法的執行過程。

『肆』 怎麼判斷粒子群優化演算法有沒有局部收斂

轉載請註明：來自網路知道——小七的風
首先說，標準的粒子群演算法是通過控制權重系數ω的線性下降來使得種群收斂的，從收斂圖上看，如果在多次迭代後（比如100次迭代後）如果最優粒子的適應度值不再變化即認為此時演算法已經達到收斂。
理論上，粒子群通過自身的更新機制使得每個粒子在每次的迭代中會向該粒子的歷史最優位置以及全局粒子位置的中間（或周圍）位置靠近，這樣雖然保證了粒子搜索的高效性（假設最優點存在於全局最優點與歷史最優點的中間位置）但勢必帶來了粒子搜索范圍的減少，所以容易出現局部收斂，並且已有相關文獻證明了這不是一個全局最優的演算法。
還有一種簡單的做法是證偽，即不去直接證明粒子群是一個全局最優，而是試圖去找到一個點，這個點的適應度值比粒子群找到的全局最優點的適應度值更好，這樣就間接說明了演算法沒有找到全局最優點（可以採用純隨機，直到找到比粒子群提供的全局最優點好為止）

『伍』 為什麼em演算法容易陷入局部最優

在統計計算中，最大期望演算法是在概率模型中尋找參數最大似然估計或者最大後驗估計的演算法，其中概率模型依賴於無法觀測的隱藏變數

『陸』 傳統優化演算法和現代優化演算法包括哪些.區別是什麼

1. 傳統優化演算法一般是針對結構化的問題，有較為明確的問題和條件描述，如線性規劃，二次規劃，整數規劃，混合規劃，帶約束和不帶約束條件等，即有清晰的結構信息；而智能優化演算法一般針對的是較為普適的問題描述，普遍比較缺乏結構信息。

2. 傳統優化演算法不少都屬於凸優化范疇，有唯一明確的全局最優點；而智能優化演算法針對的絕大多數是多極值問題，如何防止陷入局部最優而盡可能找到全局最優是點贊智能優化演算法的根本原因：對於單極值問題，傳統演算法大部分時候已足夠好，而智能演算法沒有任何優勢；對多極值問題，智能優化演算法通過其有效設計可以在跳出局部最優和收斂到一個點之間有個較好的平衡，從而實現找到全局最優點，但有的時候局部最優也是可接受的，所以傳統演算法也有很大應用空間和針對特殊結構的改進可能。

3. 傳統優化演算法一般是確定性演算法，有固定的結構和參數，計算復雜度和收斂性可做理論分析；智能優化演算法大多屬於啟發性演算法，能定性分析卻難定量證明，且大多數演算法基於隨機特性，其收斂性一般是概率意義上的，實際性能不可控，往往收斂速度也比較慢，計算復雜度較高。

『柒』 吐血跪求編譯原理課設------局部優化的實現

哥們花店的把

『捌』 多目標進化演算法 怎麼判斷陷入局部最優

一般最優化演算法只能求局部最優值，很難求出全局最優值。 許多演算法當找到局部最優點後，就不能再繼續尋找了，這叫陷入局部極值。