tsp.cpp

结合均匀设计表和小边经验公式产生初始种群

void select_roulette()
{ 
  double sum,pick;
  int i,j,m;

//  fprintf(fp,"轮盘赌选择方法选出的个体为： \n");  //验证此方法时用
 srand((unsigned)time(NULL));  //以系统时钟作为随机种子
  for (i=0;i<popsize;i++)  
  { sum=0;
	pick=rand()/(double)RAND_MAX;        //产生0~1之间的随机数
    for (j=0;(sum<pick)&&(j<popsize);j++)  
        sum+=pop[j].fitness/sumfitness;
    for (m=0;m<lchrom;m++)  
	    tempop[i].chrom[m]=pop[j-1].chrom[m];
	tempop[i].fitness=pop[j-1].fitness;
 //   fprintf(fp,"%d, ",j-1);       //验证此方法时用
  }
}
/////////////////////////////////////////
///** 轮盘赌与期望值结合的选择方法 **///
/////////////////////////////////////////

#define expect  0.925   //当个体的期望值小于此值时,此个体被淘汰

void select_roulette_expect()
{ 
  double sum,pick;
  double expt[popsize];      //个体在下一代生存的期望值
  int i,j,m,n;
  
 //fprintf(fp,"结合方法选出的个体为： \n");  //验证此方法时用

  for (i=0;i<popsize;i++)  //计算个体在下一代生存的期望值，期望值小于expect的个体不能被选择（即被淘汰）
  { expt[i]=pop[i].fitness/avgfitness;
 //   fprintf(fp,"%2d: %f\n",i,expt[i]);       //验证此方法时用
  }
  
  srand((unsigned)time(NULL));  //以系统时钟作为随机种子
  
  for (i=0;i<popsize;i++)  
  { do
	 { sum=0;
	   pick=rand()/(double)RAND_MAX;        //产生0~1之间的随机数
       for (j=0;(sum<pick)&&(j<popsize);j++)  
          sum+=pop[j].fitness/sumfitness;
       n=j-1;  //n为被选择的个体
	 }while(expt[n]<expect);   //重新产生随机数,重新选择一个个体
             
    for (m=0;m<lchrom;m++)  
	    tempop[i].chrom[m]=pop[n].chrom[m];
	tempop[i].fitness=pop[n].fitness;
  // fprintf(fp,"%2d, %f\n",n,expt[n]);       //验证此方法时用
  }
}
////////////////////////////////////////////////////////////////


////////////////////////////////////////////////////////////////  
///////****         交叉操作crossover()             ***/////////
//////***交叉前的在tempop，交叉后的个体全部转移到pop中***///////
////////////////////////////////////////////////////////////////

void replace(unsigned p,unsigned child[lchrom],unsigned r1,unsigned r2)     
{ //对匹配区域以外出现的重复进行遍历，然后替换，生成子个体
  // p：父个体在种群中的编号；child：子个体；  r1,r2 ：两个位串交叉点 
  int i,j,n;
  bool traverse;
  for(i=0;i<=r1;i++)        //匹配区域前的
  { child[i]=tempop[p].chrom[i];
    for(n=0;n<r2-r1-1;n++)  //为解决传递关系使得一旅程中会有相同的城市而采取的办法,即对于一个传递
	{ traverse=0; 	        //关系,最多遍历r2-r1-1次就可使一条旅程中不会出现相同的城市.在此过程中,
      for(j=r1+1;j<r2;j++)  //若traverse=0,说明问题已解决,则提前结束此次传递关系的遍历
	      if(child[i]==child[j])
			{child[i]=tempop[p].chrom[j]; traverse=1;break;}
       if(!traverse) break;  //如果traverse=0,则结束此传递关系的遍历
	 }
  }

  for(i=r2;i<lchrom;i++)     //匹配区域后的
  { child[i]=tempop[p].chrom[i];
    for(n=0;n<r2-r1-1;n++)
	{ traverse=0;
      for(j=r1+1;j<r2;j++)
		if(child[i]==child[j])
			{child[i]=tempop[p].chrom[j]; traverse=1;break;}
      if(!traverse) break;  //如果traverse=0,则结束此传递关系的遍历
	}
  }
}


void PMX_crossover(unsigned m,unsigned n,unsigned child1[lchrom],unsigned child2[lchrom])
{ //m,n：父个体在种群中的编号;  child1,child2//子个体
  int i;
  unsigned r1,r2;         //两个位串交叉点
  unsigned temp;

/*////
  printf("交叉前的两个父个体:\n");
  for(i=0;i<lchrom;i++)                       //输出交叉前的父个体
     printf("%d  ",tempop[m].chrom[i]);
  printf("\n");
  for(i=0;i<lchrom;i++)                        //输出交叉前的父个体
     printf("%d  ",tempop[n].chrom[i]);
*////

  r1=rand()%lchrom;
  r2=rand()%lchrom;
  while(abs(r1-r2)<2)
      r2=rand()%lchrom;
  if(r1>r2)              //比较r1、r2大小，使r1<r2
  { temp=r1; r1=r2; r2=temp; }


  for(i=r1+1;i<r2;i++)  //匹配区域进行交换
  { child1[i]=tempop[n].chrom[i];
    child2[i]=tempop[m].chrom[i];
  }
  replace(m,child1,r1,r2);           //对匹配区域以外出现的重复进行遍历，然后替换，生成子个体
  replace(n,child2,r1,r2);   
///
//  printf("r1=%d,r2=%d\n",r1,r2);  //输出位串交叉点
////
}


