form1.cs

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

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();
		private System.Windows.Forms.MenuItem menuItem6;
		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();
			this.menuItem6 = 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,
																					  this.menuItem6});
			// 
			// 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);
			// 
			// menuItem6
			// 
			this.menuItem6.Index = 4;
			this.menuItem6.Text = "时间编排";
			this.menuItem6.Click += new System.EventHandler(this.menuItem6_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=new float[param.gpn];//存放染色体的适应度;
			//开始生成初始群体			
			for(int i=0;i<param.gpn;++i)
			{				
				for(int j=0;j<param.coursenum;j++)
				{
					chroms[i,j]=rand.Next()%param.TimeSolt+1;
				}
			}
			//生成初始群体结束		
			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++)
				{
					fitness[i]=count.cfitness(ref param,chroms,i);	
					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+=n.ToString()+"@"+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++)
			{				
				fitness[i]=count.cfitness(ref param,chroms,i);	
				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
			{
				int intern=0;
				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;
						}
					}
					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;							
						}
					}
					++intern;
				}while(intern<endn);
				t*=param.sdownt;
				++n;					
				if((n%50)==0) str+=fitness.ToString()+"-->>";
				if((n%100)==0)	str+="#"+n.ToString()+"@";						
			}while(n<param.sn);
		
			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=new float[param.gpn];//存放染色体的适应度;
			b.fitness=100000;
			double t=param.st;	//考虑param.st可不可以换成avg
			//开始生成初始群体			
			for(int i=0;i<param.gpn;++i)
			{				
				for(int j=0;j<param.coursenum;j++)
				{
					chroms[i,j]=rand.Next()%param.TimeSolt+1;
				}
			}
			//生成初始群体结束
			string str="";
			///<summary>count fitness
			double avg=0.0;
			for(int i=0;i<param.gpn;i++)
			{				
				fitness[i]=count.cfitness(ref param,chroms,i);					
				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);
				//开始模拟退火；
				int [] stchrom=new int [param.coursenum];					
				float sfitness=0.0f;	//当前解适应度；				
				float stfitness=0.0f;   //邻域解适应度；
				best sb=new best();    //邻域搜索邻域最优解保存；
				sb.chrom=new int[param.coursenum];			
				double e=0.0;
				for(int p=0;p<param.gpn;++p)
				{
					sfitness=count.cfitness(ref param,chroms,p);
					sb.fitness =sfitness;
					for(int i=0;i<param.coursenum ;++i)//记录局部最优
						sb.chrom[i]=chroms[p,i];					
					int sn=0;//模拟退火内叠代次数记数器
					do
					{
						int a1=rand.Next(param.coursenum);
						int a2=rand.Next(1,param.TimeSolt+1);
						int a3=chroms[p,a1];
						chroms[p,a1]=a2;
						stfitness=count.cfitness(ref param,chroms,p);
						if(stfitness<sfitness)
						{
							sfitness=stfitness;
							//fitness[p]=stfitness;
							if(sb.fitness>sfitness)
							{
								sb.fitness=sfitness;
								for(int j=0;j<param.coursenum;j++)
									sb.chrom[j]=chroms[p,j];
							}
						}
						else
						{
						   	e=1/Math.Pow(Math.E,Math.Abs(stfitness-sfitness)/t);