遗传算法解决10城市TSP问题程序源代码

实验六：遗传算法求解TSP问题实验3篇以下是关于遗传算法求解TSP问题的实验报告，分为三个部分，总计超过3000字。

一、实验背景与原理1.1 实验背景旅行商问题（Traveling Salesman Problem，TSP）是组合优化中的经典问题。

给定一组城市和每两个城市之间的距离，求解访问每个城市一次并返回出发城市的最短路径。

TSP 问题具有很高的研究价值，广泛应用于物流、交通运输、路径规划等领域。

1.2 遗传算法原理遗传算法（Genetic Algorithm，GA）是一种模拟自然选择和遗传机制的搜索算法。

它通过选择、交叉和变异操作生成新一代解，逐步优化问题的解。

遗传算法具有全局搜索能力强、适用于多种优化问题等优点。

二、实验设计与实现2.1 实验设计本实验使用遗传算法求解TSP问题，主要包括以下步骤：（1）初始化种群：随机生成一定数量的个体（路径），每个个体代表一条访问城市的路径。

（2）计算适应度：根据路径长度计算每个个体的适应度，适应度越高，路径越短。

（3）选择操作：根据适应度选择优秀的个体进入下一代。

（4）交叉操作：随机选择两个个体进行交叉，生成新的个体。

（5）变异操作：对交叉后的个体进行变异，增加解的多样性。

（6）更新种群：将新生成的个体替换掉上一代适应度较低的个体。

（7）迭代：重复步骤（2）至（6），直至满足终止条件。

2.2 实验实现本实验使用Python语言实现遗传算法求解TSP问题。

以下为实现过程中的关键代码：（1）初始化种群```pythondef initialize_population(city_num, population_size): population = []for _ in range(population_size):individual = list(range(city_num))random.shuffle(individual)population.append(individual)return population```（2）计算适应度```pythondef calculate_fitness(population, distance_matrix): fitness = []for individual in population:path_length =sum([distance_matrix[individual[i]][individual[i+1]] for i in range(len(individual) 1)])fitness.append(1 / path_length)return fitness```（3）选择操作```pythondef selection(population, fitness, population_size): selected_population = []fitness_sum = sum(fitness)fitness_probability = [f / fitness_sum for f in fitness]for _ in range(population_size):individual = random.choices(population, fitness_probability)[0]selected_population.append(individual)return selected_population```（4）交叉操作```pythondef crossover(parent1, parent2):index1 = random.randint(0, len(parent1) 2)index2 = random.randint(index1 + 1, len(parent1) 1)child1 = parent1[:index1] +parent2[index1:index2] + parent1[index2:]child2 = parent2[:index1] +parent1[index1:index2] + parent2[index2:]return child1, child2```（5）变异操作```pythondef mutation(individual, mutation_rate):for i in range(len(individual)):if random.random() < mutation_rate:j = random.randint(0, len(individual) 1) individual[i], individual[j] = individual[j], individual[i]return individual```（6）更新种群```pythondef update_population(parent_population, child_population, fitness):fitness_sum = sum(fitness)fitness_probability = [f / fitness_sum for f in fitness]new_population =random.choices(parent_population + child_population, fitness_probability, k=len(parent_population)) return new_population```（7）迭代```pythondef genetic_algorithm(city_num, population_size, crossover_rate, mutation_rate, max_iterations): distance_matrix =create_distance_matrix(city_num)population = initialize_population(city_num, population_size)for _ in range(max_iterations):fitness = calculate_fitness(population, distance_matrix)selected_population = selection(population, fitness, population_size)parent_population = []child_population = []for i in range(0, population_size, 2):parent1, parent2 = selected_population[i], selected_population[i+1]child1, child2 = crossover(parent1, parent2)child1 = mutation(child1, mutation_rate)child2 = mutation(child2, mutation_rate)parent_population.extend([parent1, parent2]) child_population.extend([child1, child2])population =update_population(parent_population, child_population, fitness)best_individual =population[fitness.index(max(fitness))]best_path_length =sum([distance_matrix[best_individual[i]][best_individual[i +1]] for i in range(len(best_individual) 1)])return best_individual, best_path_length```三、实验结果与分析3.1 实验结果本实验选取了10个城市进行测试，遗传算法参数设置如下：种群大小：50交叉率：0.8变异率：0.1最大迭代次数：100实验得到的最佳路径长度为：1953.53.2 实验分析（1）参数设置对算法性能的影响种群大小：种群大小会影响算法的搜索能力和收敛速度。

