程序员经验分享-hwhale

禁忌搜索算法求解TSP旅行商问题C++（2020.11.19）

2023-05-16

TS算法求解TSP问题C++

  • 1、禁忌搜索算法
    • 1.1 基本思想及主要特点
    • 1.2 基本概念
    • 1.3 算法流程
  • 2、 TS求解TSP问题的C++实现
    • 2.1 输入数据文件：bayg29.tsp
    • 2.2 头文件
    • 2.3 所需的类
      • 2.3.1 城市类City
      • 2.3.2 包含城市的地图类Graph
      • 2.3.3 禁忌搜索算法类TS
    • 2.4 自定义函数
    • 2.5 全局变量
    • 2.6 主函数
    • 2.7 运行结果
      • 2.7.1 控制台运行结果
      • 2.7.2 生成result.txt文件结果
    • 2.8 MATLAB绘制最优路径结果
  • 附录（完整代码）

1、禁忌搜索算法

        禁忌搜索算法（tabu search/taboo search,TS）是一种模拟人类记忆功能特性的全局性搜索算法。它最初是由Glover提出的，主要用于解决组合优化问题，与局部优化法相比陷入局部极小值的概率更小，比遗传算法、模拟退火算法更易于利用问题的特殊信息。因此，它具有很强的全局搜索能力，在复杂问题和大型问题上有特殊的效果。禁忌搜索算法是对人类思维过程本身的一种模拟，它通过对一些局部最优解的禁忌（也可以说是记忆）达到接纳一部分较差解，从而跳出局部搜索的目的。
        “禁忌”就是禁止重复前面的工作，是一种强加的限制。禁忌搜索算法采用了禁忌技术和解空间进行搜索，避免了陷入局部最优，从而具有全局搜索能力。“禁忌准则”和“特赦准则”使该算法具有很强的“爬山”能力，因而具有智能性。禁忌搜索算法通过局部搜索机制和相应的禁忌准则来避免迂回搜索，并通过特赦准则来释放一些被禁忌的优良解，进而保证多样化的有效搜索，但存在收敛速度较慢的缺陷。禁忌搜索算法已在组合优化、生产调度、资源规划、机器学习、数据挖掘、函数优化和生态环境评价等多个领域获得了广泛应用。

1.1 基本思想及主要特点

        禁忌搜索算法的基本思想是：假设给出一个解邻域，首先在解邻域中找出一个初始局部解 x x x作为当前解，并令当前解为最优解 x ′ x^{'} x′，然后以这个当前解作为起点，在解邻域中搜索最优解 。当然，这个最优解可能与前一次所得的最优解相同，为了避免这种循环现象的出现，设置一个记忆近期操作的禁忌表，如果当前的搜索操作是记录在此表中的操作，那么这一搜索操作就被禁止；否则用 x ′ x^{'} x′取代 x x x作为当前解。但禁忌表有可能限制某些可以导致更好解的“移动”。为了尽可能不错过产生最优解的“移动”，若满足特赦准则，即使它处于禁忌表中，这个移动也可实现。
        禁忌搜索算法的主要特点是：①在搜索过程中可接受劣解，因而具有较强的“爬山”能力。②新解不是在当前解的邻域中随机产生，而是或优于当前最优解，或是非禁忌的最佳解，因而获得优良解的概率远大于其他解。
        作为一种启发式算法，禁忌搜索算法也有明显不足：①对初始解有较强的依赖性，一个较差的初始解则会降低禁忌搜索的收敛速度。②迭代搜索过程是串行的，仅是单一状态的非并行搜索。

