C++程序—遗传算法TSP.docx

#include#include#include#include#include #include#include using namespace std; #define POPULATION 1000#defineMUTATION_RATE0.5#defineCROSSOVER_RATE0.7#define MAXCITYNUM 100#define ELITISMNUMBER 20int DistanceDataMAXCITYNUMMAXCITYNUM;/最多计算100城市int CityNum;/实际计算的城市数int Longest;/当代的最长路径int Shortest;/当代的最短路径int RandInt(int x,int y) return rand()%(y-x+1)+x;void readData(char *filename)/读入城市距离矩阵FILE *p;p=fopen(filename,r);fscanf(p,%d,&CityNum);for(int i=1;i=CityNum;i+)for(int j=1;j=CityNum;j+)fscanf(p,%d,&DistanceDataij);class route/一个个体public:int RouterNodeMAXCITYNUM;int TotalDistance;int FitNess;bool operator = (const route& lhs)for(int i=0;iMAXCITYNUM;i+)if(RouterNodei!=lhs.RouterNodei)return false;return true;route OneGenerationPOPULATION;/一代route TmpGenerationPOPULATION;/中间一代void CountRouteDistance(route &r)/计算每个个体的路径长度r.TotalDistance=0;for(int i=0;iCityNum-1;i+)r.TotalDistance+=DistanceDatar.RouterNodeir.RouterNodei+1;r.TotalDistance+=DistanceDatar.RouterNodeCityNum-1r.RouterNode0;void mySwap(int &t1,int &t2)int tmp;tmp=t1;t1=t2;t2=tmp;void grabPermutation(route &r)/产生一个随机排列int i=0;for(i=0;iCityNum;i+)r.RouterNodei=i+1;for(i=0;iCityNum;i+)int tmp=RandInt(i,CityNum-1);mySwap(r.RouterNodei,r.RouterNodetmp);void initializeFirstGun()/初始化第一代int i;for(i=0;iPOPULATION;i+)grabPermutation(OneGenerationi);void calculateFitness()/计算一代的适应性int i;for(i=0;iLongest)Longest=OneGenerationi.TotalDistance;if(OneGenerationi.TotalDistanceShortest)Shortest=OneGenerationi.TotalDistance;for(i=0;iPOPULATION;i+)OneGenerationi.FitNess=Longest-OneGenerationi.TotalDistance;void elitism(int DangQianDaiShu)/每一代最优秀的前几个保留/冒泡排序int i,j;route tmp;for(i=1;iPOPULATION;i+)for(j=0;j=POPULATION-1-i;j+)if(OneGenerationj.FitNessOneGenerationj+1.FitNess)tmp=OneGenerationj;OneGenerationj=OneGenerationj+1;OneGenerationj+1=tmp;for(i=0;iELITISMNUMBER;i+)TmpGenerationi=OneGenerationi;printf(第%d代;路径长度%d;路径:,DangQianDaiShu,OneGeneration0.TotalDistance);for(i=0;iCityNum;i+)printf(%d ,OneGeneration0.RouterNodei);printf(n);route selection()int BestFitness=0;int Position;int RandShu;int i;for(i=0;iBestFitness)Position=RandShu;BestFitness=OneGenerationRandShu.FitNess;return OneGenerationPosition;float RandFloat() return (rand()/(RAND_MAX+1.0);void crossover(route mather,route father,route &baby1,route &baby2)baby1=mather;baby2=father;if ( (RandFloat() CROSSOVER_RATE)| (mather= father) return;/first we choose a section of the chromosomeint beg = RandInt(0, CityNum-2);int end = beg;/find an endwhile (end = beg)end = RandInt(0, CityNum-1);for (int pos = beg; pos end+1; +pos)/these are the genes we want to swapint gene1 =mather.RouterNodepos;int gene2 =father.RouterNodepos;/find and swap them in baby1int tmp1;int tmp2;int i;for(i=0;iCityNum;i+)if(baby1.RouterNodei=gene1)tmp1=i;for(i=0;iCityNum;i+)if(baby1.RouterNodei=gene2)tmp2=i;mySwap(baby1.RouterNodetmp1,baby1.RouterNodetmp2);/find and swap them in baby2for(i=0;iCityNum;i+)if(baby2.RouterNodei=gene1)tmp1=i;for(i=0;i MUTATION_RATE) return;if(RandFloat()0.5)int tmp1;int tmp2;/for(int i=1;itmp2)mySwap(tmp1,tmp2);int i;for(i=tmp1;i=tmp2;i+)baby.RouterNodei=temp.RouterNodetmp1+tmp2-i;/mySwap(baby.RouterNodetmp1,baby.RouterNodetmp2);/elsefor(int i=0;i2000)break;Dijidai+;/选择&杂交&变异int NowGunNum=ELITISMNUMBER;while(1)route mather=selection();route father=selection();route baby1;route baby2;crossover(mather,father,baby1,baby2);mutate(baby1);mutate(baby2);if(NowGunNumPOPULATION)T