资源描述：
《排课问题的数学模型构建与遗传算法论述》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、排课问题的数学模型构建与遗传算法论述----大学教育论文-->排课问题的数学模型构建与遗传算法论述[摘 要]分析了排课问题的数学模型,提出了一种遗传算法.该算法采用矩阵编码方案,建立罚函数满足课表问题中的多重约束条件.结果表明,该算法能比较有效的解决排课问题.[关键词]排课问题多重约束条件遗传算法适应度函数课程表问题又称时间表问题.课表编排是一个多因素的优化决策问题,是组合规划中的典型问题.课程表的编排就是解决对时间和空间资源争夺而引起的冲突.理论和实践表明,只要课程表所涉及的信息量稍有增加,就会导
2、致“组合爆炸”,使得编排方案剧增.Even等人证明了时间表问题是一个有NP难度的问题,之后很多人尝试采用各种方法对此问题求解.国内学者在排课问题方面也曾经作过一些研究,但运行结果尚存在有待改进的地方,排课效果不尽满意.认为,问题在于在建立数学模型时,排课问题的约束条件考虑得不够完善.1 排课中的基本问题在课表编排问题中涉及到班级、教师、时间、课程、教室等5个相互制约的因素.课表问题的求解过程就是对任何一门课寻找一个合适的老师和合适的时间一教室对,在安排时不能发生冲突,同时尽量满足经验常识.课表问题的
3、冲突情况:1)同一时间,一个教师同时上一门以上课程;2)同一时间,一个班级同时上一门以上课程;3)同一时间,一个教室同时上一门以上课程;4)选课人数大于当前指定的教室的最大容量.这一类冲突是绝对要避免的,否则教学无法进行.同时须满足的一些经验常识:1)一门课在一周内分散安排,提供可引导性学习环境;2)保留一些特殊的时间,如户外活动;3)一周多学时的同一门课应尽量安排在一个教室(方便教师及学生);4)尽量安排在好的教学时间点(如上午比下午好);5)安排到教室中的人数应尽量和教室的大小吻合,一方面资源合
4、理利用,另外教学效果也好;6)希望一天中上同一门课的次数不要太多;7)有的老师会喜欢上连堂等等.这一类冲突并不是绝对要避免的,只是会影响到教学效果.2 用遗传算法求解排课问题遗传算法(GeicAlgorithms,缩写GA)[1]是20世纪60年代后期Hollan创建的,一种基于自然选择和遗传变异的迭代自适应概率性搜索算法.近几年,遗传算法作为问题求解和最优化的有效工具,引起越来越多的注意.染色体是二进制字符串编码,每一个编码字符串为一候选群,这种染色体有多个,即有一群候选解.染色体是主要的进化对象
5、,像生物进化一样有繁殖、交叉和突变3种现象,这些现象称为遗传算子.遗传算法在每一次迭代时产生一组解答,这组解答最初是随机生成的,在每次迭代时又产生一组新的解答,它由模拟进化和继承的遗传操作生成,每个解答都由一个目标函数给予评价这一过程不断重复,直至达到某种形式上的收敛.新的一组解答不但可以有选择地保留一些目标函数值高的旧解答,而且可以包括一些与其它解答相结合而得到的新解答.2.1 编码及染色体表示在演化算法的设计过程中首先要确定编码方案[2].在经典的遗传算法中,常采用10进制或2进制的编码方法,在
6、所做的试验中,考虑到课表的实际特点,采用矩阵编码.一个矩阵Y表示一个可能的排课表.矩阵Y的行值为课程编号,课程编号是对学校全部班级的所有课程进行统一编号,列值为时间段号,时间段编号是对所有教室的时间段统一编号,若课程i的某一次课安排在时间段j,则yij为1,否则为0.同时引进辅助矩阵X,其行值对应全部教师的编号,列值为在一周内可用的时间段编号,它记录了在不同的时间段每个教师要上课的次数.这样,就建立了老师与班级、课程之间的联系.2.2 模型的建立在做之前必须先做一些必要的约定.假设教师集合为T={t
7、1,T2,…,Tm},班级集合为S={s1,s2,…,sm},其中m-T
8、表示教师数,~ω为一周内可用的时间段数,n=
9、S
10、表示班级数,P为学校全部班级的课程种类数,q为一周时间内各个教室的时间段数总和,r为全校可用的教室总数.λ1,λ2,…,λm}是针对排课表可能产生的不同冲突而采取的惩罚值2.2.1 约束条件 1)绝对要避免的硬性冲突:a)某一教室的某一时间段只能被一门课程占用,即b)某一时间段一个教师只能上一门课程,即c)某班学生在同一段时间内只能被安排在一个教室上课,即2)并不是绝对要避免的
11、软冲突 同一课程不要在连续的时间段内开课,即2.2.2 数学模型其中:λ1,λ2,λ3是针对硬冲突所引进的惩罚值,λ1,λ2,λ3取值为3;λ4是针对软冲突而引进的惩罚值,取值为1;这个式子量化了冲突,其数值越小,说明课表方案越好.2.2.3 适应度函数 整个遗传算法是在适应度函数的引导下进行的,笔者给出的适应度函数f=1/g,其中g为式(1)给出的函数.可见,冲突越多,适应度越小,被选中遗传的机率越小,符合自然进化的规律.2.3 遗传操作2.3.1 初始化 初始化部
