tsp.cpp

75个城市坐标的优化问题

#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 200
#define maxstring 200
struct pp{int chrom[maxstring];
          double x,fitness;
		  unsigned int parent1,parent2,xsite;
};
struct pp *oldpop,*newpop,*p1;
unsigned int popsize,lchrom,gen,maxgen,co_min,jrand;
unsigned int nmutation,ncross,jcross,maxpp,minpp,maxxy;
float pcross,pmutation,sumfitness,avg,max,min,maxold,oldrand[maxstring];
double x[maxstring]={4.8000000e+001,5.2000000e+001,5.0000000e+001,5.5000000e+001,5.4000000e+001,5.0000000e+001,5.1000000e+001,5.5000000e+001,5.5000000e+001,
5.0000000e+001,4.1000000e+001,4.5000000e+001,4.5000000e+001,4.0000000e+001,3.8000000e+001,3.3000000e+001,2.9000000e+001,3.3000000e+001,3.5000000e+001,3.0000000e+001,
2.2000000e+001,2.1000000e+001,2.1000000e+001,2.1000000e+001, 2.0000000e+001, 2.6000000e+001,2.2000000e+001,2.7000000e+001, 3.0000000e+001, 3.5000000e+001, 3.6000000e+001,
2.6000000e+001,1.5000000e+001,1.5000000e+001,1.6000000e+001, 1.2000000e+001,6.0000000e+000, 1.1000000e+001, 1.2000000e+001,7.0000000e+000, 9.0000000e+000, 1.5000000e+001,
1.0000000e+001,	1.7000000e+001, 2.6000000e+001,3.0000000e+001,3.5000000e+001,4.0000000e+001,4.0000000e+001, 3.1000000e+001,4.7000000e+001,5.0000000e+001,5.7000000e+001,
5.5000000e+001,	5.5000000e+001,6.2000000e+001,7.0000000e+001,6.2000000e+001, 6.7000000e+001,6.2000000e+001,	6.5000000e+001,	6.2000000e+001,5.5000000e+001,6.0000000e+001,
6.6000000e+001,6.6000000e+001,6.4000000e+001,5.9000000e+001,5.0000000e+001,5.4000000e+001,5.0000000e+001,4.4000000e+001,4.0000000e+001,3.6000000e+001,4.3000000e+001
};
double y[maxstring]={ 2.1000000e+001,	2.6000000e+001,		  3.0000000e+001,		  3.4000000e+001,		  3.8000000e+001,
  4.0000000e+001,	  4.2000000e+001,	4.5000000e+001,		  5.0000000e+001,		  5.0000000e+001,		  4.6000000e+001,
  4.2000000e+001,	  3.5000000e+001,   3.7000000e+001,		  3.3000000e+001,		  3.4000000e+001,		  3.9000000e+001,
  4.4000000e+001,	  5.1000000e+001,	5.0000000e+001,		  5.3000000e+001,		  4.8000000e+000,		  4.5000000e+001,
  3.6000000e+001,	  3.0000000e+001,   2.9000000e+001,		  2.2000000e+001,		  2.4000000e+001,	      2.0000000e+001,
  1.6000000e+001,	  6.0000000e+000,   1.3000000e+001,	      5.0000000e+000,		  1.4000000e+001,	      1.9000000e+001,
  1.7000000e+001,	  2.5000000e+001,   2.8000000e+001,		  3.8000000e+001,		  4.3000000e+001,		  5.6000000e+001,
  5.6000000e+001,	  7.0000000e+001,   6.4000000e+001,		  5.9000000e+001,		  6.0000000e+001,		  6.0000000e+001,
  6.0000000e+001,	  6.6000000e+001,	7.6000000e+001,		  6.6000000e+001,		  7.0000000e+001,		  7.2000000e+001,
  6.5000000e+001,	  5.7000000e+001,	5.7000000e+001,		  6.4000000e+001,	      4.8000000e+001,	      4.1000000e+001,
  3.5000000e+001,	  2.7000000e+001,   2.4000000e+001,       2.0000000e+001,	      1.5000000e+001,	      1.4000000e+001,
  8.0000000e+000,	  4.0000000e+000,	5.0000000e+000,		  4.0000000e+000,		  1.0000000e+001,	      1.5000000e+001,
  1.3000000e+001,	  2.0000000e+001,	2.6000000e+001,		  2.6000000e+001
};
float *dd,ff,maxdd,refpd,fm[201];
FILE *fp,*fp1;
double objfunc(double);
void statistics();
int select();
int flip(float);
int crossover();
void generation();
void initialize();
void report();
double decode();
float random1();
void inversion(unsigned int k,unsigned int j,int *ss);
void crtinit();
/*主程序*/
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))))
    {
      printf("memory request failed !\n");
      exit(0);
    }
  if(!(dd=(float *)farmalloc(maxstring*maxstring*sizeof(float))))
     {
     printf("memory request failed !\n");
      exit(0);
   }
  if(!(newpop=(struct pp *)farmalloc(maxpop*sizeof(struct pp))))
    {
     printf("memory request failed !\n");
     exit(0);
    }
  if(!(p1=(struct pp *)farmalloc(sizeof(struct pp))))
    {
     printf("memory request failed !\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+")))
   {
      printf("can't open file\n");
	  exit(1);
   }
   gen=0;
   srand(time(0));
   initialize();
   fputs("This is result of the tsp problem:",fp);
   fprintf(fp,"citis: %2d  psize: %3d Ref.Tsp_path: %f\n",lchrom,popsize,refpd);
   fprintf(fp,"Pc: %f pm: %f \n",pcross,pmutation);
   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*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.4f Nm: %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.4f Nm: %d\n",min,co_min);
   }while((gen<100)&&(!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);
   free(dd);
   free(p1);
   free(oldpop);
   free(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;
   printf("******SGA DATA ENTERY AND INITIALIZATION********\n");
   printf("\n");
   printf("enter population size-------->");
   scanf("%d",&popsize);
   printf("enter chromosome length------>");
   scanf("%d",&lchrom);
   printf("enter max.generations-------->");
   scanf("%d",&maxgen);
   printf("enter crossover probability-->");
   scanf("%f",&pcross);
   printf("enter mutation probability--->");
   scanf("%f",&pmutation);
   srand(time(0));
   nmutation=0;
   ncross=0;
}
/*初始数据输出*/
void initreport()
{
	int j,k;
	printf("-----------------------\n");
	printf("SGA Parameters\n");
	printf("-----------------------\n");
	printf("\n");
	printf("population size (popsize)= %d\n",popsize);
	printf("Chromosome length(lchrom)=%d\n",lchrom);
	printf("Maximum # of generation(maxgen)= %d\n",maxgen);
	printf("crossover probability(pcross)= %f\n",pcross);
	printf("Mutation probability(pmutaton)= %f\n",pmutation);
	printf("initial generation statistics\n");
	printf("-----------------------------\n");
	printf("\n");
	printf("initial population maximum fitness = %f\n",max);
	printf("initial population average fitness = %f\n",avg);
	printf("initial population minimum fitness = %f\n",min);
	printf("initial population sum of fitness = %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];
	srand(time(0));
	for(;j<popsize;j++)
	{
		j2=random(lchrom);
		for(k=0;k<j2+20;k++)
		{
			j3=rand()%lchrom;
			j4=rand()%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;
	}
}
/*初始化*/