模拟退火和遺傳算法解決TSP問題

資料集介紹

采用資料集FRI26

來自标準資料集，共有26個城市，最優解為933：

資料下載下傳連結

模拟退火和遺傳算法解決TSP問題模拟退火和遺傳算法解決TSP問題代碼下載下傳：

圖1：資料矩陣

模拟退火和遺傳算法解決TSP問題模拟退火和遺傳算法解決TSP問題代碼下載下傳：

圖2：資料集介紹

算法介紹

模拟退火

介紹：

模拟退火是一種通用機率算法，常用來在一定時間内尋找在一個很大搜尋空間中的近似最優解。

疊代過程：

疊代過程是模拟退火算法的核心步驟，分為新解的産生和接受新解兩部分：

由一個産生函數從目前解産生一個位于解空間的新解；為便于後續的計算和接受，減少算法耗時，通常選擇由目前新解經過簡單地變換即可産生新解的方法，如對構成新解的全部或部分元素進行置換、互換等，注意到産生新解的變換方法決定了目前新解的鄰域結構，因而對冷卻進度表的選取有一定的影響。
計算與新解所對應的目标函數差。因為目标函數差僅由變換部分産生，是以目标函數差的計算最好按增量計算。事實表明，對大多數應用而言，這是計算目标函數差的最快方法。
判斷新解是否被接受，判斷的依據是一個接受準則，最常用的接受準則是Metropolis準則：若Δt′<0則接受S′作為新的目前解S，否則以機率exp（-Δt′/T）接受S′作為新的目前解S。
當新解被确定接受時，用新解代替目前解，這隻需将目前解中對應于産生新解時的變換部分予以實作，同時修正目标函數值即可。此時，目前解實作了一次疊代。可在此基礎上開始下一輪試驗。而當新解被判定為舍棄時，則在原目前解的基礎上繼續下一輪試驗。

實作代碼：

// tsp_sa.cpp: 定義控制台應用程式的入口點。
//

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <fstream>
#include <iostream>
#include <assert.h>
#include <math.h>
using namespace std;

#define T0 50000.0		//初始化溫度
#define Tk (1e-8)		//終止溫度
#define d  0.98			// 退火系數
#define L 1000			// 每個溫度時的疊代次數，即鍊長
#define N 26			// 城市數量
#define TESTTIME  30    //測試次數

int solution[N];		// 用于存放一個解

int map[N][N];			//記錄地圖資料				

const char* filepath = "C://Users//56989//Desktop//dataset.txt";
ifstream infile;

//讀取資料
void readData()
{
	infile.open(filepath);
	assert(infile.is_open()); //若失敗,則輸出錯誤消息,并終止程式運作 
	for (int i = 0; i < 26; i++)
	{
		for (int j = 0; j < 26; j++)
		{
			infile >> map[i][j];
		}
	}
}

// 計算路徑長度
int pathLen(int * arr)
{
	int totlen = 0;
	for (int i = 0; i < N-1; i++)
	{
		totlen += map[arr[i]][arr[i + 1]];
	}
	totlen += map[arr[N-1]][arr[0]];	//回到出發城市
	return totlen;
}

// 初始化函數
void initSolution()
{
	for (int i = 0; i<N; i++)
		solution[i] = i;  // 初始化一個解
}

// 産生一個新解
// 此處采用随機交叉兩個位置的方式産生新的解
void genAnotherSolu()
{
	double r1 = ((double)rand()) / (RAND_MAX + 1.0);
	double r2 = ((double)rand()) / (RAND_MAX + 1.0);
	int pos1 = (int)(N*r1); //第一個交叉點的位置
	int pos2 = (int)(N*r2);

	int temp = solution[pos1];
	solution[pos1] = solution[pos2];
	solution[pos2] = temp;   // 交換兩個點
}

