分析下染色体基因 这里用 老师 课程 班级 教室 周天 上下晚 课时作为染色体编码我封装了如下类
/// <summary> /// NP 授课事件 由教室、课程、班级 时间片段构成 liyouming add 20180607 /// </summary> public class NP { ///// <summary> ///// 暂时不作为染色体基因处理 ///// </summary> public int Week { get; set; } /// <summary> /// 教室编号 /// </summary> public int TeacherId { get; set; } public string TeacherName { get; set; } /// <summary> /// 课程编号 /// </summary> public int CourseId { get; set; } /// <summary> /// 班级 /// </summary> public int ClassId { get; set; } /// <summary> /// 教室 /// </summary> public int RoomId { get; set; } /// <summary> /// 天 /// </summary> public int DayId { get; set; } /// <summary> /// 早上 下午 晚上 /// morning afterroom evevning /// </summary> public int MAE { get; set; } /// <summary> /// 科时{分上下午} /// </summary> public int TimeId { get; set; } /// <summary> /// 获取上课日上课时段片段 /// </summary> public string TimePart { get { return DayId.ToString() + MAE.ToString() + TimeId.ToString() ; } } /// <summary> /// 排除天取得天课时时间片段 /// </summary> public string SmallPart { get { return MAE.ToString() + TimeId.ToString() ; } } #region 三范式原则 /// <summary> /// 同一个老师不能再同一时间段上2个课程 /// </summary> public string TeacherGene { get { return TeacherId.ToString().PadLeft(3, '0') + DayId.ToString() + MAE.ToString() + TimeId.ToString() ; } } /// <summary> /// 同一个班级同一个时间段不能安排2个课程 /// </summary> public string ClassGene { get { return ClassId.ToString().PadLeft(3, '0') + DayId.ToString() + MAE.ToString() + TimeId.ToString() ; } } /// <summary> /// 同一个教室同一时间内不能被多次使用 /// </summary> public string RoomIdGene { get { return RoomId.ToString().PadLeft(3, '0') + DayId.ToString() + MAE.ToString() + TimeId.ToString() ; } } #endregion /// <summary> /// 老师事件编码 保证每个老师在每个班级课时总数（教学安排） /// </summary> public string TeacherEvent { get { return TeacherId.ToString().PadLeft(3, '0') + CourseId.ToString().PadLeft(3, '0') + ClassId.ToString().PadLeft(3, '0'); } } /// <summary> /// 教室某一天的课时数量 /// </summary> public string TeacherEventDay { get { return TeacherId.ToString().PadLeft(3, '0') + CourseId.ToString().PadLeft(3, '0') + ClassId.ToString().PadLeft(3, '0') + DayId.ToString(); } } /// <summary> /// 某一天的区分课时数量 /// </summary> public string TeacherEventDayMEA { get { return TeacherId.ToString().PadLeft(3, '0') + CourseId.ToString().PadLeft(3, '0') + ClassId.ToString().PadLeft(3, '0') + DayId.ToString() +MAE.ToString(); } } /// <summary> /// 上午的课时数量 /// </summary> public string TeacherEventDayM { get { return TeacherId.ToString().PadLeft(3, '0') + CourseId.ToString().PadLeft(3, '0') + ClassId.ToString().PadLeft(3, '0') + DayId.ToString()+"1"; } } /// <summary> /// 上午的课时数量 /// </summary> public string TeacherEventDayA { get { return TeacherId.ToString().PadLeft(3, '0') + CourseId.ToString().PadLeft(3, '0') + ClassId.ToString().PadLeft(3, '0') + DayId.ToString() + "2"; } } public string TeacherEventDayE { get { return TeacherId.ToString().PadLeft(3, '0') + CourseId.ToString().PadLeft(3, '0') + ClassId.ToString().PadLeft(3, '0') + DayId.ToString() + "3"; } } /// <summary> /// 基因链条 得到基因链条 /// </summary> public string GeneStrand { get { return TeacherId.ToString().PadLeft(3, '0') + CourseId.ToString().PadLeft(3, '0') + ClassId.ToString().PadLeft(3, '0') + RoomId.ToString().PadLeft(3, '0') + DayId.ToString() + MAE.ToString() + TimeId.ToString() ; } } #region /// <summary> /// 每个个体的适应值 西格玛求出每个染色体对条件的适应值（老师自定义设置的参数） /// n /// ∑= Fs(i) /// i=1 /// </summary> public int F_si { get; set; } #endregion public int CourseNum { get; set; } }
这里所有数据都在内存中测试
定义一些用于测试类
教师课程班级关系类
public class M_Teachers { /// <summary> /// 老师编号 /// </summary> public int TeacherId { get; set; } /// <summary> /// 老师名称 /// </summary> public string TeacherName { get; set; } /// <summary> /// 老师所受课程(可能存在一个老师教几门课的情况) /// </summary> public List<M_Course> Courses { get; set; } /// <summary> /// 老师所受班级 存在一个老师上多个班级的情况 /// </summary> public List<M_Class> Classes { get; set; } }
课程类
public class M_Course { /// <summary> /// 课程编号 /// </summary> public int CourseId { get; set; } /// <summary> /// 课程名称 /// </summary> public string CourseName { get; set; } public string ColorFlag { get; set; } /// <summary> /// 课程的重要程度 /// </summary> public int Weight { get; set; } }
班级类
public class M_Class { public int ClassId { get; set; } /// <summary> /// 班级名称 /// </summary> public string ClassName { get; set; } /// <summary> /// 该班级某位老师的课时数量 /// </summary> public int Num { get; set; } }
教师自定义条件类
public class TeacherConditions { public int TeacherId { get; set; } public string Name { get; set; } /// <summary> /// 限制条件 如果 Val 包含了染色体基因 那么权重就是 fi=1 * weight 不满足就是 fi=0 * weight /// 第一位是星期 第二位是上、下、晚 时段 第三位是课时 /// 设计之初用 111:表示周一上午第一节课 524:表示周五下午第四节课 332：表示周三晚上第2节课 /// </summary> public string Val { get; set; } /// <summary> /// 条件权重 /// </summary> public int Weight { get; set; } /// <summary> /// 计算权重 /// 根据染色体时间片满足条件 满足返回1 不满足返回0 最后计算权重 权重越高越会被选中 /// </summary> /// <param name="daytime">如： 524:表示周五下午第四节课</param> /// <returns></returns> public int GetWeight(string daytime) { var arr = Val.Split(','); if (arr.Contains(daytime)) return 1* Weight; return 0; } }
评价函数类
/// <summary> /// 评价函数类 /// </summary> public class Evaluation { List<TeacherConditions> teacherConditions = null; Dictionary<string, int> dic = null; public Evaluation() { teacherConditions = new List<TeacherConditions> { new TeacherConditions { TeacherId=1, //语文老师不上星期三 Val="111,112,113,114,121,122", Weight =7 } }; //节次优度 比如 语文 要优先上上午一二节课 dic = new Dictionary<string, int>(); //入下面标识该节课优度 dic["11"] = 8; dic["12"] = 8; dic["13"] = 2; dic["14"] = 7; dic["15"] = 7; dic["21"] = 8; dic["22"] = 8; dic["23"] = 5; dic["24"] = 5; } /// <summary> /// 计算评价值 /// </summary> /// <returns></returns> public List<NP> Fun_Evaluation(List<NP> nps) { //存储带有评价值的排课 List<NP> evaluation = new List<NP>(); if (nps != null && nps.Count > 0) { foreach (var item in nps) { var Fi_teacher = teacherConditions.Where(c => c.TeacherId == item.TeacherId).ToList(); if (Fi_teacher != null && Fi_teacher.Count > 0) { //评价函数值 foreach (var xi in Fi_teacher) { //得到每条数据的权重 西格玛i相对于所有条件的权重值 item.F_si += xi.GetWeight(item.TimePart); } } } } else { throw new Exception("评价值函数报错"); } return evaluation; } /// <summary> /// 节次优度(预先设置好课时的节次优度) /// </summary> /// <param name="np">所有种群</param> /// <param name="indexNp">当前基因链节次课程</param> /// <param name="classId"></param> public int Fun_IntervalOptimality(int weight, string key) { return dic[key] * weight; } /// <summary> /// 班级课时日均分布匀度 /// </summary> public void Fun_DistributionAverage() { } /// <summary> /// 教室容量利用率 /// </summary> public void Fun_RoomAvailability() { } }
遗传算法 轮盘 交叉 变异 及退火处理
/// <summary> /// 退火算法类 /// </summary> public class AnnealOperato { //int：标识每个总群的N代索引 //而List<NP> 标识每个种群的个体结合 方便采用退火算法 防止出现局部最优解 Dictionary<int, List<NP>> lst = new Dictionary<int, List<NP>>(); /// <summary> /// 获取种群、种群代数下的个体集合 /// </summary> /// <param name="index">种群i的第x代</param> /// <returns></returns> public List<NP> GetIndex(int index) { if (lst[index] == null) { throw new Exception("第" + index + "代种群不存在"); } return lst[index]; } /// <summary> /// 设置i种群第x代的种群个体集合 /// </summary> /// <param name="classId">种群索引</param> /// <param name="index">代数索引</param> /// <param name="np">种群i下第x代的种群个体集合</param> public void SetIndex(int index, List<NP> np) { lst.Add(index, np); } /// <summary> /// 获取第n代的群体（包含x个群体的个体集合） /// </summary> /// <param name="genetic"></param> /// <returns></returns> public Dictionary<int, List<NP>> GetAll() { return lst; } } /// <summary> /// 遗传算子 轮盘赌博算子、交叉算子、变异算子 /// </summary> public class GeneticOperato { ILog log = LogManager.GetLogger("GeneticOperato"); private object obj = new object(); //设置交叉概率 double Pc = 0.9; //设置变异概率 剩余空间即为 轮盘选择概率 double Pm = 0.05; /// <summary> /// 每个种群遗传的代数 /// </summary> int genetic = 3; public static List<NP> newClass = new List<NP>(); /// <summary> /// 冲突检查函数 为true的时候则可以添加 /// </summary> /// <param name="np"></param> /// <returns></returns> public bool Confict(NP np) { //某天课程超过多少不排课 if (newClass.Where(c => c.TeacherEventDay == np.TeacherEventDay).Count() > 4) { return false; } if (newClass.Where(c => c.TeacherEventDayMEA == np.TeacherEventDayM).Count() > 2) { return false; } if (newClass.Where(c => c.TeacherEventDayMEA == np.TeacherEventDayA).Count() > 2) { return false; } if (newClass.Where(c => c.TeacherEvent == np.TeacherEvent).Count() < np.CourseNum) { //不存在冲突 if (newClass.Where(c => c.TeacherGene == np.TeacherGene).Count() == 0 && newClass.Where(c => c.ClassGene == np.ClassGene).Count() == 0) { return true; } } // log.Info(string.Join(",", newClass.Select(c => c.ClassGene)) + "\r\n NP:" + np.ClassGene); //存在冲突 return false; } /// <summary> /// 轮盘赌博算子 第一种 Pr 可以设置比例 /// </summary> public NP Operato_Corona(List<NP> pop) { double m = 0; double Fi_Sum = pop.Sum(c => c.F_si); var r = new Random().NextDouble(); //r为0至1的随机数 foreach (var np in pop) { m += double.Parse(np.F_si.ToString()) / Fi_Sum; if (r <= m) return np; } return null; } NP tempnp; Random r = new Random(); public List<NP> Recurrence(List<NP> nps, int gen, AnnealOperato anneal, Evaluation evaluation) { if (gen > genetic) { return anneal.GetIndex(gen - 1); } //存储种群个体大集合 newClass = new List<NP>(); while (newClass.Count < nps.Count) { //设置算子产生下一代的概率 var Pri = r.NextDouble(); #region 轮盘赌博算子 if (Pri > Pc) //0.25 { //根据轮盘赌博法得到适应度最好的两个个体 var npi1 = Operato_Corona(nps); tempnp = new NP { ClassId = npi1.ClassId, CourseId = npi1.CourseId, DayId = npi1.DayId, F_si = npi1.F_si, MAE = npi1.MAE, RoomId = npi1.RoomId, TeacherId = npi1.TeacherId, TeacherName = npi1.TeacherName, CourseNum = npi1.CourseNum, TimeId = npi1.TimeId }; if (Confict(tempnp)) { newClass.Add(tempnp); } } #endregion #region 交叉算子 //根据两次得到的理论上最优的两个个体参交叉算法获取下一代的两个个体 0.75 if (Pri > Pm && Pri <= Pc) { var x1 = r.Next(0, nps.Count()); var x2 = r.Next(0, nps.Count()); var npi1 = nps[x1]; var npi2 = nps[x2]; var tempnp1 = new NP { ClassId = npi1.ClassId, CourseId = npi1.CourseId, DayId = npi2.DayId, F_si = npi1.F_si, MAE = npi2.MAE, RoomId = npi1.RoomId, CourseNum = npi1.CourseNum, TeacherId = npi1.TeacherId, TeacherName = npi1.TeacherName, TimeId = npi2.TimeId }; if (Confict(tempnp1)) { newClass.Add(tempnp1); } var tempnp2 = new NP { ClassId = npi2.ClassId, CourseId = npi2.CourseId, DayId = npi1.DayId, F_si = npi2.F_si, MAE = npi1.MAE, RoomId = npi2.RoomId, TeacherId = npi2.TeacherId, CourseNum = npi2.CourseNum, TeacherName = npi2.TeacherName, TimeId = npi1.TimeId }; if (Confict(tempnp2)) { newClass.Add(tempnp2); } } #endregion #region 变异算子 //产生变异下一代个体 0.05 if (Pri <= Pm) { var x1 = r.Next(0, nps.Count()); var npi1 = nps[x1]; //随机变异 tempnp = new NP { ClassId = npi1.ClassId, CourseId = npi1.CourseId, DayId = npi1.DayId, MAE = npi1.MAE, F_si = npi1.F_si, RoomId = npi1.RoomId, CourseNum = npi1.CourseNum, TeacherId = npi1.TeacherId, TeacherName = npi1.TeacherName, TimeId = npi1.TimeId, }; tempnp.DayId = r.Next(1, 6); tempnp.MAE = r.Next(1, 3); if (tempnp.MAE == 1) { tempnp.TimeId = r.Next(1, 6); } if (tempnp.MAE == 2) { tempnp.TimeId = r.Next(1, 5); } #region 冲突检测 不存在则添加 if (Confict(tempnp)) { newClass.Add(tempnp); } #endregion } #endregion } evaluation.Fun_Evaluation(newClass); anneal.SetIndex(gen, newClass); ////退火算法检查 //if (anneal.GetIndex(gen).Sum(c => c.F_si)- anneal.GetIndex(gen-1).Sum(c => c.F_si)>0) //{ // return Recurrence(newClass, gen + 1, anneal, evaluation); //} return Recurrence(newClass, gen + 1, anneal, evaluation); } public List<NP> PopX(List<NP> initNp, AnnealOperato anneal) { //初始化种群演化集合类 Evaluation evaluation = new Evaluation(); //计算初始种群评价值 evaluation.Fun_Evaluation(initNp); //保存第一代 anneal.SetIndex(0, initNp); //生成下一代 Recurrence(initNp, 1, anneal, evaluation); ////计算评价值 //evaluation.Fun_Evaluation(next); //anneal.SetIndex(n, next); var g = anneal.GetIndex(genetic); return g; } /// <summary> /// 交叉算子 Pi 可以设置比例 已完成 /// </summary> /// <param name="np"></param> /// <returns></returns> public List<NP> Operato_Intersect(List<NP> np) { //生明下一个种群 Random r = new Random(); int i = 0; while (i < np.Count / 2) { var first = r.Next(0, np.Count); var second = r.Next(0, np.Count); var tempfirst = np[first]; var tempsecond = np[second]; np[first].DayId = tempsecond.DayId; np[first].MAE = tempsecond.MAE; np[first].TimeId = tempsecond.TimeId; np[second].DayId = tempfirst.DayId; np[second].MAE = tempfirst.MAE; np[second].TimeId = tempfirst.TimeId; } //计算评价函数值 Evaluation evaluation = new Evaluation(); evaluation.Fun_Evaluation(np); return np; } /// <summary> /// 变异算子 Pv 可以设置比例 /// </summary> /// <param name="np"></param> /// <returns></returns> public List<NP> Operato_Variation(List<NP> np) { return null; } /// <summary> /// 获取下一代 /// </summary> /// <returns></returns> public List<NP> GetNext() { return null; } }
添加测试数据 设置老师 课程 班级关系 初始化种群数据
/// <summary> /// 种群操作 随机产生一个种群 /// 根据教学任务参数一个种群 /// 什么是教学任务： /// 学校老师数量、老师教那些班级、老师教什么课程、老师某一个班级某一门课程的课时数量先随按每个老师不重复的情况随机生成出来 /// </summary> public class Population { //添加测试数据 List<NP> lstNP = new List<NP>(); //6个老师负责2个班级 初始化一个教学任务计划(6个老师完成两个班级的排课计划) //班级 ：高一一班 、高三一班 List<M_Teachers> teacherIds = new List<M_Teachers>() { //张三教高一一班语文 每周20个课时 一个课时是40分钟 所受班级课时分布为 #region 张三老师 new M_Teachers { TeacherId=1, TeacherName="张三", Classes=new List<M_Class>() { new M_Class { ClassId=1, ClassName="高一一班", Num=8 }, new M_Class { ClassId=2, ClassName="高三一班", Num=12 } }, Courses=new List<M_Course> { new M_Course { CourseId=1, ColorFlag="red", Weight=8, CourseName="语文" } } }, #endregion #region 李四老师 //李四教数学 new M_Teachers { TeacherId=2, TeacherName="李四", Classes=new List<M_Class>() { new M_Class { ClassId=1, ClassName="高一一班", Num=10 }, new M_Class { ClassId=2, ClassName="高三一班", Num=10 } }, Courses=new List<M_Course> { new M_Course { CourseId=2, ColorFlag="green", Weight=6, CourseName="数学" } } }, #endregion #region 王武教英语 new M_Teachers { TeacherId=3, TeacherName="王武", Classes=new List<M_Class>() { new M_Class { ClassId=1, ClassName="高一一班", Num=8 }, new M_Class { ClassId=2, ClassName="高三一班", Num=8 } }, Courses=new List<M_Course> { new M_Course { CourseId=3, ColorFlag="yellow", Weight=5, CourseName="英语" } } }, #endregion #region 赵柳教物理 new M_Teachers { TeacherId=4, TeacherName="赵柳", Classes=new List<M_Class>() { new M_Class { ClassId=1, ClassName="高一一班", Num=5 }, new M_Class { ClassId=2, ClassName="高三一班", Num=5 } }, Courses=new List<M_Course> { new M_Course { CourseId=4, Weight=2, ColorFlag="blue", CourseName="物理" } } }, #endregion #region 郑七教化学 new M_Teachers { TeacherId=5, TeacherName="郑七", Classes=new List<M_Class>() { new M_Class { ClassId=1, ClassName="高一一班", Num=4 }, new M_Class { ClassId=2, ClassName="高三一班", Num=4 } }, Courses=new List<M_Course> { new M_Course { CourseId=5, ColorFlag="gray", Weight=2, CourseName="化学" } } }, #endregion #region 孙八教生物 new M_Teachers { TeacherId=6, TeacherName="孙八", Classes=new List<M_Class>() { new M_Class { ClassId=1, ClassName="高一一班", Num=4 }, new M_Class { ClassId=2, ClassName="高三一班", Num=4 } }, Courses=new List<M_Course> { new M_Course { CourseId=6, ColorFlag="white", Weight=2, CourseName="生物" } } }, #endregion }; /// <summary> /// 获取排列表 /// </summary> /// <returns></returns> public List<NP> GetNP() { return SetNP(teacherIds); } /// <summary> /// 根据教学计划产生随机课程表 随机产生种群 pop 这里初始化有2个班级 所以按班级生成了初始种群2个 /// </summary> public List<NP> SetNP(List<M_Teachers> teacherIds) { if (teacherIds == null) { throw new Exception("教学计划为空"); } //初始一个随机函数 var random = new Random(); var evaluation = new Evaluation(); //Z轴授课事件维度（教师+课程+班级） foreach (var teacher in teacherIds) { foreach (var course in teacher.Courses) { foreach (var classitem in teacher.Classes) { while (true) { var np = new NP { TeacherId = teacher.TeacherId, TeacherName = teacher.TeacherName, CourseId = course.CourseId, ClassId = classitem.ClassId, RoomId = 1, //教室暂时确定 不考虑教室 针对高中时确定的(一个班一个教室) 正对大学不确定 DayId = random.Next(1, 6), //随机某一天（周一到周五）根据需要设置 MAE = random.Next(1, 3), CourseNum = classitem.Num }; //上午 5个课时 if (np.MAE == 1) { np.TimeId = random.Next(1, 6); } //下午 下午 4个课时 if (np.MAE == 2) { np.TimeId = random.Next(1, 5); } //晚上 三个课时 if (np.MAE == 3) { np.TimeId = random.Next(1, 4); } if (lstNP.Where(c => c.TeacherEvent == np.TeacherEvent).Count() < classitem.Num) { //满足三大原则 + 同时还要处理教室的容纳人数要大于班级的人数（这里先不判断） // && lstNP.Where(c => c.RoomIdGene == np.RoomIdGene).Count() == 0 if (lstNP.Where(c => c.TeacherGene == np.TeacherGene).Count() == 0 && lstNP.Where(c => c.ClassGene == np.ClassGene).Count() == 0) { np.F_si += evaluation.Fun_IntervalOptimality(course.Weight, np.SmallPart); lstNP.Add(np); } continue; } else { break; } } } } } return lstNP; } }
List<NP> np = new Population().GetNP(); AnnealOperato anneal = new AnnealOperato(); GeneticOperato g = new GeneticOperato(); var p10 = g.PopX(np, anneal);
执行结果监控
可以看到适应度有 上升的趋势，但是后面又有下降 ，这里是第五代是一个局部最优解，用退火法可以改变遗传代可以得到 第三代为最优解