人工智能原理實驗報告模擬退火算法解決TSP問題目錄TOC\o"1-3"\h1旅行商問題和模擬退火算法11.1旅行商問題1旅行商問題的描述11.2模擬退火算法1根本思想12TSP模擬退火算法的實現(xiàn)22.1TSP算法實現(xiàn)2TSP算法描述2TSP算法流程32.2TSP的C實現(xiàn)42.2.1加載數(shù)據(jù)文件4計算總距離的函數(shù)5交換城市的函數(shù)5執(zhí)行模擬退火的函數(shù)52.3實驗結果62.4小結63源代碼61旅行商問題和模擬退火算法1.1旅行商問題旅行商問題的描述旅行商問題〔TravelingSalesmanProblem，簡稱TSP〕又名貨郎擔問題，是威廉·哈密爾頓爵士和英國數(shù)學家克克曼()于19世紀初提出的一個數(shù)學問題，也是著名的組合優(yōu)化問題。問題是這樣描述的：一名商人要到假設干城市去推銷商品，城市個數(shù)和各城市間的路程〔或旅費〕，要求找到一條從城市1出發(fā)，經(jīng)過所有城市且每個城市只能訪問一次，最后回到城市1的路線，使總的路程〔或旅費〕最小。TSP剛提出時，不少人認為這個問題很簡單。后來人們才逐步意識到這個問題只是表述簡單，易于為人們所理解，而其計算復雜性卻是問題的輸入規(guī)模的指數(shù)函數(shù)，屬于相當難解的問題。這個問題數(shù)學描述為：假設有n個城市，并分別編號，給定一個完全無向圖G=〔V，E〕，V={1，2，…，n}，n>1。其每一邊(i,j)E有一非負整數(shù)消耗Ci,j(即上的權記為Ci,j，i，jV)。并設G的一條巡回路線是經(jīng)過V中的每個頂點恰好一次的回路。一條巡回路線的消耗是這條路線上所有邊的權值之和。TSP問題就是要找出G的最小消耗回路。1.2模擬退火算法模擬退火算法由KirkPatrick于1982提出[7]，他將退火思想引入到組合優(yōu)化領域,提出一種求解大規(guī)模組合優(yōu)化問題的方法，對于NP-完全組合優(yōu)化問題尤其有效。模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其緩慢降溫(即退火)，使之到達能量最低點。反之，如果急速降溫(即淬火)那么不能到達最低點。加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而緩慢降溫時粒子漸趨有序，在每個溫度上都到達平衡態(tài)，最后在常溫時到達基態(tài)，內(nèi)能減為最小。根據(jù)Metropolis準那么，粒子在溫度T時趨于平衡的概率為exp(-E/(kT))，其中E為溫度T時的內(nèi)能，E為其改變量，k為Boltzmann常數(shù)。用固體退火模擬組合優(yōu)化問題，將內(nèi)能E模擬為目標函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對當前解重復產(chǎn)生“新解→計算目標函數(shù)差→接受或舍棄”的迭代，并逐步衰減t值，算法終止時的當前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索過程。退火過程由冷卻進度表(CoolingSchedule)控制，包括控制參數(shù)的初值t及其衰減因子a、每個t值時的迭代次數(shù)L和停止條件C。根本思想模擬退火算法可以分解為解空間、目標函數(shù)和初始解3局部。其根本思想是：(1)初始化：初始溫度T(充分大)，初始解狀態(tài)s(是算法迭代的起點)，每個T值的迭代次數(shù)L；(2)對k=1，……，L做第(3)至第6步；(3)產(chǎn)生新解s′；(4)計算增量cost=cost(s′)-cost(s)，其中cost(s)為評價函數(shù)；(5)假設t′0那么接受s′作為新的當前解，否那么以概率exp(-t′/T)接受s′作為新的當前解；(6)如果滿足終止條件那么輸出當前解作為最優(yōu)解，結束程序。終止條件通常取為連續(xù)假設干個新解都沒有被接受時終止算法；(7)T逐漸減少，且T趨于0，然后轉第2步運算。具體如下〔1〕新解的產(chǎn)生和接受模擬退火算法新解的產(chǎn)生和接受可分為如下4個步驟：①由一個函數(shù)從當前解產(chǎn)生一個位于解空間的新解。為便于后續(xù)的計算和接受，減少算法耗時，常選擇由當前新解經(jīng)過簡單地變換即可產(chǎn)生新解的方法，如對構成新解的全部或局部元素進行置換、互換等。產(chǎn)生新解的變換方法決定了當前新解的鄰域結構，因而對冷卻進度表的選取有一定的影響。②計算與新解所對應的目標函數(shù)差。因為目標函數(shù)差僅由變換局部產(chǎn)生，所以目標函數(shù)差的計算最好按增量計算。事實說明，對大多數(shù)應用而言，這是計算目標函數(shù)差的最快方法。③判斷新解是否被接受。判斷的依據(jù)是一個接受準那么，最常用的接受準那么是Metropo1is準那么：假設t′0那么接受S′作為新的當前解S，否那么以概率exp(-t′/T)接受S′作為新的當前解S。④當新解被確定接受時，用新解代替當前解。這只需將當前解中對應于產(chǎn)生新解時的變換局部予以實現(xiàn)，同時修正目標函數(shù)值即可。此時，當前解實現(xiàn)了一次迭代，可在此根底上開始下一輪試驗。而當新解被判定為舍棄時，那么在原當前解的根底上繼續(xù)下一輪試驗。模擬退火算法與初始值無關，算法求得的解與初始解狀態(tài)S(是算法迭代的起點)無關；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。〔2〕參數(shù)控制問題模擬退火算法的應用很廣泛，可以求解NP完全問題，但其參數(shù)難以控制，其主要問題有以下3點[7]：①溫度T的初始值設置。溫度T的初始值設置是影響模擬退火算法全局搜索性能的重要因素之一。初始溫度高，那么搜索到全局最優(yōu)解的可能性大，但因此要花費大量的計算時間；反之，那么可節(jié)約計算時間，但全局搜索性能可能受到影響。實際應用過程中，初始溫度一般需要依據(jù)實驗結果進行假設干次調(diào)整。②溫度衰減函數(shù)的選取。衰減函數(shù)用于控制溫度的退火速度，一個常用的函數(shù)為：式中是一個非常接近于1的常數(shù)，t為降溫的次數(shù)。③馬爾可夫鏈長度L的選取。通常的原那么是：在衰減參數(shù)T的衰減函數(shù)已選定的前提下，L的選取應遵循在控制參數(shù)的每一取值上都能恢復準平衡的原那么。2TSP模擬退火算法的實現(xiàn)TSP是典型的組合優(yōu)化問題，模擬退火算法是一種隨機性解決組合優(yōu)化方法。將TSP與模擬退火算法相結合，以實現(xiàn)對其求解。2.1TSP算法實現(xiàn)TSP算法描述〔1〕TSP問題的解空間和初始解TSP的解空間S是遍訪每個城市恰好一次的所有回路，是所有城市排列的集合。TSP問題的解空間S可表示為{1,2,…,n}的所有排列的集合，即S={(c1,c2,…,cn)|((c1,c2,…,cn)為{1,2,…,n}的排列〕}，其中每一個排列Si表示遍訪n個城市的一個路徑，ci=j表示在第i次訪問城市j。模擬退火算法的最優(yōu)解與初始狀態(tài)無關，故初始解為隨機函數(shù)生成一個{1,2,…,n}的隨機排列作為S0?！?〕目標函數(shù)TSP問題的目標函數(shù)即為訪問所有城市的路徑總長度，也可稱為代價函數(shù)：現(xiàn)在TSP問題的求解就是通過模擬退火算法求出目標函數(shù)C(c1,c2,…,cn)的最小值，相應地，s*=(c*1,c*2,…,c*n)即為TSP問題的最優(yōu)解。〔3〕新解產(chǎn)生新解的產(chǎn)生對問題的求解非常重要。新解可通過分別或者交替用以下2種方法產(chǎn)生：①二變換法：任選序號u,v(設uvn)，交換u和v之間的訪問順序，假設交換前的解為si=(c1,c2,…,cu,…,cv,…,cn),交換后的路徑為新路徑，即：si′=(c1,…,cu-1,cv,cv-1,…,cu+1,cu,cv+1,…,cn)②三變換法：任選序號u,v和ω(u≤vω)，將u和v之間的路徑插到ω之后訪問，假設交換前的解為si=(c1,c2,…,cu,…,cv,…,cω,…,cn)，交換后的路徑為的新路徑為：si′=(c1,…,cu-1,cv+1,…,cω,cu,…,cv,cω+1,…,cn)〔4〕目標函數(shù)差計算變換前的解和變換后目標函數(shù)的差值：Δc′=c(si′)-c(si)〔5〕Metropolis接受準那么根據(jù)目標函數(shù)的差值和概率exp(-ΔC′/T)接受si′作為新的當前解si，接受準那么：2.1.2TSP算法流程根據(jù)以上對TSP的算法描述，可以寫出用模擬退火算法解TSP問題的流程圖2-1所示：圖2-1TSP的模擬退火流程2.2TSP的C實現(xiàn)2.2.1加載數(shù)據(jù)文件下面是加載數(shù)據(jù)文件的一個例子：中國31省會城市數(shù)據(jù)：[13042312;36391315;41772244;37121399;34881535;33261556;32381229;41961044;4312790;4386570;30071970;25621756;27881491;23811676;1332695;37151678;39182179;40612370;37802212;36762578;40292838;42632931;34291908;3507237633942643;34393201;29353240;31403550;25452357;27782826;23702975];當調(diào)用數(shù)據(jù)文件函數(shù)時，包含城市坐標信息的矩陣載入到數(shù)組中。計算總距離的函數(shù)這是一個城市間計算距離的函數(shù)，根據(jù)給定路徑計算該路徑對應總路程。inlinedoubledist(intx1,inty1,intx2,inty2){returnsqrt(double((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)));}inlinedoubletotaldist(pathp){inti;doublecost=0;for(i=1;i<N;i++){cost+=D[p.City[i]][p.City[i+1]]; }cost+=D[p.City[1]][p.City[N]];returncost;}TSP問題的本錢函數(shù)是城市之間的距離。調(diào)用此函數(shù)將計算n個城市之間的距離。2.2.3交換城市的函數(shù)這是一個用于城市交換的函數(shù)，它從某路徑的鄰域中隨機的選擇一個新的路徑。pathgetnext(pathp){intx,y;pathret;ret=p;do{x=rand()%N+1;y=rand()%N+1;}while(x==y);swap(ret.City[x],ret.City[y]);ret.Length=totaldist(ret);returnret;}2.2.4執(zhí)行模擬退火的函數(shù)voidsa()//退a?火e和¨a降|ì溫?過y程¨?{doubleT;pathnewpath,curpath;inti,A_t=0;doubledelta;T=INIT_T;curpath=F_Path;while(true){for(i=1;i<=IN_K;i++){newpath=getnext(curpath);delta=newpath.Length-curpath.Length;if(delta<0.0){curpath=newpath;A_t=0;}else{doublernd=rand()%10000/10000.0;doublep=exp(-delta/T);if(p>rnd)curpath=newpath;}}if(curpath.Length<F_Path.Length)F_Path=curpath;if(T<FINAL_T)break;T=T*RATE;}}輸入?yún)?shù)：INIT_K那么是開始模擬退火過程的起始溫度。RATE是模擬退火過程的冷卻速率，冷卻速率應該始終低于1。FINAL_T是模擬退火的停止條件。2.3實驗結果2.4小結模擬退火算法是依據(jù)Metropolis準那么接受新解，該準那么除了接受優(yōu)化解外，還在一定的限定范圍內(nèi)接受劣解，此舉防止陷入局部極小值、提高解空間的搜索能力和擴大搜索范圍方面具有明顯的優(yōu)越性；其次，初始溫度T，內(nèi)循環(huán)次數(shù)K，以及溫度衰減率△t的選取對結果影響很大，適當?shù)倪x取很重要。3源代碼#include"stdafx.h"#include<iostream>#include<cmath>#include<time.h>usingnamespacestd;constintMAXN=200;//最大城市數(shù)constdoubleINIT_T=100000;//初始溫度¨constdoubleRATE=0.05;//溫度下降率constdoubleFINAL_T=1E-10;//終止溫度constintIN_K=10000;//內(nèi)層循環(huán)數(shù)structpath{//定義路徑結構類型intCity[MAXN];//依次遍歷的城市的序號doubleLength;//所有城市的總長度};intN;//城市數(shù)量doubleD[MAXN][MAXN];//任意兩個城市之間的距離pathF_Path;//最優(yōu)的遍歷路徑inlinedoubledist(intx1,inty1,intx2,inty2)//計算兩點之間的距離{returnsqrt(double((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)));}inlinedoubletotaldist(pathp)//計算遍歷路徑總長度{inti;doublecost=0;for(i=1;i<N;i++){cost+=D[p.City[i]][p.City[i+1]]; }cost+=D[p.City[1]][p.City[N]];returncost;}voidinit()//讀數(shù)據(jù)，并初始化{intC[MAXN][2];//城市的坐標inti,j;freopen("城市坐標.txt","r",stdin);scanf("%d",&N);for(i=1;i<=N;i++)scanf("%d%d",&C[i][0],&C[i][1]);for(i=1;i<N;i++)//計算任意兩個城市之間的路徑長度for(j=i+1;j<=N;j++){ D[i][j]=D[j][i]=dist(C[i][0],C[i][1],C[j][0],C[j][1]);}for(i=1;i<=N;i++)//最優(yōu)解的初始狀態(tài)F_Path.City[i]=i;F_Path.Length=totaldist(F_Path);srand((unsigned)time(NULL));}pathgetnext(pathp)//新解產(chǎn)生函數(shù){intx,y;pathret;ret=p;do{x=rand()%N+1;y=rand()%N+1;}while(x==y);swap(ret.City[x],ret.City[y]);//交換兩城市之間位置順序ret.Length=totaldist(ret);returnret;}voidsa()//退火和降溫過程{doubleT;//溫度pathnewpath,curpath;//當前路徑和新路徑inti,A_t=0;doubledelta;T=INIT_T;//賦值初始溫度curpath=F_Path;while(true){for(i=1;i<=IN_K;i++){newpath=getnext(curpath);//獲取新路徑delta=newpath.Length-curpath.Length;if(delta<0.0){cur