tspgacs.cs

遗传算法用遗传算法解决旅行商问题关键词中华人民共和国

using System;
using System.IO;

namespace scheduling.tsp
{
	/// <summary>
	/// TspGACs 的摘要说明。
	/// </summary>
	public class TspGACs
	{
		public TspGACs()
		{
			
		}

		public int CityNumber;				//城市数
		private int PopSize = 30;			//种群数
		private float CrossoverRate = 0.2F; //交叉率
		private float MutationRate = 0.08F;	//变异率

		private double[] SelectedRate;		//各染色体的选择概率
		private double[] AddSelectedRate;	//各染色体的累积概率

		private int[,] Chromosomes;			//染色体数组
		private double[,] Path;				//城市路径数组
		private double[] Distance;			//个体路径
		private double[] IndividualFitness; //个体适值(适度函数取目标值的倒数)即F(T)=1/f(T)   
		private int BestIndex;				//最好个体的下标
		private int WorstIndex;				//最差个体的下标
		private double BestFitness = 0.0;	//最好的适值
		private double WorstFitness = 0.0;	//最差的适值
		public int MaxGeneration = 1000;	//最大迭代次数
		public int curGeneration;			//当前迭代次数

		public double BestValue = 1E+38;    //最佳值
		public int[] BestIndividual;		//最佳值所在的个体
		public int BestGeneration = 0;		//最佳值所出现的代数 

		/// <summary>
		/// 初始化数据
		/// </summary>
		/// <param name="FileName"></param>
		/// <param name="nCity"></param>
		public void InitPath(string FileName,int nCity)
		{
			string file = FileName;
			FileStream fs = new FileStream(file, FileMode.Open, FileAccess.Read); 
			StreamReader sr = new StreamReader(fs); 
			
			this.CityNumber = nCity;
			SelectedRate = new double[PopSize];						//各染色体的选择概率
			AddSelectedRate = new double[PopSize];					//各染色体的累积概率
			Chromosomes = new int[this.PopSize,this.CityNumber];	//染色体数组
			Distance = new double[PopSize];							//个体路径
			IndividualFitness = new double[PopSize];				//个体适值(适度函数取目标值的倒数)即F(T)=1/f(T)   
			BestIndividual= new int[CityNumber];					//最佳值所在的个体

			string separator = " ";
			string strLine ;
			string strDist;
			double dist;
			int row = 0;
			int col = 0;
			this.Path = new double[this.CityNumber,this.CityNumber];
			//跳过标题行
			strLine = sr.ReadLine();
			while( (strLine = sr.ReadLine()) != null )  //读取文件进行处理
			{
				strLine = strLine.Trim();
				col = 0;
				while( strLine != "" )  //读取列
				{
					//读取数据
					int indexOf = strLine.IndexOf(separator);
					if(indexOf > 0)
					{
						strDist = strLine.Substring(0,strLine.IndexOf(separator)) ;

						strLine = strLine.Substring(strLine.IndexOf(separator) + separator.Length, 
							strLine.Length - strLine.IndexOf(separator) - separator.Length ) ;
						dist = Convert.ToDouble(strDist);

					}
					else
					{
						strDist = strLine.Trim();
						dist = Convert.ToDouble(strDist);

						strLine = "" ;
					}
					this.Path[row,col] = dist;
					col ++;
					strLine = strLine.Trim();
				}
				row ++;
			}

			sr.Close();
			fs.Close();

			//			for(int i = 0; i < this.CityNumber; i++)
			//			{
			//				string strRow = "";
			//				for(int j = 0;  j < this.CityNumber; j++)
			//				{
			//					strRow += this.Path[i,j] + " ";
			//				}
			//				Console.WriteLine(strRow);
			//			}

		}


		//打印路径
		public void PrintPath()
		{
			Console.WriteLine("城市间的距离为:");
			Console.Write("\t  ");
			for(int i=0;i<CityNumber;i++)
				Console.Write("城市{00} ",i+1);
			Console.WriteLine();
			for(int i=0;i<CityNumber;i++)
			{
				Console.Write("城市{000}\t",i+1);
				for(int j=0;j<CityNumber;j++)
					Console.Write("{0,6}",Path[i,j]);
				Console.WriteLine();
			}	
		}


