高校智能排课系统算法的研究与实现

研究高校智能排课优化问题,由于在资源的有限的条件下满足教学的有序性,使高校自动排课成为一个多约束、多目标优化问题。传统排课方法排课效率低、成功率低,导致课程之间冲突率高,无法满足现代高校教务管理要求。为了提高排课效率和排课成功率,提出一种自适应遗传算法的智能排课系统。首先根据教师、学生、教室、课程和课程时间段要求建立一个多约束条件的高校排课数学模型,采用

第 8第l 2卷 2期文章编号： 0— 3 8 2 1 )2— 3 9 0 1 6 9 4 (0 1 1 0 8— 4 0

计

算

机

仿

真

21 2 0年1月 1

高校智能排课系统算法的研究与实现宗薇(外交学院计算机中心，北京 10 3 ) 0 07 摘要：研究高校智能排课优化问题，由于在资源的有限的条件下满足教学的有序性，使高校自动排课成为一个多约束、目多

标优化问题。传统排课方法排课效率低、成功率低，导致课程之间冲突率高，无法满足现代高校教务管理要求。为了提高排课效率和排课成功率，提出一种自适应遗传算法的智能排课系统。首先根据教师、学生、教室、程和课程时间段要求建立课一

个多约束条件的高校排课数学模型，随机可行排课法操作产生可行排课方案，采用然后利用遗传算法在可行方案中寻找

最优排课方案。仿真结果表明，于传统排课方法，适应遗传算法不仅提高了排课效率，相对自而且提高排课的成功率，有效降低课程之间冲突率，并能够解决高校排课难题。 关键词：问题；排课遗传算法；多重约束；目多标优化中图分类号：P 0 T31文献标识码： A

Re e r h a d Re l a i n o i e st m ea l y tm g rt m s a c n ai t fUn v r iy Ti t b e S se Alo i z o h

ZONG e W i( hn oe nA ar U i rt, eig10 3, hn ) C iaF ri f i nv s y B in 00 7 C ia g s ei jABS TRACT:Re e r h u ie st i t be p o lm.t e i tl g n u o t O r ea r n e n P c mp ee s a c nv ri t y me a l rb e h el e ta tmai C U ra g me t s a N o l t n i c s i

p o lm,a d tetaiin l to saeo w f ce c n ihc n it ae n du a l e erq i me t rbe n h dt a h d r f o e in ya dhg o fc t,a n bet me th e ur ns r o me l i l r o t eo d m ol g d c t n d n s ain ma a e n .I r e o i rv h f ce c n U C S a e h s fmo

e c l e e u a i a a miit t n g me t n o d rt mp e te e in y a d S C E Sr t,t i e ol r o o i p p rp tfr r d a mp v d g n t g r m f i tl g n ra g me ts s m. F r to l,a c r i g t h a e u o wa n i r e e e c a oi o i l h t o ne l e ta r n e n y t i e i f al c o n o t e s d

tahr ads dns l s o s o r sad r i d cu et s tea oi m m d ut—ojc v d ece n t et,c sr m,cu e n e r o r me, h grh aeam l s u a o s u q e s i l t i b t ea ei nc n tan o d t n fu ie i u r u u mo e,t e rd c d fa i l ou in rt t l gr n o y h n o s i tc n ii s o n v r t c ri l m d l h n p u e sb e s lto sf mea i a d ml .T e r o sy c o e o i b n g n t g r h w s u e of d t eo t l u rc l m ln i h a i l ou in .S mu ain r s l h w a, e ei a o t m a s d t n p ma riu u p a n t ef sb e s l t s i l t e ut s o t t cl i i h i c e o o s h c mp r d w t a i o a t o s t e i r v d g n t lo t m uc e st e c riu u s e d, mp v st e e— o ae i t dt n l h d, h h r i me mp o e e e i ag r c i h q ik n u r l m p e i r e f h c o h i c e c,e h n s h u c s a e n e u e o r e o o i trt,a d c n s l e u ie i i t l r b e i n y n a c e t e s c e sr t,a d r d c s c u fc n c ae n a o v nv r t tmea e p o l m s l f s y bvr l ey we1 .

KE W O DS Tm t l gpo l G nt l rh Mut—cnt i sMu i bet eot i tn Y R: iea i rbe b n m

; ee ca o tm; l i gi i os a t; h—ojci p m z i r n v i ao

提出了许多解决此问题的算法。传统高校排课算法有：贪婪

l引言 随着大学扩招，学生日益增多，课程表是教学工作正常

算法、家系统法、专图论方法，这些方法只能针对个别的实际问题，有通用性，且关联规则很难获取，解结果不理没而求想 .。近几年， 3 J由于智能技术的不断发展，出现了模拟退火算法、遗传算法等启发式算法，并取得了不错的效果，成为当前高校排课问题的主要解决方法’。但是模拟退火算法退 6 J

运行指挥图，是组织师生有序教学重要依据，是教学管理人员的核心工作。高校排课程问题是指在教师教室、时间资和源有限的条件下，对课程进行有效调度的组合整体优化问题，涉及因素多，是一项比较复杂的系统工程。目前，高校排课问题已被证明是一个 N P完全问题，由于其具有难解性和复杂性，因此一直没有得到很好解决受到研究者的关注…。

火实施温度难以确定，以及降温的方式多样，且有时没有并考虑到实际应用中会出现的所有排课要求，易产生局部最容优解，到的结果无法满足大规模排课要求。遗传算法拟自得 然界生物进化过程的随机搜索、优化算法，具有自适应全局寻优和智能搜索等优点，且收敛性好，缺陷是交叉和变异其概率不能进行自适应调整，导致排课时产生早熟现象、收敛速度慢等缺陷，排课冲突率相当的高"。 J.. .——

对于高校排课问题，多学者对其进行了广泛的研究，许基金项目：中央高校基本科研业务费专项资金项目( Q 0 1 0 ) Z 2 1 B 5收稿日期：0 1— 5—0 21 0 1

3 9 .— 8 . .—