回火記憶功能的返回遍歷退火算法求解TSP問題.pdf

《回火記憶功能的返回遍歷退火算法求解TSP問題.pdf》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、回火記憶功能的返回遍歷退火算法求解TSP問題問題描述旅行商問題，即TSP問題（TravellingSalesmanProblem）是數(shù)學(xué)領(lǐng)域中著名問題之一。假設(shè)有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路經(jīng)的限制是每個城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。左邊的路程小于右邊的圖1TSP問題示意圖算法流程圖開始、參數(shù)初始化初始解、初始溫度T、回火初值t0、記憶裝置等參數(shù)設(shè)定否t0>0.01？是T=t0，返回搜索標(biāo)志anneal=1:2否anneal<=2？是

2、否T<退火停溫？是迭代計數(shù)iter_num，目標(biāo)連續(xù)未改變計數(shù)m_num清零iter_num

3、

4、(anneal==1&&exp(-?f/T)>rand(1))？是存儲新路徑，iter_num++，m_mun=0m_mun++新路徑<記憶路徑？否是記憶新路徑T=αT如果當(dāng)前路徑小于記憶路徑則當(dāng)前等于記憶t0=β×t0結(jié)果顯示，結(jié)束程序?qū)θ珖?4個城市的TSP問題進行計算，求解得到的最優(yōu)路徑圖如下：起始城市用紅五角標(biāo)記本次算法運行結(jié)果是：最優(yōu)路徑路程長為2119.09

5、25。經(jīng)多次運行，程序最終結(jié)果都收斂于最優(yōu)解，當(dāng)然算法的收斂性還需要進一步的驗證仿真，由于時間關(guān)系這里未作收斂性分析，有此曲線可知，中間波峰是由于回火所致。