模擬退火演算法

建議閱讀時間：10分鐘

退火是一門古老的工藝：先加熱材料，然後慢慢降溫，以釋放其內部的壓力，獲得性質更加優良的材料。

1983年，Kirkpatrick等人將退火思想引入到了優化領域，提出了模擬退火演算法 (simulated annealing algorithm)。

模擬退火演算法是一種啟發式演算法，其基本思想是模擬固體退火的過程，通過採用Metropolis重要性採樣準則來改進傳統蒙特卡洛採樣的效率，並通過一組冷卻進度表來控制演算法進程，使得模擬退火演算法在具有較高搜索效率的同時還具備了全局優化的能力，在組合優化領域應用廣泛。

模擬退火演算法應用領域

應用模擬退火演算法求解優化問題的主要步驟如下：

模擬退火演算法流程圖

可見，模擬退火演算法的思想簡單，易於實現。在應用模擬退火演算法在求解組合優化問題的時候，影響演算法效果的主要因素是其參數設置。

參數設置

• 初始溫度設置問題。溫度在退火演算法中影響著新產生狀態的接受概率。在目標函數複雜且變數眾多的情況下，為了得到較好的結果，通常設置初始溫度較高，這樣會有較好的全局尋解能力。但是這又會導致演算法的迭代次數過多，運行時間過長。

• 溫度的遞減方式。如果選擇的初始溫度過高，每次衰減的溫度過小，這樣迭代的次數就會增多，雖然能夠取得較好的解，但是計算的時間過長，效率不高；反之，雖然計算速度很快，但是有可能找不到全局最優解。

• 某一溫度下的迭代方案。從理論上講, 某一溫度下的迭代方案應為無窮多次, 但實際問題中, 在每個溫度下考慮迭代若干輪以接近平衡。迭代次數過少，遍歷不充分，過多又會造成時間開銷。

在迭代的過程中，由於每次都按概率接受新的狀態，有可能遺失了當前遇到的最優解。因此在實際應用中，常記錄演算法的整個迭代過程中出現的最好結果。

在管理科學、計算機科學、大規模集成電路設計及電子工程等科技領域中，存在著大量的組合優化問題。

而大量的實驗結果表明，模擬退火演算法是一種適合解大規模組合優化問題的有效方法。

典型的應用有旅行商問題、調度問題、0-1背包問題、圖著色問題、劃分問題和布局問題等。

祝學習愉快！

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！