遗传算法在自动排课系统中的应用

来源:用户上传      作者: 林显宁

　　摘要：排课问题是一个有约束的、多目标的组合优化问题，是一个已被证明的NP完全问题。本文旨在相关遗传算法和多目标优化理论的基础之上，结合数学分析的方法，研究了遗传算法在排课系统中的应用。
　　关键词：遗传算法 自动排课 VB SQL
　　中图分类号：TP18 文献标识码：A 文章编号：1007-9416（2013）10-0131-02
　　课程表的编排是一个涉及多种因素的组合规划问题，它要保证在课程安排中教师、学生、教室不能产生冲突（所谓冲突，就是将需上不同课程的两个或多个班安排在了同一时间、同一教室，或为同一教师在同一时间段安排了多门课程等情况），并且要满足教师的要求和资源限制等约束条件。而使用计算机进行排课能够快速地得到满足约束条件的可行结果，具有排课时间短、省人力和质量高的优点，进而使教务人员从繁杂的排课任务中解脱出来。
　　1 遗传算法
　　遗传算法是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。也是计算机科学人工智能领域中用于解决最优化的一种搜索启发式算法。因此，采用具有智能型和并行性的遗传算法，来对排课问题进行求解，是一个比较明智的选择。
　　2 排课约束条件分析
　　编排课表牵涉的因素很多，包括时间、课程、教室、校区、院系、班级、教师等。但都要遵循一个原则，那就是：课表要有利于教学设备的充分利用，要符合教学规律。将这个原则进行细化、清晰化，可以归纳为以下6项硬约束和6项软约束：
　　硬约束：（1）同一班级在同一时间只能安排一门课程；（2）同一教师在同一时间只能安排一门课程；（3）同一教室在同一时间只能安排一门课程；（4）教室总数要大于同一时间安排的课程总数；（5）教室容量必须大于上课学生人数；（6）课程要安排在它需要的类型教室中。
　　软约束：（1）优先安排全校公共基础课；（2）一周内课次多于2次以上的课程，在时间安排上要求尽量隔天安排；（3）较难课程应安排在上午第一节或下午第一节；（4）体育课后尽量避免直接排课；（5）教师一天的授课活动尽量安排在同一校区，有效地解决跨校区问题； （6）同一门课程尽量安排在固定的教室。
　　3 排课问题的数学分析
　　首先需要将排课中的主要元素用数学的符号的方法来表示出来。
　　在排课问题中某学院某学期课表的数据模型就是的组合。在自动排课前，需要进行班级课程设置、班级课程任课教师设置，这些设置就是为了确定、、三者的关系。设定好它们的就得到了要进行排课的任务，每一个排课任务就对应一个的组合。自动排课的处理过程就是在满足约束的条件下确定每个任务对应的组合在一周内与剩下的两个元素和如何进行组合。下面用数学的方法来分析排课的约束条件：
　　对于硬性约束条件1～3，用数学来表示就是、、的组合是唯一的，有且只能有一个。
　　对于硬性约束条件4，用数学来表示就是对于任意的时间片，教室总数r大于组合的数量。
　　对于硬性约束条件5，用数学来表示就是对于任意的组合，教室容量必须大于班级的人数。
　　对于硬性约束条件6，用数学来表示就是对于任意的课表组合，课程所要求的教室类型必须与教室的类型一致。
　　而针对于软性约束条件1～6，用数学来表示就是排课任务具有较高的优先级，要优先进行安排；在一周内的次数大于2时，在组合成时，每次的尽量不同；任意的课表组合，如果课程是较难的课程时，的节次n最好是1或3；课表组合，如果课程是体育课时，的节次为，则最好不要再出现为的课表组合；对于相同的排课任务，如果班级Cy是属于不同校区的，每次的尽量不同；排课任务在一周内的次数大于2时，在组合成时，每次的尽量相同。
　　4 遗传算法设计
　　遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索，是一种通过模拟自然进化过程搜索最优解的方法。系统进行排课时，具体算法描述如下：
　　4.1 编码
　　一条染色体中应包含所有排课DNA分子，每个排课DNA分子又包含班级课程信息、教师信息、教室信息和时间信息，以及院系和学期信息。由于院系和学期在处理中是提前设定好的，在每次处理时都是一个给定的值，所以在染色体中可以不考虑他们。在前面的数学分析中我们将课表组合表示为，这里将拆分为MN，则可将染色体表示为。、、、都用他们所对应的字段Id的值来表示。M表示星期，N表示每天课节数。
　　4.2 初始种群
　　采用系统的随机数，生成初始种群。在前面的数学分析中我们将排课任务表示为，在进行排课时初始化种群中的个体就是用随机函数生成染色体中的的组合。
　　4.3 确定适应度
　　确定适应度，首先对一条染色体中的每个DNA分子计算适应度，然后计算一条染色体中所有DNA分子适应度之和，将该值作为个体适应度。排课系统中适应度与排课约束中归纳的6条硬性约束和6条软性约束对应。其中最主要的有检测班级、教师和教室三者的时间冲突。所有的约束条件的满足情况就是对应的适应度。而且对于硬性约束条件，系统要求必须满足，这也就对应的要求个体的适应度必须达到硬性约束对适应度的要求。
　　4.4 选择运算和变异运算
　　选择运算和变异运算是排课系统生成下一代种群的方式和方法，通过有限次的选择运算和变异运算找到最优解。
　　4.5 排课处理流程图（图2）
　　参考文献
　　[1]于国莉.基于遗传算法的排课问题的研究[D].河北工业大学，2007.
　　[2]姚建波.基于遗传算法的排课问题的研究[D].贵州大学，2008.
　　[3]张伟，李守智，高峰等.几种智能最优化算法的比较研究[J] .Proceedings of the 24thChinese Control Conference，Guangzhou，P.R.China July 15-18，2005：1316-1320.
　　[4]吉根林.遗传算法研究综述.计算机应用与软件[J]，2004.21（2）：69～73.
　　[5]徐艳斌.基于遗传算法的高校排课系统设计与分析[D].广东工业大学，2007.
转载注明来源:https://www.xzbu.com/8/view-4740535.htm