1.2 基本概念

        禁忌搜索算法有关的基本概念包括：禁忌表（tabu list）、邻域（neighbourhood）、禁忌条件（tabu condition）、特赦准则（aspiration level）及终止准则（termination criterion）等。
        禁忌表。禁忌表是禁忌搜索算法的核心，禁忌对象和禁忌长度是禁忌表的两个关键指标。禁忌表的长度可以固定，也可以改变。处在禁忌表中的移动在近期的迭代中是被禁止的，除非满足特赦准则。邻域结构、禁忌对象、禁忌长度、特赦准则和终止准则是与禁忌搜索算法的搜索效率和求解质量直接相关的关键要素。
        邻域。对于 X X X中的每一解 x x x的邻域定义为：当前解 x x x 所有可行移动 S ( x ) S(x) S(x)而形成的解的集合称为解 x x x的邻域 N ( x ) N(x) N(x)，通常表现为以解 x x x为中心， r r r 为半径的球 B ( x , x ′ ) B(x,x^{'}) B(x,x′)。从而所有满足 ∣ ∣ x ′ − x ∣ ∣ ≤ r ||x^{'}-x||≤r ∣∣x′−x∣∣≤r 的点 x ′ x^{'} x′的集合均为 x x x的邻域解。其中 ∣ ∣ ⋅ ∣ ∣ ||\cdot|| ∣∣⋅∣∣为范数。
        禁忌条件。禁忌条件是通过禁忌表来实现的。为了避免陷入局部极小点，算法禁止一定时间内走过的区域。每运行一步，都将当前点及其目标函数值放入禁忌表中，作为禁忌区域的中心。禁忌表的长度固定为 T L TL TL，当禁忌表已满，即里面有 T L TL TL个元素时，将最早进入的元素从禁忌表中释放，并把新的元素放入表中。
        可用两重判断准则来判断一个点 x x x是否被禁忌。第一准则为首先判断点的目标函数值 f ( x ) f(x) f(x)。如果 f ( x ) f(x) f(x)跟禁忌表中的任一个函数值 f L ( x ∗ ) f_{L}(x^{*}) fL​(x∗)都不接近，即对任一 f L ( x ∗ ) f_{L}(x^{*}) fL​(x∗)都有 ∣ f ( x ) − f L ( x ∗ ) ∣ > ε |f(x)-f_{L}(x^{*})|>ε ∣f(x)−fL​(x∗)∣>ε（ ε ε ε为给定值），则点 x x x不被禁忌，否则判断第二准则。
        第二准则判断点 x x x。如果 的目标函数值跟禁忌表中点的函数值接近，则判断点 x x x跟点 x ′ x^{'} x′是否接近。如果对任一 x j ( j = 1 , 2 , . . . , n ) x_{j}(j=1,2,...,n) xj​(j=1,2,...,n)都有 ∣ x j − x j ∗ ∣ ≤ ε |x_{j}-x_{j}^{*}|≤ε ∣xj​−xj∗​∣≤ε，则点 x x x被禁忌，否则不被禁忌。
        两重准则可以减少计算量。例如，对于 n n n维变量，判断一定点是否在一个矩形区域内要做 n n n次比较，而函数值的比较只需要做一次计算即可。
        特赦规则。特赦规则的作用是防止某些更优点被禁忌，满足特赦规则的点无需判断是否被禁忌，可以直接选取作为新的当前点。特赦规则可定义为：如果点 x x x的目标函数值优于目前为止搜索到的最优点的目标函数值，说明点 x x x满足特赦规则，则被选取为新的当前点。
        终止规则当达到最大迭代步数，或在给定的迭代步数内算法搜索到的最优点没有改善时，算法将终止迭代。

1.3 算法流程

        基本禁忌搜索算法步骤如下:
        步骤1：随机生成一个初始点 x 0 x_{0} x0​，计算它的目标函数值 f ( x 0 ) f(x_{0}) f(x0​)，初始化当前点 x = x 0 x=x_{0} x=x0​，最优点 x b e s t = x 0 x_{best}=x_{0} xbest​=x0​，最优点的目标函数值 f ( x b e s t ) = f ( x 0 ) f(x_{best})=f(x_{0}) f(xbest​)=f(x0​)
        步骤2：生成当前点 x x x的邻域，计算出邻域内各点的目标函数值。
        步骤3：选邻域内目标函数值最优的点 x ∗ x^{*} x∗。
        步骤4：判断特赦规则。如果满足特赦规则，则新的当前点移到 x ∗ x^{*} x∗，即 x = x ∗ x=x^{*} x=x∗，同时更新最优点 x b e s t = x ∗ x_{best}=x^{*} xbest​=x∗， f ( x b e s t ) = f ( x ∗ ) f(x_{best})=f(x^{*}) f(xbest​)=f(x∗)，转到步骤6，否则转到步骤5.
        步骤5：判断点 x ∗ x^{*} x∗是否被禁忌，如果点 x ∗ x^{*} x∗未被禁忌，则将新的当前点移动到 x ∗ x^{*} x∗，转到步骤6，否则将 x ∗ x^{*} x∗从邻域中删除，转到步骤3.
        步骤6：更新禁忌表，并判断终止规则。若满足终止规则，则终止运算，否则转到步骤2。

2、 TS求解TSP问题的C++实现

2.1 输入数据文件：bayg29.tsp

   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.2 头文件

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

2.3 所需的类

所需的类包括城市类City、包含城市的地图类Graph、禁忌搜索算法类SA。

2.3.1 城市类City

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

2.3.2 包含城市的地图类Graph

class Graph
{
public:
	int Citycount;
	City *city;//城市数组
	double distance[citycount][citycount];//城市间的距离矩阵
	void Readcoordinatetxt(string txtfilename)//读取城市坐标文件的函数
	{
		Citycount = citycount;
		city = new City[Citycount];
		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] << "  ";
			}
		}
	}
};

2.3.3 禁忌搜索算法类TS