解TSP问题的遗传算法C语言程序#include<stdio.h>#include<stdlib.h>#include<math.h>#include<alloc.h>#include<conio.h>#include<float.h>#include<time.h>#include<graphics.h>#include<bios.h>#define maxpop 100#define maxstring 100struct pp{unsigned char chrom[maxstring];float x,fitness;unsigned int parent1,parent2,xsite;};struct pp *oldpop,*newpop,*p1;unsigned int popsize,lchrom,gem,maxgen,co_min,jrand;unsigned int nmutation,ncross,jcross,maxpp,minpp,maxxy;floatpcross,pmutation,sumfitness,avg,max,min,seed,maxold,oldrand[maxstring];unsigned char x[maxstring],y[maxstring]; float*dd,ff,maxdd,refpd,fm[201]; FILE *fp,*fp1;float objfunc(float);void statistics();int select();int flip(float);int crossover();void generation();void initialize();void report();float decode();void crtinit();void inversion();float random1();void randomize1();main(){unsigned int gen,k,j,tt;char fname[10];float ttt;clrscr();co_min=0;if((oldpop=(struct pp *)farmalloc(maxpop*sizeof(struct pp)))==NULL) {printf("memory requst fail!\n");exit(0);} if((dd=(float*)farmalloc(maxstring*maxstring*sizeof(float)))==NULL){printf("memory requst fail!\n");exit(0);} if((newpop=(struct pp *)farmalloc(maxpop*sizeof(struct pp)))==NULL){printf("memory requst fail!\n");exit(0);} if((p1=(struct pp*)farmalloc(sizeof(struct pp)))==NULL){printf("memory requst fail!\n");exit(0);} for(k=0;k<maxpop;k++) oldpop[k].chrom[0]='\0'; for(k=0;k<maxpop;k++) newpop[k].chrom[0]='\0'; printf("Enter Result Data Filename:"); gets(fname);if((fp=fopen(fname,"w+"))==NULL){printf("cannot open file\n");exit(0);}gen=0;randomize();initialize();fputs("this is result of the TSP problem:",fp);fprintf(fp,"city: %2d psize: %3d Ref.TSP_path:%f\n",lchrom,popsize,refpd);fprintf(fp,"Pc: %f Pm: %f Seed: %f\n",pcross,pmutation,seed);fprintf(fp,"X site:\n");for(k=0;k<lchrom;k++){if((k%16)==0) fprintf(fp,"\n"); fprintf(fp,"%5d",x[k]);}fprintf(fp,"\n Y site:\n"); for(k=0;k<lchrom;k++){if((k%16)==0) fprintf(fp,"\n"); fprintf(fp,"%5d",y[k]);}fprintf(fp,"\n");crtinit();statistics(oldpop);report(gen,oldpop);getch();maxold=min;fm[0]=100.0*oldpop[maxpp].x/ff; do {gen=gen+1;generation();statistics(oldpop);if(max>maxold){maxold=max;co_min=0;}fm[gen%200]=100.0*oldpop[maxpp].x/ff; report(gen,oldpop);gotoxy(30,25);ttt=clock()/18.2;tt=ttt/60;printf("Run Clock: %2d: %2d: %4.2f",tt/60,tt%60,ttt-tt*60.0);printf("Min=%6.4fNm:%d\n",min,co_min); }while((gen<100)&&!bioskey(1)); printf("\n gen= %d",gen);do{gen=gen+1;generation();statistics(oldpop);if(max>maxold){maxold=max;co_min=0;}fm[gen%200]=100.0*oldpop[maxpp].x/ff; report(gen,oldpop);if((gen%100)==0)report(gen,oldpop); gotoxy(30,25);ttt=clock()/18.2;tt=ttt/60;printf("Run Clock: %2d: %2d: %4.2f",tt/60,tt%60,ttt-tt*60.0);printf("Min=%6.4fNm:%d\n",min,co_min); }while((gen<maxgen)&&!bioskey(1));getch();for(k=0;k<lchrom;k++) {if((k%16)==0)fprintf(fp,"\n");fprintf(fp,"%5d",oldpop[maxpp].chrom[k]);}fprintf(fp,"\n");fclose(fp);farfree(dd);farfree(p1);farfree(oldpop);farfree(newpop);restorecrtmode();exit(0);}/*%%%%%%%%%%%%%%%%*/float objfunc(float x1) {float y;y=100.0*ff/x1;return y;}/*&&&&&&&&&&&&&&&&&&&*/void statistics(pop) struct pp *pop;{int j;sumfitness=pop[0].fitness; min=pop[0].fitness; max=pop[0].fitness; maxpp=0;minpp=0;for(j=1;j<popsize;j++) {sumfitness=sumfitness+pop[j].fitness;if(pop[j].fitness>max){max=pop[j].fitness;maxpp=j;}if(pop[j].fitness<min){min=pop[j].fitness;minpp=j;}}avg=sumfitness/(float)popsize;}/*%%%%%%%%%%%%%%%%%%%%*/void generation(){unsigned int k,j,j1,j2,i1,i2,mate1,mate2;float f1,f2;j=0;do{mate1=select();pp:mate2=select();if(mate1==mate2)goto pp;crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,j);newpop[j].x=(float)decode(newpop[j].chrom);newpop[j].fitness=objfunc(newpop[j].x); newpop[j].parent1=mate1;newpop[j].parent2=mate2;newpop[j].xsite=jcross;newpop[j+1].x=(float)decode(newpop[j+1].chrom);newpop[j+1].fitness=objfunc(newpop[j+1].x); newpop[j+1].parent1=mate1;newpop[j+1].parent2=mate2;newpop[j+1].xsite=jcross;if(newpop[j].fitness>min){for(k=0;k<lchrom;k++)oldpop[minpp].chrom[k]=newpop[j].chrom[k];oldpop[minpp].x=newpop[j].x;oldpop[minpp].fitness=newpop[j].fitness;co_min++;return;}if(newpop[j+1].fitness>min){for(k=0;k<lchrom;k++)oldpop[minpp].chrom[k]=newpop[j+1].chrom[k];oldpop[minpp].x=newpop[j+1].x;oldpop[minpp].fitness=newpop[j+1].fitness;co_min++;return;}j=j+2;}while(j<popsize);}/*%%%%%%%%%%%%%%%%%*/void initdata(){unsigned int ch,j;clrscr();printf("-----------------------\n");printf("A SGA\n");printf("------------------------\n");/*pause();*/clrscr();printf("*******SGA DATA ENTRY AND INITILIZATION *******\n");printf("\n");printf("input pop size");scanf("%d",&popsize); printf("input chrom length");scanf("%d",&lchrom); printf("input maxgenerations");scanf("%d",&maxgen); printf("input crossoverprobability");scanf("%f",&pcross); printf("input mutationprob");scanf("%f",&pmutation); randomize1();clrscr();nmutation=0;ncross=0;}/*%%%%%%%%%%%%%%%%%%%%*/void initreport(){int j,k;printf("pop size=%d\n",popsize);printf("chromosome length=%d\n",lchrom);printf("maxgen=%d\n",maxgen);printf("pmutation=%f\n",pmutation); printf("pcross=%f\n",pcross);printf("initial generation statistics\n"); printf("ini pop maxfitness=%f\n",max); printf("ini pop avr fitness=%f\n",avg); printf("ini pop min fitness=%f\n",min); printf("ini pop sum fit=%f\n",sumfitness); } void initpop(){unsigned char j1;unsigned int k5,i1,i2,j,i,k,j2,j3,j4,p5[maxstring];float f1,f2;j=0;for(k=0;k<lchrom;k++)oldpop[j].chrom[k]=k;for(k=0;k<lchrom;k++)p5[k]=oldpop[j].chrom[k];randomize();for(;j<popsize;j++){j2=random(lchrom);for(k=0;k<j2+20;k++){j3=random(lchrom);j4=random(lchrom);j1=p5[j3];p5[j3]=p5[j4];p5[j4]=j1;}for(k=0;k<lchrom;k++)oldpop[j].chrom[k]=p5[k]; }for(k=0;k<lchrom;k++)for(j=0;j<lchrom;j++)dd[k*lchrom+j]=hypot(x[k]-x[j],y[k]-y[j]);for(j=0;j<popsize;j++) {oldpop[j].x=(float)decode(oldpop[j].chrom); oldpop[j].fitness=objfunc(oldpop[j].x);oldpop[j].parent1=0;oldpop[j].parent2=0;oldpop[j].xsite=0;}}/*&&&&&&&&&&&&&&&&&*/void initialize(){int k,j,minx,miny,maxx,maxy; initdata();minx=0;miny=0;maxx=0;maxy=0;for(k=0;k<lchrom;k++){x[k]=rand();if(x[k]>maxx)maxx=x[k]; if(x[k]<minx)minx=x[k]; y[k]=rand();if(y[k]>maxy)maxy=y[k]; if(y[k]<miny)miny=y[k]; }if((maxx-minx)>(maxy-miny)){maxxy=maxx-minx;}else {maxxy=maxy-miny;}maxdd=0.0;for(k=0;k<lchrom;k++)for(j=0;j<lchrom;j++){dd[k*lchrom+j]=hypot(x[k]-x[j],y[k]-y[j]);if(maxdd<dd[k*lchrom+j])maxdd=dd[k*lchrom+j];}refpd=dd[lchrom-1];for(k=0;k<lchrom;k++)refpd=refpd+dd[k*lchrom+k+2]; for(j=0;j<lchrom;j++)dd[j*lchrom+j]=4.0*maxdd; ff=(0.765*maxxy*pow(lchrom,0.5)); minpp=0; min=dd[lchrom-1];for(j=0;j<lchrom-1;j++){if(dd[lchrom*j+lchrom-1]<min){min=dd[lchrom*j+lchrom-1];minpp=j;}}initpop();statistics(oldpop);initreport();}/*&&&&&&&&&&&&&&&&&&*/void report(int l,struct pp *pop){int k,ix,iy,jx,jy;unsigned int tt;float ttt;cleardevice();gotoxy(1,1);printf("city:%4d para_size:%4d maxgen:%4d ref_tour:%f\n",lchrom,popsize,maxgen,refpd);printf("ncross:%4d Nmutation:%4d Rungen:%4d AVG=%8.4f MIN=%8.4f\n\n",ncross,nmutation,l,avg,min);printf("inpath:%6.4f Minpath length:%10.4f Ref_co_tour:%f\n",pop[maxpp].x/maxxy,pop[maxpp].x,ff); printf("Co_minpath:%6.4f Maxfit:%10.8f",100.0*pop[maxpp].x/ff,pop[maxpp].fitness); ttt=clock()/18.2;tt=ttt/60;printf("Run clock:%2d:%2d:%4d.2f\n",tt/60,tt%60,ttt-tt*60.0); setcolor(1%15+1);for(k=0;k<lchrom-1;k++){ix=x[pop[maxpp].chrom[k]];iy=y[pop[maxpp].chrom[k]]+110;jx=x[pop[maxpp].chrom[k+1]];jy=y[pop[maxpp].chrom[k+1]]+110;line(ix,iy,jx,jy);putpixel(ix,iy,RED);}ix=x[pop[maxpp].chrom[0]];iy=y[pop[maxpp].chrom[0]]+110;jx=x[pop[maxpp].chrom[lchrom-1]];jy=y[pop[maxpp].chrom[lchrom-1]]+110; line(ix,iy,jx,jy); putpixel(jx,jy,RED);setcolor(11);outtextxy(ix,iy,"*");setcolor(12);for(k=0;k<1%200;k++){ix=k+280;iy=366-fm[k]/3;jx=ix+1;jy=366-fm[k+1]/3;line(ix,iy,jx,jy);putpixel(ix,iy,RED);}printf("GEN:%3d",l);printf("Minpath:%f Maxfit:%f",pop[maxpp].x,pop[maxpp].fitness); printf("Clock:%2d:%2d:%4.2f\n",tt/60,tt%60,ttt-tt*60.0);}/*###############*/float decode(unsigned char *pp) {int j,k,l;float tt;tt=dd[pp[0]*lchrom+pp[lchrom-1]]; for(j=0;j<lchrom-1;j++){tt=tt+dd[pp[j]*lchrom+pp[j+1]];} l=0;for(k=0;k<lchrom-1;k++)for(j=k+1;j<lchrom;j++){if(pp[j]==pp[k])l++;}return tt+4*l*maxdd;}/*%%%%%%%%%%%%%%%%%%*/ void crtinit(){int driver,mode;struct palettetype p;driver=DETECT;mode=0;initgraph(&driver,&mode,""); cleardevice();}/*$$$$$$$$$$$$$$$$$$$$*/ int select(){double rand1,partsum; float r1;int j;partsum=0.0;j=0;rand1=random1()*sumfitness; do{partsum=partsum+oldpop[j].fitness;j=j+1;}while((partsum<rand1)&&(j<popsize));return j-1;}/*$$$$$$$$$$$$$$$*/int crossover(unsigned char *parent1,unsigned char *parent2,int k5) {int k,j,mutate,i1,i2,j5;int j1,j2,j3,s0,s1,s2; unsigned charjj,ts1[maxstring],ts2[maxstring];float f1,f2;s0=0;s1=0;s2=0;if(flip(pcross)){jcross=random(lchrom-1); j5=random(lchrom-1); ncross=ncross+1;if(jcross>j5){k=jcross;jcross=j5;j5=k;}}else jcross=lchrom; if(jcross!=lchrom) {s0=1;k=0;for(j=jcross;j<j5;j++) {ts1[k]=parent1[j]; ts2[k]=parent2[j]; k++; }j3=k;for(j=0;j<lchrom;j++) {j2=0;while((parent2[j]!=ts1[j2])&&(j2<k)){j2++;}if(j2==k){ts1[j3]=parent2[j];j3++;}}j3=k;for(j=0;j<lchrom;j++){j2=0;while((parent1[j]!=ts2[j2])&&(j2<k)){j2++;}if(j2==k){ts2[j3]=parent1[j];j3++;}}for(j=0;j<lchrom;j++){newpop[k5].chrom[j]=ts1[j];newpop[k5+1].chrom[j]=ts2[j]; }}else{for(j=0;j<lchrom;j++){newpop[k5].chrom[j]=parent1[j]; newpop[k5+1].chrom[j]=parent2[j]; } mutate=flip(pmutation);if(mutate){s1=1;nmutation=nmutation+1;for(j3=0;j3<200;j3++){j1=random(lchrom);j=random(lchrom);jj=newpop[k5].chrom[j];newpop[k5].chrom[j]=newpop[k5].chrom[j1];newpop[k5].chrom[j1]=jj;}}mutate=flip(pmutation);if(mutate){s2=1;nmutation=nmutation+1;for(j3=0;j3<100;j3++){j1=random(lchrom);j=random(lchrom);jj=newpop[k5+1].chrom[j];newpop[k5+1].chrom[j]=newpop[k5+1].chrom[j1];newpop[k5+1].chrom[j1]=jj;}}}j2=random(2*lchrom/3);for(j=j2;j<j2+lchrom/3-1;j++)for(k=0;k<lchrom;k++){if(k==j)continue;if(k>j){i2=k;i1=j;}else{i1=k;i2=j;}f1=dd[lchrom*newpop[k5].chrom[i1]+newpop[k5].chrom[i2]]; f1=f1+dd[lchrom*newpop[k5].chrom[(i1+1)%lchrom]+newpop[k5].chrom[(i2+1)%lchrom]];f2=dd[lchrom*newpop[k5].chrom[i1]+newpop[k5].chrom[(i1+1)%lchrom]];f2=f2+dd[lchrom*newpop[k5].chrom[i2]+newpop[k5].chrom[(i2+1)%lchrom]];if(f1<f2){inversion(i1,i2,newpop[k5].chrom);}}j2=random(2*lchrom/3);for(j=j2;j<j2+lchrom/3-1;j++)for(k=0;k<lchrom;k++){if(k==j)continue;if(k>j){i2=k;i1=j;}else{i1=k;i2=j;}f1=dd[lchrom*newpop[k5+1].chrom[i1]+newpop[k5+1].chrom[i2]];f1=f1+dd[lchrom*newpop[k5+1].chrom[(i1+1)%lchrom]+newpop[k5+1].chrom[(i2+1)%lchrom]];f2=dd[lchrom*newpop[k5+1].chrom[i1]+newpop[k5+1].chrom[(i1+1)%lchrom]];f2=f2+dd[lchrom*newpop[k5+1].chrom[i2]+newpop[k5+1].chrom[(i2+1)%lchrom]];if(f1<f2){inversion(i1,i2,newpop[k5+1].chrom);} }return 1;}/*$$$$$$$$$$$$$$$*/void inversion(unsigned int k,unsigned int j,unsigned char *ss) {unsigned int l1,i;unsigned char tt;l1=(j-k)/2;for(i=0;i<l1;i++){tt=ss[k+i+1];ss[k+i+1]=ss[j-i];ss[j-i]=tt;}}/*%%%%%%%%%%%%%%%*/void randomize1(){int i;randomize();for(i=0;i<lchrom;i++) oldrand[i]=random(30001)/30000.0;jrand=0;}/*%%%%%%%%%%%*/float random1(){jrand=jrand+1;if(jrand>=lchrom){jrand=0;randomize1();}return oldrand[jrand]; }/*%%%%%%%%%%*/int flip(float probability) {float ppp;ppp=random(20001)/20000.0; if(ppp<=probability)return 1; return 0;}%TSP问题(又名:旅行商问题，货郎担问题)遗传算法通用matlab程序 %D是距离矩阵，n为种群个数,建议取为城市个数的1~2倍， %C为停止代数，遗传到第 C 代时程序停止,C的具体取值视问题的规模和耗费的时间而定%m为适应值归一化淘汰加速指数 ,最好取为1,2,3,4 ,不宜太大 %alpha为淘汰保护指数,可取为0~1之间任意小数,取1时关闭保护功能,最好取为0.8~1.0 %R为最短路径,Rlength为路径长度function [R,Rlength]=geneticTSP(D,n,C,m,alpha)[N,NN]=size(D);farm=zeros(n,N);%用于存储种群for i=1:nfarm(i,:)=randperm(N);%随机生成初始种群endR=farm(1,:);%存储最优种群len=zeros(n,1);%存储路径长度fitness=zeros(n,1);%存储归一化适应值counter=0;while counter<Cfor i=1:nlen(i,1)=myLength(D,farm(i,:));%计算路径长度endmaxlen=max(len);minlen=min(len);fitness=fit(len,m,maxlen,minlen);%计算归一化适应值rr=find(len==minlen);R=farm(rr(1,1),:);%更新最短路径FARM=farm;%优胜劣汰，nn记录了复制的个数nn=0;for i=1:nif fitness(i,1)>=alpha*rand nn=nn+1;FARM(nn,:)=farm(i,:);endendFARM=FARM(1:nn,:);[aa,bb]=size(FARM);%交叉和变异while aa<nif nn<=2nnper=randperm(2);elsennper=randperm(nn);endA=FARM(nnper(1),:);B=FARM(nnper(2),:);[A,B]=intercross(A,B); FARM=[FARM;A;B]; [aa,bb]=size(FARM);endif aa>nFARM=FARM(1:n,:);%保持种群规模为nendfarm=FARM;clear FARMcounter=counter+1endRlength=myLength(D,R);function [a,b]=intercross(a,b) L=length(a); if L<=10%确定交叉宽度W=1;elseif ((L/10)-floor(L/10))>=rand&&L>10W=ceil(L/10);elseW=floor(L/10);endp=unidrnd(L-W+1);%随机选择交叉范围，从p到p+W for i=1:W%交叉x=find(a==b(1,p+i-1)); y=find(b==a(1,p+i-1)); [a(1,p+i-1),b(1,p+i-1)]=exchange(a(1,p+i-1),b(1,p+i-1));[a(1,x),b(1,y)]=exchange(a(1,x),b(1,y));endfunction [x,y]=exchange(x,y) temp=x;x=y;y=temp;% 计算路径的子程序function len=myLength(D,p) [N,NN]=size(D);len=D(p(1,N),p(1,1)); for i=1:(N-1)len=len+D(p(1,i),p(1,i+1));end%计算归一化适应值子程序function fitness=fit(len,m,maxlen,minlen) fitness=len;for i=1:length(len)fitness(i,1)=(1-((len(i,1)-minlen)/(maxlen-minlen+0.000001))).^m;end。

