【正文】 //swich temp=citycolony[selCity][changePoint[0]]。 changePoint[1]=rand()%(CITY_NUM1)+1。 }while(selCity==cityBestFitCityXuh)。j=int(POPSIZE*pm)。 int selCity。 crossTwo(city,tempXuh,cityCross)。 }while(tempXuh[0]==tempXuh[1])。i++) { tempXuh[0]=rand()%(POPSIZE1)。 for(i=0。 int tempXuh[2]。 }//copyCityXuhTo() //交叉操作 福建農(nóng)林大學(xué)本科畢業(yè)論文 30 void Cross(PTSP city,double pc) {//交叉概率是 pc int crossNum,i。i++) { cityCross[h][i]=citycolony[tempXuh[h]][i]。h++) { for(i=0。 for(h=0。 return。} } }//forh } //exchgTempcityxuh(tempcityxuh,countCrossGene)。j++) { if(tempcityxuh[h][i]==tempcityxuh[(h+1)%2][j]) { flaglike=1。amp。 for(j=1。i=countCrossGene。h++) { k=countCrossGene。 } } }//for k // } if(samePoint!=0)//cross { 福建農(nóng)林大學(xué)本科畢業(yè)論文 29 for(h=0。amp。amp。i=CITY_NUM1。 cityCross[k][i]=0。i=CITY_NUM1。 cityCross[(k+1)%2][i]=0。i=genePoint[1]。k++)//one { j=1。h++) //{ for(k=0。 //for(h=0。 cityCross[k][j]=CITY_NUM。amp。jCITY_NUM。i=genePoint[1]。k2。} countCrossGene=genePoint[1]genePoint[0]。genePoint[0]=genePoint[1]。 }while(genePoint[0]==genePoint[1]||genePoint[0]==0||genePoint[1]==0)。 do { genePoint[0]=rand()%(CITY_NUM1)。 int i,j,k,h。 } }//exchgTempcityxuh() void crossTwo(PTSP city,int *tempXuh,int cityCross[][CITY_NUM+1]) //交叉操作 { int genePoint[2],temp1,countCrossGene,flaglike。 tempcityxuh[0][i]=tempcityxuh[1][i]。i=countCrossGene。 } } }//copyCityXuhToCityColony() void exchgTempcityxuh(int tempcityxuh[][CITY_NUM+1],int countCrossGene) { 福建農(nóng)林大學(xué)本科畢業(yè)論文 27 int i,temp。iCITY_NUM。h2。 }//Select() void copyCityXuhToCityColony(int tempcityxuh[][CITY_NUM+1],int *tempXuh,PTSP city) { int i,h。i!=j) { copyColony(i,j,city)。 //if(i!=cityBestFitCityXuh) if(cityfitness[j]=cityfitness[i]amp。tempflag1==0。jPOPSIZEamp。 tempflag1=0。iPOPSIZE。 int i,j。 }*/ } return。i++) { citycolony[toc][i]=citycolony[fromc][i]。 for(i=1。 } cityfitness[i]=N/(cityDistance[i])。end=citycolony[i][j]。j=CITY_NUM。i++){ //求適應(yīng)值 cityDistance[i]=0。 for(i=0。 } } } //求適應(yīng)值 void CalFitness(PTSP city) { int i,j。//產(chǎn)生 1～ CITY_NUM1之間的隨機(jī)數(shù) while(check(city,i,j,r)){ r=rand()%(CITY_NUM1)+1。jCITY_NUM。iPOPSIZE。 cityBestFitness=0。 citycolony[i][CITY_NUM]=0。iPOPSIZE。//新生成節(jié)點(diǎn)沒有存在于已經(jīng)生成的路徑中 } void InitColony(PTSP city)//初始化城市，隨機(jī)生成數(shù)據(jù) { int i,j,r。i++){ if(k==citycolony[pop][i]) return true。 for(i=0。 CityDistance[i][j]=sqrt(temp1*temp1+temp2*temp2)。j++){//最后一個(gè)城市還應(yīng)該返回到出發(fā)節(jié)點(diǎn) temp1=CityPos[j][0]CityPos[i][0]。i++){ for(j=0。 for(i=0。 //計(jì)算城市的距離 福建農(nóng)林大學(xué)本科畢業(yè)論文 24 void CalculatDist( ) { int i,j。 int BestFitCityXuh。//最優(yōu)路徑適應(yīng)值 double BestValue。//路徑實(shí)際長度 int BestRooting[CITY_NUM+1]。//城市種群 ,默認(rèn)出發(fā)城市編號為 0，則城市編號的最后一個(gè)城市還應(yīng)該為 0 double fitness[POPSIZE]。 double CityDistance[CITY_NUM][CITY_NUM]。 福建農(nóng)林大學(xué)本科畢業(yè)論文 23 附錄程序 // include include include include define CITY_NUM 10 //城市編號是 0~CITY_NUM1 define POPSIZE 50 define MAXVALUE 10000 //路徑越短越好 define MAXSAMETIME 15 //結(jié)果沒有改變的最大次數(shù) define N 1//需要根據(jù)實(shí)際求得的路徑值修正 unsigned seed=(unsigned)time(0)。在此，感謝 ,所有福建農(nóng)林大學(xué)的老師 ,感謝他們給予了我巨大幫助。在整個(gè)畢業(yè)設(shè)計(jì)的過程中給了我巨大的幫助。 福建農(nóng)林大學(xué)本科畢業(yè)論文 21 參 考 文 獻(xiàn) [1] 黃厚生．求解旅行商問題的新方法研究 [J]．天津：天津大學(xué)管理學(xué)院， 2020： 1． 20． [2] 高經(jīng)維 ,張煦 ,李峰 ,趙暉 .求解 TSP 問題的遺傳算法實(shí)現(xiàn) [J].計(jì)算機(jī)時(shí)代 ,2020 ,2:1921. [3] 周明 ,孫樹棟 .遺傳算法原理及應(yīng)用 [M].國防工業(yè)出版社 .1999. [4] 柳林，楊峰．求解 TSP 問題的改進(jìn)遺傳算法研究．計(jì)算機(jī)工程與 用， 2020， 42(20)：5557． [5] 陳靜．改進(jìn)遺傳算法及其在旅行推銷商問題中的應(yīng)用研究： (碩士學(xué)位論文 )．重慶：重慶大學(xué) 計(jì) 算機(jī)學(xué)院， 2020． [6] 徐麗佳，蒲海波，蔣宏?。倪M(jìn)遺傳算法的路徑規(guī)劃研究．微計(jì)算機(jī)信息． 2020(5).215253． [7] 趙振勇，王力，王保華等．遺傳算法改進(jìn)策略的研究．計(jì)算機(jī)應(yīng)用． 2020，26(12)． 189191． [8] Aytug H．， Koehler GJ． Stopping criteria for finite length geical gorithms[J]． ORASJofComputation， 1996， (8)： 183— 191． [9] 柳林，楊峰．求解 TSP 問題的改進(jìn)遺傳算法研究．計(jì)算機(jī)工程與應(yīng)用， 2020， 42(20)：5557． [10] 段海濱 .人生智能計(jì)算 .北京： 科學(xué)出版社 .2020 [11] 王超學(xué)，崔杜武，王竹榮，費(fèi)蓉．一種求解 TSP 的高效遺傳算法 [J]．西安 理工 大學(xué)學(xué)報(bào)， 2020． 1(22) [12] 韋雪潔，黎明，劉高杭，田貴超．基于知識庫求解 TSP 問題的改進(jìn)遺傳 [J]．計(jì)算機(jī)仿真， 2020， 08： 161— 163． [13] 梁艷春 ， 群 智能優(yōu)化算法及其應(yīng)用 [M]．北京：科學(xué) 出版社， 2020 [14] 紀(jì)震，廖惠連，吳青華，粒子群算法及應(yīng)用，北京：科學(xué)出版社， 2020 [15] 張軍，計(jì)算智能，北京 ： 清華大學(xué)出版社， 2020 [16]王耀南，智能控制理論及應(yīng)用，北京：機(jī)械工業(yè)出版社， 2020 福建農(nóng)林大學(xué)本科畢業(yè)論文 22 致 謝 大學(xué)本科的學(xué)習(xí)即將結(jié)束，在此首先感 謝所有曾經(jīng)教導(dǎo)過我的老師。還有不少其它的方法和策略可用于解決 TSP 問題，如模擬退火算法、濃度控制策略等都取得了很好的效果。 (2)如何獲得更好的性能是用算法解決實(shí)際問題時(shí)必須要考慮的，如針對具體問題開發(fā)相應(yīng)的初始群體的生成技術(shù)，更好的交叉、變異算子的設(shè)計(jì)，控制參數(shù)的選擇等，都是需要進(jìn)一步深入研究的重要課 題。所以，應(yīng)在算法中引入一些啟發(fā)式的算 子，能夠很好的保留父代的優(yōu)秀基因，以此提高遺傳算法的尋優(yōu)能力。如種群大小影響了種群的多樣性，過少會導(dǎo)致算法陷入局部最優(yōu)，而找不到全局最優(yōu)解，過多大大的增加算法的計(jì)算量，增大機(jī)器開銷，算法效率低下。在求解的質(zhì)量和優(yōu)化效率上都表現(xiàn)出了比較突出的能力。 福建農(nóng)林大學(xué)本科畢業(yè)論文 20 結(jié) 論 本文通過遺傳算法求解 TSP 問題，成功獲得了全局最優(yōu)解。但也不能過大，過大可能會破壞種群中的優(yōu)秀個(gè)體。在本算法中變異率因取 到 為宜。從而降低了其抑制早熟的能力。一般的 10個(gè)點(diǎn)城市，初始種群取 50 到 100為好。種群個(gè)體過少會導(dǎo)致算法過早收斂，從而陷入局部最優(yōu)解，難以獲得全局最優(yōu)解。 citycolony[selCity][changePoint[1]]=temp。 福建農(nóng)林大學(xué)本科畢業(yè)論文 18 //swich temp=citycolony[selCity][changePoint[0]]。 changePoint[1]=rand()%(CITY_NUM1)+1。 }while(selCity==cityBestFitCityXuh)。j=int(POPSIZE*pm)。 int selCity。變異操作是改善遺傳算法的局部搜索能力和維持群體的多樣性防止早熟現(xiàn)象。 在遺傳算法中，變異操作并不是最主要的。 crossTwo(city,tempXuh,cityCross)。 }while(tempXuh[0]==tempXuh[1])。i++) { tempXuh[0]=rand()%(POPSIZE1)。 for(i=0。 int tempXuh[2]。 void Cross(PTSP city,double pc) {//交叉概率是 pc int crossNum,i。 這 是 在選中用于繁 殖下一代的個(gè)體中，對兩個(gè)不同的個(gè)體的相同位置的基因進(jìn)行交換，從而產(chǎn)生新的個(gè)體，也即對兩個(gè)父染色體的部分結(jié)構(gòu)進(jìn)行重組，以產(chǎn)生新一代子染色體。針對這一問題，當(dāng)然可以采取上述構(gòu)造懲罰函數(shù)的方法，但是實(shí)驗(yàn)效果不佳。 } } } } return。amp。j++) { if(tempRand=cityaddFitness[j])//輪盤賭選中第 j個(gè) { 福建農(nóng)林大學(xué)本科畢業(yè)論文 15