爬山演算法和模擬退火區別

Ⅰ 遺傳演算法

根據問題的目標函數構造一個適值函數，對一個由多個解（每個解對應一個染色體）構成的種群進行評估、遺傳、選擇，經多代繁殖，獲得適應值最好的個體作為問題的最優解。

1，產生一個初始種群

2，根據問題的目標函數構造適值函數

3，根據適應值的好壞不斷選擇和繁殖

4，若干代後得到適應值最好的個體即為最優解

1.種群和種群大小

一般越大越好，但是規模越大運算時間越大，一般設為100~1000

2. 編碼方法 （基因表達方法

3. 遺傳運算元

包括交叉和變異，模擬了每一代中創造後代的繁殖過程。是遺傳演算法的精髓

交叉：性能在很大程度上取決於交叉運算的性能，交叉率Pc：各代中交叉產生的後與代數與種群中的個體數的比。Pc越高，解空間就越大，越耗時/

變異:Pm:種群中變異基因數在總基因數中的百分比。它控制著新基因導入種群的比例。太低，一些有用的基因就難以進入選擇；太高，後代就可能失去從雙親繼承下來的良好特性，也就失去了從過去中搜索的能力。

4.選擇策略

適者生存，優勝劣汰

5.停止准則

最大迭代數

初始種群的產生：隨機產生，具體依賴於編碼方法

編碼方法 ：二進制編碼法、浮點編碼法、符號編碼法。順序編碼，實數編碼，整數編碼。

適值函數 ：根據目標函數設計

遺傳運算 ： 交叉 ：單切點交叉，雙切點交叉，均勻交叉，算術交叉

變異 ：基本位變異（Simple Mutation）：對個體編碼串中以變異概率、隨機指定的某一位或某幾位僅因座上的值做變異運算。

均勻變異（Uniform Mutation）：分別用符合某一范圍內均勻分布的隨機數，以某一較小的概率來替換個體編碼串中各個基因座上的原有基因值。（特別適用於在演算法的初級運行階段）

邊界變異（Boundary Mutation）：隨機的取基因座上的兩個對應邊界基因值之一去替代原有基因值。特別適用於最優點位於或接近於可行解的邊界時的一類問題。

非均勻變異：對原有的基因值做一隨機擾動，以擾動後的結果作為變異後的新基因值。對每個基因座都以相同的概率進行變異運算之後，相當於整個解向量在解空間中作了一次輕微的變動。

高斯近似變異：進行變異操作時用符號均值為P的平均值，方差為P**2的正態分布的一個隨機數來替換原有的基因值。

選擇策略 ：1.輪盤賭選擇（Roulette Wheel Selection）：是一種回放式隨機采樣方法。每個個體進入下一代的概率等於它的適應度值與整個種群中個體適應度值和的比例。選擇誤差較大。

2.隨機競爭選擇（Stochastic Tournament）：每次按輪盤賭選擇一對個體，然後讓這兩個個體進行競爭，適應度高的被選中，如此反復，直到選滿為止。

3.最佳保留選擇：首先按輪盤賭選擇方法執行遺傳演算法的選擇操作，然後將當前群體中適應度最高的個體結構完整地復制到下一代群體中。

4.無回放隨機選擇（也叫期望值選擇Excepted Value Selection）：根據每個個體在下一代群體中的生存期望來進行隨機選擇運算。方法如下:

（1） 計算群體中每個個體在下一代群體中的生存期望數目N。

（2） 若某一個體被選中參與交叉運算，則它在下一代中的生存期望數目減去0.5，若某一個體未 被選中參與交叉運算，則它在下一代中的生存期望數目減去1.0。

（3） 隨著選擇過程的進行，若某一個體的生存期望數目小於0時，則該個體就不再有機會被選中。

5.確定式選擇：按照一種確定的方式來進行選擇操作。具體操作過程如下：

（1） 計算群體中各個個體在下一代群體中的期望生存數目N。

（2） 用N的整數部分確定各個對應個體在下一代群體中的生存數目。

（3） 用N的小數部分對個體進行降序排列，順序取前M個個體加入到下一代群體中。至此可完全確定出下一代群體中M個個體。

6.無回放余數隨機選擇：可確保適應度比平均適應度大的一些個體能夠被遺傳到下一代群體中，因而選擇誤差比較小。

7.均勻排序：對群體中的所有個體按期適應度大小進行排序，基於這個排序來分配各個個體被選中的概率。

8.最佳保存策略：當前群體中適應度最高的個體不參與交叉運算和變異運算，而是用它來代替掉本代群體中經過交叉、變異等操作後所產生的適應度最低的個體。

