form1.cs

遗传算法实现TSP算法

				{
					k1 = tmpgene[i,j];
					k2 = tmpgene[i,j + 1];
					sum += distance[k1,k2];
				}
				k1 = tmpgene[i,0];
				k2 = tmpgene[i,cityNum - 1];
				sum += distance[k1,k2];
				pFun[i] = sum;
				pRealFun[i] = 1 / sum;
			}
		}

		// 计算各个染色体在圆盘中的比例
		private void computerRound(double [] tmp)
		{
			double sum = 0.0;

			fitness(GROUP_NUM,gene);
			for(int i = 0; i < GROUP_NUM; i++)
			{
				sum += pRealFun[i];
			}

			for(int i = 0; i < GROUP_NUM; i++)
			{
				tmp[i] = 0.0;
			}
            
			double t = 0.0;
			for(int i = 0; i < GROUP_NUM; i++)
			{
				double temp = pRealFun[i] / sum;
				tmp[i] = t + temp;
				t += temp;
			}
		}
    
		// 在圆盘中选择合适的染色体  
		private int RoundSelect(double [] tmp)
		{
			int i;

			double db = r.NextDouble();
			for(i = 0; i < GROUP_NUM - 1; i++)
				if(tmp[i + 1] > db)
					break;
			return i;			
		}
 
		// 交叉算子的实现
		private void changeMethod(int [] tmp,int n1,int n2,int n3,int n4,ref int counter,int c1,int c2)
		{
			bool flag;
			for(int i = n2; i < n3; i++)
			{
				flag = false;
				for(int j = n1 + 1; j < n4; j++)
				{
					if(gene[c1,i] == gene[c2,j])
					{
						flag = true;
						break;
					}
				}
				if(!flag)
				{
					tmp[counter] = gene[c1,i];
					counter++;
				}
			}

		}

		//  输入迭代所需数据
		private bool input()
		{
			bool result = true;

			if((txt_time.Text.Trim() == "")||(txt_pc.Text.Trim() == "")||(txt_pm.Text.Trim() == ""))
			{
				MessageBox.Show("你需要输入迭代所需要的全部数据!");
				result = false;
			}
			else 
			{			
				startTime = DateTime.Now;
				generation = 0;
				genCounter = int.Parse(txt_time.Text);               //迭代次数
				minDis = new double[genCounter + 1];                   //最小路径
				genvalue = new int[genCounter + 1,cityNum];            //每一代的最佳路径 
				Pc = double.Parse(txt_pc.Text);                        //交叉概率        
				Pm = double.Parse(txt_pm.Text);                        //变异概率
			}

			return result;
		}

		//  输出结果
		private void getResult()
		{
			string str1 = "",str2 = "";
			double tmpMin = 0.0;
            resultProcess(ref tmpMin,ref str1,ref str2);
			
			shortPath(pnl_result);
			txt_shortDis.Text = tmpMin.ToString();
			txt_minPathLocation.Text = str1;
			txtShortPath.Text = str2;
			bestValue = tmpMin;
			double tmpFit = 1 / minDis[bestGene];
			txtMaxFit.Text = tmpFit.ToString();
		}

		//  计算每一代最优值
		private void computebest(ref int n)
		{		
			int k = 0;
			double tmpbest = 0.0;
			fitness(GROUP_NUM,gene);
			
			for(int i = 0; i < GROUP_NUM; i++)
			{
				if(tmpbest < pRealFun[i])
				{
					tmpbest = pRealFun[i];
					k = i;
				}
			}
            
			minDis[n] = pFun[k];
			string str = "";
			for(int i = 0; i < cityNum;  i++)
			{
				genvalue[n,i] = gene[k,i];
				str += gene[k,i].ToString()+"\n";
			}
		}

		// 初始化菜单
		private void initMenu()
		{
			MainMenu mainMenu = new MainMenu();
            
			Menu = mainMenu;
			MenuItem miFile = mainMenu.MenuItems.Add("文件(&F)");
			MenuItem miOpen = new MenuItem("打开(&O)", new EventHandler(this.MenuCommand), Shortcut.CtrlO);
			MenuItem miExit = new MenuItem("退出(&X)", new EventHandler(this.MenuCommand), Shortcut.CtrlX);
			miFile.MenuItems.Add(miOpen);
			miFile.MenuItems.Add("-");
			miFile.MenuItems.Add(miExit);
           
			MenuItem miIteration = new MenuItem("开始迭代(&P)",new EventHandler(this.MenuCommand));
            mainMenu.MenuItems.Add(miIteration);

			MenuItem miAbout = new MenuItem("关于",new EventHandler(this.MenuCommand));
			mainMenu.MenuItems.Add(miAbout);
		}

		//  菜单命令
		public void MenuCommand(object sender,System.EventArgs e)
		{
			MenuItem miClicked = (MenuItem)sender;

			string MenuItemText = miClicked.Text;

			if(MenuItemText == "退出(&X)")
			{
				Close();
			}
			else if(MenuItemText == "打开(&O)")
			{
				OpenFile(sender,e);
			}
			else if(MenuItemText == "开始迭代(&P)")
			{
				Operation(sender,e);
			}
			else if(MenuItemText == "关于")
			{
				string tmpstr;
				tmpstr = "\n  华南理工大学计算机科学与工程学院\t\n\n";
				tmpstr += "\t  计算机应用技术\n";
				tmpstr += "\n\t   作者:王立平\n";
				tmpstr += "\n\t   1.0 version";
				MessageBox.Show(tmpstr,"关于");
				Invalidate();
			}
		}
		
		//  按钮开始迭代触发的事件
		private void btnStart_Click(object sender, System.EventArgs e)
		{
			Operation(sender,e);
		}
		
		//  最短路径图
		private void shortPath(Panel pnl)
		{
			float tmpx = 0F,tmpy = 0F;
			int xytmp = 0;

			Graphics  g = pnl.CreateGraphics(); 
			SolidBrush sb = new SolidBrush(Color.White); 
			g.FillRectangle(sb,pnl.Left,pnl.Top,pnl.Width,pnl.Height);
			g.SmoothingMode=SmoothingMode.HighQuality;   
			Pen pen = new Pen(Color.Purple,1F); 	
			pen.StartCap = LineCap.Flat; 
			pen.EndCap = LineCap.ArrowAnchor;    
			
			seekMaxInPanel(pnl,ref tmpx,ref tmpy);
			
			int w = pnl.Width;
			int h = pnl.Height;
			xytmp = genvalue[bestGene,startInGene];
			float x1 = w - (float)xn[xytmp] * tmpx;
			float y1 = h - (float)yn[xytmp] * tmpy;
			float x2, y2;
			g.FillEllipse((new SolidBrush(Color.Red)), x1 - 10, y1 - 10, 20, 20);
			for(int i = startInGene + 1;i < cityNum; i++)
			{
				xytmp = genvalue[bestGene, i];
				x2 = w - (float)xn[xytmp] * tmpx;
				y2 = h - (float)yn[xytmp] * tmpy;
				g.DrawLine(pen,x1,y1,x2,y2);
				x1 = x2;
				y1 = y2;
			}
			for(int j = 0; j<= startInGene; j++)
			{
				xytmp = genvalue[bestGene,j];
				x2 = w - (float)xn[xytmp] * tmpx;
				y2 = h - (float)yn[xytmp] * tmpy;
				g.DrawLine(pen,x1,y1,x2,y2);
				x1 = x2;
				y1 = y2;
			}
			
			for(int i = 0; i < cityNum; i++)
			{
				x1 = w - xn[i] * tmpx;
				y1 = h - yn[i] * tmpy;
				g.DrawString(""+ (i + 1), this.Font, new SolidBrush(Color.Black), x1 - 5, y1 - 5);
			}

			pen.Dispose();   
			g.Dispose();  
		}

		//  求面板上的最大值
		private void seekMaxInPanel(Panel pnl,ref float tmpx,ref float tmpy)
		{
			float xtmpmax = 0;
			float ytmpmax = 0;
			for(int i = 0; i < cityNum; i++)
			{
				if(xtmpmax < xn[i])
				{
					xtmpmax = xn[i];
				}
				if(ytmpmax < yn[i])
				{
					ytmpmax = yn[i];
				}
			}
			tmpx  = (float)pnl.Width * 5 / 6 / xtmpmax;
			tmpy  = (float)pnl.Height * 5 / 6 / ytmpmax;
		}

		//  求初始染色体
		private void sortGene()
		{
			double temp = 0.0;
			double [] tmpFun = new double[GROUP_NUM * 2];

			fitness(GROUP_NUM * 2, selectgene);
			for(int i = 0; i < GROUP_NUM * 2; i++)
			{
				tmpFun[i] = pRealFun[i];
			}

			for(int i = 1; i < 2 * GROUP_NUM; i++)
				for(int j = 0; j < 2 * GROUP_NUM - i; j++)
					if(tmpFun[j] < tmpFun[j + 1])
					{
						temp = tmpFun[j];
						tmpFun[j] = tmpFun[j + 1];
						tmpFun[j + 1] = temp;
					}

			for(int i = 0; i < GROUP_NUM; i++)
			{
				int kk;
				for(kk = 0; kk < GROUP_NUM * 2; kk++)
					if(tmpFun[i] == pRealFun[kk])
						break;
				for(int j = 0; j < cityNum; j++)
				{	
					gene[i,j] = selectgene[kk,j];    
				}
			}
		}
		
		//  结果显示前的处理
		private void resultProcess(ref double tmpMin,ref string str1,ref string str2)
		{		
			tmpMin = double.MaxValue;
			int [] tmpbest = new int[cityNum];
			
			for(int i = 0; i < genCounter; i++)
			{
				if(tmpMin > minDis[i])
				{
					tmpMin = minDis[i];
					bestGene = i;
				}
			}

			for(int i = 0; i < cityNum; i++)
			{
				tmpbest[i] = genvalue[bestGene,i] + 1;
				if(genvalue[bestGene,i] == startCityNum - 1)
				{
					startInGene = i;
				}
			}
			
			float  xStart = xn[genvalue[bestGene,startInGene]];
			float  yStart = yn[genvalue[bestGene,startInGene]];
			float  xx = xStart;
			float  yy = yStart;
			int  kk;
			str1 = "("+ xx + ","+ yy + ")";
			str2 = "" + startCityNum;
			for(int j = startInGene + 1; j < cityNum; j++)
			{
				kk = genvalue[bestGene,j];
				xx = xn[kk];
				yy = yn[kk];
				str1 += "->("+ xx + "," + yy + ")";
				str2 += "->" + (kk + 1);
			}
			for(int j = 0; j<= startInGene; j++)
			{
				kk = genvalue[bestGene,j];
				xx = xn[genvalue[bestGene,j]];
				yy = yn[genvalue[bestGene,j]];
				str1 += "->("+ xx + ","+ yy + ")";
				str2 += "->" + (kk + 1);
			}

			endTime =  DateTime.Now;
			TimeSpan  ts = endTime - startTime;   
			int second = ts.Milliseconds;
			string str = "";
			str += "在第" + bestGene + "代时找到了最优解!\n";
			str += "一共消耗了"+ second.ToString() + "毫秒";
			MessageBox.Show(str);
		}

		//  关闭窗体
		private void btnClose_Click(object sender, System.EventArgs e)
		{
			Close();
		}
	}
}