iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 28
0
AI & Data

GA Note - 基因演算法的世界系列 第 28

【Day28】GA with you - Simulation Annealing 模擬退火法

今天來跟大家介紹模擬退火演算法(Simulated Annealing,SA)

Introduction 簡介

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

以演算法的角度來説,就是先以搜尋空間內的任一點作為起點,每一步選擇一個鄰近點-『鄰居』,然後再計算從目前的位置到達附近的鄰近點的機率。由此可知,模擬退火演算法得知該機率收斂到全局最佳解。

Pseudocode 虛擬碼

s := s0; e := E (s)                             // 設定目前狀態為s0,其能量E (s0)
k := 0                                          // 評估次數k
while k < kmax and e > emin                     // 若還有時間(評估次數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

從上面可以看到可以設定的參數有

  1. s:初始值
  2. k:迭代次數
  3. 退火速度
  4. 溫度管理

相關資料:
維基百科-模擬退火
[Day 21] Simulated annealing -- 演算法


上一篇
【Day27】GA with you - Memetic algorithm 模因演算法
下一篇
【Day29】GA with you - Particle Swarm Optimization Algorithm 粒子群演算法
系列文
GA Note - 基因演算法的世界30

尚未有邦友留言

立即登入留言