class TS
{
public:
	int x0[citycount];//初始解
	int xbest[citycount];//最优解
	int xlocalbest[citycount];//邻域内的局部最优解
	double bestdisvalue,localbestdisvalue;//最优解对应的距离值、邻域内最优解对应距离值
	int N,Neighborcount,TL,Itetime;//每次搜索邻域的数目、禁忌表的长度、迭代次数
	int **xNeighbor;//x邻域的Neigghborcount个解
	int **TabuTable,currentjinjicount;//禁忌表、禁忌表中当前被禁忌解的个数
	void Init(int neighborcount,int tl,int itetime)//初始化函数
	{
		Neighborcount = neighborcount;
		TL = tl;
		Itetime = itetime;
		currentjinjicount = 0;
		int *b;
		b = Random_N(citycount);
		for (int i = 0; i < citycount; i++)
		{
			x0[i] = b[i];
			xbest[i] = x0[i];
		}
		bestdisvalue = Evaluate(xbest);
	   TabuTable = new int*[TL];
	   for (int i = 0; i < TL; i++)
		   TabuTable[i] = new int[citycount];
	   xNeighbor = new int *[Neighborcount];
	   for (int i = 0; i < Neighborcount; i++)
		   xNeighbor[i] = new int[citycount];
	}
	double Evaluate(int X[citycount])//计算解对应目标距离值的函数
	{
		double funvalue = 0;
		for (int i = 0; i < citycount - 1; i++)
			funvalue += Map_City.distance[X[i] - 1][X[i + 1] - 1];
		funvalue += Map_City.distance[X[citycount - 1] - 1][X[0] - 1];
		return funvalue;
	}
	void GetNeighborhood(int X[citycount], int tempX[citycount])//通过邻域交换来得到邻域解的函数
	{
		for (int i = 0; i < citycount; i++)
			tempX[i] = X[i];
		int random1, random2;
		random1 = rand() % citycount;
		while (true)
		{
			random2 = rand() % citycount;
			if (random2 != random1)break;
		}
		int temp;
		temp = tempX[random1];
		tempX[random1] = tempX[random2];
		tempX[random2] = temp;
	}
	bool PanduanTabuTable(int X[citycount])//判断解是否被禁忌的函数
	{
		if (currentjinjicount == 0) return false;
		else
		{
			int flag = 0;
			for (int i = 0; i < currentjinjicount; i++)
			{
				flag = 1;
				int j = 0;
				for (; j < citycount; j++)
				{
					if (TabuTable[i][j] != X[j])
					{
						flag = 0;//解不在禁忌表中
						break;
					}
				}
				if (flag == 1) break;
			}
			if (flag == 1)//解在禁忌表中
				return true;
			else//解不在禁忌表中
				return false;
		}
	}
	bool PanduanTeShe(int X[citycount])//判断是否满则特赦规则
	{
		if (Evaluate(X) < bestdisvalue) return true;
		else return false;
	}
	void UpdateTabuTable(int X[citycount])//更新禁忌表的函数
	{
		if (currentjinjicount == TL)//禁忌表满了
		{
			//删除禁忌表中第一个解,同时将禁忌表后面的解往前挪
			for (int i = 0; i < TL - 1; i++)
			{
				for (int j = 0; j < citycount; j++)
					TabuTable[i][j] = TabuTable[i+1][j];
			}
			//将新插入的解放到禁忌表的最后
			for (int j = 0; j < citycount; j++)
				TabuTable[TL-1][j] = X[j];
		}
		else//禁忌表未满
		{
			for (int j = 0; j < citycount; j++)
				TabuTable[currentjinjicount][j] = X[j];
		}
	}
	void  GetNeighborlocalbest(int count)//获取邻域最优解的函数
	{
		int k;
		for (int i = 0; i < count; i++)
		{
			if (PanduanTabuTable(xNeighbor[i]) == false) 
			{
				k = i; break;
			}
		}
		for (int i = 0; i < citycount; i++)
			xlocalbest[i] = xNeighbor[k][i];
		localbestdisvalue = Evaluate(xlocalbest);
		for (int m = 0; m < count; m++)//再搜索count个邻域解，找出目标函数值最优的点x*
		{
			if (PanduanTabuTable(xNeighbor[m]) == false &&Evaluate(xNeighbor[m]) < localbestdisvalue)//xlocalbest未被禁忌
			{
					for (int i = 0; i < citycount; i++)
						xlocalbest[i] = xNeighbor[m][i];
					localbestdisvalue = Evaluate(xlocalbest);
			}
		}
	}
	void TeShe()//执行判断特赦操作的函数
	{
		if (PanduanTeShe(xlocalbest) == true)//如果满足特赦规则
		{
			for (int j = 0; j < citycount; j++)
			{
				x0[j] = xlocalbest[j];
				xbest[j] = xlocalbest[j];
			}
			bestdisvalue = Evaluate(xbest);
			//更新禁忌表
			UpdateTabuTable(xlocalbest);
			if(currentjinjicount < TL) currentjinjicount++;
		}
		else //如果不满足特赦规则
		{
			JinJi();
		}
	}
	void JinJi()//执行判断禁忌操作的函数
	{
		if (PanduanTabuTable(xlocalbest) == false)//xlocalbest未被禁忌
		{
			for (int j = 0; j < citycount; j++)
			{
				x0[j] = xlocalbest[j];
			}
			//更新禁忌表
			UpdateTabuTable(xlocalbest);
		}
		else
		{
			if (N > 1)
			{
				N--;
				GetNeighborlocalbest(N);
			}
		}
	}
	void TS_TSP(int neigh,int tl,int itetime,string filename)
	{
		ofstream outfile;
		outfile.open("result.txt", ios::trunc);
		Map_City.Readcoordinatetxt(filename);
		Map_City.shuchu();
		outfile << "城市名称 " << "坐标x" << " " << "坐标y" << endl;
		for (int i = 0; i < citycount; i++)
			outfile << Map_City.city[i].name << " " << Map_City.city[i].x << " " << Map_City.city[i].y << endl;
		outfile << "距离矩阵： " << endl;
		for (int i = 0; i < citycount; i++)
		{
			for (int j = 0; j < citycount; j++)
			{
				if (j == citycount - 1)
					outfile << Map_City.distance[i][j] << endl;
				else
					outfile << Map_City.distance[i][j] << "  ";
			}
		}
		Init(neigh,tl,itetime);
		outfile << "初始解如下：" << endl;
		for (int i = 0; i < citycount; i++)
		{
			if (i == 0)outfile << "f（" << x0[i] << ",";
			else if (i == citycount - 1) outfile << x0[i] << "） =  " << Evaluate(x0) << endl;
			else outfile << x0[i] << ",";
		}
		for (int t = 0; t < Itetime; t++)
		{
			for (int i = 0; i < Neighborcount; i++)
				GetNeighborhood(x0, xNeighbor[i]);//获取x0的Neighborcount个邻域解
			outfile << "第" << t + 1 << "次迭代的初始解为：";
			for (int i = 0; i < citycount; i++)
			{
				if (i == 0)outfile << "f（" << x0[i] << ",";
				else if (i == citycount - 1) outfile << x0[i] << "） =  " << Evaluate(x0) << endl;
				else outfile << x0[i] << ",";
			}
			outfile << "第" << t + 1 << "次迭代" << Neighborcount << "个邻域解：" << endl;
			for (int i = 0; i < Neighborcount; i++)
			{
				outfile << "邻域解" << i + 1 << ":";
				for (int j = 0; j < citycount; j++)
				{
					if (j == 0)outfile << "f（" << xNeighbor[i][j] << ",";
					else if (j == citycount - 1) outfile << xNeighbor[i][j] << "） =  " << Evaluate(xNeighbor[i]) << endl;
					else outfile << xNeighbor[i][j] << ",";
				}
			}
			N = Neighborcount;//有效的邻域数量
			GetNeighborlocalbest(N);
			TeShe();
			JinJi();
			std::cout << "第" << t + 1 << "次迭代后的最优解为：";
			for (int j = 0; j < citycount; j++)
			{
				if (j == 0)
					std::cout << "f(" << xbest[j] << ",";
				else if (j == citycount - 1)
					std::cout << xbest[j] << ")=" << bestdisvalue << endl;
				else
					std::cout << xbest[j] << ",";
			}
			outfile << "第" << t + 1 << "次迭代后的最优解为：";
			for (int j = 0; j < citycount; j++)
			{
				if (j == 0)
					outfile << "f(" << xbest[j] << ",";
				else if (j == citycount - 1)
					outfile << xbest[j] << ")=" << bestdisvalue << endl;
				else
					outfile << xbest[j] << ",";
			}
		}
		outfile << "迭代结束后的最优解如下：" << endl;
		for (int i = 0; i < citycount; i++)
		{
			if (i == 0)outfile << "f(" << xbest[i] << ",";
			else if (i == citycount - 1) outfile << xbest[i] << "）=" << bestdisvalue << endl;
			else outfile << xbest[i] << ",";
		}
		outfile << "迭代结束后的禁忌表如下：" << endl;
		for (int i = 0; i < currentjinjicount; i++)
		{
			for (int j = 0; j < citycount; j++)
			{
				if (j == 0)outfile << "f（" << TabuTable[i][j] << ",";
				else if (j == citycount - 1) outfile << TabuTable[i][j] << "） =  " << Evaluate(TabuTable[i]) << endl;
				else outfile << TabuTable[i][j] << ",";
			}
		}
		outfile.close();
	}
};

