模擬退火
閱讀設定
模擬退火(粵音: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 俾出嚟做輸出。
睇埋
[編輯]引咗
[編輯]- ↑ Kirkpatrick, S.; Gelatt Jr, C. D.; Vecchi, M. P. (1983). "Optimization by Simulated Annealing". Science. 220 (4598): 671–680.
- ↑ Simulated Annealing 互聯網檔案館嘅歸檔,歸檔日期2019年10月30號,.. Clever Algorithms: Nature-Inspired Programming Recipes.