// 主函數
int main(void)
{
	readData();				//讀取資料
	printf("讀資料完成\n\n");
	srand((unsigned)time(NULL)); 

	time_t start, finish;	//計算時間
	start = clock();		//開始計算時間
	
	int tempsolu[N];		//保留原來的解
	int tempLen = 0;

	double aveLen = 0.0;	//平均長度

	for (int testtime = 1; testtime <= TESTTIME; testtime++)
	{
		double T;
		T = T0;					//初始溫度

		initSolution();			//初始化一個解
		int soluLen = pathLen(solution);

		while (T > Tk)
		{
			//printf("進入.\n");
			for (int i = 1; i <= L; i++)
			{
				memcpy(tempsolu, solution, N * sizeof(int)); // 複制數組，保留原來的解
				genAnotherSolu();							 // 産生新解

				tempLen = pathLen(tempsolu);
				soluLen = pathLen(solution);

				int dif = soluLen - tempLen;

				if (dif >= 0)//原來的解更好
				{
					double ran = ((double)rand()) / (RAND_MAX);
					if (exp(-dif / T) <= ran)   // 保留原來的解
					{
						memcpy(solution, tempsolu, N * sizeof(int));
					}
				}
			}
			T = T * d; // 降溫

		}
		aveLen += pathLen(solution);
		printf("第%d次計算完成，所得路徑長度為: %d\n", testtime, pathLen(solution));

	}
	aveLen = aveLen / 30;

	finish = clock(); 

	double duration = ((double)(finish - start)) / CLOCKS_PER_SEC;	// 計算時間
	
	printf("程式運作耗時:%lf秒.\n", duration);
	printf("重複30次，求得的最優路徑平均值為：%2f.\n", aveLen);

	/*
	printf("模拟退火算法\n");
	printf("路徑如下：\n");
	for (int i = 0; i<N ; i++)  // 輸出路徑
	{
		printf("%d ", solution[i]);
	}

	printf("\n最優路徑長度為:%d\n", pathLen(solution));
	*/

	

	return 0;
}

實驗結果：

計算30次，取平均值：

模拟退火和遺傳算法解決TSP問題模拟退火和遺傳算法解決TSP問題代碼下載下傳：

圖3：模拟退火結果

遺傳算法

介紹：

遺傳算法是計算數學中用于解決最優化的搜尋算法，是進化算法的一種。進化算法最初是借鑒了進化生物學中的一些現象而發展起來的，這些現象包括遺傳、突變、自然選擇以及雜交等。

實作代碼：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <fstream>
#include <iostream>
#include <assert.h>
#include <algorithm>
using namespace std;

#define MAXGENS 500  // 最大進化代數
#define POPSIZE 100  // 種群數目
#define PXOVER 0.6   // 交叉機率
#define PMUTATION 0.1 // 變異機率
#define N 26 // 染色體長度(這裡即為城市個數)
#define TESTTIME  30    //測試次數

int pop[POPSIZE][N];	 // 種群
int fitness[POPSIZE];

int globalBest[N];		// 最佳路線
int bestFitness = 0x7FFFFFFF; // 最短路徑長度

int map[N][N];			//記錄地圖資料	

const char* filepath = "C://Users//56989//Desktop//dataset.txt";
ifstream infile;

//讀取資料
void readData()
{
	infile.open(filepath);
	assert(infile.is_open()); //若失敗,則輸出錯誤消息,并終止程式運作 
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			infile >> map[i][j];
		}
	}
	infile.close();
}

// 種群初始化
void init()
{
	int num = 0;
	while (num < POPSIZE)
	{
		for (int i = 0; i<POPSIZE; i++)
			for (int j = 0; j<N; j++)
				pop[i][j] = j;
		num++;
		for (int i = 0; i<N - 1; i++)
		{
			for (int j = i + 1; j<N; j++)
			{
				int temp = pop[num][i];
				pop[num][i] = pop[num][j];
				pop[num][j] = temp; // 交換第num個個體的第i個元素和第j個元素
				num++;
				if (num >= POPSIZE)
					break;
			}
			if (num >= POPSIZE)
				break;
		}

		while (num < POPSIZE)
		{
			double r1 = ((double)rand()) / (RAND_MAX + 1.0);
			double r2 = ((double)rand()) / (RAND_MAX + 1.0);
			int p1 = (int)(N*r1); // 位置1
			int p2 = (int)(N*r2); // 位置2
			int temp = pop[num][p1];
			pop[num][p1] = pop[num][p2];
			pop[num][p2] = temp;    // 交換基因位置
			num++;
		}
	}

	//	for (int i = 0; i<POPSIZE; i++)
	//	{
	//		for (int j = 0; j<N; j++)
	//		{
	//			pop[i][j] = j;
	//		}
	//		random_shuffle(pop[i], pop[i] + N);
	//	}
}


