摘要：本文借助于遺傳算法給出了旅行銷售員問題較優解的求解方法，并用C#語言實現。

1. 旅行銷售員問題的描述和相關定理

　　為了方便討論旅行銷售員問題（Traveling Saleman Problem，簡稱TSP），先給出圖論
中相關的一些定義：
定義1 經過圖G的每個頂點正好一次的圈，稱為G的哈密爾頓圈，簡稱H圈。
定義2 在加權圖G=（V，E）中

（1）最小的H圈稱為最佳H圈；

（2）經過每個頂點至少一次且權最小的閉通路稱為最佳銷售員回路。

　　本文要解決的問題就是求加權圖的最佳銷售員回路。而最佳銷售員回路的問題可以轉化
為最佳H圈問題。
設給定加權圖G=（V，E），用它構造以V為頂點集的完全圖G′=（V，E′），其中E′中每條
邊（x，y）的權等于圖G中頂點x到頂點y的最短路徑的長度，即
對任意∈E′，權 
圖論中相關定理如下：

定理1 加權圖G的最佳銷售員回路的長度和G′的最佳H圈的長度相同。
定理2 在加權完全圖中最佳H圈問題是NPC問題。

　　根據定理1我們可以把任意加權圖的旅行銷售員問題轉化為其加權完全圖上的最佳H圈問
題。根據定理2我們知道對該問題尋找多項式時間算法是不現實的，我們只能構造一些啟發式
近似算法來求得問題的較優解。

2. 旅行銷售員問題的遺傳算法實現

2.1 用Floyd-Warshall算法求圖中任意兩頂點的最短路徑

　　Floyd-Warshall算法步驟：
STEP0 k=0；對于所有節點i和j，令 （可以認為 ）， ；
STEP1 k=k+1；對于所有頂點i和j，若 ，則令 ；否則令 ；
STEP2 如果k==n，結束；否則轉STEP1。
其中代號意義如下：
: 圖G的頂點數目
：圖G中頂點i到j的弧的權值
：圖G中頂點i到j中間經過前k個頂點的最短路徑的長度
：圖G中頂點i到j中間經過前k個頂點的最短路徑的前一個頂點的標號
顯然， 就是頂點i到j的最短路徑的長度。
注：這個算法由命名空間TSP下的Floyd類來實現。

2.2 遺傳算子的選擇 

　　在本文中，編碼方案我們采用可能是對一個旅行最自然的表達-路徑表達。例如，一個旅
行
5-1-7-8-9-4-6-2-3
可以簡單地被表達成
（5 1 7 8 9 4 6 2 3）。
遺傳算法的運算步驟：
{
隨機初始化種群P（0），t=0；
計算P（0）中個體的適應度；
while(不滿足中止條件)
{
for(k=0；k<N；k+=2) //設N能被2整除
{
隨機從P（t）中產生兩個父體交叉操作后產生兩個后代；
把這兩個后代加入中間群體P′（t）中；
}
對中間群體P′（t）中的每個個體進行變異操作；
從P（t）和P′（t）中進行選擇操作得到N個個體賦予新群體P（t+1）中；
計算P（t+1）中每個個體的適應度；
t++；
}
}
根據實測結果，我們僅從眾多的遺傳算子中選擇幾個性能較好的算子。

2.2.1 交叉算子

　　采用由Davis提出OX算子-通過從一個親體中挑選一個子序列旅行并保存另一個親體的城
市相對次序來構造后代。例如，兩個親體（切割點以"|"標記）
p1=? 2 3 | 4 5 6 7 | 8 9）
p2=（4 5 2 | 1 8 7 6 | 9 3）
將按照下面的方式產生后代。首先，切割點之間的片段被拷貝到后代里：
o1=（x x x | 4 5 6 7 | x x）
o2=（x x x | 1 8 7 6 | x x）
為了得到o1，我們只需要移走p2中已在o1中的城市4、5、6和7后，得到
2-1-8-9-3
該序列順次放在o1中：
o1=（2 1 8 | 4 5 6 7 | 9 3）
相似地，我們可以得到另一個后代：
o2=（2 3 4 | 1 8 7 6 | 5 9）
OX交叉開拓了路徑表達的一個特性，即城市的次序（不是它們的位置）是重要的，即兩個旅
行
5-1-7-8-9-4-6-2-3
8-9-4-6-2-3-5-1-7
實際上是相同的。
注：本算子由命名空間TSP中的類Ga中的公共成員函數CrossOX()來實現。