package GA;import java.util.*;public class Tsp {private String cityName[]={"北京","上海","天津","重庆","哈尔滨","长春","沈阳","呼和浩特","石家庄","太原","济南","郑州","西安","兰州","银川","西宁","乌鲁木齐","合肥","南京","杭州","长沙","南昌","武汉","成都","贵州","福建","台北","广州","海口","南宁","昆明","拉萨","香港","澳门"};//private String cityEnd[]=new String[34];private int cityNum=cityName.length; //城市个数private int popSize = 50; //种群数量private int maxgens = 20000; //迭代次数private double pxover = 0.8; //交叉概率private double pmultation = 0.05; //变异概率private long[][] distance = new long[cityNum][cityNum];private int range = 2000; //用于判断何时停止的数组区间private class genotype {int city[] = new int[cityNum]; //单个基因的城市序列long fitness; //该基因的适应度double selectP; //选择概率double exceptp; //期望概率int isSelected; //是否被选择}private genotype[] citys = new genotype[popSize];/*** 构造函数，初始化种群*/public Tsp() {for (int i = 0; i < popSize; i++) {citys[i] = new genotype();int[] num = new int[cityNum];for (int j = 0; j < cityNum; j++)num[j] = j;int temp = cityNum;for (int j = 0; j < cityNum; j++) {int r = (int) (Math.random() * temp);citys[i].city[j] = num[r];num[r] = num[temp - 1];temp--;}citys[i].fitness = 0;citys[i].selectP = 0;citys[i].exceptp = 0;citys[i].isSelected = 0;}initDistance();}/*** 计算每个种群每个基因个体的适应度，选择概率，期望概率，和是否被选择。

//遗传算法解决简单TSP问题，（VC6.0）//一、定义头文件(defines.h)#ifndef DEFINES_H#define DEFINES_H///////////////////////////////// DEFINES /////////////////////////////////////// //窗口定义大小#define WINDOW_WIDTH 500#define WINDOW_HEIGHT 500//城市数量及城市在窗口显示的大小#define NUM_CITIES 20#define CITY_SIZE 5//变异概率，交叉概率及种群数量#define MUTATION_RATE 0.2#define CROSSOVER_RATE 0.75#define POP_SIZE 40//倍数#define NUM_BEST_TO_ADD 2//最小容许误差#define EPSILON 0.000001#endif//二、一些用得到的小函数(utils.h)// utils.h: interface for the Cutils class.//头文件名//////////////////////////////////////////////////////////////////////#ifndef UTILS_H#define UTILS_H#include <stdlib.h>#include <math.h>#include <sstream>#include <string>#include <iostream>using namespace std;//--------定义一些随机函数--------//----定义随机整数，随机[x,y]之间的整数---inline int RandInt(int x, int y){return rand()%(y-x+1)+x;}//--------------随机产生0到1之间的小数----------inline float RandFloat(){return rand()/(RAND_MAX + 1.0);}//-----------------随机产生0和1-------------inline bool RandBool(){if (RandInt(0,1))return true;elsereturn false;}//-----定义一些方便的小功能包括：整形转字符型，浮点型转字符型--- string itos(int arg);//converts an float to a std::stringstring ftos (float arg);//限制大小void Clamp(double &arg, double min, double max);void Clamp(int &arg, int min, int max);#endif//三、地图头文件（CmapTSP）#ifndef CMAPTSP_H#define CMAPTSP_H//如果没有定义那么就定义////////////////////////////////////////////////////类名：CmapTSP.h////描述：封装地图数据、城市坐标以及适应度计算。

TSP问题的遗传算法实验报告一、实验题目TSP问题的遗传算法实现二、实验目的1 熟悉和掌握遗传算法的基本概念和基本思想；2 加深对遗传算法的理解，理解和掌握遗传算法的各个操作算子；3 理解和掌握利用遗传算法进行问题求解的基本技能。

三、实验要求1 以10/个城市结点的TSP问题为例,用遗传算法加以求解；2 掌握遗传算法的基本原理、各个遗传操作和算法步骤；3能求出问题最优解，若得不出最优解，请分析原因；4要求界面显示每次迭代求出的局部最优解和最终求出的全局最优解。

四、实验代码Main函数%% 连续Hopfield神经网络的优化—旅行商问题优化计算% function main%% 清空环境变量、定义全局变量clear allclcglobal A D%% 导入城市位置load city_location%% 计算相互城市间距离distance=dist(citys,citys');%% 初始化网络N=size(citys,1);A=200;D=100;U0=0.1;step=0.0001;delta=2*rand(N,N)-1;U=U0*log(N-1)+delta;V=(1+tansig(U/U0))/2;iter_num=10000;E=zeros(1,iter_num);%% 寻优迭代for k=1:iter_num% 动态方程计算dU=diff_u(V,distance);% 输入神经元状态更新U=U+dU*step;% 输出神经元状态更新V=(1+tansig(U/U0))/2;% 能量函数计算e=energy(V,distance);E(k)=e;end%% 判断路径有效性[rows,cols]=size(V);V1=zeros(rows,cols);[V_max,V_ind]=max(V);for j=1:colsV1(V_ind(j),j)=1;endC=sum(V1,1);R=sum(V1,2);flag=isequal(C,ones(1,N)) & isequal(R',ones(1,N));%% 结果显示if flag==1% 计算初始路径长度sort_rand=randperm(N);citys_rand=citys(sort_rand,:);Length_init=dist(citys_rand(1,:),citys_rand(end,:)');for i=2:size(citys_rand,1)Length_init=Length_init+dist(citys_rand(i-1,:),citys_rand(i,:)');end% 绘制初始路径figure(1)plot([citys_rand(:,1);citys_rand(1,1)],[citys_rand(:,2);citys_rand(1,2)],'o-') for i=1:length(citys)text(citys(i,1),citys(i,2),[' ' num2str(i)])endtext(citys_rand(1,1),citys_rand(1,2),[' 起点' ])text(citys_rand(end,1),citys_rand(end,2),[' 终点' ])title(['优化前路径(长度：' num2str(Length_init) ')'])axis([0 1 0 1])grid onxlabel('城市位置横坐标')ylabel('城市位置纵坐标')% 计算最优路径长度[V1_max,V1_ind]=max(V1);citys_end=citys(V1_ind,:);Length_end=dist(citys_end(1,:),citys_end(end,:)');for i=2:size(citys_end,1)Length_end=Length_end+dist(citys_end(i-1,:),citys_end(i,:)');enddisp('最优路径矩阵');V1% 绘制最优路径figure(2)plot([citys_end(:,1);citys_end(1,1)],...[citys_end(:,2);citys_end(1,2)],'o-')for i=1:length(citys)text(citys(i,1),citys(i,2),[' ' num2str(i)])endtext(citys_end(1,1),citys_end(1,2),[' 起点' ])text(citys_end(end,1),citys_end(end,2),[' 终点' ])title(['优化后路径(长度：' num2str(Length_end) ')'])axis([0 1 0 1])grid onxlabel('城市位置横坐标')ylabel('城市位置纵坐标')% 绘制能量函数变化曲线figure(3)plot(1:iter_num,E);ylim([0 2000])title(['能量函数变化曲线(最优能量：' num2str(E(end)) ')']);xlabel('迭代次数');ylabel('能量函数');elsedisp('寻优路径无效');end% %=========================================== % function du=diff_u(V,d)% global A D% n=size(V,1);% sum_x=repmat(sum(V,2)-1,1,n);% sum_i=repmat(sum(V,1)-1,n,1);% V_temp=V(:,2:n);% V_temp=[V_temp V(:,1)];% sum_d=d*V_temp;% du=-A*sum_x-A*sum_i-D*sum_d;% %========================================== % function E=energy(V,d)% global A D% n=size(V,1);% sum_x=sumsqr(sum(V,2)-1);% sum_i=sumsqr(sum(V,1)-1);% V_temp=V(:,2:n);% V_temp=[V_temp V(:,1)];% sum_d=d*V_temp;% sum_d=sum(sum(V.*sum_d));% E=0.5*(A*sum_x+A*sum_i+D*sum_d);diff_u函数% % % % 计算dufunction du=diff_u(V,d)global A Dn=size(V,1);sum_x=repmat(sum(V,2)-1,1,n);sum_i=repmat(sum(V,1)-1,n,1);V_temp=V(:,2:n);V_temp=[V_temp V(:,1)];sum_d=d*V_temp;du=-A*sum_x-A*sum_i-D*sum_d;Energy函数% % % % % 计算能量函数function E=energy(V,d)global A Dn=size(V,1);sum_x=sumsqr(sum(V,2)-1);sum_i=sumsqr(sum(V,1)-1);V_temp=V(:,2:n);V_temp=[V_temp V(:,1)];sum_d=d*V_temp;sum_d=sum(sum(V.*sum_d));E=0.5*(A*sum_x+A*sum_i+D*sum_d);五、实验结果（图一、最优路径矩阵）（图二、优化前路线）（图三、优化后路线）（图三、能量函数）。

用遗传算法求解中国34个省会TSP问题一、TSP问题的描述旅行商问题（TSP）可以具体描述为：已知n个城市之间的相互距离，现有一个推销员从某一个城市出发，必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回到出发城市，如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短。

现给出中国34个省会数据，要求基于此数据使用遗传算法解决该TSP问题。

中国34省会位置city =1.西藏2.云南3.四川4.青海5.宁夏6.甘肃7.内蒙古8.黑龙江9.吉林10.辽宁 11.北京 12天津 13.河北 14.山东 15.河南 16.山西 17.陕西18.安徽 19.江苏20.上海 21.浙江 22.江西 23.湖北 24.湖南 25.贵州 26.广西27.广东28.福建 29.海南 30.澳门 31.香港 32.台湾 33.重庆 34.新疆像素坐标如下：Columns 1 through 11100 187 201 187 221 202 258 352 346 336 290 211 265 214 158 142 165 121 66 85 106 127 Columns 12 through 22297 278 296 274 265 239 302 316 334 325 293 135 147 158 177 148 182 203 199 206 215 233 Columns 23 through 33280 271 221 233 275 322 250 277 286 342 220 216 238 253 287 285 254 315 293 290 263 226 Column 34 104 77二、遗传算法的介绍2.1 遗传算法遗传算法的基本原理是通过作用于染色体上的基因寻找好的染色体来求解问题，它需要对算法所产生的每个染色体进行评价，并基于适应度值来选择染色体，使适应性好的染色体有更多的繁殖机会，在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始种群；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗产操作后的个体集合形成下一代新的种群，对这个新的种群进行下一轮的进化。

课程实验报告1.实验目的利用遗传算法获得TSP问题的近似解。

2.实验要求要求学生了解遗传算法解决问题的基本流程。

对TSP问题有所了解,知道TSP 问题的难点在什么地方,如何使用遗传算法来获得一个较好的近似解。

3.实验内容已知n个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。

如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？用图论的术语来说，假设有一个图g=(v,e)，其中v是顶点集，e是边集，设d=(dij)是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。

4.实验软硬件环境基本Windows系统基本运行环境，VS20125.实验方案（1）遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法遗传算法的基本运算过程如下：a)初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。

