区块链技术博客
www.b2bchain.cn

遗传算法求解TSP旅行商问题C++(2020.11.11)

这篇文章主要介绍了遗传算法求解TSP旅行商问题C++(2020.11.11)的讲解,通过具体代码实例进行17858 讲解,并且分析了遗传算法求解TSP旅行商问题C++(2020.11.11)的详细步骤与相关技巧,需要的朋友可以参考下https://www.b2bchain.cn/?p=17858

本文实例讲述了2、树莓派设置连接WiFi,开启VNC等等的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7039.html。具体如下:

遗传算法求解TSP(C++)

  • 1、输入数据文件:bayg29.tsp
  • 2 、头文件
  • 3、所需的类
  • 4 、自定义函数
  • 5 、全局变量
  • 6 、主函数
  • 7 、运行结果

1、输入数据文件:bayg29.tsp

29个城市的编号和坐标数据如下所示;

   1    1150.0  1760.0    2     630.0  1660.0    3      40.0  2090.0    4     750.0  1100.0    5     750.0  2030.0    6    1030.0  2070.0    7    1650.0   650.0    8    1490.0  1630.0    9     790.0  2260.0   10     710.0  1310.0   11     840.0   550.0   12    1170.0  2300.0   13     970.0  1340.0   14     510.0   700.0   15     750.0   900.0   16    1280.0  1200.0   17     230.0   590.0   18     460.0   860.0   19    1040.0   950.0   20     590.0  1390.0   21     830.0  1770.0   22     490.0   500.0   23    1840.0  1240.0   24    1260.0  1500.0   25    1280.0   790.0   26     490.0  2130.0   27    1460.0  1420.0   28    1260.0  1910.0   29     360.0  1980.0 

2 、头文件

#include <iostream> #include <fstream> #include <string> #include <time.h> #include <random> using namespace std; 

3、所需的类

代码中我们用到了四种类:City、Graph、Ranseti、GA
城市类City

