tsp3.cpp

用遗传算法解决tsp问题

/*********************************************************************/
/*          Solving Tsp using Genetic Algorithms and C++             */
/*********************************************************************/

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<fstream>
#include<iostream>
#include <memory.h>
#include<string>
using namespace std;
#include <time.h>
/* Change any of these parameters to match your need.*/

#define PopSize 50					// 每代的基因成员数
#define MaxGens 50000				// Max No. of generation.     最大代数
#define NumVars 10					// No. of problem variables.  城市数
double PXCross; 					// probality of crossover.
double PMutation; 
int a=0;
  double fmax,favg,fstddev;  				// probality of mutation.
#define times PopSize/10			//被淘汰的比例，这里为
#define NOW 144

double Gbase[NumVars][NumVars]={
0,41,67,34,0,69,24,78,58,62,
64,0,5,45,81,27,61,91,95,42,
27,36,0,91,4,2,53,92,82,21,
16,18,95,0,47,26,71,38,69,12,
67,99,35,94,0,3,11,22,33,73,
64,41,11,53,68,0,47,44,62,57,
37,59,23,41,29,78,0,16,35,90,
42,88,6,40,42,64,48,0,46,5,
90,29,70,50,6,1,93,48,0,29,
23,84,54,56,40,66,76,31,8,0,
};   // declarate Gbase to store the distant of two city.

int generation;          // Current generation no.
int CurBest;             // best individual.
FILE *Tsp,*All;               // An output file.
double best_val=0;    //Best population fitness.
double avg=1;         //Avg population fitness.


struct GenoType
{
  int gene[NumVars];     // A string of variables.        基因长度:10
  double fitness;  
  float ratio;
  float cratio;
};

GenoType population[PopSize+1];      // population.   population[51]
GenoType newpopulation[PopSize+1];    // new population replaces the old generation.   newpopulation[51]
GenoType last;

/* Declaration of procedure used by this genetic algorithms */
            //void SetGbase();
void GetRandoms(int* result);
void initialize();
void evaluate();
void best();
void renew();
void select();
void crossover();
void mutate();
void report();
void data();
double pp();
double pcs(int a,int b);
double pms(int c);
//void summarize();
int	 IntGenerate(int);
void swap(int *,int *);


/*******************************************************/
/*                Exchange two numbers.                */
/*******************************************************/
void swap(int *a,int *b)            
{
  int temp;
  temp=*a;
  *a=*b;
  *b=temp;
}

/*********************************************/
/*   generate a number in a specific range,  */ 
/* such as 0 to 10 (0 included, 10 excluded.)*/
/*********************************************/
int IntGenerate(int range)                       
{  
	return (rand()+time(0))%range;  
}


/*******************************************************/
/*            The initialization function              */
/*******************************************************/
void initialize()                               
{ 
   int matrix[NumVars];            //matrix[10]
   for(int i=0; i<NumVars; i++)
   matrix[i]=i;
   for(int j=0;j<PopSize;j++)
   {
     for(int k=0;k<2*NumVars;k++)
     {
       int x1=IntGenerate(NumVars);
	   int x2=IntGenerate(NumVars);
	   swap(&matrix[x1],&matrix[x2]);
     }
     for(int l=0;l<NumVars;l++)
     population[j].gene[l]=matrix[l];
   }
}

/*********************************************/
/* 计算每一代每个个体的适应度                   */
/*********************************************/
void evaluate()                                
{
	int a,b,c,d;
	for(int mem=0;mem<PopSize;mem++)
	{
		population[mem].fitness=0;
		for(int i=0;i<NumVars;i++)
		{
			a=i%NumVars;
			b=(i+1)%NumVars;
			c=population[mem].gene[a];
			d=population[mem].gene[b];
			population[mem].fitness=population[mem].fitness+Gbase[c][d];
		}  
	}
}


/********************************************************/
/*    把每一代最好的个体拷贝到population[PopSize] 中  */
/********************************************************/

void best()
{
  
	int mem;
	CurBest=0;  // Store the index of the best individual.
	for(mem=0;mem<PopSize;mem++)
		if(population[mem].fitness<population[CurBest].fitness) 
			CurBest=mem;

	population[PopSize]=population[CurBest];
	return;
}


/************************************************************************************************/
/*    比较当前和上一代的最好个体，当前的好就将其保存，上一代好就用上一代的替换当前最差的个体   */ 
/************************************************************************************************/
void renew()       
{
	int i,wor=0;
	if(population[PopSize].fitness<last.fitness){
		last=population[PopSize];
		return;
	}
	for(i=0;i<PopSize;i++){
		if(population[i].fitness>population[wor].fitness)
			wor=i;
	}
	population[wor]=last;
	return;
}


