用遗传算法求解TSP问题

{

j2=rand()%lchrom; //重新排列p5[]

for(k=0;k

for ( j=0;j

printf(\}

void inversion(unsigned int k,unsigned int j, unsigned int *ss) {

unsigned int i,l1; unsigned int tt; l1=(j-k)/2;

for(i=0;i<=l1;i++) { tt=ss[k+i]; ss[k+i]=ss[j-i]; ss[j-i]=tt; } }

//函数decode计算一个城市排列的路径长度 float decode(unsigned int *pp) {

int j;

float tt;

tt=matrix[pp[0]][pp[lchrom-1]]; for(j=0;j

void generation() {

int site;

unsigned int k,mate1,mate2; for (int i=0;i

site=crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,newpop[i].chrom,newpop[i+1].chrom); mutation(newpop[i].chrom,pmutation);

//局部爬山到最优点

climb(newpop[i].chrom);

newpop[i].x=decode(newpop[i].chrom); newpop[i].fitness=objfunc(newpop[i].x); newpop[i].parent[0]=mate1; newpop[i].parent[1]=mate2; newpop[i].xsite=site;

mutation(newpop[i+1].chrom,pmutation); climb(newpop[i+1].chrom);

//局部爬山到最优点

newpop[i+1].x=decode(newpop[i+1].chrom); newpop[i+1].fitness=objfunc(newpop[i+1].x); newpop[i+1].parent[0]=mate1; newpop[i+1].parent[1]=mate2; newpop[i+1].xsite=site;

//群体更新方式采用最佳个体保留方式，每次以一个最佳个体替代一个最差个体

if(newpop[i].fitness>max) {

for(k=0;kmax) { for(k=0;k

float objfunc(float x1) {

return 1/x1; }

int select() //轮盘赌选择函数 { }

double sum,pick;

unsigned int i,random; random=rand()000;

pick=(double)random/10000.0; sum=0;

if (sumfitness!=0) { for(i=0;(sum

i=(rand()%popsize)+1; //即i=rnd(1,popsize)

if (i<1) { i=1; }

return i-1;

void statistics(struct individual *pop) {

int j;

sumfitness=pop[0].fitness; min=pop[0].fitness; max=pop[0].fitness; maxpp=0; minpp=0;

for(j=1;jmax) { max=pop[j].fitness; maxpp=j; } if (pop[j].fitness

avg=sumfitness/(float)popsize; }

int crossover(unsigned int a[],unsigned int b[],unsigned int c[],unsigned int d[]) {

int k,j,random;

int j2,j3,j5,s0,s1,s2,jcross; //jcross和j5之间为交配区域

unsigned int ts1[maxstring],ts2[maxstring]; float random_cross; s0=0; s1=0; s2=0;

random=rand()000;

random_cross=(float)random/10000; if (random_cross<=pcross) {

jcross=( rand()%(lchrom-1) )+1; //交配区间的第一个交叉点jcross在1和

lchrom-1之间

do {

j5=( rand()%(lchrom-1) )+1; //交配区间的第二个交叉点j5在1

和lchrom-1之间

} while(j5==jcross); 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

ts1[k]=a[j]; //将交配区间的数据复制到ts1[]的前面部分

ts2[k]=b[j]; k++; } j3=k;

for (j=0;j

if(j2==k) // b[j]不在ts1[]中时

{ ts1[j3]=b[j]; j3++; } } j3=k;

for (j=0;j