form1.cs.bak

遗传算法求解大学考试时间表问题

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

namespace timetabling
{
	public enum enumarith
	{
		GA,
		SA,
		HY,
	};
	public struct PARAMETER
	{
		public string CourseFile; //课程文件名
		public string RoomFile;  //教室文件名
		public int TimeSolt;   //时间格数
		public int cms;//设置公共科目的最少被选班级数，即选此考试科目多于此数的考试科目为公共科目；
		public int [,] course;//课程和 选此课程的班级
		public int [] room;//各种类型的教室 的 数量
		public int coursenum;//考试科目数
		public int nroom;//所有教室的 容量
		public int[,] D;//D为对称矩阵,元素为即选i科目又选j科目的班级数
		public bool check;//检查硬约束冲突情况
		public int gn;//GA叠代次数		
		public int gpn;//GA种群中的个体个数
		public float gpc;  //GA交叉率
		public float gpm;  //GA变异率		
		public float st;//SA退火温度
		public int sn;//SA叠代次数
		public int sendn;//SA叠代最大收敛次数
		public float sdownt;//SA温度下降速度，t×sdownt
	}	
	public struct best
	{
		public int [] chrom;
		public float fitness;
	}

	public struct exam
	{
		public string time;
		public string room;
		public string banji;
		public string course;
	}
	/// <summary>
	public class Form1 : System.Windows.Forms.Form
	{
		private System.Windows.Forms.MainMenu mainMenu1;
		private System.Windows.Forms.MenuItem menu_parameterset;
		private System.Windows.Forms.MenuItem menu_timetabling;
		private System.Windows.Forms.MenuItem menu_spacetabling;
		private System.Windows.Forms.MenuItem menu_about;
		private System.Windows.Forms.MenuItem menu_exit;
		/// <summary>
		/// 必需的设计器变量。
		/// </summary>
		private System.ComponentModel.Container components = null;
		PARAMETER param=new PARAMETER();		
		enumarith arith=enumarith.GA;
		best b=new best ();
		

		private System.Windows.Forms.MenuItem menuItem1;
		private System.Windows.Forms.MenuItem menuItem2;
		private System.Windows.Forms.MenuItem menuItem3;
		private System.Windows.Forms.MenuItem menuItem4;
		private System.Windows.Forms.MenuItem menuItem5;
		public Random seed=new Random();
		public Random rand=new Random();

		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()
		{
			System.Resources.ResourceManager resources = new System.Resources.ResourceManager(typeof(Form1));
			this.mainMenu1 = new System.Windows.Forms.MainMenu();
			this.menuItem1 = new System.Windows.Forms.MenuItem();
			this.menuItem2 = new System.Windows.Forms.MenuItem();
			this.menuItem3 = new System.Windows.Forms.MenuItem();
			this.menuItem4 = new System.Windows.Forms.MenuItem();
			this.menuItem5 = new System.Windows.Forms.MenuItem();
			this.menu_parameterset = new System.Windows.Forms.MenuItem();
			this.menu_timetabling = new System.Windows.Forms.MenuItem();
			this.menu_spacetabling = new System.Windows.Forms.MenuItem();
			this.menu_about = new System.Windows.Forms.MenuItem();
			this.menu_exit = new System.Windows.Forms.MenuItem();
			// 
			// mainMenu1
			// 
			this.mainMenu1.MenuItems.AddRange(new System.Windows.Forms.MenuItem[] {
																					  this.menuItem1,
																					  this.menuItem5,
																					  this.menu_about,
																					  this.menu_exit});
			// 
			// menuItem1
			// 
			this.menuItem1.Index = 0;
			this.menuItem1.MenuItems.AddRange(new System.Windows.Forms.MenuItem[] {
																					  this.menuItem2,
																					  this.menuItem3,
																					  this.menuItem4});
			this.menuItem1.Text = "算法选择";
			// 
			// menuItem2
			// 
			this.menuItem2.Index = 0;
			this.menuItem2.Text = "遗传算法";
			this.menuItem2.Click += new System.EventHandler(this.menuItem2_Click);
			// 
			// menuItem3
			// 
			this.menuItem3.Index = 1;
			this.menuItem3.Text = "模拟退火";
			this.menuItem3.Click += new System.EventHandler(this.menuItem3_Click);
			// 
			// menuItem4
			// 
			this.menuItem4.Index = 2;
			this.menuItem4.Text = "混合算法";
			this.menuItem4.Click += new System.EventHandler(this.menuItem4_Click);
			// 
			// menuItem5
			// 
			this.menuItem5.Index = 1;
			this.menuItem5.MenuItems.AddRange(new System.Windows.Forms.MenuItem[] {
																					  this.menu_parameterset,
																					  this.menu_timetabling,
																					  this.menu_spacetabling});
			this.menuItem5.Text = "算法运行";
			// 
			// menu_parameterset
			// 
			this.menu_parameterset.Index = 0;
			this.menu_parameterset.Text = "参数设置";
			this.menu_parameterset.Click += new System.EventHandler(this.menu_parameterset_Click);
			// 
			// menu_timetabling
			// 
			this.menu_timetabling.Index = 1;
			this.menu_timetabling.Text = "时间编排";
			this.menu_timetabling.Click += new System.EventHandler(this.menu_timetabling_Click);
			// 
			// menu_spacetabling
			// 
			this.menu_spacetabling.Index = 2;
			this.menu_spacetabling.Text = "教室编排";
			this.menu_spacetabling.Click += new System.EventHandler(this.menu_spacetabling_Click);
			// 
			// menu_about
			// 
			this.menu_about.Index = 2;
			this.menu_about.Text = "关于";
			this.menu_about.Click += new System.EventHandler(this.menu_about_Click);
			// 
			// menu_exit
			// 
			this.menu_exit.Index = 3;
			this.menu_exit.Text = "退出";
			this.menu_exit.Click += new System.EventHandler(this.menu_exit_Click);
			// 
			// Form1
			// 
			this.AutoScaleBaseSize = new System.Drawing.Size(6, 14);
			this.BackColor = System.Drawing.SystemColors.Desktop;
			this.BackgroundImage = ((System.Drawing.Image)(resources.GetObject("$this.BackgroundImage")));
			this.ClientSize = new System.Drawing.Size(472, 345);
			this.MaximizeBox = false;
			this.Menu = this.mainMenu1;
			this.MinimizeBox = false;
			this.Name = "Form1";
			this.Text = "自动生成时间表系统";
			this.Load += new System.EventHandler(this.Form1_Load);

		}
		#endregion

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