		//初始化种群
		public void InitChromosome()
		{
			Random rand = new Random();
			for(int i=0;i<PopSize;i++)
			{
				Chromosomes[i,0] = rand.Next(CityNumber); //随机产生第一个数
				for(int j=1;j<CityNumber;j++)  //产生其余不重复的(CityNumber-1)个数	
				{
					Chromosomes[i,j] = rand.Next(CityNumber);
					for(int m=0;m<j;m++)  //需要检测当前数j前面的m:0->(j-1)个数
						//for(int k=0;k<j;k++)   =========2005-5-3==========
						for(int k=0;k<j;)
						{
							if(Chromosomes[i,j] != Chromosomes[i,k])
							{
								k++;  //=========2005-5-3============						
								continue;
							}
							else
							{
								do
								{
									Chromosomes[i,j] = rand.Next(CityNumber);
								}while(Chromosomes[i,j] == Chromosomes[i,k]);
								k = 0;  //===回溯===
							}
						}
				}
			}
		}


		//打印种群
		public void PrintChromosome()
		{
			for(int i=0;i<PopSize;i++)
			{
				Console.Write("个体{0}\t",i + 1);
				for(int j=0;j<CityNumber;j++)
					Console.Write(Chromosomes[i,j]);
				Console.WriteLine("\t路径为:{0}",Distance[i]);
			}
		}
		/*    //测试种群的合法性
			public bool TestChromosome(int individual)
			{
      	
			}
		*/
		//修复种群
		public void UpdateChromosome()
		{

		}
		//计算个体适值(适度函数取目标值的倒数)即F(T)=1/f(T) 及个体路径
		public void CalculateFitness()
		{
			double sum = 0;
			for(int i=0;i<PopSize;i++)
			{
				sum = 0;
				Distance[i] = 0;
				for(int j=0;j<CityNumber - 1;j++)
					sum += Path[Chromosomes[i,j],Chromosomes[i,j+1]];
				Distance[i] = sum + Path[Chromosomes[i,CityNumber-1],Chromosomes[i,0]];		
				IndividualFitness[i] = (double)1.0/Distance[i];
			}
		}

		//计算各染色体的选择概率SelectedRate[i]
		public void CalculateSelectedRate()
		{
			CalculateFitness();
			double sum =0;
			for(int i=0;i<PopSize;i++)
				sum += IndividualFitness[i];
			for(int i=0;i<PopSize;i++)
			{
				SelectedRate[i] = IndividualFitness[i]/sum;
				//Console.WriteLine(SelectedRate[i]);
			}
		}

