eHTA算法研究综述

【前言】eHTA算法研究综述由文秘帮小编整理而成，但愿对你的学习工作带来帮助。(Jiangsu Maritime Institute, Nanjing 211170, China) Abstract: eHTA algorithm of artificial intelligence is the heuristic search theory analysis and improvement, and design of a suitable timetabling algorithm, it contains a side strategy, choosing b...

摘要:ehta算法是对人工智能中的启发式搜索理论加以分析和改进,设计的一种适用于高校排课的算法,它包含了靠边策略、择劣策略、前景探测策略、学习策略等内容。eHTA算法应用在高校排课系统中,在减少人工干预排课次数、科学安排教师、均衡班级和教师的日负荷等方面起到了良好的效果,大大提高了排课效率。

关键词:eHTA;启发式算法;高校排课

中图分类号:TP312文献标识码:A文章编号:1009-3044(2009)26-7475-03

eHTA Algorithms Reviewed

WANG Mei

(Jiangsu Maritime Institute, Nanjing 211170, China)

Abstract: eHTA algorithm of artificial intelligence is the heuristic search theory analysis and improvement, and design of a suitable timetabling algorithm, it contains a side strategy, choosing bad strategy, tactics, learning strategy prospects detection, etc. EHTA algorithm used in universities in system, reduce artificial intervention, reasonable arrangement of course, teachers and balanced class teacher of load on the good effect, can greatly improve the efficiency of course.

Key words: eHTA; heuristic algorithm; timetabling

高校排课是教学管理中最基本的、最重要的一项工作,其实质就是为教学计划中设置的课程安排合适的时间和地点,保证整个教学工作能够顺利地进行。然而,排课问题被证明是一个NP问题,即没有答案,只可能找更好的解决方案的问题。

本文介入这个课题,就目前高校始终以自动排课和手工排课交替作业的现状,研究如何减少人工干预,实现基本自动化排课的最佳目标。

1 启发式排课算法(HTA算法)

人工智能中的启发式搜索理论(Heuristic Search theory)是根据一定的规则,逐步求得中间解,并对中间解不断进行分析和优化,最终搜索到目标。启发式搜索理论运用在排课问题上,产生的算法要受到很多限制条件的影响,需要将这个理论和排课的基本原则结合起来,满足高校对自动排课系统地要求,排课算法才能真正起到好的作用。

1.1 排课问题的分析

为了方便考虑和描述问题,将每次授课所包含的几个要素组成的4元组(课程,班级列表,教师,周学时)称作课元。将一周内可供安排的每节上课时间称作时间片,由时间片和课室构成的序偶(时间片,教室)称作时空片。将教室相同,时间在同一天的连续的若干个时空片的集合称作时空片簇。因此排课的任务是为给定的每个课元合理地分配时空片簇。

我们对影响排课的约束条件进行分类和量化,将约束条件分成三个层次:

1)硬约束条件

这个约束条件是保证排课系统能够安排出一张基本的课表,主要包括:① 按课元及周学时分配时空,做到一天之内安排两次或两次以上的课时;② 每个时空片最多只能分配给一个课元;③ 每个班级在同一个时间片内最多只能有一门课程;④ 每个教师在同一个时空片内最多只能有一门课;⑤ 其它必须满足的条件。

2)优化约束条件

旨在使课程的安排尽可能合理、科学,例如:① 为了利于学生的学习,同一班级的同一课程课元的时间间隔均匀且不在一天内安排.而课室则尽可能相同。② 教学计划中课程的性质不一样,尽可能给重点课程的课元分配好的时间片。③ 给相应的课元安排合适的教室,比如多媒体教室和机房。

3)特殊约束条件

从工作人性化的角度出发,主要是指教师个人提出的一些特殊的合理要求。特殊的约束条件一部分是静态的,有些是动态的。静态的约束条件是指在排课之前就有的约束,并且这些约束要贯穿整个课程实施的过程;而动态约束条件是指排课结束后产生的,比如调课后,原来的时间空间如何安排?

1.2 排课问题的数学描述

设C是所有课元的集合,TR是所有时空片的集合。将问题的解定义为给每个课元按照其周学时数分配互不相交的时空片的方案,满足了全部硬约束条件的解就是一个基本解或称可行解(即一张课表)。最优解为最大程度满足优化约束条件和特殊约束条件的可行解(即一张最满意的课表)。将所有的优化约束条件和特殊约束条件依次编号为1,2,...,S,并对它们赋予相应的权重wi≥0(1≤i≤s),编号前的权重大,编号后的权重小。为了在数量上体现这些约束条件的满足情况,我们引入两个概念。

定义2-1 设t是可行解,i∈C是课元,定义函数

f(i,t)=W1X1+W2X2+ …+ WnXn (1)

并称f(i,t)为课元i在可行解t中的不满意度。其中.Xj∈{0,1}(1≤j≤s)表示在t中课元i的安排是否违反了第j个约束条件,若违反,Xj=1,否则Xj=0。对于权重Wi≥0(1≤i≤s)的确定,一般来说,硬约束条件和优化约束条件的权重较大.而特殊约束条件的权重较小。

定义2-2 设t是可行解,定义评价函数:

E(t)=∑i∈c f(i.t) (2)

并称E(t)为可行解t的不满意度。