		private void Form1_Load(object sender, System.EventArgs e)
		{
		
		}

		private void menu_exit_Click(object sender, System.EventArgs e)
		{
			Application.Exit();
		}

		private void menu_about_Click(object sender, System.EventArgs e)
		{
			about about1=new about();
			about1.ShowDialog(this);
		}


		private void menu_parameterset_Click(object sender, System.EventArgs e)
		{				
			frmparam paramset=new frmparam(param,arith);
			paramset.ShowDialog();
			paramset.GetParamset(out param);
		    b.chrom=new int[param.coursenum];
		}           
			
		
		private void gatimetabling(ref best b)
		{
			int [,] chroms=new int[param.gpn,param.coursenum];
			float[] fitness;
			//开始生成初始群体			
			for(int i=0;i<param.gpn;++i)
			{				
				for(int j=0;j<param.coursenum;j++)
				{
					chroms[i,j]=rand.Next()%param.TimeSolt+1;
				}
			}
			//生成初始群体结束
			fitness=new float[param.gpn];//存放染色体的适应度
			int [] chrom=new int[param.coursenum];//临时存放单个染色体
			int [,] tchroms=new int [param.gpn,param.coursenum];//存放中间过渡染色体群
			string str="";
			b.fitness=100000;
			for(int n=0;n<param.gn;n++)
			{
				///<summary>count fitness
				double avg=0.0;
				for(int i=0;i<param.gpn;i++)
				{
					for(int j=0;j<param.coursenum;j++) chrom[j]=chroms[i,j];
				    fitness[i]=count.cfitness(ref param,chrom);	
					if(b.fitness>fitness[i])
					{
						b.fitness=fitness[i];
				        for(int j=0;j<param.coursenum;j++)
					        b.chrom[j]=chroms[i,j];
					}
					avg+=fitness[i];
				}		

				avg=avg/param.gpn;
				if((n%10)==0)
				   str+=avg.ToString()+"-->";
				///<summary>count fitness
					
				chroms=count.crossover(fitness,chroms,param,seed);
				chroms=count.mutation(chroms,param,seed);				
			}
				
				
			for(int i=0;i<param.gpn;i++)
			{
				for(int j=0;j<param.coursenum;j++) chrom[j]=chroms[i,j];
				fitness[i]=count.cfitness(ref param,chrom);	
				if(b.fitness>fitness[i])
				{
					b.fitness=fitness[i];
					for(int j=0;j<param.coursenum;j++)
						b.chrom[j]=chroms[i,j];
				}	
			}

			MessageBox.Show(str,"avgfitness run");
			view.showchrom(b.chrom);
			b.fitness=(float) count.cfitness(ref param,b.chrom);
			if(param.check==true)
				MessageBox.Show("success, no hard clash"+b.fitness.ToString(),"result");
			else MessageBox.Show("fail,have hard clash"+b.fitness.ToString(),"result");
	
		}
			