void crossover()
{ unsigned child1[lchrom],child2[lchrom];
  float r;
  int r1,r2;           //随机要交叉的两个个体
  int symbol[popsize]; //用来存放选出的要交叉的个体在种群中的编号
  int crossnum;        //要交叉的个体的数量
  int i,j;
  int n;               //n为交叉次数
 
  crossnum=0;
  for (i=0;i<popsize;i++) 
      symbol[i]=-1;
  srand((unsigned)time(NULL));  //以系统时钟作为随机种子
  for (i=0;i<popsize;i++)       //选出crossnum个个体进行交叉操作，将其余个体转到pop中
  {	r=rand()/(float)RAND_MAX;   //产生0~1之间的随机数
    if(r<pc)
	{ symbol[crossnum]=i; 
	  crossnum++;
	}
	else
	{ for (j=0;j<lchrom;j++) 
	     pop[i].chrom[j]=tempop[i].chrom[j];
	} 
  }
  srand((unsigned)time(NULL));
  for(n=(int)(crossnum/2); n>0;n--)  
  { do
	{ r1=rand()%crossnum;  //生成[0,crossnum)内的两个不同的随机数r1,r2，且与以前的不重复；
	}while(symbol[r1]==-1);            
	do
    { r2=rand()%crossnum; 
	}while((r1==r2)||symbol[r2]==-1);

	PMX_crossover(r1,r2,child1,child2); //调用交叉方法函数对选出的两个体交叉，结果在child1,child2中
	for(i=0;i<lchrom;i++)               //将交叉后的子个体转移到pop[r1]、pop[r2]中
	{ pop[r1].chrom[i]=child1[i];
	  pop[r2].chrom[i]=child2[i];
	}
    symbol[r1]=-1;
    symbol[r2]=-1;
/*///
  printf("\n交叉后生成的两个子个体:\n");
  for(i=0;i<lchrom;i++)                       //输出交叉后生成的两个子个体
     printf("%d  ",pop[r1].chrom[i]);
  printf("\n");
  for(i=0;i<lchrom;i++)                       //输出交叉后生成的两个子个体
     printf("%d  ",pop[r2].chrom[i]);
  printf("\n");
*////
  }
}
////////////////////////////////////////////////////////////////


////////////////////////////////////////////////////////////////  
///////****         变异操作mutation()             ****/////////
///////****   变异前的种群在pop中，变异后不变      ****/////////
////////////////////////////////////////////////////////////////
void mutation()
{ void insert_mutation(int p,unsigned child[lchrom]); //调用函数声明（插入变异子函数）
  FILE *fm; 
  unsigned child[lchrom];  //用于接收变异后产生的子个体
  float r;                 //选择要变异的个体时生成的随机数
  int i,j;
  
  if((fm=fopen("G:\\GA\\源程序\\mutation.txt","w+"))==NULL)
	{
		printf("Can't open file:mutation.txt!\n");
		exit(0);
	}

  srand((unsigned)time(NULL));
  for (i=0;i<popsize;i++)       //选择r<pm的个体进行变异，变异后的个体仍在pop中
  {	r=rand()/(float)RAND_MAX;   //产生0~1之间的随机数

    /////输出r(测试)
 //     fprintf(fm,"%f  ",r);

    if(r<pm)
	{ /*/////输出变异前的个体(测试)
      fprintf(fm,"变异前的父个体:\n");
      for(j=0;j<lchrom;j++)               
         fprintf(fm,"%d  ",pop[i].chrom[j]);
      *//////

	  insert_mutation(i,child);
      for(j=0;j<lchrom;j++)                  
          pop[i].chrom[j]=child[j];

	  /*//////输出变异后的子个体（测试）
      fprintf(fm,"\n变异后的子个体:\n");
      for(j=0;j<lchrom;j++)                       
         fprintf(fm,"%d  ",pop[i].chrom[j]);
      fprintf(fm,"\n");
     *////
	}	
  }

  fclose(fm);
}

void insert_mutation(int p,unsigned child[lchrom])
//p:要变异的父个体在种群pop中的编号； child:子个体
{              
  unsigned code_pos,insert_pos;         //code_pos为插入码位置，insert_pos为插入的位置
  int i;

  for(i=0;i<lchrom;i++)              //给子个体赋初值：父个体复制给子个体
	  child[i]=pop[p].chrom[i];
  srand((unsigned)time(NULL));       //随机生成插入码的位置code_pos和插入的位置insert_pos  
  code_pos=rand()%lchrom;            //两个值不能相等也不能为0（旅程的起点是固定的城市0）
  while(code_pos==0)
     code_pos=rand()%lchrom;
  insert_pos=rand()%lchrom;
  while((code_pos==insert_pos)||(insert_pos==0))
      insert_pos=rand()%lchrom;

  if(code_pos<insert_pos)                //进行插入变异
  { for(i=code_pos;i<insert_pos;i++)
        child[i]=pop[p].chrom[i+1]; 
  }
  else
  {	for(i=code_pos;i>insert_pos;i--)
        child[i]=pop[p].chrom[i-1]; 
  }
  child[insert_pos]=pop[p].chrom[code_pos];
}
////////////////////////////////////////////////////////////////