int findMin()
{
	int mindis = fitness[0];
	int minindex = 0;

	for (int i = 1; i<POPSIZE; i++)
	{
		if (fitness[i] < mindis)
		{
			mindis = fitness[i];
			minindex = i;
		}
	}

	return minindex;

}

// 計算路徑長度
double pathLen(int * arr)
{
	int totlen = 0;
	for (int i = 0; i < N - 1; i++)
	{
		totlen += map[arr[i]][arr[i + 1]];
	}
	totlen += map[arr[N - 1]][arr[0]];	//回到出發城市
	return totlen;
}

// 選擇操作
void select()
{
	double pick;
	int choice_arr[POPSIZE][N];
	double fit_pro[POPSIZE];
	double sum = 0;
	double fit[POPSIZE]; // 适應度函數數組(距離的倒數)
	for (int j = 0; j<POPSIZE; j++)
	{
		fit[j] = 1.0 / fitness[j];
		sum += fit[j];
	}
	for (int j = 0; j<POPSIZE; j++)
	{
		fit_pro[j] = fit[j] / sum; // 機率數組
	}
	// 開始輪盤賭
	for (int i = 0; i<POPSIZE; i++)
	{
		pick = ((double)rand()) / RAND_MAX; // 0到1之間的随機數  
		for (int j = 0; j<POPSIZE; j++)
		{
			pick = pick - fit_pro[j];
			if (pick <= 0)
			{
				for (int k = 0; k<N; k++)
					choice_arr[i][k] = pop[j][k]; // 選中一個個體
				break;
			}
		}

	}
	for (int i = 0; i<POPSIZE; i++)
	{
		for (int j = 0; j<N; j++)
			pop[i][j] = choice_arr[i][j];
	}
}

//交叉操作
void crossover()
{
	double pick;
	double pick1, pick2;
	int choice1, choice2;
	int pos1, pos2;
	int temp;
	int conflict1[N]; // 沖突位置
	int conflict2[N];
	int num1, num2;
	int index1, index2;
	int move = 0; // 目前移動的位置
	while (move<N - 1)
	{
		pick = ((double)rand()) / RAND_MAX; // 用于決定是否進行交叉操作
		if (pick > PXOVER)
		{
			move += 2;
			continue; // 本次不進行交叉
		}
		// 采用部分映射雜交
		choice1 = move; // 用于選取雜交的兩個父代
		choice2 = move + 1; // 注意避免下标越界
		pick1 = ((double)rand()) / (RAND_MAX + 1.0);
		pick2 = ((double)rand()) / (RAND_MAX + 1.0);
		pos1 = (int)(pick1*N); // 用于确定兩個雜交點的位置
		pos2 = (int)(pick2*N);
		while (pos1 > N - 2 || pos1 < 1)
		{
			pick1 = ((double)rand()) / (RAND_MAX + 1.0);
			pos1 = (int)(pick1*N);
		}
		while (pos2 > N - 2 || pos2 < 1)
		{
			pick2 = ((double)rand()) / (RAND_MAX + 1.0);
			pos2 = (int)(pick2*N);
		}
		if (pos1 > pos2)
		{
			temp = pos1;
			pos1 = pos2;
			pos2 = temp; // 交換pos1和pos2的位置
		}
		for (int j = pos1; j <= pos2; j++)
		{
			temp = pop[choice1][j];
			pop[choice1][j] = pop[choice2][j];
			pop[choice2][j] = temp; // 逐個交換順序
		}
		num1 = 0;
		num2 = 0;
		if (pos1 > 0 && pos2 < N - 1)
		{
			for (int j = 0; j <= pos1 - 1; j++)
			{
				for (int k = pos1; k <= pos2; k++)
				{
					if (pop[choice1][j] == pop[choice1][k])
					{
						conflict1[num1] = j;
						num1++;
					}
					if (pop[choice2][j] == pop[choice2][k])
					{
						conflict2[num2] = j;
						num2++;
					}
				}
			}
			for (int j = pos2 + 1; j<N; j++)
			{
				for (int k = pos1; k <= pos2; k++)
				{
					if (pop[choice1][j] == pop[choice1][k])
					{
						conflict1[num1] = j;
						num1++;
					}
					if (pop[choice2][j] == pop[choice2][k])
					{
						conflict2[num2] = j;
						num2++;
					}
				}

			}
		}
		if ((num1 == num2) && num1 > 0)
		{
			for (int j = 0; j<num1; j++)
			{
				index1 = conflict1[j];
				index2 = conflict2[j];
				temp = pop[choice1][index1]; // 交換沖突的位置
				pop[choice1][index1] = pop[choice2][index2];
				pop[choice2][index2] = temp;
			}
		}
		move += 2;
	}
}

