模擬退火算法在旅行商問題中的應(yīng)用

模擬退火算法在旅行商問題中的應(yīng)用

0模擬退火算法旅行商業(yè)問題tsp（旅行商業(yè)成本效益）是一個(gè)完美的pd問題。目前，解決tsp問題的主要方法有：模型退火算法、遺產(chǎn)算法、序列搜索方法、堆疊搜索算法、堆疊算法等。模擬退火算法最早思想由Metropolis在1953年提出,1983年Kirkpatrick等成功地將退火思想引入組合優(yōu)化領(lǐng)域。模擬退火算法是局部搜索算法的擴(kuò)展,理論上來說,它是一個(gè)全局最優(yōu)算法。如何在初始解附近找出一個(gè)“好的解”是一項(xiàng)關(guān)鍵技術(shù),它直接影響算法的收斂速度。本文推薦采用蟻群算法的思想,利用邊的鄰接關(guān)系,距離近的鄰點(diǎn)以較大的概率選為下一個(gè)訪問點(diǎn)。1熱平衡問題的最優(yōu)解模擬退火算法用于優(yōu)化問題的出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過程與一般優(yōu)化問題的相似性。算法的基本思想是從一給定解開始的,從鄰域中隨機(jī)產(chǎn)生另一個(gè)解,接受準(zhǔn)則允許目標(biāo)函數(shù)在有限范圍內(nèi)變壞。它由一控制參數(shù)t決定,其作用類似于物理過程中的溫度T,對于控制參數(shù)t的每一取值,算法持續(xù)進(jìn)行“產(chǎn)生新解-判斷-接受或舍棄”的迭代過程,對應(yīng)著固體在某一恒定溫度下趨于熱平衡的過程。經(jīng)過大量的解變換后,可以求得給定控制參數(shù)t值時(shí)優(yōu)化問題的相對最優(yōu)解。然后減小控制參數(shù)t的值,重復(fù)執(zhí)行上述迭代過程。當(dāng)控制參數(shù)逐漸減小并趨于零時(shí),系統(tǒng)亦越來越趨于平衡狀態(tài),最后系統(tǒng)狀態(tài)對應(yīng)于優(yōu)化問題的整體最優(yōu)解。該過程也稱冷卻過程。由于固體退火必須緩慢降溫,才能使固體在每一溫度下都達(dá)到熱平衡,最終趨于平衡狀態(tài),因此,控制參數(shù)的值必須緩慢衰減,才能確保模擬退火算法最終趨于優(yōu)化問題的整體最優(yōu)解。模擬退火算法要從鄰域中隨機(jī)產(chǎn)生另一個(gè)解,對于TSP問題,它的鄰域是指兩條路徑除局部有差別外,大多數(shù)路徑相同。解TSP問題的模擬退火算法的框架:給定起、止“溫度”T、T0和退火速度α,初始一條路徑C0;While(T>T0)do在C0的鄰域內(nèi)產(chǎn)生另一條路徑C1;計(jì)算兩條路徑所引起的目標(biāo)函數(shù)(能量)值的變化ΔE;若ΔE≤0,接受新值,否則若exp(-ΔE/T)>rand(0,1)(rand(0,1)表示0～1之間的隨機(jī)數(shù)),也接受新值,否則就拒絕;確定新的參數(shù)值,若擾動(dòng)被接受,則C0←C1,否則C0不變;若接受新值,降溫T←αT,否則不降溫;End.2城市間距離大小的策略c模擬退火算法是依賴鄰域結(jié)構(gòu)的迭代方法,如何找領(lǐng)域的解直接影響收斂速度和最優(yōu)解。針對這個(gè)問題,在上面算法中,在C0的鄰域內(nèi)產(chǎn)生另一條路徑C1,提出6種策略,這里假設(shè)有n個(gè)城市。策略A在第1～n個(gè)訪問的城市中隨機(jī)地選取第j1次和第j2次訪問的城市,在路徑C0中交換第j1次和第j2次訪問的城市,其余不變,此時(shí)的路徑為C1。如:C0=2,3,4,1,5,7,9,8,6.j1=2(第2次訪問的城市是城市3),j2=7(第7次訪問的城市是城市9),則C1=2,9,4,1,5,7,3,8,6.策略B在第1～n個(gè)訪問的城市中隨機(jī)地選取第j1次訪問的城市,在路徑C0中交換第j1次和第j1+1次訪問的城市,其余不變,此時(shí)的路徑為C1。如:C0=2,3,4,1,5,7,9,8,6,j1=2,則C2=2,4,3,1,5,7,9,8,6.策略C也稱逆轉(zhuǎn)策略,在第1～n個(gè)訪問的城市中隨機(jī)地選取第j1次和第j2次訪問的城市,在路徑C0中第j1次到第j2次訪問的城市之間的子路徑以反方向插入,其余不變,此時(shí)的路徑為C1。如:C0=2,3,4,1,5,7,9,8,6,j1=2,j2=7,則C1=2,9,7,5,1,4,3,8,6.策略D在第1～n個(gè)訪問的城市中隨機(jī)地選取第j1次和第j2次訪問的城市,假設(shè)j1<j2,在路徑C0中將第j1次訪問的城市安排到第j2次訪問的城市之后,其余不變,此時(shí)的路徑為C1。如:C0=2,3,4,1,5,7,9,8,6.j1=2,j2=7,則C1=2,4,1,5,7,9,3,8,6.策略E上面策略沒有利用城市間距離大小的信息,策略E將利用邊的鄰接關(guān)系,依據(jù)蟻群算法的思想,距離近的鄰接點(diǎn)以較大的概率選為下一個(gè)訪問點(diǎn),所以在局部調(diào)整時(shí)依據(jù)此思想。設(shè)d(i,j)表示城市i與城市j的距離,在1～n的城市中隨機(jī)地選取城市i1,離城市i1最遠(yuǎn)的城市的距離為:dmax=maxjd(i1,j)dmax=maxjd(i1,j),為了排除下一個(gè)訪問點(diǎn)為它自己,令d(i1,i1)=dmax,則下一個(gè)訪問點(diǎn)的為城市j概率為pj=dmax?d(i1,j)∑k=1n(dmax?d(i1,k))pj=dmax-d(i1,j)∑k=1n(dmax-d(i1,k))(1)假設(shè)以(1)式的概率選取的是城市j1,在路徑C0中將城市j1安排到城市i1之后,其余不變,此時(shí)的路徑為C1。如:C0=2,3,4,1,5,7,9,8,6.i1=3,j1=7,則C1=2,3,7,4,1,5,9,8,6.策略F在策略E中是在1～n的城市中隨機(jī)地選取城市i1,為了使路徑總長度和達(dá)到最短,優(yōu)先解決薄弱環(huán)節(jié),這里采用路徑中相鄰城市之間的距離大的兩個(gè)城市以較大的概率被選取,在它們之間插入其他城市。用l(n)數(shù)組記錄路徑C0相鄰城市之間的距離,具體數(shù)據(jù)如下:l(k)=d[c(k),c(k+1)],k=1,2,…,n-1l(n)=d[c(n),c(1)]選取城市i的概率為:pi=l(i)∑k=1nl(k)pi=l(i)∑k=1nl(k)(2)按(2)式以概率選取的是城市i1,后面方法同策略E,按(1)式以概率選取的是城市j1,在路徑C0中將城市j1安排到城市i1之后,其余不變,此時(shí)的路徑為C1。3局部最優(yōu)圈的驗(yàn)證以解決中國31個(gè)直轄市和省會(huì)城市的CTSP問題來測試比較,數(shù)據(jù)來源于文獻(xiàn)。假設(shè)算法的參數(shù)相同,起始溫度T=100000,終止溫度T0=1,退火速度α=0.99,各種策略各隨機(jī)測試50次,結(jié)果如表1所示。從表1可以看出,策略F是最好的算法,其次是策略E和C,策略C采用逆轉(zhuǎn)策略,可以使迭代過程突破局部最優(yōu)圈而跳到另一個(gè)搜索空間。策略A和策略D花費(fèi)的時(shí)間少,說明它們很容易落入局部最優(yōu)解。策略B效果最差,需要的時(shí)間也多。圖1是中國31城市的CTSP目前最好的解,橫坐標(biāo)x和縱坐標(biāo)y表示各城市的相對坐標(biāo),總路程為15398km,其路徑為:北京—呼和浩特—太原—石家莊—鄭州—西安—銀川—蘭州—西寧—烏魯木齊—拉薩—成都—昆明—貴陽—南寧—?？凇獜V州—長沙—武漢—南昌—福州—臺(tái)北—杭州—上海—南京—合肥—濟(jì)南—天津—沈陽—長春—哈爾濱。而本文的策略F,最好的結(jié)果如圖2所示,總路程為15383km,其路徑為:北京—沈陽—長春—哈爾濱—呼和浩特—銀川—蘭州—西寧—烏魯木齊—拉薩—成都—昆明—貴陽—南寧—?？凇獜V州—長沙—武漢—南昌—福州—臺(tái)北—杭州—上?！暇戏省嵵荨靼病仪f—濟(jì)南—天津。這說明采用策略F是一個(gè)比較好的算法。圖3顯示了迭代過程,縱坐標(biāo)表示路徑長度之和S,橫坐標(biāo)表示迭代次數(shù)N。4鉆空路線方案TSP問題組合優(yōu)化領(lǐng)域中的一個(gè)典型的問