1、基于遗传算法的智能排课系统的设计和实现摘要：本文针对遗传算法后期收敛速度慢，易陷入局部最优的困境，提出了改进方案，有效解决了智能排课问题。 关键词：遗传算法 ；排课问题；组合优化 中图分类号：N945.23 文献标识码： A 文章编号： 排课是一个比较复杂的过程，对于特殊课程的排课采取的是手动方式，而一般课程则采用自动方式。在自动排课前需要对一些参数进行初始化，课表生成后可以进行人工调整。 1 排课的约束条件 在排课的过程中，有些硬性约束条件必须遵循：如教师、教室、课程、时间和地点均不可存在冲突；也有一些软性约束因素值得考虑，这样能使课表更加的合理和人性化，如专业课尽量安排在效率较高的时间段；
2、尽量满足某些教师的特殊上课时间要求；同时排课也不能太零散，要尽量减少教师来校的次数；应尽量避免学生一天课程很满而另一天却整天没课的情况，学生的上课时间不能安排得太过集中；在某个时间段不做任何教学任务的安排，以便教师和学生能利用这个时间开展一些课余活动。 2 排课的遗传算法设计 2.1 遗传算法流程设计 遗传算法的核心内容包括：参数编码、初始群体的设定、适应度函数的设计、遗传操作设计及控制参数设定1。 （1）基因编码：对课程和授课教师进行组合编码，可以采用教师编号（5 位）+班级编号（5 位）+教室编号（4 位）+课程编号（6 位）+周学时（2 位）+特殊要求（6 位）的编码方式。 （2）产生初
3、始种群：首先把固定教学时间段的教师编码填入对应的时间段中，然后产生一个 120 的随机数，根据产生的随机数在相应的位置填入该班的其他教师编码。若填入的位置已有数据，则重新产生随机数，直到所有的教师编码无重复地填入数组。如此循环直至产生满足种群规模数量的个体，组成初始种群。可以看出，上述方式产生的。 （3）冲突检测：初始种群个体含有大量的冲突4，由于我们在编码已经考虑到时间、班级、教室避免同时上一门以上课程的冲突，因此，只需对同一时间，同一个教师同时上一门以上课程的冲突进行检测和消除。 （4）冲突消除5：读取第一个课程表二维数组 KCB(BJS，20)中第一个数据（教师编号） 。将读取的数据与
4、KCB 数组中该列下一行的数据进行比较，若一致，则选择该行随机列的数据，若可以调整，则互换这两个数据；若不可调整则再次对该行随机列的数据进行选取，直到数据互不相同。取该列第三行数据，重复操作至该列所有数据互不相同为止。读取 KCB（1，2） ，重复以上过程，直至每列数据互不相同，则冲突消除。该算法的对提高遗传算法处理效率有明显效果。 （5）构造适应度函数：构造函数 f(1)：考察多个教学时间段课程尽量分散度；函数 f(2)：教师每天授课任务均衡度；函数 f(3)：学生课时分布均衡度；函数 f(4)：课程安排时间适宜性。得到适应度函数为：其中，k(i)为权值。 （6）遗传算子 选择算子：模拟生物
5、界中的优胜劣汰的自然选择过程，采用赌盘法（如图 2 所示） ，将适应度高的个体放在轮盘较大区域，适应度低的放在轮盘的较小区域，则选择适应度高个体的几率会明显增大，从而筛选出适应度较高的个体6。 图 1 赌盘选择法 交叉算子：选择父本个体后随机选出两个个体，随机确定一个数作为交叉位置进行互换操作，如两父本个体 F1、F2，位置为左起第 6 位，则： 父本：F1=12345 6 789 F2=98765 4 321 产生子代：P1=12345 4 789 P2=98765 6 321 变异算子：在染色体上随机选择两点，将对应数据进行反转，如： 325 321 257 变异为 325 123 257
6、 （7）参数设置 种群规模，不宜过大也不宜过小。过小减弱群体多样性，可能不存在最优解；过大则会增加计算量，降低算法的运算速度。交叉率，交叉概率取值过大时，会近亲繁殖，失去活力；过小对系统不利。一般认为取值在 0.60.9 之间，本系统取 0.7。变异率，变异概率较大时，会使遗传算法变成随机搜索；当变异概率较小时，新个体的产生会少。进化迭代数，为了使最终结果既收敛又能达到最优，那么遗传代数的取值应该足够大，本文遗传代数取值为 1000。 3 实例测试及分析 本系统利用 Matlab 7.6 进行了模拟测试，用到的数据如表 1 所示： 表 1 实验数据 （1）种群规模 选取三个对照组进行实验： 表
7、 2 种群规模对排课效率的影响(单位：秒) 由表 2 可以看出，种群的规模越小，时间越短，效率也就越高。 (2)交叉概率 表 3 交叉概率对排课效率的影响(单位：秒) 从表 3 中观察到，交叉概率的取值较大时，它对系统效率的影响则较小。经过反复分析，本系统 Pc 取值为 0.7。 （3）变异概率 表 4 变异概率对排课效率的影响 从表 4 看出，过大会使算法的稳定性低，过小又会使得全局搜索难以进行，并且很难有较好的模式产生。 基于以上数据，可将排课求解过程中所需要的参数值设置如表 5 所示： 表 5 参数设置 实际求解效果如图 3 所示： 图 3 遗传进化过程适应度值变化曲线 4 结论 实验证
8、明，应用遗传算法解决排课问题时收敛效果是比较好的。 参考文献： 1张春梅,行飞.用自适应的遗传算法求解大学课表安排问题J.内蒙古大学学报:自然科学版,2002,33(4):459464 2徐艳斌.基于遗传算法的高校排课系统设计与分析.广东工业大学工学硕士学位论文D,2007,3547 3胡小兵,鲁宏伟,基丁.模糊专家系统的排课系统关键技术研究.电力学院学报(自然科学版),2001:16(4) 4朱冠宇,王乘,席大春.利用遗传算法求解中学课表安排问题.计算机工程与应用,2004(27):215,218 5孙建平,曾经梁.一个综合应用人工智能技术的课表专家系统.微机发展,2004(5):72,86 6业宁,梁作鹏,董逸生.一种基于遗传算法的 TTP 问题求解算法.东南大学学报(自然科学版),2003(1):4144
