旅行商问题(TSP)源代码

#include<iostream> #include<fstream> #include<cstring> #include<stdio.h> #include<math.h> #include<time.h> #include<vector> #include"conio.h" using namespace std; /* Change any of these parameters to match your needs */ #define POPSIZE 100 /* population size */ #define MAXGENS 300 /* max. number of generations */ //#define PXOVER 0.9 /* probability of crossover */ //#define PMUTATION 0.09 /* probability of mutation */ double PXOVER,PMUTATION; int generation; /* current generation no. */ int cur_best; /* best individual */ FILE *galog; /* an output(1) file */ FILE *output; /* an output(2) file */ int cityNumber; typedef int * Route; struct city { double x,y; //coordinate int index; //string cityName; }; struct ganotype /* genotype (GT), a member of the population */ { Route route; double distance; double fitness; double rfitness; double cfitness; double Pc,Pm; }; struct city *CityContainer; struct ganotype population[POPSIZE+1]; /* population */ struct ganotype newpopulation[POPSIZE+1]; /* new population; */ /* replaces the */ /* old generation */ /* Declaration of procedures used by this genetic algorithm */ void OpenFile(void); void adapt(int ); void initialize(void); Route randval(void); void evaluate(void); void keep_the_best(void); void elitist(void); void select(void); void crossover(void); void Xover(int,int); void Xover_2(int one,int two); void mutate(void); void report(void); double twoCityDis(int from,int to); /***************************************************************/ /* Initialization function: Initializes the values of genes */ /* within the variables bounds. It also initializes (to zero) */ /* all fitness values for each member of the population. It */ /* reads upper and lower bounds of each variable from the */ /* input file `gadata.txt'. It randomly generates values */ /* between these bounds for each gene of each genotype in the */ /* population. The format of the input file `gadata.txt' is */ /* var1_lower_bound var1_upper bound */ /* var2_lower_bound var2_upper bound ... */ /***************************************************************/ void OpenFile(void) { FILE *infile; int i; if ((infile = fopen("gadata.txt","r"))==NULL) { fprintf(galog,"\nCannot open input file!\n"); exit(1); } fscanf(infile,"%d",&cityNumber); string cityName=""; CityContainer = new city[cityNumber]; double Coordinate_x,Coordinate_y; city tempcity; for (i = 0; i < cityNumber; i++) { fscanf(infile, "%lf",&Coordinate_x); fscanf(infile, "%lf",&Coordinate_y); tempcity.index=i; tempcity.x=Coordinate_x; tempcity.y=Coordinate_y; CityContainer[i]=tempcity; //cout<<CityContainer[i].index <<" "<<CityContainer[i].x<<" "<<CityContainer[i].y<<endl ; } fclose(infile); } void adapt(int individual) { int a,b,c,d; for(int i=0;i<10;i++) { while(1) { a=rand()%(cityNumber-1); c=rand()%(cityNumber-1); if( a!=c && a+1!=c && a-1!=c) break; } b=a+1; d=c+1; double ab=twoCityDis(population[individual].route[a],population[individual].route[b]); double cd=twoCityDis(population[individual].route[c],population[individual].route[d]); double ac=twoCityDis(population[individual].route[a],population[individual].route[c]); double bd=twoCityDis(population[individual].route[b],population[individual].route[d]); if( ab+cd>ac+bd) { std::swap(population[individual].route[b],population[individual].route[c]); } } } void initialize(void) { Route temRoute; int j ; for (j = 0; j < POPSIZE; j++) { temRoute=randval(); population[j].route =temRoute; population[j].fitness = 0.0; population[j].rfitness = 0.0; population[j].cfitness = 0.0; population[j].distance = 0.0; } population[POPSIZE].route=NULL; population[POPSIZE].cfitness =0.0; population[POPSIZE].rfitness =0.0; population[POPSIZE].fitness =0.0; int rnd; for(j=0;j<10;j++) { rnd=rand()%POPSIZE; adapt(rnd); } //fclose(infile); } /***********************************************************/ /* Random value generator: Generates a value within bounds */ /***********************************************************/ int Have_same_elem(int * route,int begin,int n) { bool same=false; for(int i=begin ;i<n;i++) { for(int j=i+1;j<n;j++) { if(route[i]==route[j]) { same=true; break; } } if(same)break; } if(same) { cout<<"have the same elem"<<endl; return 1; } else return 0; } Route randval(void ) { int low,up; Route tempRoute=new int [cityNumber]; for(int i=0;i<cityNumber;i++) { tempRoute[i]=i; } for(int j=0;j<200;j++) { low=rand()%cityNumber; up=rand()%cityNumber; if(low!=up) { std::swap(tempRoute[low],tempRoute[up]); } } if(Have_same_elem(tempRoute,0,cityNumber)) cout<<"randval have problem"<<endl; return tempRoute; } double countDistance(Route route) { double Total=0.0; int city1,city2; for(int i=0;i<cityNumber-1;i++) { city1=route[i]; city2=route[i+1]; Total=Total+twoCityDis(city1,city2); } Total=Total+twoCityDis(cityNumber-1,0); return Total; } /*************************************************************/ /* Evaluation function: This takes a user defined function. */ /* Each time this is changed, the code has to be recompiled. */ /* The current function is: /*************************************************************/ void evaluate(void) { int mem; double distance; for (mem = 0; mem < POPSIZE; mem++) { distance=countDistance(population[mem].route); population[mem].distance =distance; population[mem].fitness =1.0/distance; } } void evaluate_2(void) { for(int i=0;i<POPSIZE;i++) { population[i].distance=countDistance(population[i].route); } int k,j; double tempDis; Route tempRoute; for( i=0;i<POPSIZE-1;i++) { k=i; for(j=i+1;j<POPSIZE;j++) if(population[k].distance>population[j].distance)k=j; if(i!=k) { tempRoute=population[i].route; tempDis = population[i].distance; population[i].distance=population[k].distance; population[i].route=population[k].route; population[k].distance=tempDis; population[k].route=tempRoute; } } for( i=0;i<POPSIZE;i++) { // population[i].fitness=ALPHA*pow(1-ALPHA,(double)(i-1)); //cout<<population[i].fitness; //cout<<population[i].fitness<<endl; } // getch(); } /***************************************************************/ /* Keep_the_best function: This function keeps track of the */ /* best member of the population. Note that the last entry in */ /* the array Population holds a copy of the best individual */ /***************************************************************/ void keep_the_best() { int mem; cur_best = 0; /* stores the index of the best individual */ for (mem = 0; mem < POPSIZE; mem++) { if (population[mem].fitness > population[POPSIZE].fitness) { cur_best = mem; population[POPSIZE].fitness = population[mem].fitness; }