form1.cs

模拟退火和遗传算法混和求解车辆路径问题的程序

using System;
using System.Drawing;
using System.Collections;
using System.ComponentModel;
using System.Windows.Forms;
using System.Data;

namespace WindowsApplication24zhang
{
	/// <summary>
	/// Form1 的摘要说明。
	/// </summary>
	public class Form1 : System.Windows.Forms.Form
	{
		private System.Windows.Forms.Button button1;
		private System.Windows.Forms.TextBox outputTextBox;
		/// <summary>
		/// 必需的设计器变量。
		/// </summary>
		private System.ComponentModel.Container components = null;

		public Form1()
		{
			//
			// Windows 窗体设计器支持所必需的
			//
			InitializeComponent();

			//
			// TODO: 在 InitializeComponent 调用后添加任何构造函数代码
			//
		}

		/// <summary>
		/// 清理所有正在使用的资源。
		/// </summary>
		protected override void Dispose( bool disposing )
		{
			if( disposing )
			{
				if (components != null) 
				{
					components.Dispose();
				}
			}
			base.Dispose( disposing );
		}

		#region Windows 窗体设计器生成的代码
		/// <summary>
		/// 设计器支持所需的方法 - 不要使用代码编辑器修改
		/// 此方法的内容。
		/// </summary>
		private void InitializeComponent()
		{
			this.button1 = new System.Windows.Forms.Button();
			this.outputTextBox = new System.Windows.Forms.TextBox();
			this.SuspendLayout();
			// 
			// button1
			// 
			this.button1.Location = new System.Drawing.Point(272, 32);
			this.button1.Name = "button1";
			this.button1.Size = new System.Drawing.Size(112, 32);
			this.button1.TabIndex = 0;
			this.button1.Text = "display";
			this.button1.Click += new System.EventHandler(this.button1_Click);
			// 
			// outputTextBox
			// 
			this.outputTextBox.Location = new System.Drawing.Point(216, 96);
			this.outputTextBox.Multiline = true;
			this.outputTextBox.Name = "outputTextBox";
			this.outputTextBox.ScrollBars = System.Windows.Forms.ScrollBars.Both;
			this.outputTextBox.Size = new System.Drawing.Size(264, 200);
			this.outputTextBox.TabIndex = 1;
			this.outputTextBox.Text = "";
			// 
			// Form1
			// 
			this.AutoScaleBaseSize = new System.Drawing.Size(6, 14);
			this.ClientSize = new System.Drawing.Size(680, 342);
			this.Controls.Add(this.outputTextBox);
			this.Controls.Add(this.button1);
			this.Name = "Form1";
			this.Text = "Form1";
			this.ResumeLayout(false);

		}
		#endregion

		/// <summary>
		/// 应用程序的主入口点。
		/// </summary>
		[STAThread]
		static void Main() 
		{
			Application.Run(new Form1());
		}

		public class pp                            //此程序是2002年6月的计算机集成制造系统的程序的改进
		{
			public int cityNum=30;//原始的城市数
			public int cNumber=31;//插入站点后的城市数
			public int vehicleNumber=10;
			public int vehicleCapacity=20;// 车的容量
			public int maxTime=200;//maximize iteration;
			public int popSize=80;//maximize population
			public int jrand;//creative randomnumber
			public int bestChroms;
			public double pCross=0.8;// probability of chrom crossover
			public double pMutation=0.03;// probability of chrom mutation
			public double[] oldrand=new double[100];
		}
		pp initPop=new pp();
		private void InitCity(pp initPop,ref int[,] chroms,Random seed)
		{
			int i,j;
			int number;
			Random rand=new Random(seed.Next());
			for(i=0;i<chroms.GetLength(0);i++)
			{
				for(j=0;j<chroms.GetLength(1);j+=3)
				{
					number=rand.Next(3);
					if(number==0)
					{
						chroms[i,j]=1;
						chroms[i,j+1]=0;
						chroms[i,j+2]=0;
					}
					if(number==1)
					{
						chroms[i,j]=0;
						chroms[i,j+1]=1;
						chroms[i,j+2]=0;
					}
					if(number==2)
					{
						chroms[i,j]=0;
						chroms[i,j+1]=0;
						chroms[i,j+2]=1;
					}
				}
			}
		}
		pp distancePop=new pp();
		private void cityDistance(pp distancePop,ref int[,] distance)
		{
			int[,] initDistance={{0,8,17},{0,4,8},{0,5,10},{0,12,23},{0,7,14},{0,6,13},{0,5,10},{0,6,12},{0,7,14},{0,3,6}};
			for(int i=0;i<distance.GetLength(0);i++)
			{
				for(int j=0;j<distance.GetLength(1);j++)
				{
					distance[i,j]=initDistance[i,j];
				}
			}
		}

