利用遗传算法求解中学课表安排问题.pdfVIP

维普资讯 利用遗传算法求解中学课表安排问题 朱冠宇 王 乘 席大春 (华中科技大学工程计算与仿真研究所，武汉 430074) 摘 要 论文采用三维编码方式及相应的遗传算子构成的遗传算法求解中学课表安排问题，通过实例验证该方法具有 良好的收敛性 ，可产生比较优 良的排课方案。 关键词 中学课表 遗传算法 三维编码 1TrP 文章编号 1002—8331-(2004)27—0215—04 文献标识码 A 中图分类号 TP301 GeneticAlgorithm forSolving Curriculum ScheduleProblem of SeniorHigh School Zhu Guanyu W ang Cheng XiDachun (EngineeringComputationandSimulationInstitute，HuazhongUniversityof ScienceandTechnology，Wuhan430074) Abstract： The geneticalgorithm isused forsolvingcurriculum schedule problem ofseniorhigh schoo1．A experiment verifiesthatthisalgorithm can producecurriculum schedule conformingtorequirements． Keywords：curriculum schedule，genetic algorithm，3-dimensionalcoding，rITI’P l 引言 — — 课程集合 f【l，Z，……Z}。 课表问题属于时间表问题 (1TrP：TimeTableProblem)，是典 课表问题求解 的 目标就是寻找 C、P、R、、 的合理搭配 ， 型的组合优化问题。求解课表问题 ，就是要避免在争夺与课程 要求最终结果必须符合一定的约束条件并尽量满足经验要求。 相关资源的过程中可能引发的冲突 ，给出合理 的课表安排方案。 约束条件包括 ： 70年代中期，S．Eveo等人论证了课表问题是 NP完全问题Ⅲ。 (1)对于任一班级 ，某门课程一周 内的授课时间数 (节数) 许多人尝试用近似方法 ，如分批加权排课模型2[1和基于二分 图 是固定的。 模型的排课系统3[1等求解该问题 ，然而，这些方法在课表信息量 (2)在某一时间段，对于某一教师，最多只能为其安排一门 比较大的情况下，效率不高。 课程的教学任务。 遗传算法是一种可以用于复杂系统优化计算的鲁棒有哪些信誉好的足球投注网站 (3)在某一时间段，对某一班级，最多只能为其安排一门课程。 算法。实践证明，遗传算法对于组合优化 中NP完全问题非常 (4)在某一时间段，对某一教室 ，最多只能安排一门课程的 有效 。已有人尝试利用遗传算法求解课表问题 ，但都存在一些 教学任务 。 问题。文献 5【】中所用遗传算法的适应值可能为负值 ，不利于选 经验要求主要包括： 择算子的执行 ，同时易造成个体之间适应值相差过大 ，不利于 (1)对同一班级 ，某一门课程两次上课时间尽量分散安排。 算法收敛 ；文献 6【】用课程离散度期望值来区分排课方案的优良 (2)一些主要课程，尽量安排在比较好的时间段。 程度 ，经实际检验 ，容易出现局部最劣情况 (如某班在同一天安 (3)某些教师对上课时间可能有一些要求，应适 当考虑。 排两次相同课程)；姚