为验证排考系统的运行效果本文对某高校第一学期全校.docx
- 文档编号:9609536
- 上传时间:2023-05-20
- 格式:DOCX
- 页数:17
- 大小:108.34KB
为验证排考系统的运行效果本文对某高校第一学期全校.docx
《为验证排考系统的运行效果本文对某高校第一学期全校.docx》由会员分享,可在线阅读,更多相关《为验证排考系统的运行效果本文对某高校第一学期全校.docx(17页珍藏版)》请在冰点文库上搜索。
为验证排考系统的运行效果本文对某高校第一学期全校
摘要本文针对监考安排问题,设置一般假设、确定约束条件,建立了多目标优化的数学模型;由于大规模监考安排组合的不可遍历性,本文设计了混合编码遗传算法,将排考问题简化为一个排列考试课程顺序的问题,通过初始化种群,及选择、交叉、变异算子,以求得近似最优解。
为验证排考系统的运行效果,本文对某高校2006-2007第一学期全校课程手册进行一定数据整理,在设定了一组各分目标权重和运行参数后,施用了排考系统。
排考系统所得结果令人满意。
本文的亮点是构造染色体的混合编码方法,这种方法很好的解决了搜索空间大大超过可行解域(种群繁衍过程中,产生大量无意义染色体)的问题。
本文设计的混合编码遗传算法可以推广到车辆调度、会议安排、超大规模电路板设计等有时间、空间等多重约束的多目标优化问题。
关键词时间表排考遗传算法
一问题综述
监考安排一般来说属于时间表问题(TimeTableProblem,TTP),集成了时间、空间等多重约束。
从教室(空间)的角度看类似装箱问题,但是又有时间约束及多个规划目标。
因此监考安排一个比单纯时间表问题、装箱问题、目标规划问题更复杂的特殊优化问题。
监考安排的对象可能十分庞杂,所以监考安排又是一个NP完全问题。
有很多学者对与监考安排密切相关的TTP进行了很多研究,运用的常见的方法有模拟退火,列表寻优搜索,约束满意等。
在文献[1][2]中,Hans-Joachim等人使用约束逻辑程序解决TTP问题,他将排课看成一个优化问题,加以一系列的硬约束和软约束,其中硬约束是必须满足的约束,软约束是尽可能满足的约束。
文献[3]中,Hana等人使用了一种变量解释方法,将教师,教室,课程等用变量表示,再对之实施解释。
在文献[4]中,Dorigo利用遗传算法对高中课程进行排课。
AndreaSchaerf在文献[5]中对各种排课算法作了一个综述。
总的来说,求最优解或近似最优解的方法主要有三种:
枚举法、启发式算法和搜索算法。
由于对文献的了解不够深入,本文采取了比较易于理解应用的遗传算法(启发式),并在其基础上做了混合编码设计,试图以这种比较新颖的全局优化搜索算法求得监考安排的近似最优解。
二基本假设
1、考试在日常上课的教室进行。
2、教室/考场数据(代码,可容纳学生/考生数)、考试课程数据(代码,考生人数,考生ID)为已知数据。
3、进入考试周后所有老师、学生、教室都将只有考试任务。
即不会存在上课与考试冲突等情况。
4、考试日可分为无差异的四个考试时间段,即在不考虑其它条件下,任一门课程均可在任一时间段进行考试。
5、教室/考场在考试期间不会发生变化,即如果一个教室/考场可用则其在每一考试时间段均可使用。
6、教师可为任一门考试监考。
三符号说明
1、N:
教室总数;M:
课程总数。
2、Ci=(ci,η)表示第i个教室,它可以容纳ci个考生,其教室类型为η。
i=1,2,…,N。
3、Sj=(sj,θ)表示第j门考试课程,它共有sj个考生,考试类型为θ。
j=1,2,…,M。
4、Ti表示第i个时间段。
5、R:
每个时间段可容纳的总考生数,显然
6、J={S
(1),S
(2),…,S(M)}代表一个排考次序。
7、Z(i)={Tj,Ck,Cl,…}表示S(i)被安排在第j个时间段和Ck,Cl,…这些教室。
(其中i∈[1,M];k,l∈[1,N])
8、P(t):
遗传算法中所得到的第t代种群。
四约束条件和多目标优化模型
针对学校在安排期终考试时总会碰到的各种难题,一个完善的排考结果应该满足以下约束条件:
1.同一门课程必须安排在同一时间
2.考场座位数大于考生的人数
3.一个监考老师不能同时监考两个考场
4.错开每个学生各门课的考试时间。
同时,为优化排考结果,本文设置了以下优化目标,
5.监考人次最少
6.一个学生的考试课程尽量分散
7.同一考场同一时间只能安排一门课程
五遗传算法的构造过程
约束条件及优化目标的处理
为提高遗传算法的有效性,搜索空间应尽量满足约束条件,即搜索空间应尽量接近可行解空间。
当约束条件大于一条以上时,搜索空间与可行解空间很难一致。
搜索空间与可行解空间很难一致的情况参见图表1,不一致的情况参见图表2:
图表1
图表2
在遗传算法的应用中,必须对约束条件进行处理.而目前理论界还未找到一种能够处理各种约束条件的一般化方法。
通常,在构造遗传算法时,处理约束条件有三种方法:
搜索空间限定法、可行解变换法(参见图表3)、惩罚函数法。
图表3
针对排考问题,本文综合三种方法的核心思想设计了四种大小不同的搜索空间:
(简单遗传算法)
刚性满足:
无
通过适应度函数渐进满足:
5.监考人次最少
6.一个学生的考试课程尽量分散
通过惩罚函数渐进满足:
1.同一门课程必须安排在同一时间
2.考场座位数大于考生的人数
4.错开每个学生各门课的考试时间
6.同一考场同一时间只能安排一门课程
求解结束后另行解决:
3.一个监考老师不能同时监考两个考场
(混合遗传算法)
刚性满足:
2.考场座位数大于考生的人数
通过适应度函数渐进满足:
5.监考人次最少
6.一个学生的考试课程尽量分散
通过惩罚函数渐进满足:
1.单门课程必须安排在同一时间
4.错开每个学生各门课的考试时间
6.同一考场同一时间只能安排一门课程
求解结束后另行解决:
3.一个监考老师不能同时监考两个考场
(编码遗传算法)
刚性满足:
1.单门课程必须安排在同一时间
通过适应度函数渐进满足:
5.监考人次最少
6.一个学生的考试课程尽量分散
通过惩罚函数渐进满足:
2.考场座位数大于考生的人数
4.错开每个学生各门课的考试时间
6.同一考场同一时间只能安排一门课程
求解结束后另行解决:
3.一个监考老师不能同时监考两个考场
(混合编码遗传算法)
刚性满足:
1.单门课程必须安排在同一时间
2.考场座位数大于考生的人数
通过适应度函数渐进满足:
5.监考人次最少
6.一个学生的考试课程尽量分散
通过惩罚函数渐进满足:
4.错开每个学生各门课的考试时间
6.同一考场同一时间只能安排一门课程
求解结束后另行解决:
3.一个监考老师不能同时监考两个考场
编码方法
编码方法决定了遗传算法对约束条件及优化目标的处理能力,是应用遗传算法时要解的首要问题,也是设计遗传算法时的一个关键步骤。
本文设计了四种编码方式,上文所述四种对约束条件及优化目标的处理能力即取决于这四种编码方式:
(简单遗传算法)
将课程按一定顺序排列,为每门课程设定“排考时空”(第几场考试和哪个教室)。
以“排考时空”作为基因,编制染色体。
(混合遗传算法)
引入的FFD近似算法,首先按课程按其参加考试人数排列,为每门课程设定排考时间(考试时间段)。
以排考时间段为基因,编制染色体。
按既定评价函数,即多个遗传算子运算后,对求得的近似最优染色体按FFD近似算法——对某一课程,它总是安排到到第一个能装下所有考生的考试时段中——从而得到出每门课程的考试时空。
(编码遗传算法)
引理1:
到
的全排列(其中
为自然数)与
(其中
,
)对等(存在一一映射)。
证明见附录。
引理2:
,其中,
,
,
,
。
是因引理1中的一个一一映射。
证明见附录
将课程按一定顺序排列,为每门课程设定排考时空(考试时间段和教室),得到编码串,对编码串作到
的映射,得到编码染色体。
这种编码过的染色体在交叉变异过程中不会失去实际意义。
按既定评价函数,即多个遗传算子运算后,对求得的近似最优染色体反编码就得到每门课程的时空安排。
(混合编码遗传算法)
首先按课程按其参加考试人数排列,为每门课程设定排考时间(考试时间段),得到编码串,对编码串作到
的映射,得到编码染色体。
这种编码过的染色体在交叉变异过程中不会失去实际意义。
按既定评价函数,即多个遗传算子运算后,对求得的近似最优染色体反编码——由两条引理这个解码过程得到的编码串与原染色体一一对应——就得到每门课程的时间安排(近似最优编码串)。
对求得的近似最优编码串按FFD近似算法——对某一课程,它总是安排到到第一个能装下所有考生的考试时段中——从而得到出每门课程的考试时空。
本文运用了第四种编码方式,因为其可有效控制搜索空间,提高遗传进化效率。
适应度函数和惩罚函数(评价函数)
在生物进化过程中,物种内部带有适应环境的基因的个体被保留下来,而那些因为缺失有利基因的个体则被环境所淘汰。
从而环境迫使物种保留适应环境的基因。
在遗传算法里,我们应用适应度函数和惩罚函数对基因群进行评价,那些符合我们要求的染色体因为得到奖励而被保留,那些不满足我们要求的染色体因为得到惩罚而被淘汰。
对于排考问题,由于监考老师与课程、课室的关联度相对于考生来说轻很多,安排监考老师监考的复杂度也相应比安排考生考试的复杂度要低得多。
所以,我们先不考虑安排监考老师监考的问题,等安排好考生考试后再安排相应老师到相应的考试课室,而这是个相对简单的工作。
这样,我们的主要任务是安排考生在相应的时间到相应的考场考相应的课程。
考虑同一时间段内考试教室能容纳的最大考生数为固定的,这里将单个时间段容纳的最大考生数记为w。
则
。
对于要考试的n门课程(1,2,…,n),这n门课程的任一个给定的排列,从左至右,每人数之和最接近而又不超过w的几门课程排在同一个考试场次。
这样就避免了同一课程被分配到不同的考试场次的情况。
而且不会出现同一考场同一时间考两门课程的问题和考场座位数少于该场次考生人数的问题。
在此基础上,我们构造适应度函数。
希望满足约束的染色体的适应度比相同条件下不满足目标的染色体的适应度函数值大。
对于第一个目标“一个学生的考试课程尽量分散”若每个考生所有课程考试场次的均值和标准差记为
,则相应的差异度为
,所有考生差异度之和乘以一个参数
可以用来衡量这个约束。
对于第二个目标,
表示,参考人数与实际能提供座位数的比值,这个值越大说明教室被充分利用、监考老师月被充分利用、监考老师人次越少。
构建惩罚函数:
即总考试时间段越长,越要惩罚。
即学生考试冲突越多,越要惩罚。
如果教室装不下考生,要惩罚。
最终我们得到评价函数:
选择算子
遗传算法使用选择算子来对群体中的个体进行优胜劣汰:
适应度较高的个体被遗传到下一代群体中的概率较大;适应度较低的个体被遗传到下一代群体中的概率较小。
本文采用的最优保存策略可保证迄今为止所得到的最优个体不会被交叉、变异等操作所破坏。
其具体过程是:
(1)计算个体适应度函数值
(2)找出当前群体中适应度最高的个体和适应度最低的个体。
(3)若当前群体中最佳个体的适应度比迄今为止的最好个体的适应度还要高,则以当前群体中的最佳个体作为新的迄今为止的最好个体。
(4)用迄今为止的最好个体替换当前群体中的最差个体。
交叉算子
遗传算法中的所谓交叉运算,是指对两个相互配对的染色体按某种方式相互交换其部分基因,从而形成两个新的个体。
交叉运算是遗传算法区别于其他进化算法的重要特征,它在遗传算法中起着关键作用.是产生新个体的主要方法。
本文采用均匀随机配对,单点交叉算子:
在模型中,染色体是经过编码后的
(其中
,
),为叙述方便,以下称其为个体。
其具体执行过程如下:
(1)群体中的个体进行均匀随机两两配对,即每一个体于其它任一个体配对概率相同。
(2)对每一对相互配对的个体,随机设置某一基因座之后的位置为交叉点。
若染色体的长度为n,则共有(n-1)个可能的交叉点位置。
(3)对每一对相互配对的个体,依设定的交叉概率的交叉点相互交换两个个体的部分染色体,从而产生出两个新的个体。
变异算子
变异运算是指将个体染色体编码串
(其中
,
)中的某些基因座上的基因值用该基因座的其他等位基因来替换,从而形成一个新的个体。
本文采用常用的均匀变异是用特定基因座基因取值范围内均匀分布的随机数,以一较小的概率来替换个体编码中基因座上的原有基因值。
值得注意的是,按上述编码方法,染色体最后一位取值范围只能是{1},倒数第二位属于{1,2},倒数第三位属于{1,2,3},……,依次下去,染色体第一位属于{1,2,…,n}。
因此,选定了变异的基因座后,变异还得在该基因座的取值范围内按均匀分布随机变异。
混合编码遗传算法的运行参数
l975年,DeJong在其博士论文中结合模式定理进行了大量的纯数值函数优化计算实验,树立了遗传算法的工作框架,得到了一些重要且具有指导意义的结论[4](书上)。
例如,对于规模在50—100的群体,经过10—20代的进化,遗传真法都能以很高的概率找到最优或近似最优解、他推荐了在大多数优化问题中都较适用的遗传算法的参数。
M:
群体大小,即群体中所含个体的数量,一般取为20~100。
T:
遗传算法的终止进化代数,一般取为100~500。
pc:
交叉概率,一般取为0.4~0.9。
pm:
变异概率,一般取为0.0001~0.1。
在建模过程中可根据具体问题适当调整参数的具体值。
五算法步骤
输入:
教室数据(编号,容纳考生人数)、课程数据(编号,考试人数)、
考生数据(编号,选课情况).
输出:
课程考试安排(课程号,考试时间,考试课室)
t=1.
①随机产生20组染色体,作为p(t)种群;
②计算各个个体的评价函数,执行选择算子;
③对繁殖种群执行交叉算子。
;
④执行变异算子。
;
⑤得到p(t+1)种群;
⑥当进化进行到500代,或最大适应度函数值增长不显著,则停止迭代,得到最大适应函数值的染色体,否则返回②;
⑦对⑥得到染色体解码,得到相应课程时间排列顺序(编码串);
⑧根据⑦得到的课程时间排列序列及教室、各课程相应参加考试人数数据得到考生课程考试时空安排;
六监考老师安排
待考生课程排考结束后,每个场次要用到的课程教室数确定,每个场次需要监考的数量确定,从而可以较简单地分配监考到各个教室/考场。
七实证分析及模型检验
第一步数据处理:
选取某高校2006-2007第一学期全校课程手册,对其进行数据处理,得到所需数据。
处理方法如下:
1、去除体育课:
共152课次。
理由:
一般认为体育课全部教学考试在体育场馆进行,故本文可以对其不做考虑。
2、去除任意选修课,共42课次。
理由:
一般地,任意选修课科目众多,面向全校招生,每班人数差异悬殊,所以采取随堂考试方式是较优,且在我国高校被广泛采用。
本文注重算法设计和实现考虑任意选修课意义不大,同时会影响理论的抽象程度。
本文可以对其不做考虑。
3、去除面向班级缺省的课程记录,共159课次。
理由:
如能得到全部数据是不会出现这种状况的,
这些没有面向班级的课程是模块课和英语课。
因为英语课只有3门,一个学生只能选择一个模块课,所以实际安排中可集中时间安排考试。
本文可以对其不做考虑。
4、最终得到939条课程记录,其中包含:
380门课程,447名任课教师,每周教室最大提供座位数69015位(教室数939个),学生每周选课52089人次。
5、完成数据库input.xls。
第二步计算及结果:
1.计算结果
经过对380门课程的编号,编码,计算,我们得到一个使评价函数值逐步上升并渐进稳定的染色体。
根据这个序列,通过解码(附件iii),FFD算法,我们为每门课分配了较合适的考试场次。
进而分配考试课室和监考老师。
2.总结
本文在求解确定约束条件,建立了多目标优化的数学模型过程中,加入一些启发性的遗传算法,并设计了编码、FFD算法过程,使优化效果较为理想,简化示意图见图表4。
排考结果近似最优染色体间附件
图表4
八模型优缺点分析
优点:
本文通过特殊编码方式一举解决了染色体更迭可能超出可行域的问题,更极大的提高了遗传过程的有效性。
缺点:
本文所采取的算法不一定可以求得最优解得算法,只是选优而已。
由于采用特殊编码,染色体在代际更迭时因需要解码过程而牺牲了运算量。
九模型价值及应用
本文设计的混合编码遗传算法可以推广到车辆调度、会议安排、超大规模电路板设计等有时间、空间等多重约束的多目标优化问题。
参考文献
[6]LegierskiW.Searchstrategyforconstraint-basedclass-teachertimetabling[A].In:
PATAT2000[C].KonstanzGermany,2000.155—169.
[7]MichaelW.Carter:
acomprehensivecoursetimetablingandstudentschedulingsystemattheUniversityofWaterloo[A].In:
PATAT2000[C].Konstanz,Germany,2000.64—84.
[8]MichaelA.Trick:
aschedule-then-breakapproachtosportstimetabling[A].In:
PATAT2000[C].Konstanz,Germany,2000.242—253.
[9]RudovdaH,MurrayK.Universitycoursetimetablingwithsoftconstraints[A].In:
PATAT2000[C].Konstanz,Germany,2000.73—89.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 验证 系统 运行 效果 本文 高校 第一 学期 全校