张永宏,王永吉,付立军,李 旭,胡胜文

1(中国科学院大学 工程科学学院,北京 100049)

2(中国科学院 软件研究所,北京 100190)

3(中国科学院大学,北京 100049)

4(中国科学院 沈阳计算技术研究所,沈阳 110168)

5(山东大学 大数据技术与认知智能实验室,济南 250000)

6(北京市中关村中学,北京 100086)

1 引言

排课问题是一个组合优化问题,20世纪60年代初,Gotlieb 提出了一个关于课程表,并使用算法求解了三维线性规划问题.在这之后,学术界对这一问题展开了逐步深入的讨论,讨论关注在求解方法的复杂度及问题是否一定存在解这两方面.20世纪60年代中期,Mihoc 和Balas 把求解课程表的数学表达式转化为了一个优化问题[1],之后有学者在排课的各种变量之间建立线性编程.有部分学者使用遗传算法[2,3]来解决这一类问题.遗传算法是模拟达尔文进化论自然选择的思想,是一种优胜劣汰的算法,适应环境能力差的个体,随着时间会被淘汰,剩下总群中的个体都是适应环境的个体[4].有些学者基于遗传算法做了一些优化工作,如使用两次遗传算法分别对学生分组和排课[5],排课中将每个年级的班级分为若干个组再进行排课[6],基于模式的改进遗传算法[7],二元变异算子代替传统的变异算子[8],结合水平集概念优化遗传算法[9],引入新的交叉算子及替换操作[10],提出退化混沌突变算子进行优化[11],使用遗传算法和其他算法组合的方式对排课问题进行求解[12,13]等.

这些探索使得遗传算法在解决排课问题上,具有针对课表迭……