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

C#版遗传算法解TSP问题

				if(ppindivi[i]!=-1)
				{
					if(k<l1)
					{
						Buf1[k1,k]=ppindivi[i];
						k++;
					}
					else
					{
						Buf1[k1,k+l2-l1+1]=ppindivi[i];
						k++;
					}
				}
			}
			for(int i=l1;i<=l2;i++)
				Buf1[k1,i]=Buf[i1,i];
			FitV1[k1]=Fit(k1,1);
		}
		//反转变异算子
		//对Buf1中的第i1个个体进行反转变异
		public void MutateReverse(int i1)
		{
			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];
			}
			int midl=(l1+l2)/2;
			for(int i=l1;i<=midl;i++)
			{
				int ii=Buf1[i1,i];
				Buf1[i1,i]=Buf1[i1,l1+l2-i];
				Buf1[i1,l1+l2-i]=ii;
			}
			FitV1[i1]=Fit(i1,1);
		}
		//锦标赛选择算子
		//从Buf和Buf1中选择后存入Buf2中，最后再转入Buf中
		public void SelectMatch()
		{
			int []randi;
			for(int i=0;i<N;i++)
			{
				randi=randnumber.RandDifferInt(0,2*N-1,2);
				if((randi[0]<N)&&(randi[1]<N))
				{
					if(FitV[randi[0]]<FitV[randi[1]])
					{
						for(int j=0;j<Length;j++)
							Buf2[i,j]=Buf[randi[0],j];
						FitV2[i]=FitV[randi[0]];
					}
					else
					{
						for(int j=0;j<Length;j++)
							Buf2[i,j]=Buf[randi[1],j];
						FitV2[i]=FitV[randi[1]];
					}
				}
				else if((randi[0]<N)&&(randi[1]>=N))
				{
					if(FitV[randi[0]]<FitV1[randi[1]-N])
					{
						for(int j=0;j<Length;j++)
							Buf2[i,j]=Buf[randi[0],j];
						FitV2[i]=FitV[randi[0]];
					}
					else
					{
						for(int j=0;j<Length;j++)
							Buf2[i,j]=Buf1[randi[1]-N,j];
						FitV2[i]=FitV1[randi[1]-N];
					}
				}
				else if((randi[0]>=N)&&(randi[1]<N))
				{
					if(FitV1[randi[0]-N]<FitV[randi[1]])
					{
						for(int j=0;j<Length;j++)
							Buf2[i,j]=Buf1[randi[0]-N,j];
						FitV2[i]=FitV1[randi[0]-N];
					}
					else
					{
						for(int j=0;j<Length;j++)
							Buf2[i,j]=Buf[randi[1],j];
						FitV2[i]=FitV[randi[1]];
					}
				}
				else
				{
					if(FitV1[randi[0]-N]<FitV1[randi[1]-N])
					{
						for(int j=0;j<Length;j++)
							Buf2[i,j]=Buf1[randi[0]-N,j];
						FitV2[i]=FitV1[randi[0]-N];
					}
					else
					{
						for(int j=0;j<Length;j++)
							Buf2[i,j]=Buf1[randi[1]-N,j];
						FitV2[i]=FitV1[randi[1]-N];
					}
				}
			}
			int [,]Bufm;
			Bufm=Buf;
			Buf=Buf2;
			Buf2=Bufm;
			double []FitVm;
			FitVm=FitV;
			FitV=FitV2;
			FitV2=FitVm;
		}
		//找出当前最好个体，如果是真，则从Buf中寻找，否则，从Buf和Buf1中寻找
		public void FindMinIndividual(bool iszero)
		{
			int ismin=-1;
			for(int i=0;i<N;i++)
			{
				if(MinValue>FitV[i])
				{
					ismin=i;
					MinValue=FitV[i];
				}
			}
			if(ismin!=-1)
			{
				for(int j=0;j<Length;j++){
					MinIndividual[j]=Buf[ismin,j];
				}
			}
			if(!iszero)
			{
				ismin=-1;
				for(int i=0;i<N;i++)
				{
					if(MinValue>FitV1[i])
					{
						ismin=i;
						MinValue=FitV1[i];
					}
				}
				if(ismin!=-1)
				{
					for(int i=0;i<Buf.GetLength(1);i++)
						MinIndividual[i]=Buf1[ismin,i];
				}
			}
					  
		}
		//单步运行函数
		public void GaStep()
		{
			int []randi;
			for(int i=0;i<N;i++)
			{
				randi=randnumber.RandDifferInt(0,N-1,2);
				if(randnumber.Rand01()<Pc)
					CrossOX(randi[0],randi[1],i);
				else
				{
					for(int j=0;j<Length;j++)
						Buf1[i,j]=Buf[randi[0],j];
					FitV1[i]=FitV[randi[0]];
				}
			}
			for(int i=0;i<N;i++)
			{
				if(randnumber.Rand01()<Pm)
					MutateReverse(i);
			}
			SelectMatch();
			FindMinIndividual(false);
		}
		//TSP问题的遗传算法的主程序
		public void GaTsp(string DataFileName)
		{
			Initialize(DataFileName,10,0.6,0.05,10000);
			for(int i=0;i<MaxGene;i++)
				GaStep();
			Console.WriteLine("MinValue={0}",MinValue);
			Console.WriteLine("{0}",GetPath(MinIndividual));
		}
		//TSP问题的遗传算法的主程序
		public void GaTsp(double [,]CostMat)
		{
			Initialize(CostMat,30,0.5,0.07,8000);
			for(int i=0;i<MaxGene;i++)
			{
				GaStep();
			}
			Console.WriteLine("MinValue={0}",MinValue);
			Console.WriteLine("{0}",GetPath(MinIndividual));
		}
		//获得个体的路径
		public string GetPath(int []Individual)
		{
			string path=null;
			string str="-->";
			string subpath;
			for(int i=1;i<Length;i++)
			{
				if(Individual[i-1]<10)
				{
					subpath=minfloyd.GetPath(Individual[i-1],Individual[i]).Remove(0,4);
				}
				else if(Individual[i-1]<100)
				{
					subpath=minfloyd.GetPath(Individual[i-1],Individual[i]).Remove(0,5);
				}
				else
				{
					subpath=minfloyd.GetPath(Individual[i-1],Individual[i]).Remove(0,6);
				}
				path+=subpath+str;
			}
			if(Individual[Length-1]<10)
			{
				subpath=minfloyd.GetPath(Individual[Length-1],Individual[0]).Remove(0,4);
			}
			else if(Individual[Length-1]<100)
			{
				subpath=minfloyd.GetPath(Individual[Length-1],Individual[0]).Remove(0,5);
			}
			else
			{
				subpath=minfloyd.GetPath(Individual[Length-1],Individual[0]).Remove(0,6);
			}
			path+=subpath;
			return path;
		}
	}
	class RandNumber
	{
		private Random rr=new Random(); //创建Random类的实例
		// 返回low与high之间的number个随机整数（包括low和high）
		public int[] RandInt(int low,int high,int number)
		{
			int []randvec;
			randvec=new int[number];
			for(int i=0;i<number;i++)
				randvec[i]=rr.Next()%(high-low+1)+low;
			return randvec;
		}
		// 返回0与high之间的number个随机整数（包括0和high）
		public int[] RandInt(int high,int number)
		{
			return RandInt(0,high,number);
		}
		// 返回low与high之间的number(number小于high-low+1）个不同的随机整数（包括low和
high）
		public int[] RandDifferInt(int low,int high,int number)
		{
			if(number>(high-low+1)) number=high-low+1;
			int []randvec;
			randvec=new int[number];
			randvec[0]=rr.Next()%(high-low+1)+low;
			int randi;  //存储中间过程产生的随机整数
			bool IsDiffer;//用于判断新产生的随机整数是否与以前产生的相同，若不同为真，否则
为假
			for(int i=1;i<randvec.GetLength(0);i++)
			{
				while(true)
				{
					randi=rr.Next()%(high-low+1)+low;
					IsDiffer=true;   //设定为真
					for(int j=0;j<i;j++)
					{
						if(randi==randvec[j])
						{
							IsDiffer=false; //相同为假
							break;
						}
					}
					if(IsDiffer)
					{
						randvec[i]=randi;
						break;
					}
				}
			}
			return randvec;
		}
		// 返回low与high之间的high-low+1个不同的随机整数（包括low和high）
		public int[] RandDifferInt(int low,int high)
		{
			return RandDifferInt(low,high,high-low+1);
		}
		// 返回0与high之间的high+1个不同的随机整数（包括0和high）
		public int[] RandDifferInt(int high)
		{
			return RandDifferInt(0,high,high+1);
		}
        // 返回一个[0，1]之间的服从均匀分布的随机数
		public double Rand01()
		{
			return rr.NextDouble();
		}
		// 返回number个[0，1]之间的服从均匀分布的随机数
		public double[] Rand01(int number)
		{
			double []randf=new double[number];
			for(int i=0;i<number;i++)
				randf[i]=rr.NextDouble();
			return randf;
		}
	}
	/* 
	 * 下面是Floyd算法类，注意图的顶点标号是从0开始
	 * */
	class Floyd
	{
		private double [,]Distance; //图的最短路径矩阵
		private int [,]Path; //图的最短路径的紧前顶点矩阵
		public int GetDotN()  //获得顶点数
		{
			return Path.GetLength(0);
		}
		public double GetDistance(int i,int j)  //获得顶点i到顶点j的最短距离
		{
			return Distance[i,j];
		}
		//获得图的最短路径矩阵
		public double[,] GetDistance()
		{
			return Distance;
		}
		//获得顶点ni到顶点nj的最短路径
		public string GetPath(int ni,int nj)
		{
			int []pathReverse;
			pathReverse=new int[Path.GetLength(0)];
			pathReverse[0]=Path[ni,nj];
			int k=0;
			while(pathReverse[k]!=ni)
			{
				k++;
				pathReverse[k]=Path[ni,pathReverse[k-1]];
			}
			string path=pathReverse[k].ToString();
			string str1="-->";
			for(int i=k-1;i>=0;i--)
			{
				path+=(str1+pathReverse[i].ToString());
			}
			path+=(str1+nj.ToString());
			return path;
		}
		public void MinFloyd(string DataFileName)
		{
			double [,]CostMat;
			CostMat=LSMat.LoadDoubleDataFile(DataFileName);
			MinFloyd(CostMat);
		}
		//Floyd算法的实现
		//CostMat是图的权值矩阵
		public void MinFloyd(double [,]CostMat)
		{
			int nn;  
			nn=CostMat.GetLength(0);  //获得图的顶点个数
			for(int i=0;i<nn;i++)
				for(int j=0;j<nn;j++)
				{
					if(CostMat[i,j]==0)
						CostMat[i,j]=10e+100;
				}
			Distance=new double[nn,nn];
			Path=new int[nn,nn];
			//初始化Path,Distance
			for(int i=0;i<nn;i++)
			{
				for(int j=0;j<nn;j++)
				{
					Path[i,j]=i;
					Distance[i,j]=CostMat[i,j];
				}
				Distance[i,i]=0.0;
			}
			for(int k=0;k<nn;k++)