遗传算法(GA)求解TSP问题C++程序

#include<iostream> #include<math.h> #include<ctime> using namespace std; #define PopulationSize 100 //种群大小为100 #define MaxAlgebra 500 //最大代数定为500代 #define PC 0.9 //交叉概率 #define PM 0.05 //变异概率 #define ChromLength 30 //染色体长度(即为城市的个数) #define CityTotal 30 //城市个数 struct Chrom //染色体(也即是个体)的结构 { int CityNum[ChromLength]; //每个染色体中的城市路线规划 }Population[PopulationSize],TempPopulation[PopulationSize]; //定义种群和临时种群 int BestChrom; //记录最优的个体 int BestPath[ChromLength]; //记录最优路径 int City[CityTotal][2] = { { 41,94 },{ 37,84 },{ 54,67 },{ 25,62 },{ 7,64 }, { 2,99 },{ 68,58 },{ 71,44 },{ 54,62 },{ 83,69 },{ 64,60 },{ 18,54 },{ 22,60 },{ 83,46 }, { 91,38 },{ 25,38 },{ 24,42 },{ 58,69 },{ 71,71 },{ 74,78 },{ 87,76 },{ 18,40 },{ 13,40 }, { 82,7 },{ 62,32 },{ 58,35 },{ 45,21 },{ 41,26 },{ 44,35 },{ 4,50 } }; void GeneratePopulation() //生成初始种群 { int Num = 0; int i, j; int temp; while (Num < PopulationSize-1) { for (i = 0; i < PopulationSize; i++) { for (j = 0; j < ChromLength; j++) { Population[i].CityNum[j] = j; } } Num++; for (i = 0; i < ChromLength-1; i++) { for (j = i + 1; j < ChromLength; j++) { temp = Population[Num].CityNum[i]; Population[Num].CityNum[i] = Population[Num].CityNum[j]; Population[Num].CityNum[j] = temp; Num++; if (Num >= PopulationSize) { break; } } } while (Num < PopulationSize) { int Point1 = rand() % ChromLength; int Point2 = rand() % ChromLength; temp = Population[Num].CityNum[Point1]; Population[Num].CityNum[Point1] = Population[Num].CityNum[Point2]; Population[Num].CityNum[Point2] = temp; Num++; } } } double PathDistance(int ChromIndex) { double Path = 0; //路径和 int i; for (i = 0; i < ChromLength-1; i++) { Path += sqrt(pow((City[Population[ChromIndex].CityNum[i]][0] - City[Population[ChromIndex].CityNum[i + 1]][0]), 2) + pow((City[Population[ChromIndex].CityNum[i]][1] - City[Population[ChromIndex].CityNum[i + 1]][1]), 2)); } Path += sqrt(pow((City[Population[ChromIndex].CityNum[0]][0] - City[Population[ChromIndex].CityNum[ChromLength-1]][0]), 2) + pow((City[Population[ChromIndex].CityNum[0]][1] - City[Population[ChromIndex].CityNum[ChromLength-1]][1]), 2)); return Path; } double PathDistanceExtend(int *Temp) { double Path = 0; //路径和 int i; for (i = 0; i < ChromLength - 1; i++) { Path += sqrt(pow((City[Temp[i]][0] - City[Temp[i+1]][0]), 2) + pow((City[Temp[i]][1] - City[Temp[i + 1]][1]), 2)); } Path += sqrt(pow((City[Temp[0]][0] - City[Temp[ChromLength - 1]][0]), 2) + pow((City[Temp[0]][1] - City[Temp[ChromLength - 1]][1]), 2)); return Path; } void FitnessFunction() //适值函数，找出当代种群中最优解 { int i; double MinPath = PathDistance(0); for (i = 1; i < PopulationSize; i++) { if (PathDistance(i) < MinPath) { BestChrom = i; MinPath = PathDistance(i); } } } void Cross() //遗传运算--交叉(双切点交叉) { int j, k; int Chrom1, Chrom2; //进行交叉操作的染色体 int Pointcut1, Pointcut2, temp; //交叉的两个切点 int Conflict1, Conflict2; //交叉操作后染色体1、2中基因冲突的个数 int ConflictIndex1[ChromLength], ConflictIndex2[ChromLength]; //记录冲突基因的位置 int temp1, temp2; //用于交换冲突基因的过渡 int Move = 0; double CrossProbability; //染色体的交叉概率 while(Move<ChromLength-1) { CrossProbability = ((double)rand()) / RAND_MAX; if (CrossProbability > PC) //此次不交叉 { Move += 2; continue; } Chrom1 = Move; Chrom2 = Move + 1; Pointcut1 = (int)(((double)rand()) / (RAND_MAX + 1.0)*ChromLength); //随机生成切点1 Pointcut2 = (int)(((double)rand()) / (RAND_MAX + 1.0)*ChromLength); //随机生成切点2 while (Pointcut1 > ChromLength - 2 || Pointcut1 < 1) { Pointcut1=(int)(((double)rand()) / (RAND_MAX + 1.0)*ChromLength); } while (Pointcut2 > ChromLength - 2 || Pointcut2 < 1) { Pointcut2=(int)(((double)rand()) / (RAND_MAX + 1.0)*ChromLength); } if (Pointcut1 > Pointcut2) //确保Pointcut1<=Pointcut2 { temp = Pointcut1; Pointcut1 = Pointcut2; Pointcut2 = temp; } for (j = Pointcut1; j <= Pointcut2; j++) //交换切点Pointcut1和切点Pointcut2之间的基因 { temp = Population[Chrom1].CityNum[j]; Population[Chrom1].CityNum[j] = Population[Chrom2].CityNum[j]; Population[Chrom2].CityNum[j] = temp; } Conflict1 = 0,Conflict2 = 0; for (j = 0; j < Pointcut1; j++) //寻找交叉操作的染色体中交叉位置之前的冲突基因个数和位置 { for (k = Pointcut1; k <= Pointcut2; k++) { if (Population[Chrom1].CityNum[j] == Population[Chrom1].CityNum[k]) //表示冲突 { ConflictIndex1[Conflict1] = j; Conflict1++; } if (Population[Chrom2].CityNum[j] == Population[Chrom2].CityNum[k]) //表示冲突 { ConflictIndex2[Conflict2] = j; Conflict2++; } } } for (j = Pointcut2 + 1; j < ChromLength; j++)//寻找交叉操作的染色体中交叉位置之后的冲突基因个数和位置 { for (k = Pointcut1; k <= Pointcut2; k++) { if (Population[Chrom1].CityNum[j] == Population[Chrom1].CityNum[k]) //表示冲突 { ConflictIndex1[Conflict1] = j; Conflict1++; } if (Population[Chrom2].CityNum[j] == Population[Chrom2].CityNum[k]) //表示冲突 { ConflictIndex2[Conflict2] = j; Conflict2++; } } } if (Conflict1 == Conflict2&&Conflict1 > 0) { for (j = 0; j < Conflict1; j++) { temp1 = ConflictIndex1[j]; temp2 = ConflictIndex2[j]; temp = Population[Chrom1].CityNum[temp1]; //将交叉操作的两个染色体的冲突基因互换就可以解决冲突问题 Population[Chrom1].CityNum[temp1] = Population[Chrom2].CityNum[temp2]; Population[Chrom2].CityNum[temp2] = temp; } } Move += 2; } } void Variation() //遗传运算--变异 { //随机选取染色体中两个点，将其对换位置 int i; int VariaPoint1, VariaPoint2; //进行变异的点 int Temp; double VariaProbability; //染色体变异的概率 for (i = 0; i < PopulationSize; i++) { VariaProbability = ((double)rand()) / RAND_MAX; if (VariaProbability > PM) //如果随机生成的变异概率在设置的变异概率内，则该染色体将进行变异 { continue; } /*变异操作*/ VariaPoint1 = (int)(((double)rand()) / (RAND_MAX + 1.0)*ChromLength); VariaPoint2 = (int)(((double)rand()) / (RAND_MAX + 1.0)*ChromLength); while (VariaPoint1 > ChromLength - 1) { VariaPoint1 = (int)(((double)rand()) / (RAND_MAX + 1.0)*ChromLength); } while (VariaPoint2 > ChromLength - 1) { VariaPoint2 = (int)(((double)rand()) / (RAND_MAX + 1.0)*ChromLength); } Temp = Population[i].CityNum[VariaPoint1]; Population[i].CityNum[VariaPoint1] = Population[i].CityNum[VariaPoint2]; Population[i].CityNum[VariaPoint2] = Temp; } } void SelectPolicy() //选择策略(轮转法) { int i, j; double Temp=0; double SelectProbability; //选择概率 double Fitness[PopulationSize]; //适应度 double FitnessPro[PopulationSize]; //适应度概率 double Sum = 0; for (i = 0; i < PopulationSize; i++) { Fitness[i] = 1 / PathDistance(i); Sum += Fitness[i]; } for (i = 0; i < PopulationSize; i++) { FitnessPro[i] = Fitness[i] / Sum; //某个染色体在种群中的适应度的概率 Temp += FitnessPro[i]; } for (i = 0; i < PopulationSize; i++) { SelectProbability = ((double)rand()) / RAND_MAX; for (j = 0; j < PopulationSize; j++) { SelectProbability = SelectProbability - FitnessPro[j]; if (SelectProbability <= 0) { for (int k = 0; k < ChromLength; k++) { TempPopulation[i].CityNum[k] = Population[j].CityNum[k]; } break; } } } for (i = 0; i < PopulationSize; i++) { for (j = 0; j < ChromLength; j++) { Population[i].CityNum[j] = TempPopulation[i].CityNum[j]; } } } void EvoRever() //进化逆转 { int i, j, temp, Num; int ReverFlag; //逆转标志 int