分析排课问题的数学模型
[摘 要]分析了排课问题的数学模型,提出了一种遗传算法.该算法采用矩阵编码方案,建立罚函数满足课表问题中的多重约束条件.结果表明,该算法能比较有效的解决排课问题.
[关键词]排课问题 多重约束条件 遗传算法 适应度函数
课程表问题又称时间表问题.课表编排是一个多因素的优化决策问题,是组合规划中的典型问题.课程表的编排就是解决对时间和空间资源争夺而引起的冲突.理论和实践表明,只要课程表所涉及的信息量稍有增加,就会导致“组合爆炸”,使得编排方案剧增.Even等人证明了时间表问题是一个有NP难度的问题,http://www.51lunwen.org/jylwfw/之后很多人尝试采用各种方法对此问题求解.国内学者在排课问题方面也曾经作过一些研究,但运行结果尚存在有待改进的地方,排课效果不尽满意.作者认为,问题在于在建立数学模型时,排课问题的约束条件考虑得不够完善.
1 排课中的基本问题
在课表编排问题中涉及到班级、教师、时间、课程、教室等5个相互制约的因素.课表问题的求解过程就是对任何一门课寻找一个合适的老师和合适的时间一教室对,在安排时不能发生冲突,同时尽量满足经验常识.课表问题的冲突情况:
1)同一时间,一个教师同时上一门以上课程;
2)同一时间,一个班级同时上一门以上课程;
3)同一时间,一个教室同时上一门以上课程;
4)选课人数大于当前指定的教室的最大容量.这一类冲突是绝对要避免的,否则教学无法进行.同时须满足的一些经验常识:1)一门课在一周内分散安排,提供可引导性学习环境;2)保留一些特殊的时间,如户外活动;3)一周多学时的同一门课应尽量安排在一个教室(方便教师及学生);4)尽量安排在好的教学时间点(如上午比下午好);5)安排到教室中的人数应尽量和教室的大小吻合,一方面资源合理利用,另外教学效果也好;6)希望一天中上同一门课的次数不要太多;7)有的老师会喜欢上连堂等等.这一类冲突并不是绝对要避免的,只是会影响到教学效果.
2 用遗传算法求解排课问题遗传算法(Genetic Algorithms,缩写GA)[1]是20世纪60年代后期Hollan创建的,一种基于自然选择和遗传变异的迭代自适应概率性搜索算法.近几年,遗传算法作为问题求解和最优化的有效工具,引起越来越多的注意.染色体是二进制字符串编码,每一个编码字符串为一候选群,这种染色体有多个,即有一群候选解.染色体是主要的进化对象,像生物进化一样有繁殖、交叉和突变3种现象,这些现象称为遗传算子.遗传算法在每一次迭代时产生一组解答,这组解答最初是随机生成的,在每次迭代时又产生一组新的解答,它由模拟进化和继承的遗传操作生成,每个解答都由一个目标函数给予评价这一过程不断重复,直至达到某种形式上的收敛.新的一组解答不但可以有选择地保留一些目标函数值高的旧解答,而且可以包括一些与其它解答相结合而得到的新解答.
2.1 编码及染色体表示在演化算法的设计过程中首先要确定编码方案[2].在经典的遗传算法中,常采用10进制或2进制的编码方法,在作者所做的试验中,考虑到课表的实际特点,采用矩阵编码.一个矩阵Y表示一个可能的排课表.矩阵Y的行值为课程编号,课程编号是对学校全部班级的所有课程进行统一编号,列值为时间段号,时间段编号是对所有教室的时间段统一编号,若课程i的某一次课安排在时间段j,则yij为1,否则为0.同时引进辅助矩阵X,其行值对应全部教师的编号,列值为在一周内可用的时间段编号,它记录了在不同的时间段每个教师要上课的次数.这样,就建立了老师与班级、课程之间的联系.
2.2 模型的建立在做之前必须先做一些必要的约定.假设教师集合为T = {t1,T2,…,Tm},班级集合为S = {s1,s2,…,sm},其中m-T |表示教师数,~ω为一周内可用的时间段数,n=|S|表示班级数, P为学校全部班级的课程种类数,q为一周时间内各个教室的时间段数总和, r为全校可用的教室总数.λ1,λ2,…,λm}是针对排课表可能产生的不同冲突而采取的惩罚值
2.2.1 约束条件 1)绝对要避免的硬性冲突:a)某一教室的某一时间段只能被一门课程占用,即
数学模型
其中:λ1,λ2,λ3是针对硬冲突所引进的惩罚值,λ1,λ2,λ3取值为3;λ4是针对软冲突而引进的惩罚值,取值为1
这个式子量化了冲突,其数值越小,说明课表方案越好.
2.2.3 适应度函数 整个遗传算法是在适应度函数的引导下进行的,笔者给出的适应度函数f =1/g,其中g为式(1)给出的函数.可见,冲突越多,适应度越小,被选中遗传的机率越小,符合自然进化的规律.
2.3 遗传操作
2.3.1 初始化 初始化部分的目的在于为后面的进化操作提供初始种群,它的适应度有可能是非常低的,但这并不重要.这里采用在空闲空间随机搜索的方法生成初始课表.
2.3.2 选择 选择运算又称繁殖,它用于模拟生物界去劣存优的自然选择现象.它从旧种群中选择出适应性强的某种染色体,放入匹配集中,为染色体交换和变异运算产生新种群做准备.适应度越高的染色体被选择的可能性越大,其遗传基因在下一代群体中的分布就越广,其子孙在下一代出现的数量就越多.有多种选择方法,在试验中作者采用的是适应度比例法(又称轮转法),在这种算法中某一染色体被选中的概率Pc= f(xc)/∑f(xi), (2)式中:xi为种群中第i个染色体对应的数字串;f(xi)是第i个染色体的适应度值;∑f(xi)是种群中所有染色体的适应度值之和.
2.3.3 交换 复制操作虽然能够从旧种群中选择出优秀者,但不能创造新的染色体,因此,遗传算法的开创者提出了交换操作,它模拟生物进化过程中的繁殖现象,通过两个染色体的交换组合,来产生新的优良品种.交换是对选择操作形成的配对库中,对个体随机配对并按预先设定的交换概率来决定每对是否需要进行交换操作.每一对要进行交换的个体,随机选定一交换点,该点即为染色体中的一列(即一个班级),然后将父代中的这一部分分别交换.这里针对排课问题的具体特点,采用了一种称为局部杂交的演化算子.个体(矩阵y)的每一行里面1的个数是很少的,这样在矩阵的每一列里1的个数不会很多,要达到使每一列1的个数不超过1的目的,交换其中随机选定的一行会得到很好的效果,并且节省机时.步骤:(a)设定交换概率Pc;(b)随机的利用择优选择产生两个体;(c)随机的产生[1,n]之间的随机数确定交换点;(d)交换随机点的各行.
2.3.4 变异 变异运算用来模拟生物在自然遗传环境中由于各种偶然因素引起的基因突变,它以很小的概率随机地改变遗传基因(表示染色体地符号串的某一位)的值.变异操作是按位进行的,即把某一位的内容进行变异.每个变异的位置是随机产生,一旦该位置产生后,变异的过程就是在它的同一列找另一随机位置,然后将这两个位置的数互换.步骤:(a)设置变异概率Pm;(b)随机的产生两个位置;(c)依据变异概率Pm交换两位置上的元素.
2.3.5 自适应的交换和变异概率 交换概率和变异概率的选取在相当大程度上影响算法的收敛速度和近优解的质量,为加快GAs的搜索效率和有效地防止陷于局部最优解,自适应地调整交换概率Pc和变异概率Pm,作者采用的自适应遗传算子为:
适应度函数值,favg是群体的平均适应度函数值;f′c是进行杂交的两个染色体串中适应度函数值较大者;fm是变异串的适应度函数值[3].由自适应的杂交概率和变异概率的定义可以看出,当前代的最优个体仍然保留,但较优的个体要多参加杂交和变异,以便搜索更多的区域,从而探查到更好的解.
2.4 实验结果作者所采用的编码方式能找到合理的课程安排,各门课程安排的时间段比较均匀,基本可以满足学校的要求.并且该方法编码简单,求解速度快,比较有效.不足:对于复杂的排课问题没有涉及,比如课堂人数没有限定,多媒体教室的特别安排等,有待改进.
[ 参 考 文 献 ]
[1] 凯利维茨.演化程序[M].周家驹译.北京:科学出版社,2000:16-34.
[2] 唐 勇,唐雪飞,王 玲.基于遗传算法的排课系统[J].计算机应用,2002,22:10.
[3] 熊伟清.用遗传算法求解时间表问题[J].微电子学与计算机,2001(5):30.
