【正文】 citynode /*定義城市結點*/ { struct gene city。 struct citynode *next。 }。 int i,j,k,time,n。 int s1,s2。 int cityno。 int p1bool,p2bool。 int site1,site2。 struct citynode *head。 struct citynode *p。 struct citynode *pp。 struct gene tempgene。 struct crosssite jcross。 =0。 =0。 if(flip(pcross)) { ncross++。 /*產(chǎn)生第一個子代*/ p1bool=1。 p2bool=1。 cityno=rnd(1,lchrom)。 /*隨機產(chǎn)生第一個城市的序號*/ =cityno。 /*將第一個城市的序號作為交叉點*/for(k=0。klchrom。k++) /*找到隨機產(chǎn)生的第一個序號在父個體染色體1中的位置*/ { if(parent1chrom[k].cityno==cityno) { s1=k。 break。 } } for(k=0。klchrom。k++) /*找到隨機產(chǎn)生的第一個序號在父個體染色體2中的位置*/ { if(parent2chrom[k].cityno==cityno) { s2=k。 break。 } } if((head=(struct citynode *)malloc(sizeof(struct citynode)))==NULL)nomemory(citynode)。 else { headcity=parent1chrom[s1]。 headnext=NULL。 pp=head。} do{ /*類貪婪法將產(chǎn)生與子個體染色體1不同的序號*/ s1=s11。 if(s10)s1=lchrom+s1。 s2=s2+1。 if(s2lchrom1)s2=lchroms2。 if(p1bool==1) { p=head。 while(p!=NULL) { if(parent1chrom[s1].cityno==(pcity).cityno)break。p=pnext。 } if(p!=NULL)p1bool=0。 else { if((p=(struct citynode *)malloc(sizeof(struct citynode)))==NULL)nomemory(citynode)。 else { pcity=parent1chrom[s1]。 pnext=head。 head=p。 } } } if(p2bool==1) { p=head。 while(p!=NULL) { if(parent2chrom[s2].cityno==(pcity).cityno)break。 p=pnext。 } if(p!=NULL)p2bool=0。 else { if((p=(struct citynode *)malloc(sizeof(struct citynode)))==NULL)nomemory(citynode)。 else { pcity=parent2chrom[s2]。 pnext=NULL。 ppnext=p。 pp=p。} } } }while((p1bool==1)||(p2bool==1))。 n=0。 p=head。 while(p!=NULL) { n++。 p=pnext。 } if(nlchrom) { p=head。 /*將鏈表的數(shù)據(jù)賦給子個體1的染色體*/ for(k=0。klchrom。k++) { if(p!=NULL) {child1chrom[k]=pcity。p=pnext。 } else { child1chrom[k].cityno=0。 child1chrom[k].xcoordinate=。 child1chrom[k].ycoordinate=。 } } for(j=0,k=n。(jlchrom)amp。amp。(klchrom)。j++) /*將剩余的城市找到*/ { for(i=0。in。i++) { if(parent1chrom[j].cityno==child1chrom[i].cityno)break。 } if(i==n) { child1chrom[k]=parent1chrom[j]。 k++。 } } for(time=0。timelchromn。time++)/*對個體的染色體上剩余的基因做排列*/ {site1=rnd(n,lchrom1)。 site2=rnd(n,lchrom1)。 if(site1!=site2) { tempgene=child1chrom[site1]。 child1chrom[site1]=child1chrom[site2]。 child1chrom[site2]=tempgene。 } } } else /*n=lchrom，即沒有剩余的基因*/ { p=head。 for(k=0。(klchrom)amp。amp。(p!=NULL)。k++) {child1chrom[k]=pcity。 p=pnext。 }} p=head。 /*釋放鏈表*/ while(p!=NULL) { p=pnext。 free(head)。 head=p。 } 產(chǎn)生第二個子代，與第一個子代的產(chǎn)生方法相同。 return jcross。 }附錄C OliverEil 51和CTSP 31的坐標文件Oliver30城市序號12345678910X坐標值87918371646883877471Y坐標值7384644605869767871城市序號11121314151617181920X坐標值585451374127222518Y坐標值69626784949964606254城市序號21222324252627282930X坐標值4131824254145445862Y坐標值50404042382621353532Eil 51城市序號12345678910X坐標值37495220402117315251Y坐標值52496426304763623321城市序號11121314151617181920X坐標值4231512365227171357Y坐標值41322542164123331358城市序號21222324252627282930X坐標值624216872730435858Y坐標值42575752386848674827城市序號31323334353637383940X坐標值3738466162633245595Y坐標值6946103363692235156城市序號41424344454647484950X坐標值1021530393225254856Y坐標值17106415103932552837城市序號51X坐標值30Y坐標值40CTSP 31城市序號12345678910X坐標值1304363941773712348833263238419643124386Y坐標值23121315224413991535155612291004790570城市序號11121314151617181920X坐標值3007256527882381133237153918406137803676Y坐標值197017561491167669516782179237022122578城市序號21222324252627282930X坐標值4029426334293507339434392935314025452778Y坐標值2838293119082367264332013240355023572826城市序號31X坐標值2370Y坐標值29