基于约束满足和遗传算法的排课算法

《基于约束满足和遗传算法的排课算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第36卷第14期计算机工程2010年7月Vol.36No.14ComputerEngineeringJuly2010·开发研究与设计技术·文章编号：1000—3428(2010)14—0281—04文献标识码：A中图分类号：TP311基于约束满足和遗传算法的排课算法12许秀林，胡克瑾(1.南通职业大学电子工程系，南通226007；2.同济大学经济管理学院，上海200092)摘要：针对高校排课过程中存在诸多资源约束因素的问题，提出一种将遗传算法与约束满足算法相结合的排课算法，由约束满足算法确定排课任务的优先次序，遗传算法解决单个排课任务时间片分配的优化问题。算法中单个排课任务

2、的局部最优解具有全局最优性。实验结果表明，该算法能够改进算法性能，提高排课效率。关键词：约束满足算法；遗传算法；排课问题CourseScheduleAlgorithmBasedonConstraintSatisfactionandGeneticAlgorithm12XUXiu-lin,HUKe-jin(1.DepartmentofElectronicEngineering,NantongVocationCollege,Nantong226007;2.CollegeofEconomicandManagement,TongjiUniversity,Shanghai200092)

3、【Abstract】Aimingatthefactorsofresourceconstraintsthatexistintheprocessofcourseschedule,thispaperproposesanalgorithmcombiningGeneticAlgorithm(GA)andconstraintsatisfactionalgorithmtosolvecoursescheduleproblem.Coursescheduletasksaresortedwithconstraintsatisfactionalgorithm,andasinglecoursesch

4、eduletask’stimetableisallocatedandoptimizedwithGA.Inthisalgorithm,theresultofsinglecoursescheduletaskisglobaloptimal.Experimentalresultsshowthatthismethodisfeasibletoimprovetheperformanceandtheefficiency.【Keywords】constraintsatisfactionalgorithm;GeneticAlgorithm(GA);coursescheduleproblem1概

5、述2排课问题排课问题是典型的多类资源组合优化问题。在1975年，排课是对课程教学活动的所需资源进行分配的过程。排排课问题已被S.Even等人论证为NP完全问题。这类问题的课分为2个阶段：(1)由教学计划生成开课任务书，为课程分求解只能找到较为合理、较为满意的解，而并非是真正的最配上课班级和任课教师，通常由教研室主任手工完成。(2)由优解。由于排课问题通常包含教学班级、教师、教室、时间开课任务书生成教学课表，为课程分配教室和时间。本文讨等多个约束条件，有些研究利用约束问题求解方法来求解排论的排课主要是第(2)阶段的排课，且假定第(1)阶段的排课结[1-2]课问题。作为随机优化

6、与搜索方法，遗传算法(Genetic果在相对合理的范围内。Algorithm,GA)通过对可行解进行选择、交叉、变异等遗传算排课问题实际上是一个由Course、Class、Teacher、子的作用使种群不断进化，最后得到全局最优解或近似最优Classroom、Timetable组成的五元组，用(Ac,Bc,Ct,Dc,Et)表解。文献[3]对一般的安排问题使用了遗传算法；文献[4]用具示。在五元组中，除Ac以外，其他元素都是集合变量，分别有控制约束的遗传算法解决大学课表安排问题；文献[5]在课为班级集合、教师集合、教室集合和时间片集合的子集。在表初始化、课程安排和冲突处理时

7、采用了时间片重叠法；给定Ac值后，在排课第1阶段分配Bc,Ct的值，排课第2阶文献[6]提出了独特的排课问题的基因编码方式，分别从不同段是在给定Ac,Bc,Ct3个元素的值后求解Dc,Et的值。角度应用遗传算法解决排课问题。由于用遗传算法实现大规排课活动是将教师与学生在时间和空间上根据不同的约模的排课时染色体太长，因此基本解空间规模太大导致该问束条件进行排列组合，由于课程资源的有限性，因此不同课题的可行解比例较小。有些研究人员在应用遗传算法求解排程之间在资源利用上必然存在相互制约。例如，在同一时间课问题时，往往削弱