		pp fitnessPop=new pp();
		private void chromsFitness(pp fitnessPop,int[,] chroms,int[,] distance,ref double[] cost,ref double[] fitness)
		{

			for(int i=0;i<chroms.GetLength(0);i++)
			{
				double totalCost=0.0;
				int t=0;
				for(int j=0;j<chroms.GetLength(1);j+=3)
				{
					t=j/3;
					if(j==0)
					{
						if(chroms[i,j]==1)
						{
							totalCost+=distance[t,2];
						}
						if(chroms[i,j+1]==1)
						{
							totalCost+=distance[t,1];
						}
						if(chroms[i,j+2]==1)
						{
							totalCost+=distance[t,0];
						}
					}
					else
					{
						if(chroms[i,j]==1)
						{
							totalCost+=(distance[t,2]+distance[t-1,2]*chroms[i,j-3]+distance[t-1,1]*chroms[i,j-2]);
						}
						if(chroms[i,j+1]==1)
						{
							totalCost+=(distance[t,1]+distance[t-1,2]*chroms[i,j-3]+distance[t-1,1]*chroms[i,j-2]);
						}
						if(chroms[i,j+2]==1)
						{
							totalCost+=(distance[t,0]+distance[t-1,2]*chroms[i,j-3]+distance[t-1,1]*chroms[i,j-2]);
						}
					}
				}
				cost[i]=totalCost;
				fitness[i]=1.0/cost[i];
			}
		}

		pp testrand1=new pp();
		void randomize1(ref pp testrand1,int seed)
		{
			int i;
			Random randomNumber=new Random(seed);
			for(i=0;i<testrand1.popSize;i++)
			{
				testrand1.oldrand [i]=randomNumber.NextDouble();
			}
			testrand1.jrand=0;
		}

