1、專業綜合設計報告課程名稱： 電子專業綜合設計 設計名稱： 基于模擬退火算法的TSP算法 姓 名： 學 號: 班 級： 電子0903 指導教師： 朱正為 起止日期： 專 業 綜 合 設 計 任 務 書學生班級： 電子0903 學生姓名： 學號： 20095830 設計名稱： 基于模擬退火算法的TSP算法 起止日期： 指導教師 設計要求： 旅行商問題，即TSP問題（Travelling Salesman Problem）又譯為旅行推銷員問題、貨郎擔問題，是數學領域中著名問題之一。假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最后要回到原來出發的城市

2、。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。 此設計是用模擬退火算法來實現TSP問題的尋求最優解。專 業 綜 合 設 計 學 生 日 志時間設計內容2012.11.9初步了解模擬退火算法的TSP算法2012.11.12設計算法流程、確定解題思路2012.11.20 討論算法流程及解題思路的可行性，為仿真做準備2012.12.2運用MATLAB軟件進行實驗仿真，分析仿真結果 整理實驗報告 答辯 專 業 綜 合 設 計 考 勤 表周星期一星期二星期三星期四星期五專 業 綜 合 設 計 評 語 表指導教師評語： 成績： 指導教師： 年 月 日一 設計目的和意義5二 設計原理5 2.1

3、模擬退火算法的基本原理.52.2 TSP問題介紹.6三 詳細設計步驟.73.1.算法流程83.2模擬退火算法實現步驟8四 設計結果及分析9 4.1 MATLAB程序實現及主函數.9 計算距離矩陣.9 4.1.2 初始解.10 4.1.3 生成新解.10 4.1.4 Metropolis 準則函數. .10 4.1.5 畫路線軌跡圖.11 4.1.6 輸出路徑函數.12 4.1.7 可行解路線長度函數.12 4.1.8 模擬退火算法的主函數.134.2.仿真結果15五 體會18六 參考文獻19基于模擬退火算法的TSP算法一 、設計目的和意義 旅行商問題是組合優化領域里的一個典型的、易于描述卻難以

4、處理的NP難題，其可能的路徑數目與城市數目是呈指數型增長的，求解非常困難。首先介紹了旅行商問題，給出了其數學描述以及實際應用，進而給出解決TSP的一種比較精確的算法模擬退火算法。然后闡述了模擬退火算法的基本原理，重點說明了其基本思想及關鍵技術。最后運用MATLAB語言實現了該算法，并將其運用到解決旅行商問題的優化之中。數值仿真的結果表明了該方法能夠對數據進行全局尋優，有效克服了基于導數的優化算法容易陷入局部最優的問題。 了解模擬退火算法的TSP算法的基本思路及原理，并應用MATLAB實現仿真，熟練掌握MATLAB的操作方式及應用，能正確書寫報告。 二 、設計原理 2.1 模擬退火算法的基本原理

5、 模擬退火算法足2O世紀8O年代初提出的一種基于蒙特卡羅(Mente Carlo)迭代求解策略的啟發式隨機優化算法。它通過Metropolis接受準則概率接受劣化解并以此跳出局部最優，通過溫度更新函數的退溫過程進行趨化式搜索并最終進入全局最優解集。其出發點是基于物理中固體物質的退火過程與一搬的組合優化問題之間的相似性。模擬退火法是一種通用的優化算法，其物理退火過程由以下三部分組成。（1） 加溫過程。 其目的是增強粒子的熱運動，使其偏離平衡位置。當溫度足夠高時，固體將熔為液體，從而消除系統原先存在的非均勻狀態。（2） 等溫過程。 對于與周圍環境交換熱量而溫度不變的密封系統，系統狀態的自發變化總是

6、朝自由能減少的方向進行的，當自由能達到最小時，系統達到平衡狀態。（3） 冷卻過程。 使粒子熱運動減弱，系統能量下降，得到晶體結構。 其中，加熱過程對應算法的設定初溫，等溫過程對應算法的 Metropolis 抽樣過程，冷卻過程對應控制參數的下降。這里能量的變化就是目標函數，要得到的最優解就是能量最低態。Metropolis 準則是SA算法收斂于全局最優解的關鍵所在，Metropolis 準則以一定的概率接受惡化解，這樣就使算法跳離局部最優的陷阱。 模擬退火算法為求解傳統方法難處理的TSP問題提供了一個有效的途徑和通用框架，并逐漸發展成一種迭代自適應啟發式概率性搜索算法。模擬退火算法可以用以求解