b)个体评价：计算群体P(t)中各个个体的适应度。

c)选择运算:将选择算子作用于群体。

选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。

选择操作是建立在群体中个体的适应度评估基础上的。

d)交叉运算：将交叉算子作用于群体。

所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。

遗传算法中起核心作用的就是交叉算子。

e)变异运算：将变异算子作用于群体。

即是对群体中的个体串的某些基因座上的基因值作变动。

群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t 1)。

f)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。

（2）用遗传算法模拟TSP问题TSP问题及旅行商问题,假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。

遗传算法TSP（Python代码）该代码是本⼈根据B站up主的代码所修改的。

原代码github地址：遗传算法步骤不⽤讲了，将再多还是不会写代码，倒不如花⼀上午读懂下⾯的代码。

不仅明⽩了具体步骤还能写出代码。

#!/usr/bin/env python# coding: utf-8# Author：侯昶曦 & 孟庆国# Date：2020年5⽉19⽇ 21点16分# * 本代码中使⽤的城市坐标需要保存在⼀个`csv`类型的表中。

# * 下⾯的代码可以⽣成随机的指定数量的城市坐标，保存到当前⽬录的`cities.csv`⽂件中。

# * 如果需要本地数据，请在`main()`中修改⽂件路径。

# * 相关参数在`main()`中可以修改。

