基于模擬退火算法的TSP算法

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

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

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

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

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

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

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

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

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

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

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

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

13、 |1|10|2|4|5|6|8|7|9|3就是一個合法的解，采用產(chǎn)生隨機(jī)排列的方法產(chǎn)生一個初始解S。 （3）解變換生成新解 通過對當(dāng)前解S1進(jìn)行變換，產(chǎn)生新的路徑數(shù)組即新解，這里采用的變換是產(chǎn)生隨機(jī)數(shù)的方法來產(chǎn)生將要交換的兩個城市，用二鄰域變換法產(chǎn)生新的路徑，即新的可行解S2。 例如n=10時(shí)，產(chǎn)生兩個1,10范圍內(nèi)的隨機(jī)整數(shù)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準(zhǔn)則 若路徑長度函數(shù)為（S），新解的路徑為（S2），路徑差為d=（S2）-（S1）,

14、則Metropolis準(zhǔn)則為 如果df<0,則以概率1接受新路線，否則以概率exp（-df/T）接受新路線。 （5）降溫 利用降溫速率q進(jìn)行降溫，即T=qT,若T小于結(jié)束溫度，則停止迭代輸出當(dāng)前狀態(tài)，否則繼續(xù)迭代。 四 、設(shè)計(jì)結(jié)果及分析4.1 MATLAB程序?qū)崿F(xiàn)及主函數(shù)4.1.1 計(jì)算距離矩陣 利用給出的N個城市的坐標(biāo)，算出N個城市的兩兩之間的距離，得到距離矩陣（NN）。計(jì)算函數(shù)為Distance，得到初始群種。程序如下function D=Distanse(a)% 計(jì)算兩兩城市之間的距離%輸入 a 各城市的位置坐標(biāo)%輸出 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 初始解 初始解的產(chǎn)生直接使用MATLAB自帶的函數(shù)randperm，如城市格式為N個，則產(chǎn)生初始解：S1=randperm（N）； %隨機(jī)產(chǎn)生一個初始路線 4.1.3 生成新解 解變換生成新解函數(shù)為NewAnswer，程序代碼如下：function S2=NewAnswer(S1)% 輸入% S1:當(dāng)前解% 輸出% S2：新解N=length(S1);S2=S1; a=round(

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

17、個數(shù) R2=PathLength(D,S2); %計(jì)算路線長度dC=R2-R1; %計(jì)算能力之差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 畫路線軌跡圖 畫出給的路線的軌跡圖函數(shù)為DrawPath，程序代碼如下：function DrawPath(Chrom,X)% 畫路徑函數(shù)%輸入% Chrom 待畫路徑 % X 各城市坐標(biāo)位置R=Chrom(1,:) Chrom(1,1); %一個隨

18、機(jī)解(個體)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);%坐標(biāo)轉(zhuǎn)換 annotation('textarrow',arrowx,arrowy,'HeadWidth',8,'color',0,0,1);endhold offxlabel('橫坐標(biāo)')ylabel('縱坐標(biāo)')title('軌跡圖')box on4.1.6 輸出路徑函數(shù) 將得到的路徑輸出顯示在Command Window 中，函數(shù)名為OutputPath。function p=OutputPath(R)% 輸出路徑函數(shù)%輸入：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 可行解路線長度函數(shù) 計(jì)算可行解的路線長度函數(shù)為PathLength ，程序代碼如下：function len=PathLength(D,Chrom)% 計(jì)算各個體的路徑長度% 輸入：% 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 模擬退火算法的主函數(shù) 模擬退火算法參數(shù)設(shè)置如表一所列。 表一 參數(shù)設(shè)定 降溫速率q 初始溫度T0 結(jié)束溫度Tend 鏈長L 0.9 1000 0.001 200clc;clear;close all;%ticT0=1000; % 初始溫度Tend=1e-3; % 終止溫度L=500; % 各溫度下的迭代次數(shù)（鏈長）q=0.9; %降溫速率% 加載數(shù)據(jù)load CityPosition1;%D=Distanse(X); %計(jì)算距離矩陣N=size(D,1); %城市的個

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

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

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

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

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

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