7、不同的非線性問題，對不可微甚至不連續的函數優化，能以較大的概率求的全局有化解，該算法還具有較強的魯棒性、全局收斂性、隱含并行性及廣泛的適應性，并且能處理不同類型的優化設計變量（離散的、連續的和混合型的），不需要任何的輔助信息，對目標函數和約束函數沒有任何要求。利用 Metropolis 算法并適當的控制溫度下降過程，在優化問題中具有很強的競爭力，此設計即為基于模擬退火算法的TSP算法。 SA算法實現過程如下（以最小化問題為例）： （1）初始化：取初始溫度T0足夠大，令T=T0,任取初始解S1,確定每個T時的迭代次數，即 Metropolis 鏈長 L。 （2）對當前溫度T和k=1,2，l，重復

8、步驟（3）（6）。 （3）對當前S1隨機擾動產生一個新解S2。 （4）計算S2的增量df=f（S2）-f（S1） 其中f為S1的代價函數。 （5）若df<0 ，則接受S2作為新的當前解，即S1=S2；否則計算S2的接受概率exp（-df/T），即隨機產生（0,1）區間上均勻分布的隨機數 rand，若exp（-df/T）>rand也接受S2作為新的當前解，S1=S2；否則保留當前解S1。 （6）如果滿足終止條件Stop，則輸出當前解s1為最優解，結束程序。終止條件Stop 通常為：在連續若干個 Metropolis 鏈中新解s2都沒有被接受時終止算法，或是設定結束溫度。否則按衰減函數

9、衰減 T 后返回步驟（2）。 以上步驟成為 Metropolis 過程。逐漸降低控制溫度，重復 Metropolis 過程，直至滿足結束準則 Stop，求出最優解。 2.2 TSP問題介紹 旅行商問題（Traveling Salesman Problem，簡稱TSP）又名貨郎擔問題，是威廉·哈密爾頓爵士和英國數學家克克曼(T.P.Kirkman)于19世紀初提出的一個數學問題，也是著名的組合優化問題。問題是這樣描述的：一名商人要到若干城市去推銷商品，已知城市個數和各城市間的路程（或旅費），要求找到一條從城市1出發，經過所有城市且每個城市只能訪問一次，最后回到城市1的路線，使總的路程（

10、或旅費）最小。TSP剛提出時，不少人認為這個問題很簡單。后來人們才逐步意識到這個問題只是表述簡單，易于為人們所理解，而其計算復雜性卻是問題的輸入規模的指數函數，屬于相當難解的問題。這個問題數學描述為：假設有n個城市，并分別編號，給定一個完全無向圖G=（V，E），V=1，2，n，n>1。其每一邊(i,j)E有一非負整數耗費 Ci,j(即上的權記為Ci,j，i，jV)。G的一條巡回路線是經過V中的每個頂點恰好一次的回路。一條巡回路線的耗費是這條路線上所有邊的權值之和。TSP問題就是要找出G的最小耗費回路。人們在考慮解決這個問題時，一般首先想到的最原始的一種方法就是:列出每一條可供選擇的路線(

11、即對給定的城市進行排列組合)，計算出每條路線的總里程，最后從中選出一條最短的路線。假設現在給定的4個城市分別為A、B、C和D，各城市之間的耗費為己知數，如圖1所示。我們可以通過一個組合的狀態空間圖來表示所有的組合，如圖 圖 1 頂點帶權圖 圖 2 TSP問題的解空間樹從圖中不難看出，可供選擇的路線共有6條，從中很快可以選出一條總耗費最短的路線：頂點序列為（A,C,B,D,A）。由此推算，若設城市數目為n時，那么組合路徑數則為(n-1)!。很顯然，當城市數目不多時要找到最短距離的路線并不難，但隨著城市數目的不斷增大，組合路線數將呈指數級數規律急劇增長，以至達到無法計算的地步，這就是所謂的“組合爆

12、炸問題”。假設現在城市的數目增為20個，組合路徑數則為(20-1)!1.216×1017，如此龐大的組合數目，若計算機以每秒檢索1000萬條路線的速度計算，也需要花上386年的時間6。 三 、詳細設計步驟3.1算法流程模擬退火算法求解流程框圖如圖1所示。 圖3 模擬退火算法求解流程框圖3.2模擬退火算法實現步驟如下： （1）控制參數的設置 需要設置的主要控制參數有降溫速率q、初始溫度T0、結束溫度Tend以及鏈長L。 （2）初始解 對于n個城市TSP問題，得到的解就是對1n的一個排序，其中每個數字為對應城市的編號，如對10個城市的TSP問題1,2,3,4,5,6,7,8,9,10，則

