采用三维自适应遗传算法的高校排课问题研究.pdfVIP

学兔兔 采用三维自适应遗传算法的高校排课问题研究 时小虎，等 采用三维自适应遗传算法的高校排课问题研究 时小虎 ，杨智勇 ( 甘肃广播电视大学 甘肃兰州，730000) ( 重庆工程职业技术学院 重庆，400037) 摘 要：根据教师、学生、课程、教室和时间要求建立多约束数学模型，并结合遗传算法特点，对其各个步骤进行了 改进，提出了基于三维自适应遗传算法的排课方法。实验结果表明，与传统排课方法相比，基于三维自适应遗传算法的排 课方法能有效降低课程之间的冲突率，提高排课效率和成功率。 关键词：高校排课问题；三维编码；自适应；遗传算法 Abstract：According to the requirements of teachers，students，curriculum，time and classroom in Unive~ity Timetabling Prob- lem，a multi．constrained mathematical model is established．Combining characteristics of genetic algorithm with improvements on its corresponding steps，a timetable method based on three—dimensional adaptive genetic algorithm is proposed．Experimental results indicate that，contrast to traditional timetable，its performance improve the timetable effectively and reduce the rate of conflicts be— tween the courses substantially． Keywords：University Timetabling Problem；Three—dimensional code；adaptation；Genetic Algorithm 中图分类号：TP301 文献标识码：A 文章编号：1001—9227(2013)03—0042—04 0 引 言 排课过程本身是一个充满着冲突的过程，主要涉及因素包 排课方法在高校教务管理系统中起着极其重要的作用，它的 括： 优劣直接影响着教学质量和教学资源的利用，同时，排课问题是 时间：排课问题一般是按周次来计算上课时间的，从开学 高校教务管理中较繁重和费时的任务之一，它是一个具有约束和 第一周至第M周，每周上课时间为N天(N--7)。每天可以分 多目标的组合优化问题，己被证明为一个NP完全问题n】。为了解 为上午、下午和晚上三个时间段，每个时间段主要分为P 节 决这个问题，人们提出了各种解决算法，例如基于优先级自动排 (上午为P。，下午为P ，晚上为P )。上课的最小单元是一 课算法、基于时间位图迭加匹配算法和专家系统求解算法等 ～， 节，即一个课时，通常一门课程的一次上课时间为两个或者三 这些算法解决了排课中的一些问题，但只能针对个别的实际问 个课时 (安排在上午和晚上的为两个课时，安排在下午的为三 题，通用性差，而且排课过程中各要素关联规则很难获得；实际 个课时)。 求解结果并不理想，课表优劣评判标准较少；只能对问题的某一 课程：每个课程都有自