跳去內容

模擬退火

出自維基百科,自由嘅百科全書

模擬退火粵音:mou4 ji5 teoi3 fo2;英文simulated annealing)係一種做最佳化演算法

做法

[編輯]

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

 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 軸係參數,隨住溫度值慢慢下降,參數值漸趨穩定。幅圖有好多地區性最大,所以用單純嘅爬山演算法好可能會搞唔掂。

睇埋

[編輯]

引咗

[編輯]
  1. Kirkpatrick, S.; Gelatt Jr, C. D.; Vecchi, M. P. (1983). "Optimization by Simulated Annealing". Science. 220 (4598): 671–680.
  2. Simulated Annealing 互聯網檔案館歸檔,歸檔日期2019年10月30號,.. Clever Algorithms: Nature-Inspired Programming Recipes.

[編輯]