// 變異操作
// 變異政策采取随機選取兩個點，将其對換位置
void mutation()
{
	double pick, pick1, pick2;
	int pos1, pos2, temp;
	for (int i = 0; i<POPSIZE; i++)
	{
		pick = ((double)rand()) / RAND_MAX; // 用于判斷是否進行變異操作
		if (pick > PMUTATION)
			continue;
		pick1 = ((double)rand()) / (RAND_MAX + 1.0);
		pick2 = ((double)rand()) / (RAND_MAX + 1.0);
		pos1 = (int)(pick1*N); // 選取進行變異的位置
		pos2 = (int)(pick2*N);
		while (pos1 > N - 1)
		{
			pick1 = ((double)rand()) / (RAND_MAX + 1.0);
			pos1 = (int)(pick1*N);
		}
		while (pos2 > N - 1)
		{
			pick2 = ((double)rand()) / (RAND_MAX + 1.0);
			pos2 = (int)(pick2*N);
		}
		temp = pop[i][pos1];
		pop[i][pos1] = pop[i][pos2];
		pop[i][pos2] = temp;
	}
}

//精英更新
void elitist()
{
	int best, worst;
	int bestIndex, worstIndex;

	best = fitness[0];
	worst = fitness[0];

	bestIndex = 0;
	worstIndex = 0;

	//找出最好和最壞
	for (int i = 0; i < POPSIZE; i++)
	{
		if (fitness[i] < best)
		{
			best = fitness[i];
			bestIndex = i;
		}
		else if (fitness[i] > worst)
		{
			worst = fitness[i];
			worstIndex = i;
		}
	}

	//要不更新最好
	if (best < bestFitness)
	{
		for (int i = 0; i < N; i++)
		{
			globalBest[i] = pop[bestIndex][i];
		}
		bestFitness = best;
	}
	else//要不更新最壞
	{
		for (int i = 0; i < N; i++)
		{
			pop[worstIndex][i] = globalBest[i];
		}
		fitness[worstIndex] = bestFitness;
	}
}


int main(void)
{
	
	readData();
	time_t start, finish;
	start = clock();
	double aveLen = 0.0;
	int timeTime = 0;
	while (timeTime < TESTTIME)
	{
		srand((unsigned)time(NULL));	// 初始化随機數種子
		init();

		//更新fitness
		for (int j = 0; j<POPSIZE; j++)
		{
			fitness[j] = pathLen(pop[j]);
		}

		int minindex = findMin();
		for (int j = 0; j<N; j++)
			globalBest[j] = pop[minindex][j];			// 最短路徑序列
		bestFitness = fitness[minindex];

		for (int i = 0; i<MAXGENS; i++)
		{
			select();		// 選擇
			crossover();	//交叉
			mutation();		//變異

			for (int j = 0; j<POPSIZE; j++)
				fitness[j] = pathLen(pop[j]); // 距離數組

			elitist();	//添加一個精英選擇
			minindex = findMin();

			if (fitness[minindex] < bestFitness)
			{
				bestFitness = fitness[minindex];		// 更新最短路徑
				for (int j = 0; j<N; j++)
					globalBest[j] = pop[minindex][j]; // 更新全局最短路徑序列
			}
		}

		timeTime++;
		aveLen += bestFitness;
		printf("第%d次計算，最短路徑長度為:%d\n", timeTime, bestFitness);
	}



	
	finish = clock(); // 計算結束
	double duration = ((double)(finish - start)) / CLOCKS_PER_SEC; // 計算耗時
	printf("遺傳算法\n");
	/*
	for (int i = 0; i < N; i++)
	{
		cout << globalBest[i] << " ";
	}
	cout << endl;
	printf("最短路徑長度為:%d\n", bestFitness);
	*/
	printf("程式平均耗時為:%lf秒.\n", duration/TESTTIME);
	printf("平均結果為：%2f\n", aveLen / 30);
	return 0;
}