2.2.2 變異算子

　　對于變異算子我們采用倒置變異。倒置變異是在染色體上隨機地選擇兩點，將兩點間的
子串反轉。說明如下：
原個體：（1 2 3 4 5 6 7 8 9）
隨機選擇兩點：（1 2 | 3 4 5 6 | 7 8 9）
倒置后的個體：（1 2 | 6 5 4 3 | 7 8 9）
注：本算子由命名空間TSP中的類Ga中的公共成員函數MutateReverse()來實現。

2.2.3 選擇算子

　　對于選擇算子我們采用錦標賽選擇算子。選擇時，選隨機地在群體中選擇k個個體進行比
較，適應度最好的個體將被選擇復制到下一代，參數k稱為競賽規模，常取k=2。
注：本算子由命名空間TSP中的類Ga中的公共成員函數SelectMatch()來實現。

3. 編程中的相關問題

　　根據2中的分析和算法，我們便可借助于一種編程語言來實現它，我們在這里選擇C#語言
。對于如何編程實現和編程中的一些細節我將在下面分類討論。注意整個編碼工作都在命名
空間TSP中實現。

3.1 數據的輸入輸出

　　我們知道在解決旅行銷售員問題時要輸入圖的信息，它是一個矩陣，如果每次都在C#的
集成開發環境中直接輸入，那么將不勝麻煩，并且輸入的信息還不易保存。因此，我們采用
文件輸入方式。這樣我們就有必要規定數據文件的格式。我們這里自定義了兩種數據文件（
僅限于數值數據）的格式，說明如下。
比如有一矩陣
1.2 2.3 0
0 0 3
4.3 0 5
格式1：
1………………………文件格式說明
matrix 3 3 …………數據矩陣大小的說明
5………………………數據矩陣的非零元素個數 
1 1 1.2……………非零元素所在行數、列數和元素數值，下同
1 2 2.3
2 3 3
3 1 4.3
3 3 5
注：顯然格式1方便稀疏矩陣的輸入，本格式是自定義格式。
格式2：
2………………………文件格式說明
matrix 3 3 …………數據矩陣大小的說明
1: 1.2 2.3 0 ……行前的冒號一定不能缺，下同
2: 0 0 3
3: 4.3 0 5
注：格式2是針對一般數據矩陣的輸入，本格式是自定義格式。
我們已經在c#語言中用命名空間TSP中的LSMat類實現數值數據的存取。

3.2 隨機數的產生

　　C#中帶有隨機數的產生的類，在命名空間System下的Random類中。但是它并不能滿足遺
傳算法編程的需求，于是我就實現了自己的隨機數生成類RandNumber，當然它是基于System
.Random類的。程序源碼中有詳細說明。

3.3 Floyd算法

　　我用Floyd類來實現求圖中任意兩點的最短路徑的Floyd-Warshall算法。整個算法的編制
完全按照2.1中的算法步驟進行的。

3.4 遺傳算法類

　　這個類也是主要的類了，就用Ga類實現了。這里我特別要提的是Ga的類成員CrossOx()，
按2.2.1中提供的交叉算子的計算過程，我們發現的進行一次交叉操作的時間復雜度是O(n2)
，經過仔細分析我們找到了時間復雜度為O(n)的方法，讀者仔細閱讀程序就會發現。

4.下一步的工作