class City { public: 	string name;//城市名称 	double x, y;//城市点的二维坐标 	void shuchu() 	{ 		std::cout <<name+":"<<"("<< x << "," << y <<")"<< endl; 	} }; 

包含城市的地图类Graph:

class Graph { public: 	City city[citycount];//城市数组 	double distance[citycount][citycount];//城市间的距离矩阵 	void Readcoordinatetxt(string txtfilename)//读取城市坐标文件的函数 	{ 		ifstream myfile(txtfilename, ios::in); 		double x = 0, y = 0; 		int z = 0; 		if (!myfile.fail()) 		{ 			int i = 0; 			while (!myfile.eof() && (myfile >> z >> x >> y)) 			{ 				city[i].name = to_string(_Longlong(z));//城市名称转化为字符串 				city[i].x = x; city[i].y = y; 				i++; 			} 		} 		else 			cout << "文件不存在"; 		myfile.close();//计算城市距离矩阵 		for (int i = 0; i < citycount; i++) 			for (int j = 0; j < citycount; j++) 			{ 				distance[i][j] = sqrt((pow((city[i].x - city[j].x), 2) + pow((city[i].y - city[j].y), 2))/10.0);//计算城市ij之间的伪欧式距离 				if (round(distance[i][j] < distance[i][j]))distance[i][j] = round(distance[i][j]) + 1; 				else distance[i][j] = round(distance[i][j]); 			} 	} 	void shuchu() 	{ 		cout << "城市名称 " << "坐标x" << " " << "坐标y" << endl; 		for (int i = 0; i < citycount; i++) 			city[i].shuchu(); 		cout << "距离矩阵: " << endl; 		for (int i = 0; i < citycount; i++) 		{ 			for (int j = 0; j < citycount; j++) 			{ 				if (j == citycount - 1) 					std::cout << distance[i][j] << endl; 				else 					std::cout << distance[i][j] << "  "; 			} 		} 	} }; 

染色体类Ranseti:

class Ranseti { 	public: 		int *X; 		double fitness; 		void Init() 		{ 			X = new int[citycount]; 			int *M = Random_N(citycount); 			for (int j = 0; j < citycount; j++) 				X[j] = *(M + j); 			fitness=0; 		} 		void shuchu() 		{ 			for (int j = 0; j < citycount; j++) 			{ 				if (j == citycount -1) std::cout << X[j] << " "<<fitness<<endl; 				else std::cout << X[j] << "->"; 			} 		} }; 

遗传算法类GA

class GA { public: 	Ranseti *oldranseti;//上一代种群 	Ranseti *ranseti;//下一代种群 	int Pop_Size;//种群大小 	int Itetime;//迭代次数 	double Cross_Prob;//交叉概率 	double Bianyi_Prob;//变异概率 	Ranseti Bestranseti;//最佳染色体个体 	double Bestlength;//最短路径的长度 	double *Leiji_Prob;//累积选择概率 	void Init(int popsize,int itetime,double crossprob,double bianyiprob,string filename) 	{ 		Map_City.Readcoordinatetxt(filename); 		Map_City.shuchu(); 		Pop_Size = popsize; 		Itetime = itetime; 		Cross_Prob = crossprob; 		Bianyi_Prob = bianyiprob; 		oldranseti = new Ranseti[Pop_Size]; 		ranseti = new Ranseti[Pop_Size]; 		Leiji_Prob = new double[Pop_Size]; 		for (int i = 0; i < Pop_Size; i++) 		{ 			oldranseti[i].Init(); 			oldranseti[i].fitness = Evaluate(i);//初始化适应度 		} 		int bestid = -1; 		for (int i = 0; i < Pop_Size; i++) 		{ 			int j = 0; 			for (; j < Pop_Size; j++) 			{ 				if (oldranseti[i].fitness > oldranseti[j].fitness)break; 			} 			if (j == Pop_Size) 			{ 				bestid = i; 				break; 			} 		} 		Bestranseti.Init(); 		Bestranseti.fitness = 0; 		for (int j = 0; j < citycount; j++) 			Bestranseti.X[j] = oldranseti[bestid].X[j]; 		for (int j = 0; j < citycount - 1; j++) 			Bestranseti.fitness += Map_City.distance[Bestranseti.X[j]][Bestranseti.X[j + 1]]; 		Bestranseti.fitness += Map_City.distance[Bestranseti.X[citycount - 1]][Bestranseti.X[0]]; 		Bestlength = Bestranseti.fitness; 	} 	void shuchu() 	{ 		for (int i = 0; i < Pop_Size; i++) 			oldranseti[i].shuchu(); 	} 	double Evaluate(int k)//计算染色体适应值的函数,计算路径距离 	{ 		double distancer=0; 		for (int j = 0; j < citycount-1; j++) 			distancer += Map_City.distance[oldranseti[k].X[j]][oldranseti[k].X[j + 1]]; 		distancer += Map_City.distance[oldranseti[k].X[citycount -1]][oldranseti[k].X[0]]; 		oldranseti[k].fitness = distancer; 		return distancer; 	} 	void CalculateLeijiProb() 	{ 		double Sumfitness = -0; 		for (int i = 0; i < Pop_Size; i++) 			oldranseti[i].fitness = Evaluate(i); 		for (int i = 0; i < Pop_Size; i++) 			Sumfitness += oldranseti[i].fitness;//计算种群中所有染色体的适应值之和 		double *SelectProb; 		SelectProb=new double[Pop_Size]; 		for (int i = 0; i < Pop_Size; i++) 			SelectProb[i] = oldranseti[i].fitness / Sumfitness;//计算每个染色体的选择概率 		for (int i = 0; i < Pop_Size; i++) 		{ 			Leiji_Prob[i] = 0; 			for (int j = 0; j <= i; j++) 				Leiji_Prob[i] += SelectProb[j];//计算每个染色体的累积概率 		} 	} 	void Roulette() 	{ 		for (int i = 0; i < Pop_Size; i++)//轮盘赌选择产生新种群 		{ 			double suijishu = u0(random);//产生一个0-1之间随机数 			int j = 0; 			for (; j < Pop_Size; j++) 			{ 				if (suijishu <= Leiji_Prob[j])break; 			} 			ranseti[i].Init(); 			for(int k=0;k<citycount;k++) 				ranseti[i].X[k] = oldranseti[j].X[k]; 		} 		for (int i = 0; i < Pop_Size; i++) 		{ 			ranseti[i].fitness = 0; 			for (int j = 0; j < citycount - 1; j++) 				ranseti[i].fitness += Map_City.distance[ranseti[i].X[j]][ranseti[i].X[j + 1]]; 			ranseti[i].fitness += Map_City.distance[ranseti[i].X[citycount - 1]][ranseti[i].X[0]]; 		} 	} 	void Cross(double Pc)//交叉函数采用部分匹配交叉策略 	{ 		for (int k = 0; k+1 < Pop_Size; k = k + 2) 		{ 			int k1 = k; 			int k2 = k1 + 1; 			double suijishu = u0(random); 			if (Pc > suijishu) 			{ 				int pos1 = rand() % citycount, pos2 = rand() % citycount; 				if (pos1 > pos2)//确保pos1小于pos2 				{ 					pos1 += pos2; 					pos2 = pos1 - pos2; 					pos1 = pos1 - pos2; 				} 				for (int j = 0; j <citycount; j++) 				{ 					if (j >= pos1 && j <= pos2) 					{ 						ranseti[k1].X[j]= ranseti[k1].X[j]+ranseti[k2].X[j]; 						ranseti[k2].X[j] = ranseti[k1].X[j] - ranseti[k2].X[j]; 						ranseti[k1].X[j] = ranseti[k1].X[j] - ranseti[k2].X[j]; 					} 				} 				int cishu = pos2 - pos1 + 1; 				for (int j = 0; j<citycount; j++) 				{ 					if ((j<pos1) || (j>pos2)) 					{ 						for (int jishu = 1; jishu <= cishu; jishu++) 						{ 							for (int m = pos1; m <= pos2; m++) 							{ 								if (ranseti[k1].X[j] == ranseti[k1].X[m]) 								{ 									ranseti[k1].X[j] = ranseti[k2].X[m]; 								} 							} 						} 					} 				} 				for (int j = 0; j<citycount; j++) 				{ 					if ((j<pos1) || (j>pos2)) 					{ 						for (int jishu = 1; jishu <= cishu; jishu++) 						{ 							for (int m = pos1; m <= pos2; m++) 							{ 								if (ranseti[k2].X[j] == ranseti[k2].X[m]) 								{ 									ranseti[k2].X[j] = ranseti[k1].X[m]; 								} 							} 						} 					} 				} 			} 		} 		for (int i = 0; i < Pop_Size; i++) 		{ 			ranseti[i].fitness = 0; 			for (int j = 0; j < citycount - 1; j++) 				ranseti[i].fitness += Map_City.distance[ranseti[i].X[j]][ranseti[i].X[j + 1]]; 			ranseti[i].fitness += Map_City.distance[ranseti[i].X[citycount - 1]][ranseti[i].X[0]]; 		} 	} 	void Bianyi(double Pm)//变异函数 	{ 		for (int k = 0; k < Pop_Size; k++) 		{ 			double suijishu = u0(random); 			if (Pm > suijishu) 			{ 				int pos1 = rand() % citycount, pos2 = rand() % citycount;//随机选出两个变异位置,然后将两个位置上的城市序号进行交换 				while (pos2 == pos1) 					pos2 = rand() % citycount; 				ranseti[k].X[pos1] += ranseti[k].X[pos2]; 				ranseti[k].X[pos2] = ranseti[k].X[pos1] - ranseti[k].X[pos2]; 				ranseti[k].X[pos1] = ranseti[k].X[pos1] - ranseti[k].X[pos2]; 			} 			ranseti[k].fitness = 0; 			for (int j = 0; j < citycount - 1; j++) 				ranseti[k].fitness += Map_City.distance[ranseti[k].X[j]][ranseti[k].X[j + 1]]; 			ranseti[k].fitness += Map_City.distance[ranseti[k].X[citycount - 1]][ranseti[k].X[0]]; 		} 	} 	void SelectBestRanseti() 	{ 		for (int i = 0; i < Pop_Size; i++) 		{ 			if (ranseti[i].fitness < Bestranseti.fitness) 			{ 				for (int j = 0; j < citycount; j++) 					Bestranseti.X[j] = ranseti[i].X[j]; 			} 		} 		Bestranseti.fitness = 0; 		for (int j = 0; j < citycount - 1; j++) 			Bestranseti.fitness += Map_City.distance[Bestranseti.X[j]][Bestranseti.X[j + 1]]; 		Bestranseti.fitness += Map_City.distance[Bestranseti.X[citycount - 1]][Bestranseti.X[0]]; 	} 	void GA_TSP() 	{ 		ofstream outfile; 		outfile.open("result.txt",ios::trunc); 		for (int k = 0; k < Itetime; k++) 		{ 			outfile << "第" << k + 1 << "代种群:" << endl; 			CalculateLeijiProb();//计算上一代种群染色体的累积概率 			Roulette();//轮盘赌法选择出下一代种群 			SelectBestRanseti();//获得最好个体 			outfile << "轮盘赌选择后的新种群:" << endl; 			for (int i = 0; i < Pop_Size; i++) 				for (int j = 0; j < citycount; j++) 				{ 					if(j== citycount -1)outfile << ranseti[i].X[j] <<" "<<ranseti[i].fitness << " " << endl; 					else outfile << ranseti[i].X[j]<<"->"; 				} 			Cross(Cross_Prob); 			SelectBestRanseti();//获得最好个体 			outfile << "交叉后的新种群:" << endl; 			for (int i = 0; i < Pop_Size; i++) 				for (int j = 0; j < citycount; j++) 				{ 					if (j == citycount - 1)outfile << ranseti[i].X[j] << " " << ranseti[i].fitness <<" "<< endl; 					else outfile << ranseti[i].X[j] << "->"; 				} 			Bianyi(Bianyi_Prob); 			SelectBestRanseti();//获得最好个体 			outfile << "变异后的新种群:" << "n"; 			for (int i = 0; i < Pop_Size; i++) 				for (int j = 0; j < citycount; j++) 				{ 					if (j ==citycount - 1)outfile << ranseti[i].X[j] << " " << ranseti[i].fitness << " " << endl; 					else outfile << ranseti[i].X[j] << "->"; 				} 			SelectBestRanseti();//获得最好个体 			std::cout << "第" << k + 1 << "次迭代的最优路径长度为:" << Bestranseti.fitness<<endl; 			outfile << "第" << k + 1 << "次迭代的最优路径长度为:" << Bestranseti.fitness << endl; 			for (int i = 0; i < Pop_Size; i++) 			{ 				for (int j = 0; j < citycount; j++) 				{ 					oldranseti[i].X[j] = ranseti[i].X[j]; 				} 				oldranseti[i].fitness = ranseti[i].fitness; 			} 		} 		std::cout<<"****************迭代结束!****************"<<endl; 		std::cout << Itetime << "次迭代结束后的最优路径长度为:" << Bestranseti.fitness<<endl; 		std::cout << Itetime << "次迭代结束后的最优个体如下:" << endl; 		outfile << Itetime << "次迭代结束后的最优路径长度为:" << Bestranseti.fitness << endl; 		outfile << Itetime << "次迭代结束后的最优个体如下:" << endl; 		for (int j = 0; j < citycount; j++) 		{ 			if (j == citycount - 1) 			{ 				std::cout << Bestranseti.X[j] << endl; 				outfile << Bestranseti.X[j] << endl; 			} 			else 			{ 				std::cout << Bestranseti.X[j] << "->"; 				outfile << Bestranseti.X[j] << "->"; 			} 		} 		outfile.close(); 	} }; 

4 、自定义函数

四舍五入取整函数

double round(double r){ return (r > 0.0) ? floor(r + 0.5) : ceil(r - 0.5);} 

随机生成1~n的一个排列的函数

int * Random_N(int n) { 	int *geti; 	geti = new int[n]; 	int j = 0; 	while(j<n) 	{ 		while (true) 		{ 			int flag = -1; 			int temp = rand() % n + 1; 			if (j > 0) 			{ 				int k = 0; 				for(; k < j; k++) 				{ 					if (temp == *(geti + k))break; 				} 				if (k == j) 				{ 					*(geti + j) = temp; 					flag = 1; 				} 			} 			else 			{ 				*(geti + j) = temp; 				flag = 1; 			} 			if (flag == 1)break; 		} 		j++; 	} 	return geti; } 

5 、全局变量

std::default_random_engine random((unsigned int)time(NULL)); std::uniform_real_distribution<double> u0(0, 1); //随机数分布对象 const int citycount = 29;//城市的数量作为全局常量,需提前在代码中赋值 Graph Map_City;//定义全局对象图,放在Graph类后 GA zq;//种群类,放在GA类后 

6 、主函数

int main() { 	std::cout << "****************遗传算法求解旅行商问题!****************" << endl; 	std::cout << "****************城市数量:"<<citycount <<"****************"<< endl; 	zq.Init(50,100,0.8,0.9, "E:\下学期课程\Matlab智能计算\GA_TSP\GA_TSP\bayg29.tsp"); 	std::cout<<"****************初始化后的种群如下:****************"<<endl; 	zq.shuchu(); 	zq.GA_TSP(); 	system("pause"); 	return 0; } 

7 、运行结果

控制台运行结果:
遗传算法求解TSP旅行商问题C++(2020.11.11)
生成的result.txt文件结果:
遗传算法求解TSP旅行商问题C++(2020.11.11)

本文转自互联网,侵权联系删除遗传算法求解TSP旅行商问题C++(2020.11.11)

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 遗传算法求解TSP旅行商问题C++(2020.11.11)
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们