模擬退火算法的動力系統模型及收斂性分析
摘要：模擬退火算法是經典的擬物類自然計算方法,其算法設計及應用研究取得了豐碩的成果,模擬退火策略也廣泛地融入到現代群智能演化算法的研究之中.早期的性能分析和收斂性分析等理論研究主要是基于隨機過程中的馬爾科夫鏈理論,獲得了依概率意義的收斂性定理.由于物理和數學已經積淀了深厚的理論基礎和豐富的分析工具,可以用來進行隨機啟發式算法的理論分析和設計.該文試圖運用動力系統理論分析模擬退火算法的運行機理和收斂性,將算法搜索最優解的過程比擬為質點作彈性運動,算法運行過程中函數值的變化就是質點在作簡諧振動或阻尼振動,建立其常微分方程動力系統模型.運用常微分方程的定性理論對該動力系統模型進行求解和分析,證明了模擬退火算法前、中期的局部收斂性和后期的全局收斂性,對其運行機理給出了合理的理論解釋.同時,基于建立的動力系統模型,分析了算法衰減因子與收斂速度的關系,得到了模擬退火算法收斂速度的估計.在此基礎之上,提出了一個模擬退火回火算法的改進策略,一個簡單易行的回火時刻判據,當彈性系數趨于很小的值時,即可以當作回火時刻.選取幾個典型的測試問題,運用基本的模擬退火算法進行實驗驗證.首先,實驗表明數值收斂曲線與理論分析的收斂性結論相吻合;其次,實驗驗證了收斂速度隨退火溫度變化的理論分析與數值實驗相吻合;同時實驗也驗證了提出的回火時刻判據的有效性.最后,理論與實驗分析表明該文建立的動力系統模型適合描述模擬退火算法.
注: 保護知識產權,如需閱讀全文請聯系計算機學報雜志社
相關推薦
更多