将(2)作为我们的目标函数,即搜索到尽可能使E(t)达到较小值的可行解t。

1.3 HTA算法分析

1.3.1 优先权策略

课元所具有的属性包括课程的类型、班级的数量、周学时,根据这些属性可以给课元赋以优先权。一般地,课元的优先权值越大,课元的约束就越多,从而可供其选择的满意的时空片或时空片簇就少,所以应该优先安排。优先权策略就是,按照课元的优先权由大到小依次来给课元安排时空片簇。

1.3.2 最佳分配策略

所有可用教室和上课时间构成一个完全时空片簇,将时空片簇上的排课情况视为格局TR,在任一时刻,由所有已被“合法”安排了时空片簇(即满足硬约束条件)的课元子集Csub 在TR中形成的部分课表TR(Csub)为系统在此时刻的格局。所有课元均已被安排了时空片簇的格局称为目标格局(即可行解)。剩余课元中尚有课元可合法安排的非目标格局为活格局。否则称为死格局。

在某活格局TR(Csub )下,对于课元c∈C-Csub,称TR(Csub)中每一个能合法安排下c的空闲时空片簇为课元c的可行时空片簇。

在某活格局TR(Csub)下,考虑课元c ∈C―Csub的安排。设FS≠Φ 是该格局下课元c的可行时空片簇集。对于任意的ts ∈FS,定义课元c对ts的不满意度为:

g(c,ts,TR(Csub)) = W1X1+ W2 X2+…+Ws Xs

其中W j,(1≤j≤s)为评价函数E(t)中的权值,Xj ∈{0,1}表示在部分课表TR(Csub)中若将ts分配给c后c的安排是否满足第j个约束条件,若不满足,则Xj=1,否则Xj=0。

显然,若从格局TR(Csub)最后能到达目标格局TR(C),则有g(c,ts,TR(Csub))≤f(c,TR(C))。

1.3.3 HTA 算法描述

根据上面的两个策略,对启发式排课算法(HTA)用下列流程图1描述。

由于HTA算法的结果对于课元优先次序很敏感,即排课结果往往会因课元的优先次序不同而差别较大,而在这里又常常需要人工的干预。为了在较大程度上消除这种敏感性,对HTA算法进行改进,采用靠边策略、择劣策略、前景策略、学习策略等,提高HTA算法的效率,改进的HTA算法称为eHTA算法。

2 优化的启发式排课算法(eHTA)

2.1 靠边策略和择劣策略应用

在某活格局TR(Csub)下,考虑课元c ∈C-Csub的安排,其周学时为P,每次课时p=2,那么在部分课表TR(Csub )中任意大小为p(2)的空闲时空片簇都有可能是其可行时空片簇。例如,某个最大空闲时空片簇如图2所示。

图2 最大空闲时空片簇

其大小为8。P=4,p=2,对于课元而言,实际上它对应7个大小为2的空闲时空片簇:1-2,2-3,3-4、4-5,5-6,6-7,7-8。我们首先考虑靠边的两个时空片7-8和1-2。采用靠边策略一方面可以缩小搜索范围,另一方面可以使得时空片的剩余空间更好利用,为后面课元的安排留下更多的机会。其次,在优化排课后,从可行的时空片簇中选择最劣的时空片簇,目的也是为了后面的排课在时空片簇上有更多的选择。

2.2 前景探测策略应用

在某活格局α = TR(Csub)下,考虑课元c ∈C-Csub的安排。设FS≠Φ 是该格局下课元c的可行时空片簇集。对于任意的ts∈FS,新格局TR(Csub ) ∪{cts)(在TR(Csub)中将课元c安排在ts处后所得的新课表)均可能是格局α的后继格局。用h(c,ts,α)来度量每个新格局的前景:从新格局TR(Csub )∪{cts}出发,使用最佳分配策略依次对C-(Csub∪{c})中课元进行排课。若最后能达到目标格局(可行解),该可行解的不满意度即为h(c,ts,α);若最终到达的是一死格局,则h(c,ts,α)=W0 × FailSet,其中FailSet是该死格局中未能安排的课元集。W0是比任何可行解的不满意度都大的一个数。其搜索过程如图3所示。

2.3 学习策略应用

根据前景探测策略,若得到一个可行解TR(C),则可以计算每个课元在这张课表中的不满意度f(c,TR(C)),然后挑选出最不满意的课元;若不能得到一个可行解,而是到达一个死格局,则认为其中未能安排的课元是最不满意的课元.对最不满意的课元增加其优先权值,然后再应用前景探测策略进行下一轮排课。

2.4 eHTA算法描述

根据上述两个策略,用流程图4描述eHTA算法。

3 总结

本文以人工智能学中的启发式搜索理论为基础,设计出能够应用在实际排课系统中的eHTA算法。该算法运用分层规划思想,提出靠边策略、前景策略和学习策略。实验证明,排课中应用eHTA算法大大减少了人工干预的次数,提高了排课效率。

参考文献:

[1] 胡小兵,鲁宏伟.基于模糊专家系统的排课系统关键技术研究[J].电力学院学报:自然科学版,2006,16(4).

[2] 吴金荣.求解排课问题的分支定界算法[D].中国科学院数学与系统科学研究院,2002.

[3] 董艳云,钱晓群,张宇舒.基于课元组相关运算的高校排课算法[J].西南交通大学学报,1998,33(6).