////////////////////////////////////////////////////////////////  
////////****    种群统计结果报告report()          ****//////////
////////////////////////////////////////////////////////////////
void report()
{ int i;
  fprintf(fp,"************************************************************\n");
  fprintf(fp,"种群的总适应度=%f;  平均适应度=%f\n",sumfitness,avgfitness);
  fprintf(fp,"--------------------------------------------------------\n");
  fprintf(fp,"最优个体情况：\n");
  fprintf(fp,"最短旅程： ");
  for(i=0;i<lchrom;i++)
     fprintf(fp,"%d ",bestvidual.chrom[i]);

  fprintf(fp,"最大适应度：%f； 最短旅程距离：%f\n",bestvidual.bestfitness,shortdis);
  fprintf(fp,"最优个体出现的代数：%d\n",bestvidual.generation);

}

////////////////////////////////////////////////////////////////  
/////////********          主函数           ********////////////
////////////////////////////////////////////////////////////////
void main()
{  int i,j;
   double minfit,maxfit;
   if((fp=fopen("G:\\GA\\源程序+小边\\out.txt","a+"))==NULL)
	{
		printf("Can't open file:out.txt!\n");
		exit(0);
	}
   dis_two();   //计算任意两个城市的距离

 
   bestvidual.bestfitness=0;
   bestvidual.generation=0;
   inipop_table();    //生成初始种群及计算初始种群的适应度
/*///输出初始种群(测试)
   fprintf(fp,"初始种群为：\n");
 for (i=0;i<popsize;i++)    
  {for (j=0;j<lchrom;j++)
     fprintf(fp,"%d ",pop[i].chrom[j]);
   fprintf(fp,"\n");
  }
*//////
   sum_avgfit(pop); //求初始种群的总适应度sumfitness和平均适应度avgfitness及最优个体
 /* ///
   fprintf(fp,"初识种群的适应度为：\n");
   for (i=0;i<popsize;i++)    //输出适应度(测试时用)
  {
     fprintf(fp,"%d:  %f ",i,pop[i].fitness);
   fprintf(fp,"\n");
   }
*////  
   shortdis=1/bestvidual.bestfitness;
   for(cur_generation=1;cur_generation<termgen;cur_generation++)   //循环终止条件是：进化代数达到termgen
  { if((shortdis-19.801476)<1e-6)   break;
    select_roulette_expect();     //轮盘赌和期望值结合的方法选择较优个体
 //   select_roulette();     //轮盘赌选择较优个体
    crossover();  //以概率pc对种群中的某些个体进行交叉操作
    mutation();   //以概率pm对种群中的某些个体进行变异操作
	fit();       //求种群中每个个体的适应度及最优个体
    sum_avgfit(pop); //求种群的总适应度sumfitness和平均适应度avgfitness
	shortdis=1/bestvidual.bestfitness;
  }
/*///
fprintf(fp,"最终种群为：\n");
 for (i=0;i<popsize;i++)    //输出最终种群(测试)
  {for (j=0;j<lchrom;j++)
     fprintf(fp,"%d ",pop[i].chrom[j]);
   fprintf(fp,"\n");
  }
*//////

   report();   

 /////验证小边经验公式
  int t;
  int N;
  int edgenum;//记录边在整个序列中的序号
  unsigned citya,cityb;

  fprintf(fp,"--------------------------------------------------------\n");
  fprintf(fp,"小边经验公式测试结果如下：\n");
  if(lchrom%2==0) //城市个数为偶数
	  N=(lchrom*lchrom-4*lchrom+8)/4;
  else
	  N=(lchrom*lchrom-4*lchrom+7)/4;//城市个数为奇数
  for(t=0;t<lchrom;t++)
  { edgenum=1;
    citya=bestvidual.chrom[t];
   if(lchrom-1==t)
          cityb=bestvidual.chrom[0];
    else   cityb=bestvidual.chrom[t+1];

	for(i=0;i<lchrom-1;i++)
		for(j=i+1;j<lchrom;j++)      
			if(dis[citya][cityb]>dis[i][j])  edgenum++;
    edgenum++;
	if(edgenum<=N)
	{ 
	  fprintf(fp,"小边经验公式N=%d；最短回路中的边(%u to %u)的在所有边的排列中的序号为%d(<=N)，故成立！\n",N,citya,cityb,edgenum); 
	  break;
	} 
  }
  if(edgenum>N)  
  	  fprintf(fp,"所求最短回路中不存在一条边，满足其在所有边的排列中的序号<=N，故小边经验公式不成立！\n");
 ///////---end 验证小边经验公式
 

   fclose(fp);

}