【正文】 的排列順序補充到的末尾得到。文中對TSPLIB中經典的Oliver Eil 51和中國旅行商問題CTSP 31進行了求解，它們的坐標文件見附錄C。為了比較四組實現(xiàn)方法的優(yōu)劣我們需要用到以下幾個衡量指標：最佳個體的路徑長度、程序中最佳個體得到的最早代數(shù)和平均路徑隨進化代數(shù)的變化情況。因此我們認為若某個算法運行到最后一代后得到的最佳個體它的路徑長度較其他算法運行到最后一代后得到的最佳個體的路徑長度越小則此算法較好，但是前提是必須保證最佳個體是全局最優(yōu)的或滿意的。最佳個體路徑長度Oliver 30Eil 51CTSP 31PMX+EMPMX+RMSGX+EMSGX+RM表二 最佳個體路徑長度的統(tǒng)計數(shù)據(jù)圖十三 四組方法下Oliver 30最佳個體的路徑圖從圖十三和表二的對照中可以看出路徑之間的交叉點越多得到的路徑越長。圖十四 四組方法下Eil 51最佳個體的路徑圖對于Eil 51同樣SGX+RM得到了最短的路徑，最佳個體路徑圖中沒有交叉點，而PMX+EM得到的最佳路徑最長，最佳個體路徑圖中的交叉點個數(shù)最多。根據(jù)表二對Oliver Eil 51和CTSP 31求解結果的比較可以知道SGX+RM收斂到的解比其他三種方法收斂到的解都好，即類貪婪交叉算子和變異算子的結合使用比其他三種方法要好。最佳個體最早代數(shù)Oliver 30Eil 51CTSP 31PMX+EM407782349PMX+RM467831276SGX+EM744792359SGX+RM6222610567表三 最佳個體代數(shù)分布表從表三的統(tǒng)計數(shù)據(jù)我們可以看到SGX+RM在Eil 51和CTSP 31得到的最佳個體的最早代數(shù)最晚，即搜索最優(yōu)個體的能力較強，隨著進化代數(shù)的增加，算法并沒有停止在局部最優(yōu)情況，而是能跳出局部最優(yōu)情況繼續(xù)向全局最優(yōu)搜索。 平均路徑隨進化代數(shù)變化的比較對Oliver Eil 51和CTSP 31各代得到的平均路徑變化情況進行統(tǒng)計，如圖十六、十七和十八所示。圖十七Eil 51的平均路徑變化情況從圖十七看到SGX+RM的平均路徑收斂到了比其他三種方法都低的數(shù)值，PMX+RM和SGX+EM的平均路徑在700代左右收斂到了幾乎相同的數(shù)值，但大于SGX+RM收斂的平均路徑，小于PMX+EM收斂的平均路徑。圖十八 CTSP 31的平均路徑變化情況從圖十八可以看到SGX+RM的平均路徑同樣收斂到了低于其他三種方法的數(shù)值，PMX+RM收斂到的數(shù)值最大，PMX+EM收斂到的數(shù)值大于SGX+EM的數(shù)值。 結論從以上三個方面通過對四組方法的比較我們得出結論：SGX+RM在運行相同的進化代數(shù)后得到了比PMX+EM、PMX+RM和SGX+EM都小的全局最優(yōu)解或滿意解，由SGX+RM得到最佳個體的最早代數(shù)比其他三種方法得到最佳個體的最早代數(shù)晚可以推斷SGX+RM跳出局部最優(yōu)的能力強于其他三種方法，比較平均路徑長度隨進化代數(shù)的變化可以知道SGX+RM的平均路徑長度對于三個實例均收斂到了低于其他三種方法的平均路徑長度?？偨Y本文基于遺傳算法針對TSP進行了求解，實現(xiàn)了四組不同的遺傳算子并得到了較好的結果。文章的不足之處是輸入文件的城市位置是用坐標的形式表示的，而非距離矩陣表示，程序在計算城市之間的距離時是用二維平面上兩點間直線距離公式計算的，這樣計算得到的城市距離對于文中算法的運行沒有影響，但是脫離了實際，實際中任何兩個城市之間通常不是直線到達的，而是彎曲的曲線路徑。最后感謝同學們在四年來對我的幫助，感謝在我身邊關心我的每一位親人。參考文獻【1】王小平、——原理、應用與軟件實現(xiàn)[M]，西安交通大學出版社，2002年1月第一版：p150，p123129【2】周明、[M]，國防工業(yè)出版社，1999年7月第一版：p158，p143155【3】張文修、[M]，西安交通大學出版社， 2003年5月第2版：p1333【4】陳國良、王煦法、莊鎮(zhèn)泉、[M]，人民郵電出版社，1996年6月第一版：p1147【5】[J]，微電子學與計算機，2006年第23卷第10期：p104—105【6】Hiroaki SENGOKU、Ikuo Fast TSP Solver Using GA on JAVA[J]：p23【7】[M]，清華大學出版社，2005年7月第三版：p330344【8】敖友云、[J]，計算機與數(shù)字工程，2002年第34卷：p54【9】李曉英、萬劍怡、[J]，科技廣場，2006年2月：p12【10】李艷萍、[J]，太原理工大學學報，2008年5月第39卷第3期：p270附錄附錄A 部分匹配交叉法C源程序struct crosssite crossover_PMX(struct gene *parent1chrom,struct gene *parent2chrom,struct gene *child1chrom,struct gene *child2chrom) { int site1,site2,midsite。 struct crosssite jcross。 =0。 /*在site1后和site2后之間的區(qū)域交叉*/ site2=rnd(0,lchrom1)。 /*總交叉次數(shù)加1*/ if(site1!=site2) { if(site1site2) /*保證site1site2*/ { midsite=site1。 site2=midsite。 =site2+1。i=site1。 child2chrom[i]=parent2chrom[i]。i=site2。 child2chrom[i]=parent1chrom[i]。ilchrom。 child2chrom[i]=parent2chrom[i]。time(site2site1)。j=site2。i=site1。 } if(child2chrom[i].cityno==child2chrom[j].cityno) { child2chrom[i]=child1chrom[j]。ilchrom。 } if(child2chrom[i].cityno==child2chrom[j].cityno) { child2chrom[i]=child1chrom[j]。 =site2+1。ilchrom。 child2chrom[i]=parent2chrom[i]。 =0。ilchrom。 child2chrom[i]=parent2chrom[i]。}附錄B 類貪婪交叉法C源程序struct crosssite crossover_SGX(struct gene *parent1chrom,struct gene *parent2chrom,struct gene *child1chrom,struct gene *child2chrom) { struct citynode /*定義城市結點*/ { struct gene city。 }。 int s1,s2。 int p1bool,p2bool。 struct citynode *head。 struct citynode *pp。 struct crosssite jcross。 =0。 /*產生第一個子代*/ p1bool=1。 cityno=rnd(1,lchrom)。 /*將第一個城市的序號作為交叉點*/for(k=0。k++) /*找到隨機產生的第一個序號在父個體染色體1中的位置*/ { if(parent1chrom[k].cityno==cityno) { s1=k。 } } for(k=0。k++) /*找到隨機產生的第一個序號在父個體染色體2中的位置*/ { if(parent2chrom[k].cityno==cityno) { s2=k。 } } if((head=(struct citynode *)malloc(sizeof(struct citynode)))==NULL)nomemory(citynode)。 headnext=NULL。} do{ /*類貪婪法將產生與子個體染色體1不同的序號*/ s1=s11。 s2=s2+1。 if(p1bool==1) { p=head。p=pnext。 else { if((p=(struct citynode *)malloc(sizeof(struct citynode)))==NULL)nomemory(citynode)。 pnext=head。 } } } if(p2bool==1) { p=head。 p=pnext。 else { if((p=(struct citynode *)malloc(sizeof(struct citynode)))==NULL)nomemory(citynode)。 pnext=NULL。 pp=p。 n=0。 while(p!=NULL) { n++。 } if(nlchrom) { p=head。klchrom。p=pnext。 child1chrom[k].xcoordinate=。 } } for(j=0,k=n。amp。j++) /*將剩余的城市找到*/ { for(i=0。i++) { if(parent1chrom[j].cityno==child1chrom[i].cityno)break。 k++。timelchromn。 site2=rnd(n,lchrom1)。 child1chrom[site1]=child1chrom[site2]。 } } } else /*n=lchrom，即沒有剩余的基因*/ { p=head。(klchrom)amp。(p!=NULL)。 p=pnext。 /*釋放鏈表*/ while(p!=NULL) { p=pnext。 head=p。 return jcro