2.4 自定义函数

        随机生成TSP问题的一个可行解的函数

int * Random_N(int n)//随机生成TSP问题的一个可行解的函数
{
	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;
}

2.5 全局变量

std::default_random_engine random((unsigned int)time(NULL));
std::uniform_real_distribution<double> u(0, 1); //随机数分布对象
const int citycount = 29;
Graph Map_City;//定义全局对象图,放在Graph类后

2.6 主函数

int main()
{
	system("mode con cols=200");
	system("color fc");
	TS ts;
	ts.TS_TSP(8, 20, 100, "E:\\计算智能代码\\TS_TSP\\TS_TSP\\bayg29.tsp");
	system("pause");
	return 0;
}

2.7 运行结果

        运行结果分为控制台运行结果和生成的result.txt文件结果

2.7.1 控制台运行结果

在这里插入图片描述
在这里插入图片描述

2.7.2 生成result.txt文件结果

在这里插入图片描述
在这里插入图片描述

2.8 MATLAB绘制最优路径结果

在这里插入图片描述

附录（完整代码） 

#include <iostream>
#include <fstream>
#include <string>
#include <random>
#include <time.h>
using namespace std;
std::default_random_engine random((unsigned int)time(NULL));
std::uniform_real_distribution<double> u(0, 1); //随机数分布对象
const int citycount = 29;
class City
{
public:
	string name;//城市名称
	double x, y;//城市点的二维坐标
	void shuchu()
	{
		std::cout << name + ":" << "(" << x << "," << y << ")" << endl;
	}
};
class Graph
{
public:
	int Citycount;
	City *city;//城市数组
	double distance[citycount][citycount];//城市间的距离矩阵
	void Readcoordinatetxt(string txtfilename)//读取城市坐标文件的函数
	{
		Citycount = citycount;
		city = new City[Citycount];
		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] << "  ";
			}
		}
	}
};
Graph Map_City;//定义全局对象图,放在Graph类后
int * Random_N(int n)//随机生成TSP问题的一个可行解的函数
{
	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;
}
class TS
{
public:
	int x0[citycount];//初始解
	int xbest[citycount];//最优解
	int xlocalbest[citycount];//邻域内的局部最优解
	double bestdisvalue,localbestdisvalue;//最优解对应的距离值、邻域内最优解对应距离值
	int N,Neighborcount,TL,Itetime;//每次搜索邻域的数目、禁忌表的长度、迭代次数
	int **xNeighbor;//x邻域的Neigghborcount个解
	int **TabuTable,currentjinjicount;//禁忌表、禁忌表中当前被禁忌解的个数
	void Init(int neighborcount,int tl,int itetime)//初始化函数
	{
		Neighborcount = neighborcount;
		TL = tl;
		Itetime = itetime;
		currentjinjicount = 0;
		int *b;
		b = Random_N(citycount);
		for (int i = 0; i < citycount; i++)
		{
			x0[i] = b[i];
			xbest[i] = x0[i];
		}
		bestdisvalue = Evaluate(xbest);
	   TabuTable = new int*[TL];
	   for (int i = 0; i < TL; i++)
		   TabuTable[i] = new int[citycount];
	   xNeighbor = new int *[Neighborcount];
	   for (int i = 0; i < Neighborcount; i++)
		   xNeighbor[i] = new int[citycount];
	}
	double Evaluate(int X[citycount])//计算解对应目标距离值的函数
	{
		double funvalue = 0;
		for (int i = 0; i < citycount - 1; i++)
			funvalue += Map_City.distance[X[i] - 1][X[i + 1] - 1];
		funvalue += Map_City.distance[X[citycount - 1] - 1][X[0] - 1];
		return funvalue;
	}
	void GetNeighborhood(int X[citycount], int tempX[citycount])//通过邻域交换来得到邻域解的函数
	{
		for (int i = 0; i < citycount; i++)
			tempX[i] = X[i];
		int random1, random2;
		random1 = rand() % citycount;
		while (true)
		{
			random2 = rand() % citycount;
			if (random2 != random1)break;
		}
		int temp;
		temp = tempX[random1];
		tempX[random1] = tempX[random2];
		tempX[random2] = temp;
	}
	bool PanduanTabuTable(int X[citycount])//判断解是否被禁忌的函数
	{
		if (currentjinjicount == 0) return false;
		else
		{
			int flag = 0;
			for (int i = 0; i < currentjinjicount; i++)
			{
				flag = 1;
				int j = 0;
				for (; j < citycount; j++)
				{
					if (TabuTable[i][j] != X[j])
					{
						flag = 0;//解不在禁忌表中
						break;
					}
				}
				if (flag == 1) break;
			}
			if (flag == 1)//解在禁忌表中
				return true;
			else//解不在禁忌表中
				return false;
		}
	}
	bool PanduanTeShe(int X[citycount])//判断是否满则特赦规则
	{
		if (Evaluate(X) < bestdisvalue) return true;
		else return false;
	}
	void UpdateTabuTable(int X[citycount])//更新禁忌表的函数
	{
		if (currentjinjicount == TL)//禁忌表满了
		{
			//删除禁忌表中第一个解,同时将禁忌表后面的解往前挪
			for (int i = 0; i < TL - 1; i++)
			{
				for (int j = 0; j < citycount; j++)
					TabuTable[i][j] = TabuTable[i+1][j];
			}
			//将新插入的解放到禁忌表的最后
			for (int j = 0; j < citycount; j++)
				TabuTable[TL-1][j] = X[j];
		}
		else//禁忌表未满
		{
			for (int j = 0; j < citycount; j++)
				TabuTable[currentjinjicount][j] = X[j];
		}
	}
	void  GetNeighborlocalbest(int count)//获取邻域最优解的函数
	{
		int k;
		for (int i = 0; i < count; i++)
		{
			if (PanduanTabuTable(xNeighbor[i]) == false) 
			{
				k = i; break;
			}
		}
		for (int i = 0; i < citycount; i++)
			xlocalbest[i] = xNeighbor[k][i];
		localbestdisvalue = Evaluate(xlocalbest);
		for (int m = 0; m < count; m++)//再搜索count个邻域解，找出目标函数值最优的点x*
		{
			if (PanduanTabuTable(xNeighbor[m]) == false &&Evaluate(xNeighbor[m]) < localbestdisvalue)//xlocalbest未被禁忌
			{
					for (int i = 0; i < citycount; i++)
						xlocalbest[i] = xNeighbor[m][i];
					localbestdisvalue = Evaluate(xlocalbest);
			}
		}
	}
	void TeShe()//执行判断特赦操作的函数
	{
		if (PanduanTeShe(xlocalbest) == true)//如果满足特赦规则
		{
			for (int j = 0; j < citycount; j++)
			{
				x0[j] = xlocalbest[j];
				xbest[j] = xlocalbest[j];
			}
			bestdisvalue = Evaluate(xbest);
			//更新禁忌表
			UpdateTabuTable(xlocalbest);
			if(currentjinjicount < TL) currentjinjicount++;
		}
		else //如果不满足特赦规则
		{
			JinJi();
		}
	}
	void JinJi()//执行判断禁忌操作的函数
	{
		if (PanduanTabuTable(xlocalbest) == false)//xlocalbest未被禁忌
		{
			for (int j = 0; j < citycount; j++)
			{
				x0[j] = xlocalbest[j];
			}
			//更新禁忌表
			UpdateTabuTable(xlocalbest);
		}
		else
		{
			if (N > 1)
			{
				N--;
				GetNeighborlocalbest(N);
			}
		}
	}
	void TS_TSP(int neigh,int tl,int itetime,string filename)
	{
		ofstream outfile;
		outfile.open("result.txt", ios::trunc);
		Map_City.Readcoordinatetxt(filename);
		Map_City.shuchu();
		outfile << "城市名称 " << "坐标x" << " " << "坐标y" << endl;
		for (int i = 0; i < citycount; i++)
			outfile << Map_City.city[i].name << " " << Map_City.city[i].x << " " << Map_City.city[i].y << endl;
		outfile << "距离矩阵： " << endl;
		for (int i = 0; i < citycount; i++)
		{
			for (int j = 0; j < citycount; j++)
			{
				if (j == citycount - 1)
					outfile << Map_City.distance[i][j] << endl;
				else
					outfile << Map_City.distance[i][j] << "  ";
			}
		}
		Init(neigh,tl,itetime);
		outfile << "初始解如下：" << endl;
		for (int i = 0; i < citycount; i++)
		{
			if (i == 0)outfile << "f（" << x0[i] << ",";
			else if (i == citycount - 1) outfile << x0[i] << "） =  " << Evaluate(x0) << endl;
			else outfile << x0[i] << ",";
		}
		for (int t = 0; t < Itetime; t++)
		{
			for (int i = 0; i < Neighborcount; i++)
				GetNeighborhood(x0, xNeighbor[i]);//获取x0的Neighborcount个邻域解
			outfile << "第" << t + 1 << "次迭代的初始解为：";
			for (int i = 0; i < citycount; i++)
			{
				if (i == 0)outfile << "f（" << x0[i] << ",";
				else if (i == citycount - 1) outfile << x0[i] << "） =  " << Evaluate(x0) << endl;
				else outfile << x0[i] << ",";
			}
			outfile << "第" << t + 1 << "次迭代" << Neighborcount << "个邻域解：" << endl;
			for (int i = 0; i < Neighborcount; i++)
			{
				outfile << "邻域解" << i + 1 << ":";
				for (int j = 0; j < citycount; j++)
				{
					if (j == 0)outfile << "f（" << xNeighbor[i][j] << ",";
					else if (j == citycount - 1) outfile << xNeighbor[i][j] << "） =  " << Evaluate(xNeighbor[i]) << endl;
					else outfile << xNeighbor[i][j] << ",";
				}
			}
			N = Neighborcount;//有效的邻域数量
			GetNeighborlocalbest(N);
			TeShe();
			JinJi();
			std::cout << "第" << t + 1 << "次迭代后的最优解为：";
			for (int j = 0; j < citycount; j++)
			{
				if (j == 0)
					std::cout << "f(" << xbest[j] << ",";
				else if (j == citycount - 1)
					std::cout << xbest[j] << ")=" << bestdisvalue << endl;
				else
					std::cout << xbest[j] << ",";
			}
			outfile << "第" << t + 1 << "次迭代后的最优解为：";
			for (int j = 0; j < citycount; j++)
			{
				if (j == 0)
					outfile << "f(" << xbest[j] << ",";
				else if (j == citycount - 1)
					outfile << xbest[j] << ")=" << bestdisvalue << endl;
				else
					outfile << xbest[j] << ",";
			}
		}
		outfile << "迭代结束后的最优解如下：" << endl;
		for (int i = 0; i < citycount; i++)
		{
			if (i == 0)outfile << "f(" << xbest[i] << ",";
			else if (i == citycount - 1) outfile << xbest[i] << "）=" << bestdisvalue << endl;
			else outfile << xbest[i] << ",";
		}
		outfile << "迭代结束后的禁忌表如下：" << endl;
		for (int i = 0; i < currentjinjicount; i++)
		{
			for (int j = 0; j < citycount; j++)
			{
				if (j == 0)outfile << "f（" << TabuTable[i][j] << ",";
				else if (j == citycount - 1) outfile << TabuTable[i][j] << "） =  " << Evaluate(TabuTable[i]) << endl;
				else outfile << TabuTable[i][j] << ",";
			}
		}
		outfile.close();
	}
};
int main()
{
	system("mode con cols=200");
	system("color fc");
	TS ts;
	ts.TS_TSP(8, 20, 100, "E:\\计算智能代码\\TS_TSP\\TS_TSP\\bayg29.tsp");
	system("pause");
	return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

禁忌搜索算法求解TSP旅行商问题C++（2020.11.19） 的相关文章

  • ROS问题：ERROR: cannot launch node of type

    在运行launch文件时 xff0c 出现如下错误提示 xff1a 原因是没有source 所以解决方案就是在编译完成之后添加source devel setup bash xff0c 问题解决 参考网址 xff1a ERROR canno

  • 标注工具labelme的使用

    在做目标检测任务时 xff0c 少不了对图像进行标注 xff0c 标注工具有好几种 xff0c labelme是其中比较好用的一种 labelme可对图像进行标注 xff0c 包括多边形 矩形 线 点和图像级标注 它是用Python编写的

  • Linux小技巧之终端terminal全选

    当打开一个终端 xff0c 经过若干指令后 xff0c 终端上输出的内容较多 xff0c 直接框选这些内容进行选择比较费事 有没有全选的功能呢 xff1f 答案是有的 xff01 方法1 xff1a 终端菜单栏全选 当窗口比较小时 xff0

  • 如何使用set::key_comp 和 set::value_comp 标准模板库 (STL) 函数

    下面的代码示例演示如何使用 Visual C 43 43 set key comp 和 set value comp 的 STL 功能 所需要的头文件 xff1a lt set gt 原型 template lt class K class

  • Linux小技巧之终端快捷键大全

    在前面一篇博客中记录了终端全选的技巧 下面记录一下关于终端使用的其它一些小技巧 F1查看帮助F11全屏Shift 43 Ctrl 43 T 打开一个新的终端Shift 43 Ctrl 43 N新建一个窗口打开终端Shift 43 Ctrl

  • ROS问题：Yolo v4移植到ROS后检测结果/darknet_ros/detection_image在rviz中显示乱码

    在前面一篇博客 xff08 Yolo v4移植ROS xff09 中介绍了将Yolo v4移植到ROS中 由于Yolo v4的源码在Yolo v3源码的基础上有改动 xff0c 移植成功后会出现一个小bug xff0c 如下图所示 xff1

  • 吉洪诺夫正则化(Tikhonov regularization )

    最近看了看吉洪诺夫正则化方法 xff0c 对其基本内容作了一个简单的了解 现在总结如下 1 正则化 定义 xff1a 正则化 regularization xff0c 是指在线性代数理论中 xff0c 不适定问题通常是由一组线性代数方程定义

  • C++中getline()、gets()等函数的用法

    在学习C 43 43 的过程中 xff0c 经常会遇到输入输出的问题 xff0c 以下总结一下下面几个函数的用法 xff1a 1 cin 2 cin get 3 cin getline 4 getline 5 gets 1 cin gt g

  • C++字母大小写转换方法

    字母大小写这个问题相对比较简单 xff0c 总结了一些常用的大小写转换的方法 xff0c 欢迎指正补充 xff01 思路1 xff1a 根据字母的ASCII表进行转换 xff1a 由表格可以看出 xff0c 对应大小写字母之间相差32 xf

  • C++ 标准输出控制小数点后位数的方法

    在C 43 43 中 xff0c 要实现这个功能 xff0c 就要用到std命名空间中常用于流的控制符 xff0c 这里通常要用到setprecision 函数 xff0c 可以通过这个函数控制小数点后面位数 还要注意的是 xff0c 使用

  • C++中string::npos的一些用法总结

    一 关于npos的定义 在MSDN中有如下说明 xff1a basic string npos static const size type npos 61 1 定义 The constant is the largest represen

  • CMake：通过target_link_libraries链接第三方库

    sdbusplus 通过new method call同步调用service的method 风静如云的博客 CSDN博客 例子中需要在编译时链接 lsdbusplus lsystemd 这两个第三方库 那么通过cmake怎么指定呢 其实很简

  • 在ubuntu终端打开谷歌浏览器的命令

    安装好谷歌浏览器后 xff0c 用以下命令在终端打开谷歌浏览器 adb shell am start n com android chrome com google android apps chrome Main 之后便出现如下内容 xf

  • PELCO_D通信协议

    1 球机通信接口 xff08 EIA RS 485 xff09 数据传输方式 xff1a 异步半双工串行通讯 通信波特率 xff1a 9600Bps 数据格式 xff1a Start Bit xff1a 1 Bit xff1b Data B

  • C buffer

    这学期在Dartmouth上ENGS20 Introduction to Scientific Computing xff0c 好多东西不记下来就会忘 xff0c 所以开一个笔记 在C语言中 xff0c 输入和输出都是有buffer的 xf

  • 寄存器值的操作方法

    通过这段时间的工作和学习 xff0c 我感觉在嵌入式硬件编程中 xff0c 大多数情况下都是对相应硬件的功能寄存器进行设置和操作 一 寄存器的设置和操作特性 1 xff0c 一个寄存器的每个位有其不同的意义 xff0c 进行不同的设置会使硬

  • UART串口通信（回环测试）

    一 UART串口通信简介 UART xff08 Universal Asynchronous Receiver Transmitter xff09 是采用异步串行通信方式的通用异步收发传输器 xff0c 在发送数据时将并行数据转换为串行数据

  • extern "C"的作用

    extern 34 C 34 的作用 一 前些天 编程序是用到了很久以前写的C程序 想把里面的函数利用起来 连接发现出现了找不到具体函数的错误 以下是假设旧的C程序库 C的头文件 c h ifndef C H define C H exte

  • 输入分钟数，按小时和分钟输出

    copyright C 2014 2015 Lighting Studio Co Ltd File name xff1a Author xff1a Jerey Jobs Version 0 1 Date Description xff1a

  • 输入一个32位的整数a,使用按位异或^运算,生成一个新的32位整数b,使得该整数b的每一位等于原整数a中该位左右两边两个bit位的异或结果

    程序要求 xff1a 输入一个32位的整数a 使用按位异或 运算 生成一个新的32位整数b 使得该整数b的每一位等于原整数a中该位左右两边两个bit位的异或结果 copyright C 2014 2015 Lighting Studio C

随机推荐

  • sqlite回调函数的解释与使用

    gt 在sqlite3的api函数中有一个sqlite3 exec xff0c 用来执行sql语句 xff1a 函数原型 xff1a int sqlite3 exec sqlite3 ppDb An open database const

  • Linux节点理解

    一 inode是什么 xff1f 理解inode xff0c 要从文件储存说起 文件储存在硬盘上 xff0c 硬盘的最小存储单位叫做 扇区 xff08 Sector xff09 每个扇区储存512字节 xff08 相当于0 5KB xff0

  • OSSempend();OSSemPost();函数的解析

    浅析 COS II v2 span class hljs number 85 span 内核OSSemPend 和OSSemPost 函数工作原理 文章来源 http span class hljs comment gliethttp cu

  • 矩阵键盘时钟

    span class hljs preprocessor include lt reg52 h gt span class hljs comment 包含头文件 xff0c 一般情况不需要改动 xff0c 头文件包含特殊功能寄存器的定义 s

  • opencv上gpu版surf特征点与orb特征点提取及匹配实例

    一 前言 本文主要实现了使用opencv里的gpu版surf特征检测器和gpu版orb检测器 xff0c 分别对图片进行特征点提取及匹配 xff0c 并对寻获的特征点进行了距离筛选 xff0c 将匹配较为好的特征点进行展示 二 实现代码 我

  • while(c = getchar() != '\n')和while((c = getchar()) != '\n')区别

    在利用while循环和getchar 读取缓存中的数据时 xff0c 发现了一些问题 在最初 xff0c 我利用while c 61 getchar 61 n 的时候 xff0c 发现总是不能将我想要读取的值正确的赋值给c xff0c 在我

  • C++template模板

    模板 xff08 Template xff09 指C 43 43 程序设计设计语言中采用类型作为参数的程序设计 xff0c 支持通用程序设计 C 43 43 的标准库提供许多有用的函数大多结合了模板的观念 xff0c 如STL以及IO St

  • Linux Ubuntu 14.04平台下安装EDK2

    Linux Ubuntu 14 04平台下安装EDK2 博客是基于https github com tianocore tianocore github io wiki Common instructions和 UEFI原理和编程 完成的

  • ubuntu下安装和使用

    在ubuntu下完善代码的时候 会遇到想要跳转到函数定义处 或者跳转到其他相关文件的情况下 此时要借助linux下的ctags工具 在这里 xff0c 我会尽我所能细致地讲清楚如何把vim变成source insight 然而你仍然需要积极

  • STM32 嵌入式系统开发分层设计思想简谈

    简介 开始之前自我介绍一下 xff0c 我在大学学的是物联网工程专业 xff0c 可惜的是发现嵌入式并不好找工作 于是后面自学了前端 xff0c 并到美团从事了1年相关的开发工作 xff0c 但是发现嵌入式才是真爱 xff0c 于是又转到嵌

  • 基于51单片机的智能导盲杖语音播报积水检测温度提示灯光照明proteus仿真原理图

    功能介绍 xff1a 0 本系统采用STC89C52作为单片机 1 导盲仗的上部和底部分别设置超声波传感器 xff0c 利用超声波测距原理分别测得盲人面部和脚底离障碍物的距离 xff0c 并将障碍信息通过语音播报传递给盲人 2 导盲杖设有光

  • 我是如何在2个小时用智能CCD图像检测系统实现一个零件的自动分选项目

    项目实例完整代码可以下载Examples xff1a https pan baidu com s 1YPjR TPJYLmriXNVnNbgZg 提取码 xff1a 52ai 有一种水表的塑料齿轮 xff0c 是有注塑机大批量生产出来 xf

  • keil找不到芯片型号的解决方法

    1 上官网下载对应的固件包 http www keil com dd2 Pack eula container 例如 2 点击 Pack installer 3 点击 File gt Import xff0c 选中下载的固件包 如果选择后左

  • 基于llibcurl库做基本http GET/POST操作代码demo

    libcurl库详细解说请欣赏 xff1a https www cnblogs com xietianjiao p 13260021 html libcurl是一个跨平台的网络协议库 xff0c 支持http https ftp gophe

  • 网络-udp—代码

    01 socket的基本使用 py import socket def main 创建一个udp套接字 udp socket 61 socket socket socket AF INET socket SOCK DGRAM 可以使用套接字

  • Nginx 获取自定义请求header头和URL参数

    一 获取 header 请求头 在 ngx lua 中访问 Nginx 内置变量 ngx var http HEADER 即可获得请求头HEADER的内容 在 nginx配置中 xff0c 通过 http HEADER 即可获得请求头HEA

  • QT与C程序编译问题extern C

    最近在调测试程序 xff0c 小师妹的QT程序与我的C语言的测试程序 xff0c 编译时有问题 xff0c 在小城的帮助下 xff0c 解决了问题 xff0c 网上的帖子是这样的 因为C编译的时候会在函数名前面加一个 xff0c 比如f1

  • ArcGIS将Tif文件导出为高清图片的一种方法，亲测有效

    ArcGIS将Tif文件导出为高清图片的一种方法 xff0c 亲测有效 总共分如下三个步骤第一步 xff0c 打开ArcGIS xff0c 添加tif数据 xff0c 保存为mxd地图文档第二步 xff0c 导出图片 xff0c 点击Fil

  • 重装正版Windows 10和Microsoft office home and student 2019教程（2020.10.29）

    目录 环境准备 xff1a 一个U盘 xff08 至少8G xff09 步骤 第一步 利用微软下载工具制作U盘启动盘 到微软官网下载Windows 10 界面 xff0c 点击立即下载工具 后会弹出一个下载界面 xff0c 下载此文件Med

  • 禁忌搜索算法求解TSP旅行商问题C++（2020.11.19）

    TS算法求解TSP问题C 43 43 1 禁忌搜索算法1 1 基本思想及主要特点1 2 基本概念1 3 算法流程 2 TS求解TSP问题的C 43 43 实现2 1 输入数据文件 xff1a bayg29 tsp2 2 头文件2 3 所需的

热门标签