退火算法（一種物理算法）

退火算法（一種物理算法）

退火算法 （一種物理算法） 次瀏覽 | 2022.08.12 12:43:59 更新 來源 ：互聯網 精選百科 本文由作者推薦 退火算法一種物理算法

模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態，最后在常溫時達到基態，內能減為最小。作為模擬退火算法應用，討論旅行商問題（Travelling Salesman Problem,簡記為TSP）：設有n個城市，用數碼1，......，n代表。溫度T的初始值設置是影響模擬退火算法全局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優解的可能性大，但因此要花費大量的計算時間；反之，則可節約計算時間，但全局搜索性能可能受到影響。

中文名

退火算法

外文名

Simulate Anneal Arithmetic

全稱

模擬退火算法

來源

固體退火原理

參數控制

模擬退火算法的應用很廣泛，可以求解NP完全問題，但其參數難以控制。[1]其主要問題有以下三點：

（1）溫度T的初始值設置問題。

溫度T的初始值設置是影響模擬退火算法全局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優解的可能性大，但因此要花費大量的計算時間；反之，則可節約計算時間，但全局搜索性能可能受到影響。實際應用過程中，初始溫度一般需要依據實驗結果進行若干次調整。

（2）退火速度問題。

模擬退火算法的全局搜索性能也與退火速度密切相關。一般來說，同一溫度下的“充分”搜索（退火）是相當必要的，但這需要計算時間。實際應用中，要針對具體問題的性質和特征設置合理的退火平衡條件。

（3）溫度管理問題。

溫度管理問題也是模擬退火算法難以處理的問題之一。實際應用中，由于必須考慮計算復雜度的切實可行性等問題，常采用如下所示的降溫方式：

T（t+1）=k×T（t）

式中k為正的略小于1.00的常數，t為降溫的次數

優缺點及改良方式

優點：計算過程簡單，通用，魯棒性強，適用于并行處理，可用于求解復雜的非線性優化問題。

缺點：收斂速度慢，執行時間長，算法性能與初始值有關及參數敏感等缺點。

經典模擬退火算法的缺點：

（1）如果降溫過程足夠緩慢，多得到的解的性能會比較好，但與此相對的是收斂速度太慢。

（2）如果降溫過程過快，很可能得不到全局最優解。

模擬退火算法的改進：

（1）設計合適的狀態產生函數，使其根據搜索進程的需要

表現出狀態的全空間分散性或局部區域性。

（2）設計高效的退火策略。

（3）避免狀態的迂回搜索。

（4）采用并行搜索結構。

（5）為避免陷入局部極小，改進對溫度的控制方式

（6）選擇合適的初始狀態。

（7）設計合適的算法終止準則。

也可通過增加某些環節而實現對模擬退火算法的改進。

主要的改進方式包括：

（1）增加升溫或重升溫過程。在算法進程的適當時機，將溫度適當提高，從而可激活各狀態的接受概率，以調整搜索進程中的當前狀態，避免算法在局部極小解處停滯不前。

（2）增加記憶功能。為避免搜索過程中由于執行概率接受環節而遺失當前遇到的最優解，可通過增加存儲環節，將一些在這之前好的態記憶下來。

（3）增加補充搜索過程。即在退火過程結束后，以搜索到的最優解為初始狀態，再次執行模擬退火過程或局部性搜索。

（4）對每一當前狀態，采用多次搜索策略，以概率接受區域內的最優狀態，而非標準SA的單次比較方式。

（5）結合其他搜索機制的算法，如遺傳算法、混沌搜索等。

（6）上述各方法的綜合應用。

參考資料