今天來跟大家介紹模擬退火演算法(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 -- 演算法