9.隨機聯賽選擇：每次選取幾個個體中適應度最高的一個個體遺傳到下一代群體中。

10.排擠選擇：新生成的子代將代替或排擠相似的舊父代個體，提高群體的多樣性。

之前在網上看到的一個比方，覺得很有趣：

{

既然我們把函數曲線理解成一個一個山峰和山谷組成的山脈。那麼我們可以設想所得到的每一個解就是一隻袋鼠，我們希望它們不斷的向著更高處跳去，直到跳到最高的山峰。所以求最大值的過程就轉化成一個「袋鼠跳」的過程。

下面介紹介紹「袋鼠跳」的幾種方式。

爬山演算法：一隻袋鼠朝著比現在高的地方跳去。它找到了不遠處的最高的山峰。但是這座山不一定是最高峰。這就是爬山演算法，它不能保證局部最優值就是全局最優值。

模擬退火：袋鼠喝醉了。它隨機地跳了很長時間。這期間，它可能走向高處，也可能踏入平地。但是，它漸漸清醒了並朝最高峰跳去。這就是模擬退火演算法。

遺傳演算法：有很多袋鼠，它們降落到喜瑪拉雅山脈的任意地方。這些袋鼠並不知道它們的任務是尋找珠穆朗瑪峰。但每過幾年，就在一些海拔高度較低的地方射殺一些袋鼠。於是，不斷有袋鼠死於海拔較低的地方，而越是在海拔高的袋鼠越是能活得更久，也越有機會生兒育女。就這樣經過許多年，這些袋鼠們竟然都不自覺地聚攏到了一個個的山峰上，可是在所有的袋鼠中，只有聚攏到珠穆朗瑪峰的袋鼠被帶回了美麗的澳洲。

}

（把那些總是愛走下坡路的袋鼠射殺，這就是遺傳演算法的精粹！）

遺傳演算法並不保證你能獲得問題的最優解，但是使用遺傳演算法的最大優點在於你不必去了解和操心如何去「找」最優解。（你不必去指導袋鼠向那邊跳，跳多遠。）而只要簡單的「否定」一些表現不好的個體就行了。（把那些總是愛走下坡路的袋鼠射殺，這就是遺傳演算法的精粹！）

改進與變形

編碼方法：

Ⅱ 模擬退火法^[1，]

模擬退火演算法最早在1953年由 Metropolis等人提出。在地球物理中的最早應用是Rothman在1983年利用模擬退火演算法處理地震資料的剩餘靜校正。模擬退火法也是類似於蒙特卡洛法的隨機搜索方法。但是在產生模型的過程中引入一些規則，能有效地加快搜索速度，有時又稱這類方法為啟發式蒙特卡洛法。

模擬退火法概念源於統計物理學，是模擬固體熔化狀態逐漸緩慢冷卻最終達到能量最小的結晶狀態的物理過程。對於一個熔化的金屬，當處於某個溫度的熱平衡狀態時，它的每一個分子都有它可能所處的狀態，有些分子可能能量高一些，有些分子可能能量低一些，分子處於何種狀態的概率由分子所具有的能量決定。設分子所有可能的能級總數為n(微觀粒子的能量都是量子化的，不連續的)，則分子處於某種狀態的概率滿足玻爾茲曼概率分布:

地球物理反演教程

其中:Ei為第i個分子的能量;K為玻爾茲曼常數;T為絕對溫度;n為分子所有可能的能級總數，分母稱為配分因子;p_i為第i個分子處於能量E_i的概率。

如果把地球物理反演的模型向量看作分子，把目標函數看作分子的能量，把目標函數的極小值看成分子冷卻結晶的最小能量，反演問題(最優化問題)可以模擬式(8.11)金屬退火的過程，通過緩慢地減小溫度進行反演，使目標函數(能量)逐漸達到極小值，這時所對應的模型(分子狀態)就是反演結果。

為了改善於蒙特卡洛法的隨機搜索方法，1953年 Metropolis等人在產生模型的過程中引入Metropolis接受准則，模型產生並不是完全隨機，而是以前一個模型為基礎隨機產生。對能量減小的模型完全接受，對能量增加的模型按一定的概率接受，這樣能有效地加快搜索速度，同時又有可能跳出局部極小值。具體如下:

設原來模型向量為m_i，新的模型為m_i+1(在m_i基礎上隨機修改產生)，各自的能量(目標函數)為E(m_i)和E(m_i+1)。如果E(m_i+1)＜E(m_i)，則目標函數在減小，新模型可以接受。如果E(m_i+1)＞E(m_i)，則目標函數在增加，按照一定概率來確定是否接受新的模型。具體規則見式(8.12):