		//计算各染色体的累积选择概率
		public void CalAddSelectedRate()
		{
			for(int i=0;i<PopSize;i++)
			{
				AddSelectedRate[i] = 0.0;
				for(int k=0;k<=i;k++)
					AddSelectedRate[i] += SelectedRate[k];
				//Console.WriteLine(AddSelectedRate[i]);
			}
		}
		//寻找最好和最差的个体 & 打印个体和适值
		public void FindBestAndWorstIndividual()
		{
			CalculateFitness();
			BestIndex = 0;
			WorstIndex = 0;
			BestFitness = IndividualFitness[BestIndex];
			WorstFitness = IndividualFitness[WorstIndex];
	
			for(int i=1;i<PopSize;i++)
				if (IndividualFitness[i] > BestFitness)
				{
					BestFitness = IndividualFitness[i];
					BestIndex = i;
				}
				else if(IndividualFitness[i] < WorstFitness)
				{
					WorstFitness = IndividualFitness[i];
					WorstIndex = i;
				}
			if(BestValue > Distance[BestIndex])
			{
				BestValue = Distance[BestIndex];
				BestGeneration = curGeneration;
				for(int j=0;j<CityNumber;j++)
					BestIndividual[j] = Chromosomes[BestIndex,j];
			}
			Console.Write("第{0,3}代最好的个体为：{1}: ",curGeneration,BestIndex + 1);
			for(int j=0;j<CityNumber;j++)
				Console.Write(Chromosomes[BestIndex,j]);
			Console.WriteLine("\t路径为:{0}",Distance[BestIndex]);
			//Console.WriteLine("第{0,3}代最差的个体为：{1}  路径为:{2}",curGeneration,WorstIndex + 1,Distance[WorstIndex]);
		}
		//选择操作
		public void SelectionOperator()
		{
			int index = 0;
			double Ri = 0.0;
			int[,] OffSpring = new int[PopSize,CityNumber];
			Random rand = new Random();
			//Step1:求出种群中适应度最大的个体，将其作为下一代的个体，即最优个体必遗传到下一代
			for(int j=0;j<CityNumber;j++)
				OffSpring[0,j]= Chromosomes[BestIndex,j];
			//Step2:计算每个个体的选择概率P(k)=F(k)/Sum(F(i)) k=0,1,...PopSize
			CalculateSelectedRate();
			//Step3:计算每个个体的累加概率S(k)
			CalAddSelectedRate();
			//Step4:产生PopSize个[0，1)间的均匀分布的随机数Ri，若S(K-1)<Ri<S(K),则选择个体k为下代个体
			for(int i=1;i<PopSize;i++)
			{
				Ri = rand.NextDouble();
				if(Ri < AddSelectedRate[0])
					index = 0;
				else
					for(int k=1;k<PopSize;k++)
						if(Ri > AddSelectedRate[k - 1] && Ri <= AddSelectedRate[k])
							index = k;
				for(int j=0;j<CityNumber;j++)
					OffSpring[i,j] = Chromosomes[index,j];
			}
	
			for(int i=0;i<PopSize;i++)
				for(int j=0;j<CityNumber;j++)
					Chromosomes[i,j] = OffSpring[i,j];
		}