13、 |1|10|2|4|5|6|8|7|9|3就是一個合法的解，采用產生隨機排列的方法產生一個初始解S。 （3）解變換生成新解 通過對當前解S1進行變換，產生新的路徑數組即新解，這里采用的變換是產生隨機數的方法來產生將要交換的兩個城市，用二鄰域變換法產生新的路徑，即新的可行解S2。 例如n=10時，產生兩個1,10范圍內的隨機整數r1和r2，確定兩個位置，將其對換位置，如r1=4，r2=7 9 5 1 6 3 8 7 10 4 2 得到的新解為 9 5 1 7 3 8 6 10 4 2 （4）Metropolis準則 若路徑長度函數為（S），新解的路徑為（S2），路徑差為d=（S2）-（S1）,

14、則Metropolis準則為 如果df<0,則以概率1接受新路線，否則以概率exp（-df/T）接受新路線。 （5）降溫 利用降溫速率q進行降溫，即T=qT,若T小于結束溫度，則停止迭代輸出當前狀態，否則繼續迭代。 四 、設計結果及分析4.1 MATLAB程序實現及主函數4.1.1 計算距離矩陣 利用給出的N個城市的坐標，算出N個城市的兩兩之間的距離，得到距離矩陣（NN）。計算函數為Distance，得到初始群種。程序如下function D=Distanse(a)% 計算兩兩城市之間的距離%輸入 a 各城市的位置坐標%輸出 D 兩兩城市之間的距離row=size(a,1);D=zero

