基于遗传算法的排课系统研究

基于遗传算法的排课系统的研究

谷冰

（沈阳建筑大学 信息学院）

摘 要：排课问题是一个有约束的、多目标的组合优化问题，并且已经被证明为一个NP完全问题。本文主要基于遗传算法，结合排课系统的一些具体需求，研究并实现一个排课系统。 【关键词】排课问题；遗传算法；组合优化 一、背景

近年来随着大学扩招，大学生人数的增加，每学期的排课问题一直是学校一项巨大的工作任务，使用人工手动排课对于这样一个庞大的课程体系来说简直是天方夜谭。其中，最突出的问题就是班级多、课程多、教师少、教室少，从而导致传统的手工排课方法，由于工作量巨大、效率低下，容易出错已经不能满足需求；因此，研究计算机排课系统有重大的现实意义。

二、遗传算法

遗传算法（Genetic Algorithms，GA）是根据自然界的选择和进化原来发展起来的高度并行、随机、自适应的随机搜索算法。其模拟达尔文的适者生存原理，每个种群所面临的问题是寻找一种对复杂和变化着的环境最有利的适应方式。

遗传算法维持一个潜在的群体（染色体、变量），定义一个函数为：

tt

P(t)={ x1??,xn}

染色体通常形成是一串的数组，近年来基于实数编码的遗传算法也得到广泛的应用。每个解用其“适应值”进行评价其优劣程度。然后通过选择更新（t+1次迭代）个新的群体。新群体的成员通过杂交和变异进行变换，以形成新的解。杂交组合了两个亲体染色体的特征，并通过交换父代相应的片段形成了两个相似的后代。例如，如果父代用五维向量来表示，如下：

(a1 ,b1 ,c1 ,d1 ,e1)，(a2 ,b2 ,c2 ,d2 ,e2) 在第二个基因后杂交，染色将产生后代 (a1 ,b1 ,c2 ,d2 ,e2)

杂交算子的意图是在不同潜在解之间进行信息交换。

变异是通过用一个等于变异率的概率随机地改变染色体上的一个或多个基因。变异算子的意图是向群体加入一些额外的变化性。

我们可以把遗传算法简化以下步骤：

1) 产生初始遗传群体的方法。

2) 用“适应值”评价解的适应度的评价函数。 3) 改变后代组成的遗传算子。 4) 遗传算子所使用的各种参数：

流程图如图1。

实际问题集 编码形成染色体 产生初始种群1 计算其适应度 选择一个个体 选择两个个体 选择两个个体 复制新种群 杂交操作 变异操作 产生种群2 经过优化的种群 解决实际问题

三、排课问题

高校排课涉及到教师、班级、课程、教室和时段各个复杂的因素，衡量一个课表的好坏通常有硬约束和软约束两大类，硬约束有:

1. 一个教师或者一个班级或者一个教室在同一时间段内只能安排一门课程； 2. 分配的教室可容纳人数应该大于学生数。 软约束有：

1. 在对于一个教师、班级、教室每天安排尽量均匀。 2. 不同类型的课程能按不同的优度安排相对较好时段。

四、排课系统设计

遗传算法首先要考虑的是如何表现其问题，即如何对染色体编码，使之适用于遗传算法操作。

1． 编码：考虑到程序的可操作性，用十进制编码方式来表示。 （1） 教师ID编码格式，用6位表示为：

1-5 职称 0-9 入学年份 1-9 系/学院 0-9 1-9 系/学院 0-9 教研室 0-9 专业 0-9 1-9 0-9 教师编号 0-9 班号 1-9 （2） 班级ID编码，于教师ID形式，用6位表示： （3） 课程ID编码，用10位表示【2】： 2或3 一次2或3节课 1-9 上课班级数 1-9 1-5 0-9 1-3 每周有几次课 0-9 0-9 0-9 0-9 课程上课人课程性类型 数等级 质 课程原始编号 其中课程类型：1-9分别可以用来代表普通课、体育课、实验课、实践课等等；上课人

数等级：1代表50人以内，2代表50到100，3代表100到150，4代表150到200，5代表200以上；

课程性质：1为专业课、2为非专业课

如每周4节的“网络基础”课程表示为2151322512 （4） 教室编码，用6位表示： 0-9 教室类型 0-9 楼号 1-9 0-9 0-9 楼内编号 0-9 2． 种群操作

（1） 初始化种群。初始化的目的是为了以后的遗传操作产生种群。在此，本文采用

以教师作为染色体：

首先根据教学任务书中教师、班级和课程的对应关系，对染色体的教师ID、班级ID和课程ID进行编码并组合。根据课程ID中课程类型的要求以及教室分类表随机分配教室；再根据课程ID中上课次数和上课节数随机安排时段；最后根据染色体编码方案产生初始化种群。

（2） 选择操作，本文采用按比例的适应度分配法。

（3） 交叉操作。交叉是根据选择操作的结果，选取一对染色体作为父个体，再取一

随机值（设为r）与系统预设的交叉率值（设为t）比较，若r

按染色体编码方案，我们选择最简单的单点交叉方式，交叉点为第23位，也即交换两个染色体的教室编码和时段编码，这样不会影响到每位教师所教授的课程，也不会造成教师课表内含其他教师的教授课程或每代演化后染色体结构不合理等问题。 五、结论

本设计以matlab实现排课系统，并以某高校2009-2010年第二学期的实际数据进行测试，样例数据结果无教室冲突、无时段冲突、无教师冲突，课程安排间隔比较合理，结果较为满意。

实现自动排课问题是一项艰巨的任务，但其意义非常重大，至今仍没有一套完整，成熟的方案来实现。本文根据遗传算法的基本原理，并根据实际需求，大胆创新，对排课中的约束性等问题提出了一套适用的方案，基本满足了实际工作中的需求，但对于多项限制条件等排课问题求解，仍没有达到最优解，这对于多说研究人员来说是继续探讨的课题，希望在排课领域的研究有所长者给予指正。 【参考文献】

【1】王力.高校通用排课管理系统设计与实现【J】.计算机应用，2002（5）：37,38,42. 【2】谭定英,蔡逸仪,李学征.基于遗传算法的排课系统研究【J】.现代计算机:下半月版,2009(9).

【3】周明,孙树栋.遗传算法原理及应用.国防工业出版社,1999.

本文来源：https://www.bwwdw.com/article/ucir.html