tsp.cpp

75个城市坐标的优化问题

void initialize()
{
	int k,j,minx,miny,maxx,maxy;
	initdata();
	minx=0;
	miny=0;
	maxx=0;
	maxy=0;
	for(k=0;k<lchrom;k++)
	{
		if(x[k]>maxx)
			maxx=x[k];
		if(x[k]<minx)
			minx=x[k];
		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-1;k++)
		 refpd=refpd+dd[k*lchrom+k+1];
	 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 gen,struct pp *pop)
{
	int k,ix,iy,jx,jy;
	unsigned int tt;
	float ttt;
	cleardevice();
	gotoxy(1,1);
	printf("cities: %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,gen,avg,min);
	printf("Ref.co_minpath: %6.4f Minpath length :%10.4f Ref_co_tour: %f\n",pop[maxpp].x/maxxy,pop[maxpp].x,ff);
	printf("co_minpath :%6.4f maxfitness: %10.8f",100.0*pop[maxpp].x/ff,pop[maxpp].fitness);
	ttt=clock()/18.2;
	tt=ttt/60;
	printf("Run clock: %2d: %2d: %4.2f\n",tt/60,tt%60,ttt-tt*60.0);
	setcolor(gen%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<gen%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);
	}
	fprintf(fp,"GEN: %3d",gen);
	fprintf(fp,"minpath: %f maxfitness: %f",pop[maxpp].x,pop[maxpp].fitness);
	fprintf(fp,"clock: %2d: %2d: %4.2f\n",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 char jj,ts1[maxstring],ts2[maxstring];
	float f1,f2;
	s0=0;
	s1=0;
	s2=0;
	if(flip(pcross))
	{
		jcross=rand()%(lchrom-1);
		j5=rand()%(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=rand()%lchrom;
				j=rand()%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=rand()%lchrom;
				j=rand()%lchrom;
				jj=newpop[k5+1].chrom[j];
				newpop[k5+1].chrom[j]=newpop[k5+1].chrom[j1];
				newpop[k5+1].chrom[j1]=jj;
			}
		}
	}
	j2=rand()%(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=rand()%(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,int *ss)
{
	unsigned int i,l1;
	unsigned char tt;
	l1=(j-k)/2;
	for(i=0;i<11;i++)
	{
		tt=ss[k+i+1];
		ss[k+i+1]=ss[j-i];
		ss[j-i]=tt;
	}
}
/*重启动随机数发生器*/
void randomize1()
{
	int i;
	srand(time(0));
    for(i=2;i<lchrom;i++)
		oldrand[i]=rand()%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=rand()%20001/20000.0;
	if(ppp<=probability)
		return 1;
	return 0;
}