15、s(row,row);for i=1:row for j=i+1:row D(i,j)=(a(i,1)-a(j,1)2+(a(i,2)-a(j,2)2)0.5; D(j,i)=D(i,j); endend4.1.2 初始解 初始解的產生直接使用MATLAB自帶的函數randperm，如城市格式為N個，則產生初始解：S1=randperm（N）； %隨機產生一個初始路線 4.1.3 生成新解 解變換生成新解函數為NewAnswer，程序代碼如下：function S2=NewAnswer(S1)% 輸入% S1:當前解% 輸出% S2：新解N=length(S1);S2=S1; a=round(

16、rand(1,2)*(N-1)+1); %產生兩個隨機位置 用來交換W=S2(a(1);S2(a(1)=S2(a(2);S2(a(2)=W; %得到一個新路線4.1.4 Metropolis 準則函數Metropolis 準則函數為 Metropolis，程序代碼如下：function S,R=Metropolis(S1,S2,D,T)% 輸入% S1： 當前解% S2: 新解% D: 距離矩陣（兩兩城市的之間的距離）% T: 當前溫度% 輸出% S： 下一個當前解% R： 下一個當前解的路線距離%R1=PathLength(D,S1); %計算路線長度N=length(S1); %得到城市的

17、個數 R2=PathLength(D,S2); %計算路線長度dC=R2-R1; %計算能力之差if dC<0 %如果能力降低 接受新路線 S=S2; R=R2;elseif exp(-dC/T)>=rand %以exp(-dC/T)概率接受新路線 S=S2; R=R2;else %不接受新路線 S=S1; R=R1;end4.1.5 畫路線軌跡圖 畫出給的路線的軌跡圖函數為DrawPath，程序代碼如下：function DrawPath(Chrom,X)% 畫路徑函數%輸入% Chrom 待畫路徑 % X 各城市坐標位置R=Chrom(1,:) Chrom(1,1); %一個隨

18、機解(個體)figure;hold onplot(X(:,1),X(:,2),'o','color',0.5,0.5,0.5)plot(X(Chrom(1,1),1),X(Chrom(1,1),2),'rv','MarkerSize',20)for i=1:size(X,1) text(X(i,1)+0.05,X(i,2)+0.05,num2str(i),'color',1,0,0);endA=X(R,:);row=size(A,1);for i=2:row arrowx,arrowy = dsxy2figxy(g

19、ca,A(i-1:i,1),A(i-1:i,2);%坐標轉換 annotation('textarrow',arrowx,arrowy,'HeadWidth',8,'color',0,0,1);endhold offxlabel('橫坐標')ylabel('縱坐標')title('軌跡圖')box on4.1.6 輸出路徑函數 將得到的路徑輸出顯示在Command Window 中，函數名為OutputPath。function p=OutputPath(R)% 輸出路徑函數%輸入：R 路徑R=R,

20、R(1);N=length(R);p=num2str(R(1);for i=2:N p=p,'>',num2str(R(i);enddisp(p)4.1.7 可行解路線長度函數 計算可行解的路線長度函數為PathLength ，程序代碼如下：function len=PathLength(D,Chrom)% 計算各個體的路徑長度% 輸入：% D 兩兩城市之間的距離% Chrom 個體的軌跡row,col=size(D);NIND=size(Chrom,1);len=zeros(NIND,1);for i=1:NIND p=Chrom(i,:) Chrom(i,1); i1

21、=p(1:end-1); i2=p(2:end); len(i,1)=sum(D(i1-1)*col+i2);end4.1.8 模擬退火算法的主函數 模擬退火算法參數設置如表一所列。 表一 參數設定 降溫速率q 初始溫度T0 結束溫度Tend 鏈長L 0.9 1000 0.001 200clc;clear;close all;%ticT0=1000; % 初始溫度Tend=1e-3; % 終止溫度L=500; % 各溫度下的迭代次數（鏈長）q=0.9; %降溫速率% 加載數據load CityPosition1;%D=Distanse(X); %計算距離矩陣N=size(D,1); %城市的個

22、數% 初始解S1=randperm(N); %隨機產生一個初始路線% 畫出隨機解的路徑圖DrawPath(S1,X)pause(0.0001)% 輸出隨機解的路徑和總距離disp('初始種群中的一個隨機值:')OutputPath(S1);Rlength=PathLength(D,S1);disp('總距離：',num2str(Rlength);% 計算迭代的次數TimeTime=ceil(double(solve('1000*(0.9)x=',num2str(Tend);count=0; %迭代計數Obj=zeros(Time,1); %目標值

23、矩陣初始化track=zeros(Time,N); %每代的最優路線矩陣初始化% 迭代while T0>Tend count=count+1; %更新迭代次數 主函數代碼如下： temp=zeros(L,N+1); for k=1:L % 產生新解 S2=NewAnswer(S1); % Metropolis法則判斷是否接受新解 S1,R=Metropolis(S1,S2,D,T0); %Metropolis 抽樣算法 temp(k,:)=S1 R; %記錄下一路線的及其路程 end % 記錄每次迭代過程的最優路線 d0,index=min(temp(:,end); %找出當前溫度下最優

24、路線 if count=1 | d0<Obj(count-1) Obj(count)=d0; %如果當前溫度下最優路程小于上一路程則記錄當前路程 else Obj(count)=Obj(count-1);%如果當前溫度下最優路程大于上一路程則記錄上一路程 end track(count,:)=temp(index,1:end-1); %記錄當前溫度的最優路線 T0=q*T0; %降溫 fprintf(1,'%dn',count) %輸出當前迭代次數end% 優化過程迭代圖figureplot(1:count,Obj)xlabel('迭代次數')ylabel

25、('距離')title('優化過程')% 最優解的路徑圖DrawPath(track(end,:),X)% 輸出最優解的路線和總距離disp('最優解:')S=track(end,:);p=OutputPath(S);disp('總距離：',num2str(PathLength(D,S);disp('-')toc4.2仿真結果及分析優化前的一個隨機路線圖如圖4所示： 圖4總路線距離約為57.00優化以后的最優解路線如下圖5： 圖5該優化路徑的總路程近似為30.00，已為最優解。模擬退火算法進化過程圖如下圖6：由圖可

26、以看出，優化前后路徑長度得到很大改進，變為原來的52.4%，65代以后路徑長度已經保持不變了，可以認為已經是最優解了。 上圖為用模擬退火算法解決TSP的GUI（Graphics User Interface,圖形用戶界面）。這是由14個城市構成的一個對稱TSP實例，利用上述算法對該實例進行模擬退火求解，設定初始溫度T0=1000，冷卻速率為0.9，經過仿真得到的最優解與已知最優解非常接近，所需時間也令人滿意。五 、體會使用MATIAB對求解TSP問題的模擬退火算法程序進行了仿真。平均結果表明，首先該算法能夠找到TSP問題的最優解，說明算法的正確性。其次算法對TSP問題的求解時間并不呈指數增長，

27、說明了算法的有效性。5.1關于MATLAB的體會MATLAB 是當今科學界最具影響力、也是最具活力的軟件，它起源于矩陣運算，并已經發展成一種高度集成的計算機語言。 然后，了解到了MATLAB軟件的功能。它提供了強大的科學運算、靈活的程序設計流程、高質量的圖形可視化與界面設計、便捷的與其他程序和語言接口的功能。我們應該熟練掌握其使用方法。5.2關于基于模擬退火算法的TSP算法的體會 模擬退火算法是依據Metropolis準則接受新解，該準則除了接受優化解外，還在一定的限定范圍內接受劣解，這正是模擬退火算法與局部搜索法的本質區別，在避免陷入局部極小值、提高解空間的搜索能力和擴大搜索范圍方面具有明顯的優越性。本次設計給出了一種TSP的求解算法，并用MATLAB語言編程實現了算法。算法實驗結果表明，對大多數組合優化問題而言，模擬退火算法在求最優解和求解時間均達到了滿意的結果。利用MATLAB語言實現的模擬退火程序，能夠找到系統的最優解，仿真結果證明了該方法的有效性。采用該方法既可使我們熟悉MATLAB語言，又可以加深對模擬