		private void satimetabling(ref best b)
		{
			int [] chrom=new int [param.coursenum];
			int [] tchrom=new int [param.coursenum];
					
			int bestn=0;
			double fitness=0.0;
			double tfitness=0.0;
			for(int i=0;i<param.coursenum ;++i)//生成初始解
				chrom[i]=rand.Next(1,param.TimeSolt+1);
			fitness=count.cfitness(ref param,chrom);
			b.fitness=(float)fitness;
			for(int i=0;i<param.coursenum ;++i)//生成初始解
				b.chrom[i]=chrom[i];

			int n=0;
			int endn=0;
			double t=param.st;
			//double tt=param.st/param.sn;
			double e=0.0;
			string str="";
			
			do
			{
				for(int i=0;i<param.coursenum;++i)//产生一个邻域解							
						tchrom[i]=chrom[i];
				tchrom[rand.Next(param.coursenum)]=rand.Next(1,param.TimeSolt+1);
				tfitness=count.cfitness(ref param,tchrom);
				if(tfitness<fitness)
				{
					for(int i=0;i<param.coursenum;++i)
						chrom[i]=tchrom[i];
					fitness=tfitness;
					if(fitness<b.fitness)
					{
						b.fitness=(float)fitness;
						for(int i=0;i<param.coursenum;++i)//产生一个邻域解							
							b.chrom[i]=chrom[i];
						bestn=n;
					}
					t*=param.sdownt;
					++n;
					endn=0;
					if((n%20)==0) str+=fitness.ToString()+"-->>";
				}
				else
				{
					e=1/Math.Pow(Math.E,Math.Abs(tfitness-fitness)/t);
					//e=1/Math.Pow(Math.E,200/(1+t));					
					if(e>rand.NextDouble())
					{
						for(int i=0;i<param.coursenum;++i)
							chrom[i]=tchrom[i];
						fitness=tfitness;
						t*=param.sdownt;
						++n;
						endn=0;
						if((n%20)==0) str+=fitness.ToString()+"-->>";
					}
					else
					{
						++endn;
						if(endn>param.sendn) break;
					}
				}						
			}while(n<param.sn);
		
			MessageBox.Show(n.ToString(),param.sendn.ToString()+"+"+param.sn.ToString());
			MessageBox.Show(str,"the result of sa_timetalbing");
			MessageBox.Show(b.fitness.ToString()+"  n="+bestn.ToString(),"best:");
			view.showchrom(b.chrom);
			b.fitness=count.cfitness(ref param,b.chrom);
			if(param.check==true)
				MessageBox.Show("success, no hard clash"+fitness.ToString(),"result");
			else MessageBox.Show("fail,have hard clash"+fitness.ToString(),"result");			
		}			
			
		private void hytimetabling(ref best b)
		{
			int [,] chroms=new int[param.gpn,param.coursenum];
			float[] fitness;
			b.fitness=100000;
			
			//开始生成初始群体
			
			for(int i=0;i<param.gpn;++i)
			{				
				for(int j=0;j<param.coursenum;j++)
				{
					chroms[i,j]=rand.Next()%param.TimeSolt+1;
				}
			}
			//生成初始群体结束
			fitness=new float[param.gpn];//存放染色体的适应度
			int [] chrom=new int[param.coursenum];//临时存放单个染色体
			int [,] tchroms=new int [param.gpn,param.coursenum];//存放中间过渡染色体群
			string str="";

			///<summary>count fitness
			double avg=0.0;
			for(int i=0;i<param.gpn;i++)
			{
				for(int j=0;j<param.coursenum;j++) chrom[j]=chroms[i,j];
				fitness[i]=count.cfitness(ref param,chrom);	
				
				if(b.fitness>fitness[i])
				{
					b.fitness=fitness[i];
					for(int j=0;j<param.coursenum;j++)
						b.chrom[j]=chroms[i,j];
				}	
				
				avg+=fitness[i];
			}
			avg=avg/param.gpn;
			str+=avg.ToString()+"-->";
			///<summary>count fitness
			///
			for(int n=0;n<param.gn;n++)
			{
				chroms=count.crossover(fitness,chroms,param,seed);
				chroms=count.mutation(chroms,param,seed);
				//开始模拟退火；