E(m_i+1)＜E(m_i) 完全接受m_i+1為新模型

地球物理反演教程

式(8.12)就是Metropolis接受准則。它使得反演過程可以接受使目標函數增加的模型，因此也就使得模擬退火法有可能跳出局部極小，收斂於全局極小值點。由於玻爾茲曼常數K只是起到尺度因子的作用，在實際計算中K可取為1來簡化公式。從式(8.12)可以看出，當溫度較低時，p_i+1/p_i較小，因此接受使能量增加的新模型的可能性較小。而一般溫度較低時，目標函數較小，模型比較靠近真實模型，這時基本上只接受使目標函數減小的模型，使模型盡快收斂於極小值點。

在模擬退火反演中，要求溫度T隨著迭代次數的增加而緩慢降溫。常用的溫度函數有兩種。

(1)指數下降型:

T_k=T₀·exp(-ck^1/N) (8.13)

式中:k為迭代次數;c為衰減因子;N為模型參數的個數;T₀為初始溫度。上式也可以改寫為

地球物理反演教程

通常選擇0.7≤α≤1。在實際應用中可採用0.5或1代替式(8.14)的1/N。圖8.4(a)為指數降溫曲線。採用參數為:T₀=200℃，α=0.99，1/N=0.9。

(2)雙曲線下降型:

T=T₀α^k (8.15)

式中:T₀為初始溫度;k為迭代次數;α為衰減因子，通常取0.99。初始溫度T₀不能取得太高，否則增加計算時間浪費機時;T₀也不能太低，否則模型選取不能遍及整個模型空間，只是在初始模型附近選取，不能進行全局尋優。所以T₀的確定只有通過實驗計算得到。圖8.4(b)為雙曲線降溫曲線。採用參數為:T₀=200℃，α=0.99。從圖8.4可以看出通過對不同溫度曲線和相關參數進行選擇，可以控制溫度下降的方式和速度。

圖8.4 模擬退火法降溫曲線

模擬退火法主要有三種:

(1)MSA演算法(Metropolis Simulated Annealing);

(2)HBSA演算法(Heat Bath Simulated Annealing);

(3)VFSA演算法(Very Fast Simulated Annealing)。

圖8.5 模擬退火MSA演算法程序流程圖

前面介紹的利用 Metropolis接受准則的演算法就是經典的模擬退火法。圖8.5為模擬退火 MSA演算法的程序流程圖。從中可以看出 MSA演算法有一套模型修改准則，依次改變模型參數，每次改變都是在原來模型基礎上改變一個參數，因此容易保持已有搜索成果，持續不斷地向目標函數最小值點接近，因此搜索效率比蒙特卡洛法高。此外，MSA演算法允許接受使目標函數增加的模型，這樣又易於跳出局部極小，達到全局極小。但 MSA演算法在任何溫度下和蒙特卡洛法一樣都是在模型全空間進行搜索，不能根據當前溫度和模型減小搜索空間，此外由於模型的修改全憑運氣，所以不可能像前面介紹的最小二乘法那樣目標函數基本上持續減小，而是呈不規則振盪在宏觀上逐漸減小，因此效率較低。

HBSA演算法與 MSA演算法的不同之處是在模型的修改上。也是首先隨機選擇一個初始M維模型向量m₀(它具有M個參數);然後限制各個模型參數可能的取值范圍，對取值離散化。假設每個模型參數都有N個可能的值，首先固定模型第2個參數m₀(2)直到第M個參數m₀(M)保持不變，只修改第1個參數m₀(1);計算m₀(1)的所有取值時的目標函數，然後按式(8.16)計算「概率」，它就是式(8.11)配分因子取1的公式。即

地球物理反演教程

選擇「概率」最大的為模型第1個參數的修改值。照此依次對所有模型參數進行修改完成依次迭代計算。在每次迭代計算中保持溫度不變。隨著迭代次數增加，溫度降低，最終達到穩定狀態，獲得最小能量解。這種方法的計算由於要計算某個參數的所有可能值，所以計算量也是很大的。

1989年Ingber提出了VFSA演算法，由於速度較快，最為常用。它使得模擬退火法從理論走向了實際應用。VFSA演算法在流程上與傳統的模擬退火法相同，但是在模型修改、接受概率以及降溫曲線上有所改進。

(1)模型修改:常規模擬退火法採用高斯隨機分布修改模型，在任何溫度下都是在模型全空間進行搜索。而Ingber提出採用依賴於溫度的似cauchy分布產生新的模型。即

地球物理反演教程

