模擬退火

模擬退火（粵音：mou4 ji5 teoi3 fo2；英文：simulated annealing）係一種做最佳化嘅演算法。

做法

睇埋：最佳化同爬山演算法

模擬退火係爬山演算法（hill climbing）嘅一個變種；喺每步當中，最簡單嘅模擬退火演算法會考慮周圍嘅可能 $p$ 值嘅 $z$ 值，foreach 呢啲 $p$ 值，將佢個 $z$ 值 ±s，當中 s 係一個隨機俾嘅數值（溫度值），然後個演算法會再按邊個 $p$ 嘅（±s 後）$z$ 數值比較接近理想數值，決定參數要變成邊個可能 $p$ 值－噉做嘅話，個演算法唔會咁易企喺一個地區性最細或者地區性最大嗰度唔郁，但因為 $z$ 比較近理想數值嘅 $p$ 會比較大機會被選中，所以經過好多步之後，個演算法最後得出嗰個 $p$ 值好有可能會係 $z$ 值理想嘅。一段用模擬退火嘅虛擬碼如下：

 Input:
   ProblemSize,
   iteration, // 重複幾多次
   max_temp, // 最大溫度值
 Output:
   S_best // 最佳嘅參數值
 
 Initialize:
   S_current = CreateInitialSolution(ProblemSize); // 將現時參數值設做隨機數值。
   S_best = S_current; // 暫時當最佳參數值係現時數值。
 
 for (i = 1 to iteration)
   S_i = CreateNeighborSolution(S_current); // 搵 S_current 周圍嘅參數值。
   current_temp = CalculateTemperature(i, max_temp); //「現時溫度」由 i 同 max_temp 話事。
   if Cost(S_i) < Cost(S_current) // 如果 S_i 嘅指標值靚過 S_current 嘅...
     S_current = S_i;
     if Cost(S_i) < Cost(S_best) // 如果 S_i 嘅指標值靚過 S_best 嘅...
       S_best = S_i;
     end
   else if (Exp[((Cost(S_current) - Cost(S_i)) / current_temp]) > rand()
   // 當中 rand() 係一個隨機產生嘅數值；隨住 current_temp 變細，呢個 elseif 發生嘅機會率會愈嚟愈細。
     S_current = S_i;
 end
 
 return S_best; // 最後就將 S_best 俾出嚟做輸出。

模擬退火嘅一個示範；Y 軸係需要最大化嗰個指標，X 軸係參數，隨住溫度值慢慢下降，參數值漸趨穩定。幅圖有好多地區性最大，所以用單純嘅爬山演算法好可能會搞唔掂。

睇埋

• 爬山演算法