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