遗传算法在大学排课问题中的应用

当今时代， 伴随着计算机技术的快速发展， 许多繁琐的人 工操作已经被计算机系统所取代。排课系统作为高校教务管 理系统中最重要也最复杂的部分之一，已经成为国内外众多 高校以及软件公司的研究课题，在这方面也取得了许多的理 论成果和实现方法。因此，研究开发一个实用的排课系统具 有十分重要的现实意义。 1 研究背景 随着我国教育体制改革的不断深入和发展，高校的办学 规模逐年扩大， 因此， 编排一张适用的、 科学的课表已经成为 每一所高校在新学期开始之前必须进行的一项极其重要工作。 简而言之， 它具体的工作内容就是将课程、 教师、 教室和学生 四者之间进行合理的调度分配，从而达到四者之间的完美结 合， 从而使整个教学活动能够正常、 有序地顺利进行。
167
—— 科协论坛 ・ 2010 年第 9 期 （下） ——
教育科学
与 人才培养
(5)按照一定的变异概率及变异方法生成新个体。 (6) 由交叉和变异产生新一代种群， 之后返回第 （2） 步， 最 后进行冲突检测与消除。 通常可利用编码技术对变量进行编码，将变量转化成适 合群体进化的表达形式。对目标函数进行处理操作，使其能 够蕴含遗传算法的适应度函数。这样，在群体进化的过程之 中，适应度就能够反映模型的目标函数。当群体进化结束的 时候， 适应度值最大的那个个体对应的目标函数值最小， 这个 个体即为最优解。最佳个体的产生过程是这样的：首先产生 一个初始化种群，然后对初始化种群中的每一个个体进行适 应度的计算，得出个体对环境的适应程度。计算后的这个个 体能否满足准则判定， 如果能够满足， 那么算法就找到了这个 个体并停止计算， 如果不满足准则判定， 那么算法将会对这个 种群进行选择、 交叉、 变异等相关操作。遗传操作的目的是从 初始化种群中筛选出较优的个体， 之后进行演变， 对演变后的 子代群体， 再重新进行优化准则的判定， 如此循环下去， 直到 找到一个最优的个体， 或者不满足其它循环条件为止。 约束条件和优化的目标有轻重缓急的分别,约束条件必须 满足,优先级别必须最高,同时， 各种优化目标之间也有优先级 的分别,应尽量满足级别较高的优化目标。 将它们都转化成罚 值, 而其罚值权则是不同的, 高一级的罚值权比所有低级的罚 值的和值还要大。 由此可以得出,采用静态定标罚值权的方法 是不可取的,因此我们采用动态罚值权的定标方法。 遗传进化 在进行选择的操作过程中,我们着眼于目标函数或者适应度函 数的相对值而并不关心它的绝对值,确定这个个体目标函数的 真正目的在于确定该个体在群体中的优劣,因此我们可以根据 整个群体情况进行罚值权的统一定标,把各级的罚值用向量进 行表示,此时， 目标函数就是各级罚值的带权和。 如果想终止可以采用以下方法： (1)给定一个迭代步数； (2) 当设定与估计的最优解的距离小于某个范围时， 就终 止搜索； (3)当与最优解的距离连续若干步保持不变时， 就终止搜索。 排课问题同样是一个 N-P 问题，无论应用哪种方法冲突 问题的出现都不可能避免。但是，解决冲突问题的方法有很 多种,这里采用一种利用二进制 0、 1 矩阵检测冲突的方法。 在 冲突检测过程中其基本的约束条件为： (1)任何教师在同一时间最多只能安排一门课。 (2)任何班级在同一时间最多只能安排一门课。 (3)任何教室在同一时间最多只能有一门课程被安排。 为了避免冲突的出现， 在本系统的设计、 实现过程中引进 了冲突检测函数， 保证当排完一位教师的所有相关课程后， 系 统就会通过该冲突检测函数对这位教师课程安排的冲突情况 进行检测并做出相应的修正。 参考文献： [1] 毕晓君.信息智能处理技术[M].北京： 电子工业出版社， 2010. [2] 陈强.通用高校排课算法研究[J].科技广场， 2006 年 第 07 期. [3] 张文修， [M]. 西安:西 梁怡.遗传算法的数学基础 （第 2 版） 安交通大学出版社， 2003. [4] 潘以锋.高校智能排课系统的算法[J].上海师范大学学报(自 (10) . 然科学版)， 2的感受， 这样不仅调动了 他们的兴趣， 同时也大大提高了教学效果； 其次， 园林树木学教 师本身应利用一切机会到各地考察、 研究， 在专业知识方面进 一步完善自己， 在课堂讲授中就会做到绘声绘色。作为学生， 则必须对实验和教学实习格外重视。在教学时数不断缩短的 情况下， 理论课教学必须是突出重点， 不可能面面俱到。学生 只有在实验和实习过程中， 依靠自己亲手的观察和解剖， 才能 对一些结构、 概念和术语理解透彻， ?使课内知识进一步深化， 做到永生不忘。 园林树木学这门学科实践性很强， 必须经过从 课本到实际观察， 再到课本几个来回的重复， 才能够对树种的 形态特征了如指掌。如： 学生到山上实习， 让他们投入到大自 然的怀抱， 在老师对现场树种的讲解下， 学生边认树木边采集 标本， 通过大量的实物， 使学生很轻松、 自如掌握了知识要点， 很顺利的就记住了每种园林树木的特征、 特性， 同时还培养学 生观察、 思维、 动手、 综合解决生产实际问题和创新等能力， 与 学生呆在枯燥的实验室里， 面对变形的干标本相比， 学习效果 明显要强得多。寓教于乐， 在游玩中认识了不少树种， 是最有 效的授课方法。 4 重视学生学法指导， 培养学生自学能力 哈佛大学教学理念： 学习是为了有能力继续学习。 一个优 秀的学生不是老师教出来的， 而是在老师的指导下学出来的。 方法是运用知识的桥梁。 在教学过程中， 教师只有依据学生的 特点， 结合相应的教学内容， 有意识地渗透有科学性、 有针对性 的学法指导， 融教法与学法为一体， 才能使学生养成良好的学 习习惯， 掌握科学的学习方法， 最终实现教师 “授人以渔” ， 培养
查找方便、 检索迅速、 可靠性较高、 保密性较好、 存储量较大、 人工成本较低、使用寿命较长等。这些优点可以极大地提高 排课管理工作的效率。排课系统是对一个教育单位而言是不 可缺少的重要组成部分,排课效果的好坏直接影响到教学工作 能否有序地、 正常地开展， 对于学校的领导来说也是一项至关 重要的工作,因此排课系统必须为用户提供充足的信息以及快 捷的查询手段。利用计算机进行排课操作，任何具有使用者 都能够清晰的看到教学中的各种信息， 可以高效、 快速的工作， 这不但减轻了教务人员手工排课的工作，而且极大提高了管 理工作的效率， 可以合理高效地分配、 利用教学资源， 间接地 提高了教学质量， 推进了教学活动的良性循环。因此， 研究并 改进一个排课系统具有十分重要的实际意义。 2 排课原则 排课问题实质上一种资源竞争问题。在排课过程中要全 面考虑教师、 课程、 教室、 时间、 学生人数等多方面因素， 做到 统筹兼顾， 才能排出即符合教学规律， 又满足各方面要求的课 程表。一个好的课表应该既能符合学校的管理要求，又能满 足所有参与者的基本要求，尽量使绝大多数课程的安排能够 令学校师生满意。为了达到这样的目的，在排课中必须遵守 以下六个基本原则： (1)在同一时间段内， 一位教师只能安排一门课程。 (2)在同一时间段内， 一个班级只能安排一门课程。 (3)在同一时间段内， 一间教室只能安排一门课程。 (4)根据能提供的教室总数安排同一时间段内安排的课程 总数， 二者要相适应。 (5) 每门课程的学生人数不应大于所安排教室的座位数， 二者也要相适应。 (6) 多媒体教室应合理安排， 因为有的科目用多媒体设备 教学的效果比较好， 但是有的科目并不需要多媒体教室， 如果 安排了多媒体， 就造成了教学资源的浪费。 同时， 为了使排出的课表更具人性化、 更合理、 更科学， 排 课还需要考虑以下五个因素： (1)尽可能保证同一个班级连续的两门课之间更换教室的 机率最小， 或就近安排。 (2)每门课程在一周内的上课时间尽可能合理分布。 (3)同一门课程的不同上课时间应尽可能安排在同一间教 室， 同时要隔一天以上再安排， 以给任课教师留出充足的备课 和批改作业的时间，使学生也有足够的时间复习和消化所学 的内容， 并有时间预习下次课的内容。 (4) 学生每天必修课的安排尽可能趋于合理、 平衡， 应尽量 避免出现全天有课， 而第二天一天没课的情况。 (5) 满足个别教师(如外聘教师)的特殊上课时间要求。 3 遗传算法在排课问题中的应用 遗传算法应用类似基因演化的循环过程，它的演算过程 如下： (1)根据排课的因素产生相关基因编码和染色体,并随机产 生一定数目的初始种群， 即一定数目的班级课程表。 (2)对个体， 即班级课程表适应度进行评估, 如果个体的适 应度与优化准则相符, 则输出最佳个体和它所代表的最优解, 并结束计算,否则进入第 （3） 步。 (3)依据适应度情况选择再生个体。 (4)按照一定的交叉概率及交叉方法生成新个体。
教育科学
与 人才培养
遗传算法在大学排课问题中的应用
□ 王 维 陈满林 胡冠宇
130012） （长春工业大学软件职业技术学院 摘 吉林・长春
要：针对排课问题， 基于遗传算法的特点分析了解决排课问题的可能性, 介绍了排课原则， 以及遗传算法在
排课问题上的应用性研究， 利用遗传算法进行编码， 交叉、 变异， 以及进行冲突检测,用遗传算法解决这一复杂的 NP 问题。 关键词：排课 遗传算法 最优解 冲突检测 文章编号：1007-3973（2010）09-167-02 大学课表的编排不但数量多、 规模大、 涉及的因素多、 限 制条件多， 而且结构复杂， 要想编排出合理、 科学的课表必然 要消耗大量的时间与精力，它复杂性的原因在于排课中资源 约束条件与特殊要求对有限时空目标的限制。由于近几年各 个高校连年扩招， 使得课程安排的工作量逐年增大， 学校自身 问题的逐步暴露， 这也给课程安排增加了许多的难度， 这些问 题主要包括： 教室资源的不足、 师资力量的不足、 多媒体教学 设备的不足等， 这些问题的出现对排课工作提出更高的要求。 伴随着科学技术的不断发展和提高,计算机具有的强大功 能已经被人们所深刻地认识,计算机应用技术也已经逐渐进入 人类社会的各个领域，同时在各个领域都发挥着非常重要的 作用。作为计算机应用技术的一部分, 通过计算机进行排课, 具有手工排课无法比拟的优点， 包括： 排课速度快、 省时省力、 中图分类号：O24 文献标识码：A
学生终身的学习能力。例如， 我与学生交流时发现， 学生普遍 感觉记忆园林树木种类特征、 科属特征、 拉丁文学名是一件很 枯燥的事情， 有些学生时间花费不少， 就是记不住。我告诉他 们理解是记忆的前提， 记忆是理解的过程， 如果不理解而硬背， 只能成为知识的 “容器” 。 并总结了在理论结合实际的基础上， 运用主要树种法、 常见法、 本地法、 要点法、 比较归纳法、 总论指 导法、 各论主体法、 识别基础法等多种方法， 实践效果良好。 如： 园林树木的科、 属、 种虽然很多， 但相似的科与科、 属与属、 种与 种之间的形态特征等却有一定的规律， 采用比较法找到这一规 律， 即找出它们的相同特征和不同特征， 记忆将会成为一件比 较轻松的事情。通过比较， 不仅掌握的它们的规律所在， 强化 了记忆效果， 更掌握了园林树木学的重要学习方法。 由理解到 记忆抓知识的实质； 由分散到集中抓知识的积累； 由累加到串 联抓知识的结构； 由应试到应用抓知识的运用。这样， 学生在 学习中通过主动思考， 积极思维， 就能实现学习目标。学会学 习是时代发展的需要， 更是学生终身学习与发展的需要。 综上所述，教师在教学中要灵活运用各种有效的教学方 法， 努力探索， 从而达到最佳教学效果。 参考文献： [1] 邱国金, 孙贤琦, 刘国华.高职 《园林树木学》 课程的教改 研究与实践[J]. 中国农业教育,2003.02. [2] 沈大刚《园林树木学》 . 课程的教改研究与实践[J].安徽农 业科学,2009.02. [3] 陈建《园林树木学》 . 教改初探[J].安徽农业科学, 2007.08.