退火算法

退火算法

一種物理算法
模拟退火算法來源于固體退火原理,将固體加溫至充分高,再讓其徐徐冷卻,加溫時,固體内部粒子随溫升變為無序狀,内能增大,而徐徐冷卻時粒子漸趨有序,在每個溫度都達到平衡态,最後在常溫時達到基态,内能減為最小。作為模拟退火算法應用,讨論旅行商問題(Travelling Salesman Problem,簡記為TSP):設有n個城市,用數碼1,......,n代表。溫度T的初始值設置是影響模拟退火算法全局搜索性能的重要因素之一、初始溫度高,則搜索到全局最優解的可能性大,但因此要花費大量的計算時間;反之,則可節約計算時間,但全局搜索性能可能受到影響。
  • 中文名:退火算法
  • 外文名:Simulate Anneal Arithmetic
  • 别名:
  • 全稱:模拟退火算法
  • 來源:固體退火原理

參數控制

模拟退火算法的應用很廣泛,可以求解NP完全問題,但其參數難以控制。其主要問題有以下三點:

(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)上述各方法的綜合應用。

相關詞條

相關搜索

其它詞條