C语言解决TSP问题的编程

/*通过C语言的运用遗传算法解决TSP问题*/#includestdlib.h#includestdio.h#includemath.h#includestdafx.h#includetime.h#definePopSize50/*种群类DNA个数*/#defineMaxGens200/*最大代数*/#defineN10/*问题规模*/#definePC0.8/*交叉概率*/#definePM0.01/*突变概率*/#defineRAND_MAX10intcity[N];intbegin_city=0;/*出发城市*/doubler[N][N]={0,1,4,6,8,1,3,7,2,9,1,0,7,5,3,8,3,4,2,4,4,7,0,3,8,3,7,9,1,2,6,5,3,0,3,1,5,2,9,1,8,3,8,3,0,2,3,1,4,6,1,8,3,1,2,0,3,3,9,5,3,3,7,5,3,3,0,7,5,9,7,4,9,2,1,3,7,0,1,3,2,2,1,9,4,9,5,1,0,1,9,4,2,1,6,5,9,3,1,0};intgeneration;/*当前代数*/intCurBest;/*最优个体*/structGenoType{intgene[N];/*城市序列*/doublefitness;/*当前城市序列对应的适应值*/doublerfitness;/*适应率*/doublecfitness;/*轮盘对应的起始区间值*/};structResultType{doublebest_val;/*最佳适应度*/doubleavg;/*平均适应度*/doublestddev;/*标准差*/};GenoTypepopulation[PopSize+1];/*种群*/GenoTypenewpopulation[PopSize+1];/*新种群*/ResultTyperesult[MaxGens];/*种群换代记录*//*函数声明*/voidinitialize();/*初始化*/voidevaluate();/*评价函数*/voidFind_the_best();/*找出最优*/voidelitist();/*择优函数*/voidselect();/*选择*/voidcrossover();/*交叉*/voidmutate();/*变异*/voidreport();/*报告输出*/intIntGenerate();/*产生一个城市节点*/voidswap(int*,int*);/*交换两值*/voidswap(int*a,int*b){inttemp;temp=*a;*a=*b;*b=temp;}/*产生一个0到10的数，作为城市编号*/intIntGenerate(){intRANGE_MIN=0;intRANGE_MAX=N;intrand_10;rand_10=(((double)rand()/(double)RAND_MAX)*RANGE_MAX+RANGE_MIN);returnrand_10;}/*初始化种群*/voidinitialize(){intmatrix[N];intx1,x2;inti,j;/*生成一个定值序列，0点为开始点*/for(i=1;iN;i++)matrix[i]=i;for(j=0;jPopSize;j++){population[i].gene[0]=begin_city;/*gene[0]表示出发城市，i表示城市次序*/for(i=0;iN;i++)/*N次交换足以产生各种结果了*/{x1=0;x2=0;while(x1==0)x1=IntGenerate();while(x2==0)x2=IntGenerate();swap(&matrix[x1],&matrix[x2]);}for(inti=1;iN;i++)population[j].gene[i]=matrix[i];}}/*评价函数：计算出该种群的适应性*/voidevaluate(){intcurrent_city=begin_city;intnext_city;for(intmem=0;memPopSize;mem++){population[mem].fitness=0;for(inti=1;iN;i++){next_city=population[mem].gene[i];population[mem].fitness+=r[current_city][next_city];current_city=next_city;}population[mem].fitness+=r[current_city][begin_city];}}/*找出该代种群中的最优个体，并将其存储.*/voidFind_the_best(){intmem,i;CurBest=0;for(mem=1;memPopSize;mem++)if(population[mem].fitnesspopulation[CurBest].fitness)//一次冒泡找出最优CurBest=mem;//找到最优个体后，将其存储起来for(i=0;iN;i++)population[PopSize].gene[i]=population[CurBest].gene[i];population[PopSize].fitness=population[CurBest].fitness;}/*择优函数：将当代中的最优及最差个体保存下来,如果新种群中最优个体优于父代中最优个体，则将其保存下来,否则，将当代中最差个体替换为父代中最优个体*/voidelitist()//择优函数{inti;doublebest,worst;intbest_mem,worst_mem;best=population[0].fitness;worst=population[0].fitness;//冒泡比较两个个体中的适应度，并可能选择较大的放入worst_mem和较小的放入best_memfor(i=0;iPopSize-1;++i){if(population[i].fitnesspopulation[i+1].fitness){if(population[i].fitness=best){best=population[i].fitness;best_mem=i;}if(population[i+1].fitness=worst){worst=population[i+1].fitness;worst_mem=i+1;}}else{if(population[i+1].fitness=worst){worst=population[i+1].fitness;worst_mem=i;}if(population[i+1].fitness=best){best=population[i+1].fitness;best_mem=i+1;}}/*end冒泡*/}/*如果新种群中最优个体优于父代中最优个体，则将其保存下来；*//*否则，将当代中最差个体替换为父代中最优个体*/if(best=population[PopSize].fitness){for(i=0;iN;i++)population[PopSize].gene[i]=population[best_mem].gene[i];population[PopSize].fitness=population[best_mem].fitness;}else{for(i=0;iN;i++)population[worst_mem].gene[i]=population[PopSize].gene[i];population[worst_mem].fitness=population[PopSize].fitness;}}//轮盘赌算法根据轮盘赌算法来选择复制的个体voidselect()//选择{intmem,i,j;doublesum=0.0;doublep;doublex[PopSize];for(mem=0;memPopSize;mem++)sum+=population[mem].fitness;/*由于此处选择应是fitness越小越好，而传统的轮盘赌算法为适应值越大越好，顾需将其做一个转换*/for(mem=0;memPopSize;mem++)x[mem]=sum-population[mem].fitness;sum=0.0;/*求得传统适应总值*/for(mem=0;memPopSize;mem++)sum+=x[mem];/*求得适应率*/for(mem=0;memPopSize;mem++)population[mem].rfitness=x[mem]/sum;/*求得轮盘对应的各个区间*/population[0].cfitness=population[0].rfitness;for(mem=1;memPopSize;mem++){population[mem].cfitness=population[mem-1].cfitness+population[mem].rfitness;}//通过轮盘来选择是否保留该个体for(i=0;iPopSize;i++){p=rand()%1000/1000.0;if(ppopulation[0].cfitness)newpopulation[i]=population[0];else{for(j=0;jPopSize;j++)if(p=population[j].cfitness&&ppopulation[j+1].cfitness)newpopulation[i]=population[j+1];}}/*将新种群中的个体复制到原种群中*/for(i=0;iPopSize;i++)population[i]=newpopulation[i];}/*交叉：实质为将一段路径‘串’逆序*/voidcrossover(){inti,j;intmin,max,flag;doublex;for(i=0;iPopSize;i++){x=rand()%1000/1000.0;if(xPC){min=0;max=0;while(min==0)min=IntGenerate();while(max==0)max=IntGenerate();if(maxmin){inttemp;temp=max;max=min;min=temp;}flag=max;for(j=min;j=(max+min)/2;j++){swap(&population[i].gene[j],&population[i].gene[flag]);flag=flag-1;}}}}/*变异：将种群中两个位置的节点值互换*//*变异操作*/voidmutate(){inti;doublex;intx1,x2;for(i=0;iPopSize;i++){x=(int)rand()%1000/1000.0;if(xPM){x1=0;x2=0;while(x1==0)x1=IntGenerate();while(x2==0)x2=IntGenerate();swap(&population[i].gene[x1],&population[i].gene[x2]);}}}/*报告输出：将过程记录在输出文件中*/voidreport(){inti;doublebest_val;/*最佳适应度*/doubleavg;/*种群平均适应度*/doublestddev;/*种群适应度标准差*/doublesum_square;/*适应度的平方和*/doublesquare_sum;doublesum;/*适应度总和*/sum=0.0;sum_square=0.0;for(i=0;iPopSize;i++){sum+=populatio