from matplotlib import pyplot as pltimport numpy as npimport pandas as pdimport time# ⽣成城市坐标city_num = 10 # 城市数量name = ["city's name"] * city_num # 这个并没什么⽤，但是不要省，省了的话还要修改代码x = [np.random.randint(0, 100) for i in range(city_num)]y = [np.random.randint(0, 100) for i in range(city_num)]with open("cities.csv", "w") as f:for i in range(city_num):f.write(name[i]+","+str(x[i])+","+str(y[i])+"\n")f.write(name[0]+","+str(x[0])+","+str(y[0])+"\n") # 最后⼀个节点即为起点# 打印城市的坐标position = pd.read_csv("cities.csv", names=['ind','lat','lon'])plt.scatter(x=position['lon'], y=position['lat'])plt.show()position.head()def create_init_list(filename):data = pd.read_csv(filename,names=['index','lat','lon']) # lat->纬度 lon->经度data_list = []for i in range(len(data)):data_list.append([float(data.iloc[i]['lon']),float(data.iloc[i]['lat'])])return data_listdef distance_matrix(coordinate_list, size): # ⽣成距离矩阵，邻接矩阵d = np.zeros((size + 2, size + 2))for i in range(size + 1):x1 = coordinate_list[i][0]y1 = coordinate_list[i][1]for j in range(size + 1):if (i == j) or (d[i][j] != 0):continuex2 = coordinate_list[j][0]y2 = coordinate_list[j][1]distance = np.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)if (i == 0): # 起点与终点是同⼀城市d[i][j] = d[j][i] = d[size + 1][j] = d[j][size + 1] = distanceelse:d[i][j] = d[j][i] = distancereturn ddef path_length(d_matrix, path_list, size): # 计算路径长度length = 0for i in range(size + 1):length += d_matrix[path_list[i]][path_list[i + 1]]return lengthdef shuffle(my_list):#起点和终点不能打乱temp_list=my_list[1:-1]np.random.shuffle(temp_list)shuffle_list=my_list[:1]+temp_list+my_list[-1:]return shuffle_listdef product_len_probability(my_list,d_matrix,size,p_num): # population, d, size,p_numlen_list=[] # 种群中每个个体（路径）的路径长度pro_list=[]path_len_pro=[]for path in my_list:len_list.append(path_length(d_matrix,path,size))max_len=max(len_list)+1e-10gen_best_length=min(len_list) # 种群中最优路径的长度gen_best_length_index=len_list.index(gen_best_length) # 最优个体在种群中的索引# 使⽤最长路径减去每个路径的长度，得到每条路径与最长路径的差值，该值越⼤说明路径越⼩ mask_list=np.ones(p_num)*max_len-np.array(len_list)sum_len=np.sum(mask_list) # mask_list列表元素的和for i in range(p_num):if(i==0):pro_list.append(mask_list[i]/sum_len)elif(i==p_num-1):pro_list.append(1)else:pro_list.append(pro_list[i-1]+mask_list[i]/sum_len)for i in range(p_num):# 路径列表路径长度概率path_len_pro.append([my_list[i],len_list[i],pro_list[i]])# 返回最优路径最优路径的长度每条路径的概率return my_list[gen_best_length_index],gen_best_length,path_len_prodef choose_cross(population,p_num): # 随机产⽣交配者的索引，越优的染⾊体被选择⼏率越⼤ jump=np.random.random() # 随机⽣成0-1之间的⼩数if jump<population[0][2]:return 0low=1high=p_nummid=int((low+high)/2)# ⼆分搜索# 如果jump在population[mid][2]和population[mid-1][2]之间，那么返回midwhile(low<high):if jump>population[mid][2]:low=midmid=(low+high) // 2elif jump<population[mid-1][2]: # 注意这⾥⼀定是mid-1high=midmid=(low+high) // 2else:return middef product_offspring(size, parent_1, parent_2, pm): # 产⽣后代son = parent_1.copy()product_set = np.random.randint(1, size+1)parent_cross_set=set(parent_2[1:product_set]) # 交叉序列集合cross_complete=1for j in range(1,size+1):if son[j] in parent_cross_set:son[j]=parent_2[cross_complete]cross_complete+=1if cross_complete>product_set:breakif np.random.random() < pm: #变异son=veriation(son,size,pm)return sondef veriation(my_list,size,pm):#变异，随机调换两城市位置ver_1=np.random.randint(1,size+1)ver_2=np.random.randint(1,size+1)while ver_2==ver_1:#直到ver_2与ver_1不同ver_2 = np.random.randint(1, size+1)my_list[ver_1],my_list[ver_2]=my_list[ver_2],my_list[ver_1]return my_listdef main(filepath, p_num, gen, pm):start = time.time()coordinate_list=create_init_list(filepath)size=len(coordinate_list)-2 # 除去了起点和终点d=distance_matrix(coordinate_list,size) # 各城市之间的邻接矩阵path_list=list(range(size+2)) # 初始路径# 随机打乱初始路径以建⽴初始种群路径population = [shuffle(path_list) for i in range(p_num)]# 初始种群population以及它的最优路径和最短长度gen_best,gen_best_length,population=product_len_probability(population,d,size,p_num)# 现在的population中每⼀元素有三项，第⼀项是路径，第⼆项是长度，第三项是使⽤时转盘的概率 son_list = [0] * p_num # 后代列表best_path=gen_best # 最好路径初始化best_path_length=gen_best_length # 最好路径长度初始化every_gen_best=[gen_best_length] # 每⼀代的最优值for i in range(gen): #迭代gen代son_num=0while son_num < p_num: # 循环产⽣后代，⼀组⽗母亲产⽣两个后代father_index = choose_cross(population, p_num) # 获得⽗母索引mother_index = choose_cross(population, p_num)father = population[father_index][0] # 获得⽗母的染⾊体mother = population[mother_index][0]son_list[son_num] = product_offspring(size, father, mother, pm) # 产⽣后代加⼊到后代列表中 son_num += 1if son_num == p_num:breakson_list[son_num] = product_offspring(size, mother, father, pm) # 产⽣后代加⼊到后代列表中 son_num += 1# 在新⼀代个体中找到最优路径和最优值gen_best, gen_best_length,population = product_len_probability(son_list,d,size,p_num)if(gen_best_length < best_path_length): # 这⼀代的最优值⽐有史以来的最优值更优best_path=gen_bestbest_path_length=gen_best_lengthevery_gen_best.append(gen_best_length)end = time.time()print(f"迭代⽤时：{(end-start)}s")print("史上最优路径:", best_path, sep=" ")#史上最优路径print("史上最短路径长度:", best_path_length, sep=" ")#史上最优路径长度# 打印各代最优值和最优路径x = [coordinate_list[point][0] for point in best_path] # 最优路径各节点经度y = [coordinate_list[point][1] for point in best_path] # 最优路径各节点纬度plt.figure(figsize=(8, 10))plt.subplot(211)plt.plot(every_gen_best) # 画每⼀代中最优路径的路径长度 plt.subplot(212)plt.scatter(x,y) # 画点plt.plot(x,y) # 画点之间的连线plt.grid() # 给画布添加⽹格plt.show()if __name__ == '__main__':filepath = r'cities.csv' # 城市坐标数据⽂件p_num = 200 #种群个体数量gen = 1000 #进化代数pm = 0.1 #变异率main(filepath, p_num, gen, pm)运⾏结果：迭代⽤时：3.543527126312256s史上最优路径: [0, 8, 1, 9, 7, 5, 4, 3, 2, 6, 10]史上最短路径长度: 303.83238696200436。

