禁忌搜尋算法求解TSP旅行商問題C++（2020.11.19）

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;
}