c#版遗传算法解tsp问题.txt

C#版遗传算法解TSP问题

摘要：本文借助于遗传算法给出了旅行销售员问题较优解的求解方法，并用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:[e-mail]


程序代码：

 


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++)
			{