TSP问题的遗传算法求解方案算法的软件实现4.1 开发环境介绍本文中的所有算法是在Visual C++ 6.0 的操作平台上进行开发的，并结合STL进行编程。

1、Visual C++ 6.0简介Visual C++ 6.0 是微软公司最新出品的功能最为强大的可视化开放工具，是计算机界公认的最优秀的应用开发工具之一。

Microsoft的基本类库使得开发Windows应用程序比以往任何时候都要容易。

Visual C++作为一种程序设计语言，它同时也是一个集成开发工具，提供了软件代码自动生成和可视化的资源编辑功能。

2、Visual C++ 6.0的优势(1).拥有强大的编辑环境。

(2).拥有强大的类库的支持。

(3).拥有强大的调试环境。

(4).拥有较强的低层控制能力。

(5).拥有强大的帮助系统MSDN的支持。

(6).拥有一个高效的编译器，产生的可执行文件体积小巧、运行速度快。

3、STL简介STL（Standard Template Library），即标准模板库，是一个具有工业强度的，高效的C++程序库。

它被容纳于C++标准程序库（C++ Standard Library）中，是ANSI /ISO C++标准中最新的也是极具革命性的一部分。

该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。

为广大C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。

这种现象有些类似于Microsoft Visual C++中的MFC（Microsoft Foundation Class Library），或者是Borland C++ Builder中的VCL (Visual Component Library)，但是它比二者具有更强的优势。

更加值得一提的是，它具备以下几个区别于其它软件库的优点：(1).经过类属编程方法精心组织的，可互换的编程模块能够提供比传统组件设图4.1 遗传算法解TSP的具体流程图计方法丰富得多的组合方式。