		pp testrand2=new pp();
		double random1(ref pp testrand2,int seed)
		{
			if(testrand2.jrand>=testrand2.popSize)
			{
				testrand2.jrand=0;
				randomize1(ref testrand2,seed);
			}
			return testrand2.oldrand[testrand2.jrand++];
		}
		pp selectPop=new pp();
		public int chromsSelect(pp selectPop,double[] fitness,int seed)//染色体的选择操作
		{
			int i;
			double sumfitness;
			double maxmizeFitness;
			sumfitness=fitness[0];
			maxmizeFitness=fitness[0];
			for(i=1;i<fitness.Length;i++)
			{
				if(fitness[i]-maxmizeFitness>1e-6)
					selectPop.bestChroms=i;
				sumfitness+=fitness[i];
			}
				
			double rand1,partsum=0.0;
			int j=0;

			randomize1(ref selectPop,seed);
			rand1=random1(ref selectPop,seed)*sumfitness;
			do
			{
				partsum=partsum+fitness[j];
				j=j+1;
			}while((partsum-rand1<1e-6)&&(j<selectPop.popSize));
			return j-1;
		}
		//染色体的交叉
		pp popCross=new pp();
		private void chromsCross(double[] fitness, pp popCross,ref int[,] chroms,Random seed)
		{
			int i,j;
			int t1,t2;
			
			Random rand=new Random(seed.Next());
			for(i=0;i<chroms.GetLength(0);i+=2)
			{
				if(i==0)
				{
					t1=chromsSelect(popCross,fitness,seed.Next());
					t2=popCross.bestChroms;
				}
				else
				{
					t1=chromsSelect(popCross,fitness,seed.Next());
					t2=chromsSelect(popCross,fitness,seed.Next());
				}
				double rpc;
				rpc=rand.NextDouble();
				if(rpc<=popCross.pCross)
				{
					int[] temp1=new int[popCross.cityNum];
					int[] temp2=new int[popCross.cityNum];
					int cross1,cross2;
					for(j=0;j<chroms.GetLength(1);j++)
					{
						temp1[j]=chroms[t1,j];
						temp2[j]=chroms[t2,j];
					}
					int crossnumber=rand.Next(9);
                    cross1=crossnumber*3;
					cross2=rand.Next(crossnumber+1,10)*3;
					for( j=cross1;j<cross2;j++)
					{
						chroms[t1,j]=temp2[j];
						chroms[t2,j]=temp1[j];
					}
				}
			}
		}
		pp popMutation=new pp();
		private void chromsMutation(pp popMutation,ref int[,] chroms,Random seed)
		{
			int i;
			int m1;
			int[] temp=new int[popMutation.cityNum];
			Random rand =new Random(seed.Next());
			for(i=0;i<chroms.GetLength(0);i++)
			{
				if(rand.NextDouble()<=popMutation.pMutation)
				{
					m1=rand.Next(9)*3;
					if(chroms[i,m1]==1)
					{
						chroms[i,m1+2]=1;
						chroms[i,m1]=0;
					}
					if(chroms[i,m1+1]==1)
					{
						chroms[i,m1+2]=1;
						chroms[i,m1+1]=0;
					}	
				}
			}
		}
		private void chromsGeneration()
		{
			pp chromsPopulation=new pp();
			Random seed=new Random();
			int[,] chroms=new int[chromsPopulation.popSize,chromsPopulation.cityNum];
			InitCity(chromsPopulation,ref chroms,seed);
//			for(int i=0;i<chroms.GetLength(0);i++)
//			{
//				for(int j=0;j<chroms.GetLength(1);j++)
//				{
//					if(j%3==0)
//					{
//						outputTextBox.Text+="/";
//					}
//					outputTextBox.Text+=chroms[i,j];
//				}
//               outputTextBox.Text+="*********************************************";
//			}

			int[,] distance=new int[10,3];
			cityDistance(chromsPopulation,ref distance);

			double[] fitness=new double[chromsPopulation.popSize];
			double[] cost=new double[chromsPopulation.popSize];
			chromsFitness(chromsPopulation,chroms,distance,ref cost,ref fitness);
			chromsCross(fitness,chromsPopulation,ref chroms,seed);
			chromsMutation(chromsPopulation,ref chroms,seed);
			chromsFitness(chromsPopulation,chroms,distance,ref cost,ref fitness);

			int best=0;
			int bestGeneration=0;
			double bestSolution=cost[0];
			int[] bestChroms=new int[chromsPopulation.cityNum];

			for(int i=0;i<cost.Length;i++)
			{
				if(cost[i]-bestSolution<1e-6)
				{
					bestSolution=cost[i];
					best=i;
				}
			}
			for(int j=0;j<bestChroms.Length;j++)
			{
				bestChroms[j]=chroms[best,j];
			}
		
			int times;
			times=0;
			while(times<chromsPopulation.maxTime)
			{
				chromsCross(fitness,chromsPopulation,ref chroms,seed);
				chromsMutation(chromsPopulation,ref chroms,seed);
				chromsFitness(chromsPopulation,chroms,distance,ref cost,ref fitness);
				bool repeat=false;
				for(int i=0;i<cost.Length;i++)
				{
					if(cost[i]-bestSolution<1e-6)
					{
						bestSolution=cost[i];
						best=i;
						repeat=true;
					}
				}
				if(repeat==true)
				{
					for(int j=0;j<bestChroms.Length;j++)
					{
						bestChroms[j]=chroms[best,j];
					}
					bestGeneration=times;
				}
				times++;
			}
			outputTextBox.Text+="\n"+"bestSolution="+bestSolution+" ";
			outputTextBox.Text+="*********************************************";
			for(int i=0;i<bestChroms.Length;i++)
			{
				if(i%3==0)
				{
					outputTextBox.Text+="/";
				}
				outputTextBox.Text+=bestChroms[i]+" ";
			}
			outputTextBox.Text+="*********************************************";
			outputTextBox.Text+="bestGeneration="+bestGeneration+" ";
		}
		private void button1_Click(object sender, System.EventArgs e)
		{
			outputTextBox.Text="";
			System.DateTime d = System.DateTime.Now;
			chromsGeneration();
			outputTextBox.Text+=System.DateTime.Now.Subtract(d)+" ";
		}
	}
}