模擬退火算法簡介與實例

1、模擬退火算法簡介與實例2010-07-10 12:30:55| 分類：algorithms |標簽：|字號大中小 訂閱摘要模擬退火算法是S. Kirkpatrick, C. D. Gelatt 和M. P. Vecchi在1983年所發(fā)明。是一種典型的概率模擬算 法（Monte Carlo算法），其基本想想與冶金上的退火有相似之處，在一個相當大的空間內(nèi)搜索最優(yōu)解， 而每次只搜索與自己臨近的狀態(tài)。此算法被證明以接近概率1接近最優(yōu)解。其中有較好的物理思想，是模 擬類算法中的典范。模擬退火算法由于要計算相臨狀態(tài)，這與Ising模擬的計算模擬有相似之處，因此本文 也將對Ising做一個介紹。本文介紹算

2、法的基本思想并做一個例子求解TSP問題（旅行商問題），重在介 紹算法思想，具體算法的優(yōu)化與改進不是本文涵蓋范圍。1. Ising 模型Ising模型描述的是物體的鐵磁性質(zhì)，在鐵和鎳這類金屬中，當溫度低于居里溫度時，原子的自旋自發(fā)地傾 向某個方向，而產(chǎn)生宏觀磁矩。溫度高于居里溫度時，自旋的取向非常紊亂，因而不產(chǎn)生凈磁矩。當溫度從大于或小于兩邊趨于居里溫度時，金屬的比熱容趨于無限大。這是物質(zhì)在鐵磁性狀態(tài)和非鐵磁性狀態(tài)之間的 相變。伊辛模型就是模擬鐵磁性物質(zhì)的結(jié)構(gòu)，解釋這類相變現(xiàn)象的一種粗略的模型。它的優(yōu)點在于，用統(tǒng) 計物理方法，對二維情形求得了數(shù)學(xué)上嚴格的解。這就使得鐵磁性物質(zhì)相變的大致特征，獲得

3、了理論上的 描述。1.1模型描述這個模型所研究的系統(tǒng)是由N個陣點排列成n維周期性點陣，這里n=2。點陣的幾何構(gòu)形可以是立方的或六角形的，每個陣點上都賦予一個取值 +1或-1的自旋變量i,如果i = +1,即第N個陣點的自旋向上；如i = -1， 即第個N陣點的自旋向下并且認為只是最近鄰的自旋之間有相互作用。點陣的位形用一組自旋變量（這里i =2）來確定，如下圖所示圖1,模型圖示圖2，最近臨磁子1.2模型計算1）兩個相臨磁子趨向平行能量最低，即兩個磁子的自旋方向非平行與平行。能量相差A(yù)E2）每個磁子的磁矩為 m,總的磁矩為每個磁子的磁矩和。3）總的能量為每對相臨磁子能量和。4）隨機選擇晶格內(nèi)的磁

4、子，與和它相臨的磁子比較，如果翻轉(zhuǎn)后能量降低則接受翻轉(zhuǎn)，如果能量升高則以 概率3）接受翻轉(zhuǎn)，b為波爾茲曼常數(shù)。5）模型選擇周期性邊界條件，即模型的左邊界與右邊界相聯(lián)，上邊界與下邊界相聯(lián)1.3模擬結(jié)果圖3較低溫度運行一段時間后圖4較低溫度運行更長一段時間后圖5較高溫度運行一段時間后在較低的溫度下運行一段時間后可以發(fā)現(xiàn)有相同磁矩塊聚集的情況，即岀現(xiàn)磁疇。具體比熱計算與相變點 計算本文不做進一步討論。2. 模擬退火算法模擬退火算法的關(guān)鍵是與Ising模型的計算一樣，要找到系統(tǒng)中的能量”與 能量差”并且使最優(yōu)的解處在能量最小的地方，用概率法模擬能量的變化過程。下面雙TSP (旅行商問題)來說明這種方法

5、，旅行商問題描述的是一個旅行商要在N之間游走來販賣貨物，而路費的成本與距離成正比，因此他想在N個城市之間找到僅一條最短路徑，即能去所有城市一次且僅一次，最后回到出發(fā)點。這個簡單的問題被證明為NP問題，對于N個城市的問題計算量為 0(N!),對于N=40時的計算量就已是目前全世界最強的計算機都難以 解決。因此必須尋找其它的可行的算法。模擬退火算法就是其中一種。2.1計算步驟本算法對于TSP問題的計算方法如下，我們隨機選擇一種路徑，稱為一種配置。記這種配置為：計算這種配置下的路徑總長度珀圖6退火前的配置我們隨機選擇其中的兩個城市I,j ,把之間的城市反轉(zhuǎn)，之后把這個配置改變?yōu)?計算此種配置下的路徑

6、總長度鼻q是°】的一個近臨配置，如果 厶“I 則我們就真的把原配置更新為新配置，如果,這種情況下并不直接拒絕這種新的配置，而是以概率巳心j2,T為算法中設(shè)定的溫度，如果這種步驟不斷進行下去，將使得總的路徑長度趨于變小，但是如果T的值較大則路徑長度不易達到最小，因不易在模擬中被拒絕。但是隨著模擬過程的進行，如果T的值不斷減小，則能使路徑不斷減小，并且使較大的路徑增長變化不易被接受。因此在模擬過程中要確定合適的溫度變化速度，也就是退火速度。如果城 市較多，則要減小溫度變化的速度，這與冶煉中較大塊的金屬降溫速度較慢一致。圖7,經(jīng)過兩次模擬運算后的結(jié)果在運算之前的路徑的總長度為36580.3

7、，兩次模擬之后的結(jié)果分別為6025.71和5925.48 ，這個是模擬退火算法的特點，每次運算都有隨機性，找到的不一定是最優(yōu)解，但是與是優(yōu)解的配置相差不多。3. 模擬退火應(yīng)用模擬退火算法是隨機模擬算法（Monte Carlo算法）中十分重要的一種，此算法在求解最優(yōu)解的過程中不易被 最局部最優(yōu)解束縛，因為在計算過程中對于較長的路徑如果溫度合適也能跳到長路徑上去。此算法的主要 對于系統(tǒng)的維度并不敏感，并且對于有多個，甚至成百上千的系統(tǒng)優(yōu)化目標也不會顯著增大計算量（相對 于原問題中的指數(shù)級的運算量，此算法的計算果可近似看成是線性的），并且可以對于具體的問題和對于 解的需求，可以調(diào)解系統(tǒng)中溫度的變化速度，在解的精度和計算速度之間尋找一個權(quán)衡。（注：本文關(guān)于Ising模型和模擬退火算法的源代碼放在以下網(wǎng)址上，僅供參考）http:/cid-http:/cid-1.參考文獻 vxmlnamespace prefix ="o" ns ="urn:schemas-microsoft-com:office:office" />