/**************************************************************/
/* Selection function: Standard proportional selection for    */
/* minimization problems incorporating elitist model - makes  */
/* sure that the best member survives                         */
/**************************************************************/

void select()      // 轮盘选择
{
  int mem,i,j;
  double sum=0;
  int dup[times],gone[times];
  float tmp;

  for(i=0;i<times;i++)
  {
	  dup[i]=0;  gone[i]=0;
  }
  
  for(mem=0;mem<PopSize;mem++)
	  sum+=population[mem].fitness;

  for(mem=0;mem<PopSize;mem++)
	  population[mem].ratio=population[mem].fitness/sum;

  population[0].cratio=population[0].ratio;
  for(mem=1;mem<PopSize;mem++)
	    population[mem].cratio=population[mem].ratio+population[mem-1].cratio;

  for(i=0;i<times;i++)
  {
	  tmp=(double) IntGenerate(100)/100;
	  if(tmp<=population[0].cratio) dup[i]=0;
	  else{
		  for(j=0;j<PopSize;j++)
		  {
			  if(population[j].cratio<tmp && tmp<=population[j+1].cratio)
			  {
				  dup[i]=j+1;
				  break;
			  }
		  }
	  }
  }

  for(mem=0;mem<PopSize;mem++)
	    population[mem].cratio=1-population[mem].cratio;

  for(i=0;i<times;i++)
  {
	  tmp=(double) IntGenerate(100)/100; 
	  if(tmp>=population[0].cratio) gone[i]=0;
	  else{
		  for(j=0;j<PopSize;j++)
		  {
			  if(population[j].cratio>tmp && tmp>=population[j+1].cratio)
			  {
				  gone[i]=j;
				  break;
			  }
		  }
	  }
  }

  for(i=0;i<times;i++)
  	  population[dup[i]]=population[gone[i]];
}


/***************************************************************/
/* Crossover selection: selects two parents that take part in  */
/* the crossover. Implements a single point crossover          */
/***************************************************************/
void crossover()
{
  int i,j,max,min,k,n;
  min=0;
  //max=0;
  double x;
  int twemp;
  int temp;
  int ran1,ran2;
  int m,m2,m3;
  int father[NumVars];
  int mother[NumVars];
  int randoms[PopSize];
  GetRandoms(randoms);
 // printf("\n%d",a);
 // printf("\n");
 // a++;
  for(i=0;i<PopSize;)
  { 
	  x=rand()%1000/1000.0;
	  ran1=randoms[i];
	  ran2=randoms[i+1];
	  PXCross=pcs(ran1,ran2);
	  if(x<PXCross){
	  min=IntGenerate(NumVars);
	  max=IntGenerate(NumVars);
//	  printf("% d",min);
	  if(max<min)
	   {
		  temp=min;
		  min=max;
		  max=temp;
	   }
	   //=============================个体1交换部分的不同元素
       m=0;
	   for(k=min;k<=max;k++){
		   n=0;
		   for(j=min;j<=max;j++){
			   if(population[ran1].gene[k]!=population[ran2].gene[j]){
				   n++;
			   }
		   }
		   if(n==max-min+1){
			   father[m]=population[ran1].gene[k];
			   m++;
		   }
	   }
	   m2=m;
	 //=============================个体2交换部分的不同元素
	   m=0;
	   for(k=min;k<=max;k++){
		   n=0;
		   for(j=min;j<=max;j++){
			   if(population[ran2].gene[k]==population[ran1].gene[j]) break;
			   else n++;
		   }
		   if(n==max-min+1){
			   mother[m]=population[ran2].gene[k];
			   m++;
		   }
	   }
	   //===========================================
	   for(k=min;k<=max;k++){
			twemp=population[ran1].gene[k];		
			population[ran1].gene[k]=population[ran2].gene[k];
			population[ran2].gene[k]=twemp;
			
		}
   //============================个体1交换部分的不同元素补进个体1
	   m3=0;
	   for(k=min;k<=max;k++){
		   for(j=0;j<NumVars;j++){
			   if(population[ran1].gene[k]==population[ran1].gene[j]&&!(j>=min&&j<=max)){
					population[ran1].gene[j]=father[m3];
					m3++;
					break;
			   }
		   }
		}
	   //=====================
	   m3=0;
	   for(k=min;k<=max;k++){
		   for(j=0;j<NumVars;j++){
			   if(population[ran2].gene[k]==population[ran2].gene[j]&&!(j>=min&&j<=max)){
					population[ran2].gene[j]=mother[m3];
					m3++;
					 break;
			   }
		   }
		}
	  }
	   i=i+2;
  }
 // printf("\n");
}


