form1.cs.bak

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

				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)
				{
					for(int i=0;i<param.coursenum ;++i)//生成初始解
						chrom[i]=chroms[p,i];
					sfitness=count.cfitness(ref param,chrom);
					sb.fitness =sfitness;
					for(int i=0;i<param.coursenum ;++i)//记录局部最优
						sb.chrom[i]=chrom[i];
					
					if(b.fitness>sfitness)//记录全局最优
					{
						b.fitness=sfitness;
						for(int j=0;j<param.coursenum;j++)
							b.chrom[j]=chrom[j];
					}
					
					int sn=0;//模拟退火叠代次数记数器
					int endn=0;
			    	double t=param.st;	//考虑param.st可不可以换成avg
					//double t=avg;
				
					//string str="";			
					do
					{
						for(int i=0;i<param.coursenum;++i)//产生一个邻域解							
							stchrom[i]=chrom[i];
						stchrom[rand.Next(param.coursenum)]=rand.Next(1,param.TimeSolt+1);
						stfitness=count.cfitness(ref param,stchrom);
						if(stfitness<sfitness)
						{
							for(int i=0;i<param.coursenum;++i)
								chrom[i]=stchrom[i];
							sfitness=stfitness;
							//fitness[p]=stfitness;
							t*=param.sdownt;
							++sn;
							endn=0;

							if(sb.fitness>sfitness)
							{
								sb.fitness=sfitness;
								for(int j=0;j<param.coursenum;j++)
									sb.chrom[j]=chrom[j];
							}
							
							if(b.fitness>sfitness)
							{
								b.fitness=sfitness;
								for(int j=0;j<param.coursenum;j++)
									b.chrom[j]=chrom[j];
							}
						}
						else
						{
						   	e=1/Math.Pow(Math.E,Math.Abs(stfitness-sfitness)/t);
							//e=1/Math.Pow(Math.E,200/(1+t));					
							if(e>rand.NextDouble())
							{
								for(int i=0;i<param.coursenum;++i)
									chrom[i]=stchrom[i];
								//fitness[p]=stfitness;
								sfitness=stfitness;
								t*=param.sdownt;
								++sn;
								endn=0;
							}
							else
							   ++endn;	
						}
						if(endn>param.sendn) break;						
					}while(sn<param.sn);
					for(int i=0;i<param.coursenum ;++i)//写回遗传算法群 
						chroms[p,i]=sb.chrom[i];
					fitness[p]=sb.fitness;
				}
				avg=0.0;
				for(int i=0;i<param.gpn;++i)
					avg+=fitness[i];
				avg/=param.gpn;
				str+=avg.ToString()+"-->";				
			}
			int ttt=0;
			for(int i=1;i<param.gpn;i++)
			{if(fitness[ttt]>fitness[i])ttt=i;}
			for(int i=0;i<param.coursenum;i++) chrom[i]=chroms[ttt,i];
			fitness[ttt]=count.cfitness(ref param,chrom);
			view.showchrom(chroms,ttt,param.coursenum);

			MessageBox.Show(str,"avgfitness run");
			if(param.check==true)
				MessageBox.Show("success, no hard clash"+fitness[ttt].ToString(),"result");
			else MessageBox.Show("fail,have hard clash"+fitness[ttt].ToString(),"result");	
}
		
		
		private void menu_timetabling_Click(object sender, System.EventArgs e)
		{
			
			switch(arith)
			{
				case enumarith.GA:
					gatimetabling(ref b);		
					break;
				case enumarith.SA:
					satimetabling(ref b);
					break;
				case enumarith.HY:
					hytimetabling(ref b);
					break;
			}
		}

		private void menuItem2_Click(object sender, System.EventArgs e)
		{
			this.Text="自动生成时间表系统---遗传算法";
			arith=enumarith.GA;
		}
		private void menuItem4_Click(object sender, System.EventArgs e)
		{
			this.Text="自动生成时间表系统---混合遗传算法";
			arith=enumarith.HY;		
		}
		private void menuItem3_Click(object sender, System.EventArgs e)
		{
			this.Text="自动生成时间表系统---模拟退火算法";
			arith=enumarith.SA;
		}

		private void menu_spacetabling_Click(object sender, System.EventArgs e)
		{
			if(param.check==false) 
				MessageBox.Show("There have clash,pls schedule the time","notice!");
			else
			{
				
				exam [][]result=new exam[param.coursenum][];
				for(int i=0;i<param.coursenum;++i)
					result[i]=new exam[param.D[i,i]];

				for(int i=0;i<param.coursenum;++i)
				{
					int a=i+1;
					for(int j=0;j<param.D[i,i];++j)
					{					
						result[i][j].course="考试科目"+a.ToString();
						result[i][j].time="时间"+b.chrom[i].ToString();
						result[i][j].banji="班级"+param.course[i,j+1].ToString();
					}
				}
				

				for(int t=1;t<=param.TimeSolt;++t)
				{
					int e1;
					e1=0;
					for(;e1<param.coursenum;++e1)
						if(b.chrom[e1]==t) break;
					if(e1==param.coursenum) continue;
					int e2;
					e2=0;
					
					for(int i=0;i<param.room[2];++i)
					{
						for(int j=0;j<4;++j)
						{
							result[e1][e2].room="C0"+i.ToString();
							e2++;
							if(e2==param.D[e1,e1])//如果这一考试科目已排满，则排下一在此时间考试的科目
							{
								e2=0;
								for(++e1;e1<param.coursenum;++e1)
									if(b.chrom[e1]==t) break;								
							}
							if(e1==param.coursenum) break;
						}
						if(e1==param.coursenum) break;
					}
					if(e1==param.coursenum) continue;
					
					for(int i=0;i<param.room[1];++i)
					{
						for(int j=0;j<2;++j)
						{
							result[e1][e2].room="B0"+i.ToString();
							e2++;
							if(e2==param.D[e1,e1])//如果这一考试科目已排满，则排下一在此时间考试的科目
							{
								e2=0;
								for(++e1;e1<param.coursenum;++e1)
									if(b.chrom[e1]==t) break;								
							}
							if(e1==param.coursenum) break;
						}
						if(e1==param.coursenum) break;
					}
					if(e1==param.coursenum) continue;
					
					for(int i=0;i<param.room[0];++i)
					{
							result[e1][e2].room="A0"+i.ToString();
							e2++;
							if(e2==param.D[e1,e1])//如果这一考试科目已排满，则排下一在此时间考试的科目
							{
								e2=0;
								for(++e1;e1<param.coursenum;++e1)
									if(b.chrom[e1]==t) break;								
							}
						if(e1==param.coursenum) break;
					}					
				}

				FileStream strm;
				try//保存编排结果
				{
					strm=new FileStream("result.txt",FileMode.OpenOrCreate,FileAccess.Write);
					strm.SetLength(0);	
					StreamWriter sr=new StreamWriter (strm);
					string str=param.coursenum.ToString();
					sr.WriteLine(str);
					for(int i=0;i<param.coursenum;++i)
					{
						sr.WriteLine(param.D[i,i]);
						foreach(exam res in result[i])
						{
							str=res.time+"\r\n"+res.room+"\r\n"+res.banji+"\r\n"+res.course;
							sr.WriteLine(str);
						}
					}					
					sr.WriteLine("end");
				
					sr.Flush();
					//MessageBox.Show("create about file have finished!","congradulation");
					strm.Flush();
					strm.Close();					   			  
				}
				catch(Exception ee)
				{
					MessageBox.Show(ee.Message,"erro");
					MessageBox.Show("不能打开文件，请重新设置参数","erro");

				}

			}
		}
	}

	public  class view
	{
		public static void showchrom(int [] chrom)
		{
			string str="";
			foreach(int t in chrom)
			{
				str+=t.ToString()+"  ";
			}
			MessageBox.Show(str,"showchrom");
		}
		public static void showchrom(int [,]chroms, int j,int t)//j表示第几行，t表示有多少列；
		{
			string str="";
			for(int i=0;i<t;i++)
			{
				str+=chroms[j,i].ToString()+"  ";
			}
			MessageBox.Show(str,"showchrom");
		}
		public static void showfitness(float [] fitness)
		{
			string str="";
			int i=1;
			foreach(float t in fitness)
			{
				str+="//"+i.ToString()+":"+t.ToString()+" ";
				++i;
			}
			MessageBox.Show(str,"showfitness");

		}
		public static void showavgfitness(float [] fitness)
		{
			string str="";			
			int i=1;
			double avg=0.0;
			foreach(float t in fitness)
			{
				avg+=t;
				++i;
			}
			avg=avg/i;
			str+="avgfitness="+avg.ToString();
			MessageBox.Show(str,"show avgfitness");

		}
	}
	public class count
	{
		public static float cfitness( ref PARAMETER param,int[] chroms)
		{
			float f1;
			float f2;
			float f4;
			float f3;
			float f;
			int t;
			f1=0;f2=0;f3=0;f4=0;
			param.check=true;			
			for(int i=0;i<(param.coursenum-1);i++)//软约束1	任意学生不希望连续参加两门考试
			{
				for(int j=i+1;j<(param.coursenum-1);j++)
				{
					t=Math.Abs (chroms[i]-chroms[j]);
					
					if((t<3)&&(t>0))//这里的3为参数，由每天考试的时间数决定
					{
						if(param.D[i,j]>0) f1+=(float)Math.Pow(2,t);//这里2为参数
						
					}
				}
			}
			for(int i=0;i<param.coursenum /3;i++)//软约束2	公共科目（参加人数较多的科目）编排在头几天,主要是为了评分的考虑
			{
				if(param.D[i,i]>param.cms)
					if(chroms[i]>(param.TimeSolt/2)) f2+=1;//公共课没有排到前几个时间段;
			}
			for(int i=0;i<(param.coursenum-1);i++)//硬约束1	同一时间段同一学生不能参加两门以上不同的考试科目
			{
				for(int j=i+1;j<(param.coursenum-1);j++)
				{
					
					if(chroms[i]==chroms[j]) 
					{
						if(param.D[i,j]!=0)
						{
							f3+=param.D[i,j];
							param.check=false;
						}
					}
				}
			}
			for(int i=1;i<(param.TimeSolt+1);i++)//硬约束2.	同一时间段所有科目参加的人数和不能超过所有教室容量
			{
				t=0;
				for(int j=0;j<(param.coursenum-1);j++)
				{
					if(i==chroms[j])
					{
						t+=param.D[j,j];
					}
				}
				if(t>param.nroom)
				{ 
					f4+=t-param.nroom;
					param.check=false;
				}
			}
			f=f1+f2+500*f3+300*f4;		
			return f;
		}

		public static int[,] crossover(float[] fitness,int[,] chroms,PARAMETER param,Random seed)
		{
			int [,] tchroms=new int [param.gpn,param.coursenum];//存放中间过渡染色体群
			int[] t1=new int [param.coursenum];//存放中间过渡染色体
			int [] t2=new int [param.coursenum];//存放中间过渡染色体
			int t3;
			int n;
			float rpc;
			Random rand=new Random(seed.Next());
			for(int i=0;i<param.gpn;i+=2)
			{				
				t1=select(fitness,chroms,param,seed.Next());				
				t2=select(fitness,chroms,param,seed.Next());
				
				rpc=(float)rand.NextDouble();
				if(rpc<=param.gpc)//开始交叉
				{
					n=rand.Next(param.coursenum)+1;
					if(rand.Next(2)==1)
					{
						for(int j=n;j<param.coursenum;j++)
						{
							t3=t1[j];t1[j]=t2[j];t2[j]=t3;
						}
					}
					else
					{
						for(int j=0;j<n;j++)
						{
							t3=t1[j];t1[j]=t2[j];t2[j]=t3;
						}
					}
				}//交叉完成；
				
				for(int j=0;j<param.coursenum;j++)//写入临时染色体
				{
					tchroms[i,j]=t1[j];
					tchroms[i+1,j]=t2[j];
				}
			}
			return tchroms;
		}
		private static int[] select(float []fitness,int[,] chroms,PARAMETER param,int seed)
		{
			/// <summary>
			///锦标赛选择法，随机从群里选择三个染色体，适应度高的生存
			/// </summary>
			int []t=new int [param.coursenum];
			int n;
			int m;
			Random rand=new Random(seed);			
			n=rand.Next()%(param.gpn);		
			for(int i=1;i<2;i++)//锦标赛选择，从3个里选择最大，地一个在循环外选择；
			{
				m=rand.Next()%(param.gpn);
				if(fitness[n]>fitness[m]) n=m;					
			}			
			for(int i=0;i<param.coursenum;i++) t[i]=chroms[n,i];
			return t;
		}

		public static int[,] mutation(int [,] chroms,PARAMETER param,Random seed)
		{
			Random rand =new Random(seed.Next());
			int t;
			for(int i=0;i<param.gpn;i++)
			{
				if(rand.NextDouble()>(double)param.gpm) break;
				t=rand.Next()%param.coursenum;
				chroms[i,t]=rand.Next(param.TimeSolt)+1;
			}
			return chroms;
		}		
	}
}