y_i=Tsgn(u-0.5)[(1+1/T^|2u-1|-1](8.18)

其中:m_i為當前模型第i個參數，m'_i為修改後的模型參數;u為[0，1]的隨機數;[A_i，B_i]為m_i和m'_i的取值范圍;sgn( )為符號函數。

採用以上方式能在高溫下進行大范圍的搜索，低溫時在當前模型附近搜索，而且由於似cauchy分布具有平坦的「尾巴」，使其易於迅速跳出局部極值。這一改進大大加快了模擬退火法的收斂速度。

(2)接收概率:當E(m_i+1)＞E(m_i)時，VFSA演算法採用如下概率接受公式:

地球物理反演教程

上式當h→1時變為式(8.12)。h通過實驗獲得。

(3)降溫曲線(退火計劃):Ingber在1989年採用式(8.13)得出指數降溫曲線。從圖8.4可知，溫度下降較快。

總之，VFSA演算法在模型修改、接受概率以及降溫曲線上的改進使得模擬退火演算法收斂速度大大加快。後人在此基礎上還有很多的改進，讀者可以參考相關文獻。

模擬退火法的優點:由於不需要計算偏導數矩陣，不需要解線性方程組(當然正演計算的除外)，結構簡單，易於編程;此外，由於它搜索范圍大，能接受較差模型，因此易於達到全局極小。缺點:隨機搜索，計算量巨大，往往要計算成百上千次正演，這與前面的最小二乘法十幾次的正演計算相比反演時間太長，因此一般應用在一維反演之中，在二維、三維等高維反演中應用較少。

Ⅲ 演算法式和爬山法的區別

爬山演算法是一種簡單的貪心搜索演算法，該演算法每次從當前解的臨近解空間中選擇一個最優解作為當前解，直到達到一個局部最優解。爬山演算法實現很簡單，其主要缺點是會陷入局部最優解，而不一定能搜索到全局最優解。

演算法式：把解決問題的方法一一進行嘗試，最終找到解決問題的答案。特點：問題解決的系列搜索，採用試誤的方式解決問題，優點：一定可以找到某種解決問題的方法，缺點：耗時耗力。

爬山法與手段目的分析法的區別：

使用爬山法的每一步都在逐漸接近最終目標，不存在中途折回的情況；在使用手段目的分析法時，人們有時為了達到目的，不得不暫時擴大目標狀態與初始狀態的差異，以有利於達到最終目標。

比如，兩兵交戰，若敵我力量懸殊，我軍可採取迂迴戰術曲線救國，先假裝投降，獲取情報，再一舉反攻。

Ⅳ 遺傳演算法、數值演算法、爬山演算法、模擬退火 各自的優缺點

遺傳演算法：優點是能很好的處理約束，能很好的跳出局部最優，最終得到全局最優解，全局搜索能力強；缺點是收斂較慢，局部搜索能力較弱，運行時間長，且容易受參數的影響。
模擬退火：優點是局部搜索能力強，運行時間較短；缺點是全局搜索能力差，容易受參數的影響。
爬山演算法：顯然爬山演算法較簡單，效率高，但是處理多約束大規模問題時力不從心，往往不能得到較好的解。
數值演算法：這個數值演算法的含義太廣，你說的是哪一種數值演算法？多數數組演算法與爬山演算法的有優缺點類似。
PS：望採納！

Ⅳ 遺傳演算法、數值演算法、爬山演算法、模擬退火 各自的優缺點

遺傳演算法：其優點是能很好地處理約束，跳出局部最優，最終得到全局最優解。缺點是收斂速度慢，局部搜索能力弱，運行時間長，容易受到參數的影響。

模擬退火：具有局部搜索能力強、運行時間短的優點。缺點是全局搜索能力差，容易受到參數的影響。

爬山演算法：顯然爬山演算法簡單、效率高，但在處理多約束大規模問題時，往往不能得到較好的解決方案。

數值演算法：這個數值演算法的含義太寬泛了，指的是哪種數值演算法，陣列演算法與爬山演算法一樣，各有優缺點。

(5)爬山演算法和模擬退火區別擴展閱讀：

注意事項：

遺傳演算法的機制比較復雜，在Matlab中已經用工具箱中的命令進行了打包，通過調用可以非常方便的使用遺傳演算法。

函數GA：［x，Fval，reason］＝GA（＠fitnessfun，Nvars，options）x為最優解，Fval為最優值，＠Fitnessness為目標函數，Nvars為自變數個數，options為其他屬性設置。系統的默認值是最小值，所以函數文檔中應該加上一個減號。

要設置選項，您需要以下函數：options＝GaOptimset（＇PropertyName1＇，＇PropertyValue1＇，＇PropertyName2＇，＇PropertyName3＇，＇PropertyValue3＇…）通過該函數，可以確定一些遺傳演算法的參數。