【導(dǎo)讀】城市，且每個(gè)城市只能訪問(wèn)一次，最后又必須返回出發(fā)城市。要安排其訪問(wèn)次序，使其旅行路線。TSP是經(jīng)典的NP-hard組合優(yōu)化問(wèn)題之一，也是一個(gè)測(cè)試算法優(yōu)劣性的標(biāo)準(zhǔn)問(wèn)題，且現(xiàn)實(shí)中有很多應(yīng)用問(wèn)題都可歸結(jié)或轉(zhuǎn)化為T(mén)SP問(wèn)題。故對(duì)此問(wèn)題的求解具有理論與實(shí)用兩方面。傳統(tǒng)的求解方法在面對(duì)較大規(guī)模的問(wèn)題時(shí)，很不容易得到最優(yōu)解。并行、隨機(jī)和自適應(yīng)搜索算法。特別適合于處理傳統(tǒng)搜索算法解決不好的復(fù)雜和非線形問(wèn)題。的兩個(gè)最大的顯著特點(diǎn)是隱含并行性和全局搜索。對(duì)遺傳算法及其應(yīng)用的研究是目前智能計(jì)算的

　　

【正文】 { i=i。 }*/ } return。 }//copyColony() //選擇算法 void Select(PTSP city) {//選擇算子 double tempRand,tempflag1。 26 int i,j。 for(i=0。iPOPSIZE。i++)//選 POPSIZE 次 { tempRand=(rand()%100000)/*3。 tempflag1=0。 for(j=0。jPOPSIZEamp。amp。tempflag1==0。j++) { if(tempRand=cityaddFitness[j])//輪盤(pán)賭選中第 j 個(gè) { tempflag1=1。 //if(i!=cityBestFitCityXuh) if(cityfitness[j]=cityfitness[i]amp。amp。i!=j) { copyColony(i,j,city)。 } } } } return。 }//Select() void copyCityXuhToCityColony(int tempcityxuh[][CITY_NUM+1],int *tempXuh,PTSP city) { int i,h。 for(h=0。h2。h++) { for(i=1。iCITY_NUM。i++) { citycolony[tempXuh[h]][i]=tempcityxuh[h][i]。 } } }//copyCityXuhToCityColony() void exchgTempcityxuh(int tempcityxuh[][CITY_NUM+1],int countCrossGene) { int i,temp。 for(i=1。i=countCrossGene。i++) { 27 temp=tempcityxuh[0][i]。 tempcityxuh[0][i]=tempcityxuh[1][i]。 tempcityxuh[1][i]=temp。 } }//exchgTempcityxuh() void crossTwo(PTSP city,int *tempXuh,int cityCross[][CITY_NUM+1]) //交叉操作 { int genePoint[2],temp1,countCrossGene,flaglike。 int samePoint=0。 int i,j,k,h。 int tempcityxuh[2][CITY_NUM+1]。 do { genePoint[0]=rand()%(CITY_NUM1)。 genePoint[1]=rand()%(CITY_NUM1)+1。 }while(genePoint[0]==genePoint[1]||genePoint[0]==0||genePoint[1]==0)。 if(genePoint[0]genePoint[1]) {temp1=genePoint[0]。genePoint[0]=genePoint[1]。genePoint[1]=temp1。} countCrossGene=genePoint[1]genePoint[0]。 for(k=0。k2。k++)//相同的部分屏蔽 { for(i=genePoint[0]+1。i=genePoint[1]。i++) { for(j=1。jCITY_NUM。j++) { if(!(jgenePoint[0]amp。amp。j=genePoint[1])) { if(cityCross[k][j]==cityCross[(k+1)%2][i]) { ++samePoint。 cityCross[k][j]=CITY_NUM。//用 CITYNUM 代表 H } } } } 28 } samePoint=samePoint/2。 //for(h=0。h2。h++) //{ for(k=0。k2。k++)//one { j=1。 for(i=genePoint[0]+1。i=genePoint[1]。i++) { tempcityxuh[k][j++]=cityCross[(k+1)%2][i]。 cityCross[(k+1)%2][i]=0。 } for(i=1。i=CITY_NUM1。i++) { if(cityCross[k][i]==CITY_NUM) { tempcityxuh[k][j++]=cityCross[k][i]。 cityCross[k][i]=0。 } } for(i=1。i=CITY_NUM1。i++) { if(cityCross[k][i]!=0amp。amp。!(igenePoint[0]amp。amp。i=genePoint[1])) { tempcityxuh[k][j++]=cityCross[k][i]。 } } }//for k // } if(samePoint!=0)//cross { for(h=0。h2。h++) { k=countCrossGene。 29 for(i=1。i=countCrossGene。i++) { flaglike=0。 for(j=1。j=countCrossGeneamp。amp。flaglike==0。j++) { if(tempcityxuh[h][i]==tempcityxuh[(h+1)%2][j]) { flaglike=1。 } } if(flaglike==0) {tempcityxuh[(h+1)%2][++k]=tempcityxuh[h][i]。} } }//forh } //exchgTempcityxuh(tempcityxuh,countCrossGene)。 copyCityXuhToCityColony(tempcityxuh,tempXuh,city)。 return。 }//crossTwo() void copyCityXuhTo(PTSP city,int *tempXuh,int cityCross[][CITY_NUM+1]) { int i,h。 for(h=0。h2。h++) { for(i=0。i=CITY_NUM。i++) { cityCross[h][i]=citycolony[tempXuh[h]][i]。 } } return。 }//copyCityXuhTo() //交叉操作 void Cross(PTSP city,double pc) {//交叉概率是 pc int crossNum,i。 30 int cityCross[2][CITY_NUM+1]。 int tempXuh[2]。 crossNum=int(POPSIZE*pc)。 for(i=0。icrossNum/2。i++) { tempXuh[0]=rand()%(POPSIZE1)。 do { tempXuh[1]=rand()%(POPSIZE1)。 }while(tempXuh[0]==tempXuh[1])。 copyCityXuhTo(city,tempXuh,cityCross)。 crossTwo(city,tempXuh,cityCross)。 } }//Cross() //變異操作 void Mutation(PTSP city,double pm) {//變異概率是 pm int changePoint[2],temp,j。 int selCity。 for(j=1。j=int(POPSIZE*pm)。j++) { do { selCity=rand()%(POPSIZE)。 }while(selCity==cityBestFitCityXuh)。 do { changePoint[0]=rand()%(CITY_NUM1)。 changePoint[1]=rand()%(CITY_NUM1)+1。 }while(changePoint[0]==changePoint[1]||changePoint[0]==0||changePoint[1]==0||changePoint[0]changePoint[1]3)。 31 //swich temp=citycolony[selCity][changePoint[0]]。 citycolony[selCity][changePoint[0]]=citycolony[selCity][changePoint[1]]。 citycolony[selCity][changePoint[1]]=temp。 } }//Mutation() void OutPut(PTSP city) { int i,j。 printf(The population is:\n)。 for(i=0。iPOPSIZE。i++){ for(j=0。j=CITY_NUM。j++){ printf(%5d,citycolony[i][j])。 } printf(%5d,int(cityDistance[i]))。 printf(\n)。 } printf(The best rooting is:\n)。 printf(%d:,cityBestFitCityXuh)。 for(i=0。i=CITY_NUM。i++) printf(%5d,citycolony[cityBestFitCityXuh][i])。 printf(\nIt39。s cost value is %f\n,(cityBestValue))。 } //計(jì)算最好的適應(yīng)度值 void findBestFitAndValueaddFit(PTSP city) { int i。 cityBestValue=MAXVALUE。 cityBestFitness=0。 cityaddFitness[0]=cityfitness[0]。 for(i=0。iPOPSIZE。i++) 32 { if(i!=0) cityaddFitness[i]=cityfitness[i]+cityaddFitness[i1]。 if(cityfitness[i]cityBestFitness) { cityBestFitness=cityfitness[i]。 cityBestFitCityXuh=i。 } if(cityDistance[i]cityBestValue) { cityBestValue=cityDistance[i]。 } } for(i=0。iPOPSIZE。i++) { cityaddFitness[i]=cityaddFitness[i]/cityaddFitness[POPSIZE1]。 } return。 }//findBestFitAndValue() int canOver(int *flagExit,int *countSameTime,double lastBestFitness,PTSP city) { int flagRet。 flagRet=0。 if(cityBestFitness==lastBestFitness) { ++(*countSameTime)。 if(*countSameTimeMAXSAMETIME) { flagRet=1。 (*flagExit)=1。 } } else (*countSameTime)=0。 return flagRet。 }//canOver() 33 int main(int argc, char* argv[]) { PTSP city。 double pcross,pmutation。//交叉概率和變異概率