遺傳算法結果：

模拟退火和遺傳算法解決TSP問題模拟退火和遺傳算法解決TSP問題代碼下載下傳：

圖4：遺傳算法結果圖

走過的坑：

遺傳算法收斂特别慢。我所實作的版本經過了多次！多次！的改良。才勉強達到模拟退火的水準。不然效果特别差。
遺傳算法的初始化對最終結果有較大的影響，這點和模拟退火有很大的不同。
遺傳算法實作難度大于模拟退火。整個過程耗費了本人很多很多時間!

兩者對比：

兩者結果其實類似。無論從時間上還是從結果上。
其實遺傳算法要次于模拟退火。一是遺傳算法很依賴初始解，這給構造帶來了極大的挑戰。二是遺傳算法收斂特别慢，容易陷入局部最優。
遺傳算法的交叉算子，選擇算子有多種并且實作相對複雜，并且需要調的參數比模拟退火多。針對簡單問題時，不建議使用遺傳算法。

代碼下載下傳：

包括sa的源碼、GA源碼以及資料集

有不足之處請多指教 ?

資料集來源：

http://people.sc.fsu.edu/~jburkardt/datasets/tsp/tsp.html

http://people.sc.fsu.edu/~jburkardt/datasets/tsp/fri26_d.txt

模拟退火部落格：

https://www.cnblogs.com/lyrichu/p/6688459.html

https://www.cnblogs.com/flashhu/p/8884132.html

https://www.cnblogs.com/rvalue/p/8678318.html

TSP介紹：

https://baike.baidu.com/item/TSP問題/840008?fr=aladdin

GA:

https://www.cnblogs.com/lyrichu/p/6152928.html

https://blog.csdn.net/greedystar/article/details/80343841#五、源代碼

模拟退火和遺傳算法解決TSP問題模拟退火和遺傳算法解決TSP問題代碼下載下傳：

模拟退火和遺傳算法解決TSP問題

資料集介紹

算法介紹

模拟退火

遺傳算法

走過的坑：

兩者對比：

代碼下載下傳：

繼續閱讀

【發車優化】基于遺傳算法的公共汽車排程排班優化的研究與實作附Matlab代碼

TensorFlow（五）隊列與線程

利用NSGA-II算法求解多元多目标函數優化問題

【搞搞算法】用遺傳算法解決多目标規劃問題_論文閱讀筆記

使用matlab實作簡單的遺傳算法（一）

用Python實作基于遺傳算法（GA）求解混合流水工廠中的房間排程問題（HFSP）1 問題描述2 算法3 代碼4 實驗結果

科學計算之遺傳算法python實作遺傳算法

NSGA2一些目标函數在matlab中的測試結果

遺傳算法的matlab實作

遺傳算法原理及其matlab程式實作一、遺傳算法背景二、遺傳算法原理及其數學模型三、遺傳算法中關鍵參數的設定及作用四、遺傳算法matlab實作代碼5 結尾篇

遺傳算法及其實作遺傳算法的思想

算法篇----簡易版的粒子群（PSO）實作（Matlab語言）前言1 定義變量2 初始化種群3 計算粒子适應度4 更新個體最優值5 更新全局最優值6 更新粒子的速度和位置7 适應度函數8 完整代碼9 實驗結果

基于體均值理論的換熱器閉合模型的發展前言：換熱器設計一直以來都非常重要，在當今世界變得越來越關鍵，并且與優化密切相關。常

遺傳算法_C語言

遺傳算法的進一步探究—多種群_數學模組化matlab算法(六)

《算法圖解》-C8貪婪算法一、貪婪算法二、NP完全問題