/**************************************************************/
/* Mutation: Random uniform mutation. A variable selected for */
/* mutation is replaced by a random value between lower and   */
/* upper bounds of this variable                              */
/**************************************************************/
void mutate()
{
  int i;
  double x;
  for(i=0;i<PopSize;i++)
  {    
	  x=rand()%1000/1000.0;
	  PMutation=pms(i);
	  if(x<PMutation)
	  {
	    int x1=IntGenerate(NumVars);
		int x2=IntGenerate(NumVars);
		swap(&population[i].gene[x1],&population[i].gene[x2]);
	  }
  }
}

//**************************************************************
void data()
{
	int i;
  double stddev;      //std. deviation of population fitness.
  double sum_square;  //sum of square for std. calc.
  double square_sum;  //square of sum for std. calc.
  double sum;         //total population fitness.
 
  sum=0.0;
  sum_square=0.0;
  
  
  for(i=0;i<PopSize;i++)
  {
	  sum+=population[i].fitness;
	  sum_square+=population[i].fitness*population[i].fitness;
  }
  avg=sum*1.0/(1.0*PopSize);
  square_sum=avg*avg*PopSize;
  stddev=sqrt((sum_square-square_sum)/(PopSize-1));
  best_val=last.fitness;

  fmax=best_val;
  favg=avg;
  fstddev=stddev;
}

/***************************************************************/
/* Report function: Reports progress of the simulation. Data   */
/* dumped into the  output file are separated by commas        */
/***************************************************************/
void report()
{
  
 fprintf(Tsp, "\n%5d.          %6.3f         %6.3f         %6.3f ", generation, 
                                      fmax, favg, fstddev);

}
//***********************************************************
//pc的自适应计算
//**********************************************************
double pcs(int a,int b)
{ 
	double larger;
	double k1=0.8;
	double k2=0.8;
	double pc;
	if(population[a].fitness>population[b].fitness){
		larger=population[a].fitness;
	}
	else{
		larger=population[b].fitness;
	}
	if(larger>=favg){
		pc=k1*(fmax-larger)/(fmax-favg);
	}
	else{
		pc=k2;
	}
	return pc;
}
//***********************************************************
//pm的自适应计算
//**********************************************************
double pp()
{
	double k4=0.1;
	double pms=k4;
	return pms;
}
double pms(int c)
{ 
	double k3=0.1;
	double k4=0.1;
	double pms=0;
	if(population[c].fitness>=favg){
		pms=k3*(fmax-population[c].fitness)/(fmax-favg);
	}
	else{
		pms=k4;
	}
	return pms;
}
/**************************************************************/
/*将数组重新随机排序
/**************************************************************/
void GetRandoms(int* result)
{
	int all[PopSize];
	int i, r, tmp;
	for(i = 0; i < PopSize; i++) {
		all[i] = i + 1;
	}
	for(i = 0; i < PopSize; i++) {
		r = i + rand() % (PopSize - i);
		tmp = all[r];
		all[r] = all[i];
		all[i] = tmp;
	}
	memcpy(result, all, PopSize * sizeof(int));
}

/**************************************************************/
/* Main function: Each generation involves selecting the best */
/* members, performing crossover & mutation and then          */
/* evaluating the resulting population, until the terminating */
/* condition is satisfied                                     */
/**************************************************************/

int main()
{
  int i,z;
  PXCross=0.8; 					// probality of crossover.
  PMutation=0.1;
  fmax=0;
  favg=0;

  
  if ((All = fopen("All.txt","w"))==NULL)		//All.txt用作统计，包含最优解和得到最优解所需的后代数
  {
      exit(1);
  }
  
  for(z=0;z<100;z++){                  //程序运行的次数

	  int zz=z;
	  char fname[8]="   .txt";
	  for(i=0;i<3;i++){
		  fname[2-i]=zz%10+48;
		  zz=zz/10;
	  }


	  if ((Tsp = fopen(fname,"w"))==NULL)
	  {
		  exit(1);
	  }
	  generation = 0;
	  last.fitness=9999999;

	  fprintf(Tsp, "\n generation     best            average         standard \n");
	  fprintf(Tsp, " number         value           fitness         deviation \n");

	  initialize();
	  evaluate();
	  best();
	  renew();


		srand(time(0));
	  while(generation<MaxGens && last.fitness>NOW)
	  {
		  data();
		  crossover();
		  mutate();
		  evaluate();
		  select();
		  best();
		  renew();
		  report();
		  generation++;

	  }

	  fprintf(Tsp,"\n\n Simulation completed\n");
	  fprintf(Tsp,"\n Best member: \n");
	  for (i = 0; i < NumVars; i++)
		  fprintf (Tsp,"\n var(%d) = %3d ",i,population[PopSize].gene[i]);  
	  fprintf(Tsp,"\n\n Best fitness = %7.3f     ",last.fitness);
	  fclose(Tsp);
	  printf("Success\n");

	  fprintf(All,"%d\n",generation);
  }
  fclose(All);

  return 0;
}