form1.cs

遗传算法实现TSP算法

			this.btnStart.Name = "btnStart";
			this.btnStart.Size = new System.Drawing.Size(80, 32);
			this.btnStart.TabIndex = 13;
			this.btnStart.Text = "开始迭代";
			this.btnStart.Click += new System.EventHandler(this.btnStart_Click);
			// 
			// btnClose
			// 
			this.btnClose.Location = new System.Drawing.Point(112, 224);
			this.btnClose.Name = "btnClose";
			this.btnClose.Size = new System.Drawing.Size(72, 32);
			this.btnClose.TabIndex = 14;
			this.btnClose.Text = "退出";
			this.btnClose.Click += new System.EventHandler(this.btnClose_Click);
			// 
			// JSPFrm
			// 
			this.AutoScaleBaseSize = new System.Drawing.Size(6, 14);
			this.ClientSize = new System.Drawing.Size(584, 382);
			this.Controls.Add(this.btnClose);
			this.Controls.Add(this.btnStart);
			this.Controls.Add(this.txtCityNum);
			this.Controls.Add(this.label6);
			this.Controls.Add(this.grp_path);
			this.Controls.Add(this.groupBox2);
			this.Controls.Add(this.groupBox1);
			this.Controls.Add(this.groupBox3);
			this.Name = "JSPFrm";
			this.Text = "遗传算法--旅行商问题";
			this.groupBox1.ResumeLayout(false);
			this.groupBox2.ResumeLayout(false);
			this.grp_path.ResumeLayout(false);
			this.grp_oper.ResumeLayout(false);
			this.ResumeLayout(false);

		}
		#endregion

		[STAThread]
		static void Main() 
		{
			Application.Run(new JSPFrm());
		}

		/// <summary>
		/// 打开文件，文件中含有点的坐标
		/// </summary>
		/// <param name="sender"></param>
		/// <param name="e"></param>
		private void OpenFile(object sender, System.EventArgs e)
		{
			OpenFileDialog openFileDialog = new OpenFileDialog();
			openFileDialog.Filter = "文本文件(*.txt)|*.txt|所有文件(*.*)|*.*";
			openFileDialog.RestoreDirectory = true;
			openFileDialog.FilterIndex = 1;
			StreamReader din;

			string tmpstring = null;
			if (openFileDialog.ShowDialog() == DialogResult.OK)
			{
				string fName = openFileDialog.FileName;
				if(File.Exists(fName))
				{
					try   
					{   
						FileStream fs = new FileStream(fName,FileMode.Open, FileAccess.Read, FileShare.None);  
						din = new StreamReader(fs, System.Text.Encoding.Default);
						tmpstring = din.ReadLine();
						cityNum = int.Parse(tmpstring.Trim());
						ps = new PointF[cityNum];
						xn = new float[cityNum];
						yn = new float[cityNum];
						citySerial = new int[cityNum];
								
						float x1,x2;
						count = 0;
						tmpstring = din.ReadLine();	
						while(tmpstring != null)
						{
							string[] tmpstr = tmpstring.Split(' ');
							citySerial[count] = int.Parse(tmpstr[0].ToString());
							x1 = (float)(double.Parse(tmpstr[1].ToString()));
							xn[count] = x1;
							x2 = (float)(double.Parse(tmpstr[2].ToString()));	
							yn[count] = x2;
							PointF tmppt = new PointF(x1,x2); 
							ps[count] = tmppt;
							count++;
							tmpstring = din.ReadLine();
						}

						this.Invalidate();

						txtCityNum.Text = cityNum.ToString();
						txtStartCity.Focus();
						txt_shortDis.Clear();
						txtShortPath.Clear();
						txt_minPathLocation.Clear();
						txtMaxFit.Clear();
						btnStart.Enabled = true;
						txtStartCity.Text =  Convert.ToString(1);
						txt_pc.Text = Convert.ToString(0.6);
						txt_pm.Text = Convert.ToString(0.1);
						txt_time.Text = Convert.ToString(150);
						isShowResult = false;

						din.Close();   
						fs.Close();   
					}
					catch(Exception ex)
					{
						MessageBox.Show(ex.ToString());
						return;
					} 
				}
				else 
				{
					MessageBox.Show("文件"+fName+"不存在!");
				}
			}
		}

		//  画出路径
		protected override void OnPaint(PaintEventArgs e)
		{
			if(!isFirstEntered)
			{	
				if(!isShowResult)
					this.DrawCity(pnl_result);
				else
					this.shortPath(pnl_result);
			}
			else
			{
				base.OnPaint(e);
				isFirstEntered = false;
			}
		}
			
		//  画出城市图
		private void DrawCity(Panel pnl)   
		{			
			float tmpx = 0F,tmpy = 0F;
			Graphics  g = pnl.CreateGraphics(); 
			SolidBrush sb = new SolidBrush(Color.White); 
			g.FillRectangle(sb,pnl.Left,pnl.Top,pnl.Width,pnl.Height);
			Pen pen = new Pen(Color.Blue); 
			Pen pen1 = new Pen(Color.Red); 
			seekMaxInPanel(pnl,ref tmpx,ref tmpy);

			float x1 = 0.0F;
			float y1 = 0.0F;
			for(int i = 0; i < cityNum; i++)   
			{
				 x1 = pnl.Width - xn[i] * tmpx;
				 y1 = pnl.Height - yn[i] * tmpy;	
				if(i == startCityNum - 1)
				{
					g.DrawEllipse(pen1,x1 - 5,y1 - 5,10,10);
				}
			    g.DrawLine(pen1,x1 - 2,y1,x1 + 2,y1);
				g.DrawLine(pen1,x1,y1 - 2,x1,y1 + 2);
				g.DrawString("" + (i + 1),this.Font,new SolidBrush(Color.Black),x1-5,y1-5);
				
				for(int j = i;j < cityNum; j++)
				{   
					float x2 = pnl.Width - xn[j] * tmpx;
					float y2 = pnl.Height - yn[j] * tmpy;
					g.DrawLine(pen,x1,y1,x2,y2);   
				}   
			}
			pen.Dispose();   
			g.Dispose();   
		}

		/// <summary>
		/// 初始化种群
		/// </summary>
		private void InitPop()
		{
			int i,j;

			generation = 0;
			startCityNum = int.Parse(txtStartCity.Text);
			calDistance();
			pFun = new double[GROUP_NUM * 2];
			pRealFun = new double[GROUP_NUM * 2];

			gene = new int[GROUP_NUM, cityNum];          //初始化染色体
			selectgene = new int[GROUP_NUM * 2, cityNum];
			for(i = 0; i < GROUP_NUM; i++) 
				for(j = 0; j < cityNum; j++)
					gene[i, j] = cityNum;
			
			for(i = 0; i < GROUP_NUM; i++) 
			{
				int n = 0, k;
				while(n < cityNum)
				{
					k = r.Next(cityNum);
					if(gene[i, k] == cityNum)
					{	
						gene[i,k] = n;
						n++;
					}
				}
			}	
		}

		// 变异算子
		private void Mutation()
		{
		    int m,k1,k2,temp;
			for(int i = 0; i < GROUP_NUM; i++)
			{
				double d = r.NextDouble();
				if(d < Pm)
				{
					m = r.Next(GROUP_NUM);
					k1 = r.Next(cityNum);
					k2 = r.Next(cityNum);

					temp = gene[m,k1];
					gene[m,k1] = gene[m,k2];
					gene[m,k2] = temp;
				}
			}
			generation++;
		}

		//  交叉操作
		private void CrossOver()
		{
			int i,j;
			int c1,c2;            // 随机选出两条染色体
			int k1,k2;            //交叉点
			int ctmp1,ctmp2;      //计数器 
			double [] tmp = new double[GROUP_NUM]; 
			int [,] tmpgene = new int[GROUP_NUM * 2,cityNum];
		
			computerRound(tmp);		
			for(i = 0; i < GROUP_NUM; i++)
				for(j = 0; j < cityNum; j++)
					tmpgene[i,j] = 0;

			//  交叉操作的实现
			for(j = 0;j < GROUP_NUM; j++)
			{
				c1 = RoundSelect(tmp);
				c2 = RoundSelect(tmp);
				
				while(c1 == c2)
				{
					 c2 = RoundSelect(tmp);
				}

				ctmp1 = 0;
				ctmp2 = 0;
				k1 = r.Next(cityNum / 2);
				k2 = r.Next(cityNum / 2,cityNum);

				double d = r.NextDouble();
				if(d < Pc)
				{
					int [] itmp1 = new int[cityNum];  //存放交叉后的其中一条染色体
					int [] itmp2 = new int[cityNum];  //存放交叉后的另一条染色体
					changeMethod(itmp1,k1,k2,cityNum,k2,ref ctmp1,c1,c2);	
					changeMethod(itmp2,k1,k2,cityNum,k2,ref ctmp2,c2,c1);
					changeMethod(itmp1,k1,0,k2,k2,ref ctmp1,c1,c2);
					changeMethod(itmp2,k1,0,k2,k2,ref ctmp2,c2,c1);
	
					for(i = 0; i <= k1; i++)
					{
						gene[c1,i] = itmp1[i];
						gene[c2,i] = itmp2[i];
					}
					for(i = k1 + 1; i < k2; i++)
					{
						int temp = gene[c2,i];
						gene[c2,i] = gene[c1,i];
					    gene[c1,i] = temp;
					}
					for(i = cityNum - 1; i >= k2; i--)
					{
						gene[c1,i] = itmp1[i - k2 + k1 + 1];
						gene[c2,i] = itmp2[i - k2 + k1 + 1];
					}
				}
			}
		}

		//  选择算子
		private void SelectParentPop()
		{
			int i,j,k;
			double [] tmp = new double[GROUP_NUM];
			int  [,]  temp = new int[GROUP_NUM * 2,cityNum]; 
 
			computerRound(tmp);
			
			for(i = 0; i <  GROUP_NUM * 2; i++)
			{
				k = RoundSelect(tmp);
				for(j = 0; j < cityNum; j++)
					temp[i,j] = gene[k,j]; 
			}

			for(i = 0; i < GROUP_NUM * 2; i++)
				for(j = 0; j < cityNum; j++)
					selectgene[i,j] = temp[i,j]; 
			sortGene();
		}

		//  迭代求最佳值
		private void Operation(object sender, System.EventArgs e) {
			// 输入值正确
			if (input()) {
				InitPop();
				computebest(ref generation);
				while(generation < genCounter)
				{	
					SelectParentPop();
					CrossOver();
					Mutation();
					computebest(ref generation);
				}
				getResult();
			}
		}

		//  计算城市间的距离
		private void calDistance()
		{
			distance = new double[cityNum,cityNum];
			float [] txn = new float[cityNum];
			float [] tyn = new float[cityNum];
	
			for(int i = 0; i < cityNum; i++)
			{
				txn[i] = ps[i].X;
				tyn[i] = ps[i].Y;
				distance[i, i] = 0.0;
			}

			double x, y, xy;
			for(int i = 0; i < cityNum - 1; i++)
			{
				for(int j = i + 1; j < cityNum; j++)
				{
					x = txn[j] - txn[i];
					y = tyn[j] - tyn[i];
					xy = Math.Sqrt(x * x + y * y);
					distance[i, j] = xy;
					distance[j, i] = xy;  
				}
			}
		}

		// 计算各个染色体的适应度
		private void fitness(int n,int[,] tmpgene)
		{
			double sum;
			int k1,k2;

			for(int i = 0; i < n; i++)
			{
				sum = 0.0;
				for(int j = 0; j < cityNum - 1; j++)