【正文】 大學本科畢業(yè)論文 8 第 3 章 TSP 問題及研究的基本方法 TSP問題概述 旅行商問題 (Travelling Salesman Problem，簡記 TSP) 經典說法為：有一名旅行商要從一個城市去若干個城市推銷貨物，從城市 A 出發(fā)，經其余各城 市且每個城市只能訪問一次，然后回到城市 A，問選擇怎樣的旅行路線，才能使旅行的總長度最短 (各城市間距離為已知 )。 TSP的應用與價值 TSP 在現實生活中有很多應用。在當前，很多的現實事物，包括城市，建筑和地標都已經有了平面電子地圖。一些機器的目標就是為了在某種材料片上鉆削不同的孔。鉆頭的重定位所消耗的時間依賴于鉆頭需要移動的距離。 福建農林大學本科畢業(yè)論文 9 TSP問題的數學模型 TSP 問題的數學模型如下：設有 n個城 市，尋找一條巡回路徑 T=(t1， t2，．．．， tn)，使得下列目標函數最?。? f(T)= ???1n1di(ti,ti+1)+d(tn,t1) 其中 ti為 城 市號，取值為 1 到 n 之間的自然數， d(i,j)為城市 i 和城市 j 之間的距離，對于對稱式 TSP，有 d(i， j)=d(j， i)。對于具有一個城市的 TSP 問題，其可能的路徑數目為 (n1)!／ 2， 5 個城市的情形對應120／ 10=12 條路線， 10個城市的情景對應 3628800／ 20=181440 條路線?？焖佟⒂行У亟鉀Q TSP 問題有著極高的實際應用價值，也就吸引了眾多領域的學者對它進行研究。 (2)兩個城市間的距離是非對稱的 ,它所對應的是圖論中的有向圖 . 從問題本身的限制條件的強弱 ,可分為三類 : (但是一般都要求城市間的費用不為負數 ),只是給出距離矩陣 ,求最小回路 。 雖然傳統(tǒng)算法能夠找 TSP 問題的最優(yōu)解，但隨著問題規(guī)模的不斷增長，算法所需要的時間非常巨大，因此只適用于求解規(guī)模較小的 TSP 問題。此方法需較 強技術性，禁忌長度較難取。 (3)蟻群算法 又稱 螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機率型算法。為了避免螞蟻兩次走上同 一條路徑 ( 非法路徑 ) ， 為每個螞蟻設置一個禁忌表以記錄它福建農林大學本科畢業(yè)論文 11 已走過的路徑。人工神經網絡算法成為近年來的熱點研究領域，涉及到 數學 、電氣工程、 計算機工程 、 物理學 等諸多學科，其應用領域包括了建模、時間序列分析、模式識別和控制等，并且仍然在一斷擴展。 TSP問題因其典型性已成為各種啟發(fā)式的搜索，優(yōu)化算法的間接比較標準，而遺傳算法方法就本質來說，主要處理復雜問題的一個魯棒性強的啟發(fā)式隨機搜索算法。編碼機制的主要工作是把對象抽象為由特定符號按一定順序排成的串。這個初始群體也就是問題假設解得集合。適應度較高的物種將會得到更多的繁殖的機會；從而導致適應度低的物種被淘汰。 int start,end。 for(j=1。 cityDistance[i]=cityDistance[i]+CityDistance[start][end]。常用的選擇可略包括以下幾種： (1) 輪盤賭法。 (5) 排序選擇方法。設群體大小為 N，個體 i 的適應度值 Fi，則個體 i 被選擇的概率 Psi為： Psi=Fi／ ??nj j1F (n=l， 2?．． n) 顯然，概率 Psi反映了個體 i的適應度在整個群體的個體適應度總和中所占的比例。 void Select(PTSP city) { //選擇算子 double tempRand,tempflag1。i++)//選 POPSIZE 次 { tempRand=(rand()%100000)/*3。amp。amp。針對這一問題，當然可以采取上述構造懲罰函數的方法，但是實驗效果不佳。 void Cross(PTSP city,double pc) {//交叉概率是 pc int crossNum,i。 for(i=0。 }while(tempXuh[0]==tempXuh[1])。 在遺傳算法中，變異操作并不是最主要的。 int selCity。 }while(selCity==cityBestFitCityXuh)。 福建農林大學本科畢業(yè)論文 18 //swich temp=citycolony[selCity][changePoint[0]]。種群個體過少會導致算法過早收斂，從而陷入局部最優(yōu)解，難以獲得全局最優(yōu)解。從而降低了其抑制早熟的能力。但也不能過大，過大可能會破壞種群中的優(yōu)秀個體。在求解的質量和優(yōu)化效率上都表現出了比較突出的能力。所以，應在算法中引入一些啟發(fā)式的算 子，能夠很好的保留父代的優(yōu)秀基因，以此提高遺傳算法的尋優(yōu)能力。還有不少其它的方法和策略可用于解決 TSP 問題，如模擬退火算法、濃度控制策略等都取得了很好的效果。在整個畢業(yè)設計的過程中給了我巨大的幫助。 福建農林大學本科畢業(yè)論文 23 附錄程序 // include include include include define CITY_NUM 10 //城市編號是 0~CITY_NUM1 define POPSIZE 50 define MAXVALUE 10000 //路徑越短越好 define MAXSAMETIME 15 //結果沒有改變的最大次數 define N 1//需要根據實際求得的路徑值修正 unsigned seed=(unsigned)time(0)。//城市種群 ,默認出發(fā)城市編號為 0，則城市編號的最后一個城市還應該為 0 double fitness[POPSIZE]。//最優(yōu)路徑適應值 double BestValue。 //計算城市的距離 福建農林大學本科畢業(yè)論文 24 void CalculatDist( ) { int i,j。i++){ for(j=0。 CityDistance[i][j]=sqrt(temp1*temp1+temp2*temp2)。i++){ if(k==citycolony[pop][i]) return true。iPOPSIZE。 cityBestFitness=0。jCITY_NUM。 } } } //求適應值 void CalFitness(PTSP city) { int i,j。i++){ //求適應值 cityDistance[i]=0。end=citycolony[i][j]。 for(i=1。 }*/ } return。iPOPSIZE。jPOPSIZEamp。 //if(i!=cityBestFitCityXuh) if(cityfitness[j]=cityfitness[i]amp。 }//Select() void copyCityXuhToCityColony(int tempcityxuh[][CITY_NUM+1],int *tempXuh,PTSP city) { int i,h。iCITY_NUM。i=countCrossGene。 } }//exchgTempcityxuh() void crossTwo(PTSP city,int *tempXuh,int cityCross[][CITY_NUM+1]) //交叉操作 { int genePoint[2],temp1,countCrossGene,flaglike。 do { genePoint[0]=rand()%(CITY_NUM1)。genePoint[0]=genePoint[1]。k2。jCITY_NUM。 cityCross[k][j]=CITY_NUM。h++) //{ for(k=0。i=genePoint[1]。i=CITY_NUM1。i=CITY_NUM1。amp。h++) { k=countCrossGene。 for(j=1。j++) { if(tempcityxuh[h][i]==tempcityxuh[(h+1)%2][j]) { flaglike=1。 return。h++) { for(i=0。 }//copyCityXuhTo() //交叉操作 福建農林大學本科畢業(yè)論文 30 void Cross(PTSP city,double pc) {//交叉概率是 pc int crossNum,i。 for(i=0。 }while(tempXuh[0]==tempXuh[1])。 int selCity。 }while(selCity==cityBestFitCityXuh)。 //swich temp=citycolony[selCity][changePoint[0]]。 changePoint[1]=rand()%(CITY_NUM1)+1。j=int(POPSIZE*pm)。 crossTwo(city,tempXuh,cityCross)。i++) { tempXuh[0]=rand()%(POPSIZE1)。 int tempXuh[2]。i++) { cityCross[h][i]=citycolony[tempXuh[h]][i]。 for(h=0。} } }//forh } //exchgTempcityxuh(tempcityxuh,countCrossGene)。amp。i=countCrossGene。 } } }//for k // } if(samePoint!=0)//cross { 福建農林大學本科畢業(yè)論文 29 for(h=0。amp。 cityCross[k][i]=0。 cityCross[(k+1)%2][i]=0。k++)//one { j=1。 //for(h=0。amp。i=genePoint[1]。} countCrossGene=genePoint[1]genePoint[0]。 }while(genePoint[0]==genePoint[1]||genePoint[0]==0||genePoint[1]==0)。 int i,j,k,h。 tempcityxuh[0][i]=tempcityxuh[1][i]。 } } }//copyCityXuhToCityColony() void exchgTempcityxuh(int tempcityxuh[][CITY_NUM+1],int countCrossGene) { 福建農林大學本科畢業(yè)論文 27 int i,temp。h2。i!=j) { copyColony(i,j,city)。tempflag1==0。 tempflag1=0。 int i,j。i++) { citycolony[toc][i]=citycolony[fromc][i]。 } cityfitness[i]=N/(cityDistance[i])。j=CITY_NUM。 for(i=0。//產生 1～ CITY_NUM1之間的隨機數 while(check(city,i,j,r)){ r=rand()%(CITY_NUM1)+1。iPOPSIZE。 citycolony[i][CITY_NUM]=0。//新生成節(jié)點沒有存在于已經生成的路徑中 } void InitColony(PTSP city)//初始化城市，隨機生成數據 { int i,j,r。 for(i=0。j++){//最后一個城市還應該返回到出發(fā)節(jié)點 temp1=CityPos[j][0]CityPos[i][0]。 for(i=0。 int BestFitCityXuh。//路徑實際長度 int BestRooting[CITY_NUM+1]。 double CityDistance[CITY_NUM][CITY_NUM]。在此，感謝 ,所有福建農林大學的老師 ,感謝他們給予了我巨大幫助。 福建農林大學本科畢業(yè)論文 21 參 考 文 獻 [1] 黃厚生．求解旅行商問題的新方法研究 [J]．天津：天津大學管理學院， 2020： 1． 20． [2] 高經維 ,張煦 ,李峰 ,趙暉