模擬退火

維基百科,自由的百科全書
跳至導覽 跳至搜尋

模擬退火是一種通用概率演算法,常用來在一定時間內尋找在一個很大搜尋空間中的近似最優解。模擬退火是S. Kirkpatrick, C. D. Gelatt和M. P. Vecchi在1983年所發明。而V. Černý在1985年也獨立發明此演算法

簡介[編輯]

模擬退火來自冶金學的專有名詞退火。退火是將材料加熱後再經特定速率冷卻,目的是增大晶粒的體積,並且減少晶格中的缺陷。材料中的原子原來會停留在使內能有局部最小值的位置,加熱使能量變大,原子會離開原來位置,而隨機在其他位置中移動。退火冷卻時速度較慢,使得原子有較多可能可以找到內能比原先更低的位置。

模擬退火的原理也和金屬退火的原理近似:我們將熱力學的理論套用到統計學上,將搜尋空間內每一點想像成空氣內的分子;分子的能量,就是它本身的動能;而搜尋空間內的每一點,也像空氣分子一樣帶有「能量」,以表示該點對命題的合適程度。演算法先以搜尋空間內一個任意點作起始:每一步先選擇一個「鄰居」,然後再計算從現有位置到達「鄰居」的概率。

可以證明,模擬退火算法所得解依概率收斂到全局最優解。

演算步驟[編輯]

初始化[編輯]

生成一個可行的解作為當前解輸入迭代過程,並定義一個足夠大的數值作為初始溫度。

迭代過程[編輯]

迭代過程是模擬退火算法的核心步驟,分為新解的產生和接受新解兩部分:

  1. 由一個產生函數從當前解產生一個位於解空間的新解;為便於後續的計算和接受,減少算法耗時,通常選擇由當前新解經過簡單地變換即可產生新解的方法,如對構成新解的全部或部分元素進行置換、互換等,注意到產生新解的變換方法決定了當前新解的鄰域結構,因而對冷卻進度表的選取有一定的影響。
  2. 計算與新解所對應的目標函數差。因為目標函數差僅由變換部分產生,所以目標函數差的計算最好按增量計算。事實表明,對大多數應用而言,這是計算目標函數差的最快方法。
  3. 判斷新解是否被接受,判斷的依據是一個接受準則,最常用的接受準則是Metropolis準則:若Δt′<0則接受S′作為新的當前解S,否則以概率exp(-Δt′/T)接受S′作為新的當前解S。
  4. 當新解被確定接受時,用新解代替當前解,這只需將當前解中對應於產生新解時的變換部分予以實現,同時修正目標函數值即可。此時,當前解實現了一次迭代。可在此基礎上開始下一輪試驗。而當新解被判定為捨棄時,則在原當前解的基礎上繼續下一輪試驗。

模擬退火算法與初始值無關,算法求得的解與初始解狀態S(是算法迭代的起點)無關;模擬退火算法具有漸近收斂性,已在理論上被證明是一種以概率1收斂於全局最優解的全局優化算法;模擬退火算法具有並行性。

停止準則[編輯]

迭代過程的停止準則:溫度T降至某最低值時,完成給定數量迭代中無法接受新解,停止迭代,接受當前尋找的最優解為最終解。

退火方案[編輯]

在某個溫度狀態T下,當一定數量的迭代操作完成後,降低溫度T,在新的溫度狀態下執行下一個批次的迭代操作。

偽代碼[編輯]

尋找能量E(s)最低的狀態s

s := s0; e := E (s)                           // 设定目前状态为s0,其能量E (s0)
k := 0                                       // 评估次数k
while k < kmax and e > emax                  // 若还有时间(评估次数k还不到kmax)且结果还不够好(能量e不够低)则:
  sn := neighbour (s)                         //   隨機選取一鄰近狀態sn
  en := E (sn)                                //   sn的能量为E (sn)
  if random() < P(e, en, temp(k/kmax)) then  //   決定是否移至鄰近狀態sn
    s := sn; e := en                         //     移至鄰近狀態sn
  k := k + 1                                 //   评估完成,次数k加一
return s                                     // 回传状态s

參見[編輯]

外部連結[編輯]