【正文】 高 尚 . 求解旅行商 問題 的 蟻 群 遺傳 混合算法 [J]，微 電 子 學與計算機， 2020 年 04 期 [7] 邢文 訓 著 . 現(xiàn) 代 優(yōu) 化 計 算方法 [M],第 2 版，北京： 清華 大 學 出版社， 2020 [8] 王萬森著 . 人工智能原理及其 應 用 [M],第 2 版 ，北京： 電 子工 業(yè) 出版社，2020 [9] 梁 艷 春等著 . 群智能 優(yōu) 化算法理 論與應 用 [M]，北京：科 學 出版社， 2020 [10] Ingber L,Rosen algorithms and fast simulated annealing:A Computer ,16(Ⅱ ):87100 [11] 康立山， 謝 云， 羅 祖 華 ，非 數(shù)值并 行算法 —— 模 擬 退火算法 [M],北京 :科 學 出版社 ,1997 。但總體上還是達到了課題的要求。因而理論上能夠找到最優(yōu)解，但實際使用過程中諸多的參數(shù)如起始溫度，溫度下降速率，迭代次數(shù)等都需要人為的測試和調(diào)整，而這些參數(shù)將直接影響能否搜索到最優(yōu)解，所以模擬退火算法仍然存在一些缺點。該程序基本實現(xiàn)了該課題的任務目標，研究模擬退化算法的基本原理以及 TSP組合優(yōu)化問題，用一種程序語言實現(xiàn)基于模擬退火算法的 TSP問題求解方法。 本文給出了用模擬退火算法求解旅行商問題的流程，給出了各參數(shù)的如何取值。但在以后我將繼續(xù)學習相關知識去豐富自己。并且實現(xiàn)不了解題目，導致花費時間從而未在只做城市節(jié)點圖分布的功能模塊。 畢業(yè)設計課題研究到此完成了模擬退火算法求解 TSP 問題基 本系統(tǒng)及其編碼部分和實現(xiàn)均已演示完畢。 經(jīng)過上面的一系列操作后，我 可以繼續(xù)觀察程序運行情況，一會后，程序得出最終結果，如圖 和平均出現(xiàn)的概率。圖 。界面如圖 ， 模擬退火算法在 TSP問題中的應用研究 第五章 算法運行分析 25 圖 輸入文本文件的文件名 3．輸入錯誤的文件 在顯示要輸入文件名的地方輸入一個錯誤的文件觀看 系統(tǒng)反應，輸入，程序反應如圖 ， 圖 輸入一個錯誤的文件名 DOS環(huán)境下界面顯示情況與預先預想的一樣沒有出現(xiàn)異常情況。然后，跳出 DOS界面顯示如圖 ， 圖 成功在 DOS下運行程序界面 成功運行了程序代碼， DOS環(huán)境下顯示出所要達到的目的。 } 模擬退火算法在 TSP問題中的應用研究 第五章 算法運行分析 24 第 五章 算法運行分析 第 4 章給出了應用開發(fā)的組織結構和各個功能模塊的具體實現(xiàn)，這章介紹程序 編碼實現(xiàn)后的運行界面圖示以及結果分析情況。 else result = exp( (fi fj)/t )。 fj = evaluate(j)。 double result = 0。按一定方式將 T降溫，即令 T(t+1)＝ kT(t)， i=i+1，然后檢查退火過程是否結束，如果不是繼續(xù)交換，如果是的話輸出 Si作為最優(yōu)輸出。 } 這段程序代碼是多最優(yōu)解排序，并且統(tǒng)計最優(yōu)解出現(xiàn)次數(shù)和計算出最優(yōu)解的出現(xiàn)頻率。 getch()。 printf(\t\t%d\t%\n, Recperc[i].nflag, statlist)。 j++) { printf(%c, Recperc[i].list[j])。 for(int j=0。i4。 例如圖 圖 統(tǒng)計概率和最優(yōu)解 程序代碼如下： printf(最優(yōu)解排序 \t序列 \t\t\t出現(xiàn)次數(shù) \t出現(xiàn)的概率 \n)。 這些將在 。 printf(最優(yōu)解排序 \t序列 \t\t\t出現(xiàn)次數(shù) \t出現(xiàn)的概率 \n)。 printf(請按任意鍵結束 !)。語句的輸入使 DOS界面顯示的圖 , 圖 輸入顯示圖 模 擬退火算法在 TSP問題中的應用研究 第四章 算法具體設計與編碼實現(xiàn) 22 DOS界面下顯示出“清輸入旅行城市文件全名” ,這個也就是要求輸入我們所編寫文本文件 .。 scanf(%s, amp。而 scanf是 C語言和 C++語言中提供的按指定格式進行標準輸入的函數(shù)。在這里界面的輸出輸入形式主要應用的 printf語句和 scanf語句進行完成的。 圖 建立的 同時，也可以自己編寫具體的城市坐標，用來自己分析模擬退火算法求解TSP問題的優(yōu)缺點。所以，接下來將要把程序正確運行界面進行詳細的講解。最后，在 DOS界面中輸出每一次新的鄰域解產(chǎn)生的形式和其在計算函數(shù)部分算出來的某一個序列中城市之間的距離總和。 i++) { out(stimulation(sequence))。 for(i=0。i++) { Recperc[i].nvalue=1000。 for(i=0。 //設置種子 int *sequence。 } fclose(pfile)。 citycoordinate[i][0] = firsttemp。firsttemp, amp。 i++) { fscanf(pfile, %s\t%f\t%f, amp。 for(i=0。 amount = city_number。 } fscanf(pfile, %d, amp。 getch()。 if( (pfile = fopen( filename, r )) == NULL ) { 模 擬退火算法在 TSP問題中的應用研究 第四章 算法具體設計與編碼實現(xiàn) 20 printf( 打不開旅行城市文件（ %s） !\n, filename)。filename)。 printf(請輸入旅行城市文件全名： )。 int i。 主體 main函數(shù)程序代碼實現(xiàn)： int main(int argc, char* argv[]) { char filename[81]。主函數(shù)調(diào)用其他函數(shù)，其他函數(shù) 也可以互相調(diào)用。選擇出現(xiàn)的頻率最高的 路徑 最短路徑，并且，顯示出最短路徑的值。并且一次循環(huán)知道溫度降低，達到平衡。然后，將這個初始化序列解，計算它的最短路徑。語句來 設置的種子，即初始解得序列。實現(xiàn)城市坐標的數(shù)據(jù)輸入。應用 pfile = fopen( filename, r )語句來打開文件，并且通過 fscanf(pfile, %d, amp。 模擬退火算法求解 TSP問題的系統(tǒng)編程，主要通過主體函數(shù)中的讀取文本文件中事先所記錄的城市坐標來實現(xiàn)數(shù)據(jù)輸入的。 } 求解 TSP問題的算法主體模塊詳細設計 主要介紹整個關鍵 main（）函數(shù)主體和 DOS界面上的顯示計 算概率的信息。 save[0] = temp。i++) { if(save[i]==0) { temp = save[i]。 for(int i=1。 k++。 break。iamount。 temp = rand() % amount。j++) save[j] = 1。 for(int j=0。 int *save =NULL。 result[m] = temp。 temp = result[n]。 n++。 m = rand() % (amount 1)。k++) result[k] = i[k]。 for(int k=0。 } void Neighbour(int *i,int *result) //i代表父序列， result代表子序列。并且將交換的結果儲存在 result 中。 本程序代碼中利用上訴所講的 2opt 方法產(chǎn)生新的路徑。 2opt 算法的主要思想是在所有城市中隨機選取兩個城市，然后將兩個城 市在路徑中的序列交換位置產(chǎn)生新的路徑。 通過以上兩個函數(shù)代碼可以達到我們所希望達到的要求。 計算某一個序列中城市之間的距離總和是通過 for 函數(shù)進行循環(huán)相加將值不斷賦給 result 并且通過 result += distance(x[amount1],x[0])。 } 計算兩個城市之間的距離主要 是根據(jù)坐標軸上的 2點求距離公式計算的。 } result += distance(x[amount1],x[0])。counteramount1。 } 計算某一個序列中城市之間的距離總和 double evaluate(int *x)/ { double result = 0。 result = sqrt( (citycoordinate[x][0] citycoordinate[y][0]) * (citycoordinate[x][0] citycoordinate[y][0]) + (citycoordinate[x][1] citycoordinate[y][1]) * (citycoordinate[x][1] citycoordinate[y][1]) )。用來進行比較出 所有路徑之中的最小值 的路徑距離。以備主函數(shù)調(diào)用文本文件中點的坐標軸位置進行計算兩個點之間的路徑距離建立個表格，如表 表 城市坐標表 A 40 44 B 24 14 C 17 22 D 22 76 E 51 94 F 87 65 G 68 52 H 84 36 I 66 25 J 61 26 將這個表 txt文本文件中保存并且命名“為 ”。在坐標軸上選擇恰當?shù)?10個點，描繪和 10個城市。 定義坐標表的具體參數(shù)與具體實現(xiàn) 1．城市坐標表的定義 在這里我們選擇了簡單的 TSP模型，應用 10個點之間坐標。實 際應用過程中，初始溫度一般需要依據(jù)實驗結果進行若干次調(diào)整。 return result。 }while( fabs(f2 f1) 1e5)。 t = alpha * t。 }while(time L)。 j = temp。 if ( (random == ) || (random random0_1()) ) { temp = i。 do { Neighbour(i,j)。 do { f1 = f2。 //每個溫度的迭代次數(shù) ,也就是每一個溫度上的平衡條件 int time = 0。 //初始溫度，降溫系數(shù) int k = 0。 模 擬退火算法在 TSP問題中的應用研究 第四章 算法具體設計與編碼實現(xiàn) 15 j[m] = 0。mamount。 int *i = new int[amount]。 double random = 0。該系統(tǒng)設置的溫度下降系數(shù)為a=。另一類是非時齊算法，整個過程僅由一個馬爾可夫鏈構成，要求相連的狀態(tài)轉(zhuǎn)移中，溫度 t 是下降的。 2．溫度的下降函數(shù) 溫度管理問題也是模擬退火算法難以處理的問題之一。因此，溫度參數(shù)的設定影響到模擬退火算法能否收斂到全局最優(yōu)解。 算法溫度的選擇和變化 溫度參數(shù)是模擬退火算法中一 個關鍵的參數(shù)，初始溫度不夠高或退火時間不夠長將會使得搜索過快，從而使得算法容易陷于局部最優(yōu)解。然后從 Xi的鄰域中隨即選擇 Xj，計算 Xi與 Xi的路徑差，比較差值。 圖 Y Y Y Y N N N N 選擇初始路徑 X0 確定初始溫度 T0 當前路徑 Xi=X0 當前溫度 Ti=T0 當前路徑 Xi=Xj △ f=0 Exp(△ f/Ti)random(0,1) 跳出內(nèi)循環(huán) 跳出外循環(huán) 結 束 當前溫度 Ti下降 從 Xi的鄰域中隨機選擇 Xi，計算 Xi 與 Xj 的路程差 △ f=f(Xj)f(Xi) 模 擬退火算法在 TSP問題中的應用研究 第四章 算法具體設計與編碼實現(xiàn) 14 圖 。新路徑的產(chǎn)生：隨機產(chǎn)生 1和 n之間的兩相異數(shù) k和 m，不妨假設 km，則將原路徑 (w1,w2,…,wk,wk+1,…,wm,wm+1,…,wn) 變?yōu)樾侣窂剑? (w1,w2,…,wm,wk+1,…,wk,wm+1,…,wn) 上述變換