一種改進的模擬退火算法在TSP問題中的研究與應用.pdf

1、旅行商問題(簡稱TSP)既是組合優(yōu)化問題又是經(jīng)典的NP難問題,有很廣泛的應用價值,近些年來伴隨著計算機學科不斷地前進,TSP這個“老問題”也逐漸回到人們的視野之中,成為了科研的新焦點,更是作為各種新算法正確性與可行性驗證的重要依托。模擬退火算法自從被提出就因其簡練且方便使用而具有極大的拓展空間,并且目前已經(jīng)成功地投入到了很多方面的使用中,展示出了良好的效果。然而模擬退火算法依然存在著其自身的不足,即避免陷入局部極小值以及解空間的搜索能力

2、和范圍這兩項指標不是很理想。
　　 本文針對模擬退火算法的兩點不足,對傳統(tǒng)的模擬退火算法進行了改進,提出了多種群多算子的模擬退火算法來求解經(jīng)典的TSP問題。該算法借鑒了遺傳算法的隱含并行性的優(yōu)點,提出了多種群的并行機制來提高其尋優(yōu)效率也就是全局最優(yōu)解的尋找能力,和傳統(tǒng)算法中一個個地優(yōu)化解相比,改進了的方法在效率上有了很大的提高；為了增大解空間的搜索能力和范圍,本文通過改進狀態(tài)產(chǎn)生函數(shù)來解決,一般新路徑的產(chǎn)生通常是用二變換法或三變

3、換法等單一的構造方法來實現(xiàn),而這里采用多種算子來產(chǎn)生新的解空間,并且通過某種設定概率的方式來決定運用哪種操作(即算子)來產(chǎn)生新的解空間,這樣做大大增加了解空間的涵蓋面積,進而為算法跳出局部最優(yōu)解和搜索全局最優(yōu)增大了可能性。
　　 本文運用了新改進的算法,通過旅行商問題來進行驗證,分別對其中的CHN31、ATT48和EIL51進行求解。仿真結果表明,該算法得到了很好的效果,不僅避免了傳統(tǒng)的模擬退火算法極易陷入局部極小值,而且增加了