1 研究目的
排课之所以是学校教务管理工作中的一个难点, 原因在于在排课的过程中需要考虑课程、教师、教室要求等诸多资源的合理化、最优化配置。传统的手工排课易于出错而且非常麻烦, 例如, 我院排课员排完一个年级的课程至少需要一整天的时间。实际排课中, 存在大量纵横交错、相互制约的不确定因素, 使人工排课变得更加繁锁、复杂。因此, 设计一个自动排课的程序可以使教务管理从繁杂的人工活动中解脱出来, 真正做到教务管理科学化、正规化、现代化。
2 系统总体设计
2.1 排课系统应能实现如下功能
(1) 资源查询:用户可按照校区对教师和教室及课程的分配情况进行查询。
(2) 用户网上申请:用户登录系统时需先进行用户信息注册、提交;管理员登录系统时可进行数据库信息的更新和用户权限的分配。
(3) 教学资源的维护:管理员可对系统的记录进行修改和上传。
(4) 排课查询:用户可以输入个人信息来查询教师和教室及课程的分配情况。
(5) 帮助:提供详细的系统使用说明。
其中, 资源查询将面向全校所有师生员工开放, 用户信息由分配用户权限的管理员通过验证机制使系统导入不同的界面。
2.2 系统构架
通过对客户需求的分析, 系统划分为用户和管理员两个接口, 资源管理模块、排课管理模块和使用帮助三个模块。
3 排课管理模块的设计
用户在整个系统的使用中会启动排课模块进行排课, 而这一模块的应用是整个系统的核心, 因此, 该模块的设计是关系到系统性能是否优良的关键。
3.1 遗传算法及其思想
遗传算法 (GeneticAlgorithm, GA) 是一类以Darwin自然进化论和Mendel遗传变异理论为基础的求解复杂全局优化问题的仿生型算法, 基于适者生存, 优胜劣汰的进化原则, 对包含可能解的群体反复使用遗传学的基本操作, 不断地生成新的群体, 使种群不断进化, 同时以全局并行搜索技术来搜索优化群体中的最优个体, 以求得满足要求的最优解或准最优解。GA可广泛用于组合优化、机器学习、规划设计、人工神经网络训练和图像处理等领域, 是生物遗传学和计算机科学的有效结合[1]。其研究思想是从一个种群开始的, 而一个种群由经过基因编码的一定数目的个体组成。初始种群产生后, 按照适者生存的原理, 逐代演化出越来越好的近似解。在每一代, 通过交叉和变异操作, 产生出新的种群。在新一代中, 根据适应程度选择部分适应能力强的后代, 淘汰部分适应能力差的后代, 从而保持种群大小的稳定性。这样经过若干代后, 算法收敛于最好的基因个体。
3.2 编码
遗传算法中的进化过程是建立在编码 (Encoding) 的基础上的。遗传算法实现的第一步就是对基因进行编码, 将实际问题中的课表转化为计算机可以识别的变量。如何将课表转化为基因编码是利用遗传算法解决排课问题中的首要问题。
Holland的编码方法是二进制0, 1串, 其优点是编码、解码操作简单, 一目了然, 交叉、变异等遗传操作便于实现。
同时考虑到现行绝大部分高校课表的时间制度是每周最多5天, 每天最多4次课, 1次课为2学时, 程序中采用长度为20的二进制编码来表示课表基因。1表示有1次课, 0表示没有课。如下面这个课表就可以用一个基因Gene来表示。
如图1所示。
3.3 交叉
简单的交叉 (即单点交叉) 可分两步进行:首先对配对库中的个体进行随机配对然后在配对个体中随机设定交叉点, 配对个体彼此交换部分信息[2]。考虑到课表问题的特殊性, 我对单点交叉操作做了一些改进。为了保证交叉以后基因的周课时总数不变, 程序对交叉点的选择加了一个判断条件:当两个基因在交叉点前面的1相等时, 则进行交叉。
交叉产生两个子代:
子代a:10110001000010001100
子代b:00101110100100101000
3.4 变异
变异操作是按位 (bit) 进行的, 即把某一位的内容进行变异。对于二进制编码的个体来说, 若某位原为0, 则通过变异操作后变为1, 反之亦然, 变异操作也是随机进行的[2]。
如变异操作时随机产生两个变异点x, y。设变异前的基因为Gene, 为了保证变异有效, 即变异后, 基因要发生变化, 程序对变异操作增加了对有效变异的判断。当Gene[x]+Gene[y]=1时, 交换Gene[x], Gene[y的数值就产生了新一代的基因, 记做G e n e_n e w。
3.5 适应度函数的设计
适应度函数是评估选择操作的依据, 适应度函数的设计直接影响到遗传算法的性能[2]。在对适应度函数的设计过程中, 我们用课时质量来衡量某一时段的学习效率, 一般情况下, 我们希望难度较大的课程排在上午, 如计算机系的C语言。
表1中所表示的是课时质量, 我们把它放在一个长20的串String中, String={1.0, 0.8, 0.6, 0.4, 1.0, 0.8, 0.6, 0.4, 1.0, 0.8, 0.6, 0.4, 1.0, 0.8, 0.6, 0.4, 1.0, 0.8, 0.6, 0.4}。
假设基因Gene中有课的时段数, 即1的个数为class_sum, 基因对应的难度系数为Hardness, 难度系数是一个介于-1到+1之间的浮点数, 则难度系数越高表示课程越难, 反之亦然。
则课时质量为
3.6 遗传算法的流程
根据遗传算法思想, 设计了如下的流程:
Step1:设定初始群体和循环代数。注意群体和循环代数的设定。如果过大则程序的运行时间会过长, 如果过小, 排课质量就会下降, 经过反复试验数据, 我认为可设定群体population=20, 循环代数generation_max=40。
Step2:产生population个初始基因作为第一代原始群体, 并令generation=1。
Step3:如果generation>40则结束遗传算法, 否则继续执行。
Step4:群体中前population个基因直接保留到下一代, generation=generation+1。
Step5:对群体的前population个基因进行交叉操作, 产生population个新基因, 将新基因加入到新一代群体中;对群体的前population个基因进行变异操作;将新基因加入到新一代群体。
Step6:对新一代群体中3*population个基因分别利用适应度函数计算并排序, 值越大的越靠前。
跳转到Step2。
3.7 遗传算法性能测试
我以种群规模为20, 遗传代数最大值为40进行算法性能测试, 得到下面的结果。
由下图可以看出遗传算法在刚开始时能够很快地收敛到近似最优解附近 (如1-17代) , 但却会在最优解附近徘徊很久才收敛到最优解。原因是遗传算法的设计很难在收敛速度和收敛于最优解之间取得平衡。算法采用的参数往往是经过多次测试而获得的经验参数, 这也是遗传算法的一个明显的缺点[3]。
如图2所示。
摘要：排课是学校教务管理中需要解决的重要问题, 该排课系统的应用为解决这一问题提供了重要参考价值。系统的主要功能是排课模块的设计, 该论文重点研究了遗传算法在系统中的应用, 即以遗传算法为理论基础, 通过编码、适应度函数的设计等实现排课问题。
关键词：排课,遗传算法,编码,适应度函数
参考文献
[1] C.C.Gotlieb.The Construction ofClass-Teacher Time-Tables[Z].1963.
[2] 周春光, 梁艳春.计算智能人工神经网络模糊系统进化计算[M].吉林大学出版社, 2001 (2) :40～150.
[3] 唐勇, 唐雪飞, 王玲.基于遗传算法的排课系统[Z].2002.