		//交叉操作
		public void CrossOverOperator()
		{
			int Temp = 0;
			Random rand = new Random();
			int Point1,Point2;
			double[] Pc = new double[PopSize];
			int[] CrossoverIndividual = new int[PopSize]; 
			int[] Offspring1 = new int[CityNumber];
			int[] Offspring2 = new int[CityNumber];
			int index = 0;
	
			//Step1:根据交叉的概率求出用于交叉的个体
			for(int i=0;i<PopSize;i++)
				Pc[i] = rand.NextDouble();
			index = 0;
	
			//Console.Write("用于交叉的个体为");
			for(int i=0;i<PopSize;i++)
				if(Pc[i] < CrossoverRate)
				{
					CrossoverIndividual[index] = i;
					//Console.Write("({0},{1})",CrossoverIndividual[index] + 1,index);
					index++;
				}
	
			//Step2:实施交叉操作(0X:顺序交叉)
			/*=========0X:顺序交叉===========
			//1:从第一双亲中随机选一个子串
			//2:将子串复制到一个空字串的相应位置，产生一个原始后代
			//3:删去第二个双亲中子串已有的城市，得到原始后代需要的其他城市的顺序
			//4:按照这个城市顺序，从左到右将这些城市定位到后代的空缺位置上
			=================================*/
			if(index % 2 !=0)
				index = index -1;
			//Console.WriteLine("用于交叉的个体的个数为:({0})",index);
			for(int i=0;i<index - 1;i+=2)
			{
				for(int j=0;j<CityNumber;j++)
				{
					Offspring1[j] = 1000;
					Offspring2[j] = 1000;
				}
	   
				Point1 = rand.Next(CityNumber - 2);
				do
				{
					Point2 = rand.Next(CityNumber);
				}while(Point1 >= Point2);
	    
				//记录下两个父代的子串
				for(int k=Point1 + 1;k<=Point2;k++)
				{
					Offspring2[k] = Chromosomes[CrossoverIndividual[i],k];
					Offspring1[k] = Chromosomes[CrossoverIndividual[i + 1],k];
				}
				/*================
				Console.WriteLine("步骤一的结果为:");
				for(int m=0;m<CityNumber;m++)
				{
				Console.Write("{0}\t",Offspring1[m]);
				}
				Console.WriteLine();
				for(int m=0;m<CityNumber;m++)
				{
				Console.Write("{0}\t",Offspring2[m]);
				}
				Console.WriteLine();
				=======================*/
				//删除对应有的字串
				for(int k=Point1 + 1;k<=Point2;k++)
					for(int j=0;j<CityNumber;j++)
					{
						if(Chromosomes[CrossoverIndividual[i],j] == Offspring1[k])
							Chromosomes[CrossoverIndividual[i],j] = 1000;  //用1000作上删除标记
						if(Chromosomes[CrossoverIndividual[i + 1],j] == Offspring2[k])
							Chromosomes[CrossoverIndividual[i + 1],j] = 1000;  //用1000作上删除标记
					}
				/*========================
				Console.WriteLine("步骤二的结果为:");
				for(int m=0;m<CityNumber;m++)
				{
				Console.Write("{0}\t",Chromosomes[CrossoverIndividual[i],m]);
				}
				Console.WriteLine();
				for(int m=0;m<CityNumber;m++)
				{
				Console.Write("{0}\t",Chromosomes[CrossoverIndividual[i+1],m]);
				}
				Console.WriteLine();
				==========================*/
				//填充其余字串
				Temp = CityNumber - Point2 + Point1;
				int[] Offspring11 = new int[Temp];
				int[] Offspring22 = new int[Temp];
				int m1;
				int m2;
				m1 = 0;
				m2 = 0;
				for(int j=0;j<CityNumber;j++)
				{
					if(Chromosomes[CrossoverIndividual[i],j] != 1000)
						Offspring11[m1++] =Chromosomes[CrossoverIndividual[i],j];
				}
				for(int j=0;j<CityNumber;j++)
				{
					if(Chromosomes[CrossoverIndividual[i + 1],j] != 1000)
						Offspring22[m2++] =Chromosomes[CrossoverIndividual[i + 1],j];
				}
				/*========================
				Console.WriteLine("步骤三的结果为:");
				for(int m=0;m<Temp;m++)
				{
				Console.Write("{0}\t",Offspring11[m]);
				}
				Console.WriteLine();
				for(int m=0;m<Temp;m++)
				{
				Console.Write("{0}\t",Offspring22[m]);
				}
				Console.WriteLine();
				========================*/
				for(int m=0;m<m1;m++)
				{
					for(int j=0;j<CityNumber;j++)
					{
						if(Offspring1[j] ==1000)
						{
							Offspring1[j] =Offspring11[m];
							break;
						}
					}
				}

				for(int m=0;m<m2;m++)
				{
					for(int j=0;j<CityNumber;j++)
					{
						if(Offspring2[j] ==1000)
						{
							Offspring2[j] =Offspring22[m];
							break;
						}
					}
				}
				//将子代复制回父代
				for(int j=0;j<CityNumber;j++)
				{
					Chromosomes[CrossoverIndividual[i],j] = Offspring1[j];
					Chromosomes[CrossoverIndividual[i +1],j] = Offspring2[j];
				}
			}
		}
		//变异操作
		public void MutationOperator()
		{
			//思路:将个体编码串中随机选取的两个基因座之间的基因逆序排列  
			double Pm = 0.0;
			Random rand = new Random();
			int individual;
			//int genepos;
			int Point1,Point2;
			int temp;
			//Console.WriteLine();
			//Console.Write("用于变异的个体为：");
			for(int i=0;i<PopSize * CityNumber;i++)
			{
				Pm = rand.NextDouble();
				if(Pm < MutationRate)
				{
					individual = i/CityNumber;
					//Console.Write("{0}  ",individual);
					//genepos = i%CityNumber;
					//Point1 = rand.Next(CityNumber - 2);
					Point1 = i%CityNumber;
					do
					{
						Point2 = rand.Next(CityNumber);
					}while(Point1 > Point2);
					for(int j=Point1 + 1,k=Point2;j < k;j++,k--)
					{
						temp = Chromosomes[individual,j];
						Chromosomes[individual,j] = Chromosomes[individual,k];
						Chromosomes[individual,k] = temp;
					}	    
				}
			}
		}
		//打印结果
		public void PrintResult()
		{
	
		}

	}
}