　　我們下一步的工作將繼續豐富遺傳算法的工作，同時還將用另一類啟發式算法-螞蟻算法
來實現TSP的求解。我們會努力把這個問題做得更好。
My Email:wanbaocheng@163.com


程序代碼：

 


namespace TSP
{
	//數據文件格式：
	//第一行有兩個數據：矩陣行數  矩陣列數
	//接下來的行的數據：行  列  該行該列的元素值
	//注意數據與數據之間是用空格隔開的，沒有給出的矩陣的某些位置的值用0來代替
	using System;
	using System.IO;
	class TestClass
	{
		public static void TestGa(string DataFileName)
		{
			Ga ga=new Ga();
			ga.GaTsp(DataFileName);
		}
		public static void TestGa2()
		{
			RandNumber rands=new RandNumber();
			Ga ga=new Ga();
			int n=36;
			double [,]CostMat=new double[n,n];
			double [,]vec=new double[n,2];
			for(int i=0;i<n;i++)
			{
				vec[i,0]=rands.Rand01();
				vec[i,1]=rands.Rand01();
			}
			for(int i=0;i<n;i++)
				for(int j=0;j<n;j++)
				{
					if(i==j) CostMat[i,j]=0.0;
					else
					{
						double s1=vec[i,0]-vec[j,0];
						double s2=vec[i,1]-vec[j,1];
						CostMat[i,j]=Math.Sqrt(s1*s1+s2*s2);
					}
				}
			ga.GaTsp(CostMat);
			LSMat.SaveDataFile(@"d:\c#\tsp\out01.txt",CostMat,2);
		}
		public static void TestLSMat()
		{
			int n=6;
			double [,]mat=new double[n,n];
			for(int i=0;i<n;i++)
				for(int j=0;j<n;j++)
				{
					mat[i,j]=(double)(i+1)*(j+1);
				}
			//LSMat.SaveDataFile(@"D:\eeee1.txt",mat,1);
			double [,]mat2;
			mat2=LSMat.LoadDoubleDataFile(@"D:\eeee1.txt");
			for(int i=0;i<mat2.GetLength(0);i++)
			{
                Console.Write("{0}: ",i);
				for(int j=0;j<mat2.GetLength(1);j++)
				{
					Console.Write("{0}  ",mat2[i,j]);
				}
				Console.Write("\n");
			}
		}
		public static void Main(string[] args)
		{
			//TestGa(@"d:\c#\Tsp\data01.txt");
			TestGa2();
			//TestLSMat();
		}
	}
	/* 下面是TSP問題的遺傳算法實現類
	 * */
	class Ga
	{
		private Floyd minfloyd=new Floyd();//創建Floyd類
		private double [,]Distance;
		private int N; //群體規模
		private int Length; //個體長度
		private double Pc; //交叉概率
		private double Pm; //變異概率
		private int MaxGene; //最大迭代代數
		public int []MinIndividual; //當前代的最好個體指針
		public double MinValue; //到當前代至最好個體的適應度值
		private int [,]Buf;  //群體矩陣
		private int [,]Buf1; //中間群體矩陣
		private int [,]Buf2; //中間群體矩陣
		private double []FitV; //群體Buf的每個個體的適應度
		private double []FitV1;//群體Buf1的每個個體的適應度
		private double []FitV2;//群體Buf2的每個個體的適應度
		private int[] ppindivi; //交叉算子中用到的中轉向量
		private int[] pp;//交叉算子中用到的中轉向量
		private RandNumber randnumber=new RandNumber();//創建一個隨機數類
		//類初始化函數
		public void Initialize(string DataFileName,int N1,double Pc1,double Pm1,int Ma
xGene1)
		{
			minfloyd.MinFloyd(DataFileName);
			Distance=minfloyd.GetDistance();
			for(int i=0;i<Distance.GetLength(0);i++)
				Distance[i,i]=0;
			N=N1;
			Length=Distance.GetLength(0);
			Pc=Pc1;
			Pm=Pm1;
			MaxGene=MaxGene1;
			MinValue=double.MaxValue;
			Buf=new int[N,Length];
			Buf1=new int[N,Length];
			Buf2=new int[N,Length];
			FitV=new double[N];
			FitV1=new double[N];
			FitV2=new double[N];
			MinIndividual=new int[Length];
			int []individual;
			for(int i=0;i<N;i++)
			{
				individual=randnumber.RandDifferInt(Length-1);
				for(int j=0;j<Length;j++)
					Buf[i,j]=individual[j];
				FitV[i]=Fit(i,0);
			}
			ppindivi=new int[Length];
			pp=new int[Length];
		}
		//類初始化函數
		public void Initialize(double [,]CostMat,int N1,double Pc1,double Pm1,int MaxG
ene1)
		{
			minfloyd.MinFloyd(CostMat);
			Distance=minfloyd.GetDistance();
			for(int i=0;i<Distance.GetLength(0);i++)
				Distance[i,i]=0;
			N=N1;
			Length=Distance.GetLength(0);
			Pc=Pc1;
			Pm=Pm1;
			MaxGene=MaxGene1;
			MinValue=double.MaxValue;
			Buf=new int[N,Length];
			Buf1=new int[N,Length];
			Buf2=new int[N,Length];
			FitV=new double[N];
			FitV1=new double[N];
			FitV2=new double[N];
			MinIndividual=new int[Length];
			int []individual;
			for(int i=0;i<N;i++)
			{
				individual=randnumber.RandDifferInt(Length-1);
				for(int j=0;j<Length;j++)
					Buf[i,j]=individual[j];
				FitV[i]=Fit(i,0);
			}
			ppindivi=new int[Length];
			pp=new int[Length];
		}
		//返回第i個個體的適應度（order==0,返回Buf的;order==1,返回Buf1的;否則返回Buf2的
）
		public double Fit(int i,int order)
		{
			if(order==0)
			{
				double fitv=0.0;
				for(int j=0;j<Length-1;j++)
					fitv+=Distance[Buf[i,j],Buf[i,j+1]];
				fitv+=Distance[Buf[i,Length-1],Buf[i,0]];
				return fitv;
			}
			if(order==1)
			{
				double fitv=0.0;
				for(int j=0;j<Length-1;j++)
					fitv+=Distance[Buf1[i,j],Buf1[i,j+1]];
				fitv+=Distance[Buf1[i,Length-1],Buf1[i,0]];
				return fitv;
			}
			else
			{
				double fitv=0.0;
				for(int j=0;j<Length-1;j++)
					fitv+=Distance[Buf2[i,j],Buf2[i,j+1]];
				fitv+=Distance[Buf2[i,Length-1],Buf2[i,0]];
				return fitv;
			}
		}
		//順序交叉算子。由雙親Buf中的第i1和j1兩個個體交叉后得到的后代賦給Buf1中的第k1個
個體
		public void CrossOX(int i1,int j1,int k1)
		{
			/* 產生[0，Length-1]間的兩個隨機整數。大的賦給l1,小的賦給l2。
			 * */
			int []randi;
			randi=randnumber.RandDifferInt(0,Length-1,2); 
			int l1,l2;
			if(randi[0]>randi[1])
			{
				l1=randi[1];
				l2=randi[0];
			}
			else
			{
				l1=randi[0];
				l2=randi[1];
			}
			//結束l1和l2的賦值

			//把Buf的第j1個個體賦給中轉向量ppindivi
			for(int i=0;i<Length;i++)
				ppindivi[i]=Buf[j1,i];
			//獲得pp，其中pp[ii]表示頂點ii在個體ppindivi中的位置
			for(int i=0;i<Length;i++)
				pp[ppindivi[i]]=i;
			//把Buf中的第i1個個體中的l1到l2之間的頂點在第i2個個體中用-1標記出來
			for(int i=l1;i<=l2;i++)
				ppindivi[pp[Buf[i1,i]]]=-1;
			int k=0;
			for(int i=0;i<Length;i++)
			{