一種改進(jìn)的模擬退火算法在TSP問(wèn)題中的研究與應(yīng)用.pdf

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

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

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