（计算机应用技术专业论文）基于智能规划的排课系统的研究与设计.pdf

摘要 智能规划( p l a n n i n g ) 是人工智能研究领域近年来飞速发展起来的一个热门 分支，也是一个多领域交叉的研究领域，它涉及知识表达、知识推理、非单调 逻辑、情景演算、人机交互和知识挖掘等各个方面。其发展不仅对于人工智能 领域具有重要的意义，甚至会从根本上改变人类使用计算机的传统方式。 最令人瞩目的是1 9 9 5 年b l u m 和f u r s t 提出的基于规划图的快速规划方法 图规划g r a p h p l a n “o 。图规划方法引起了整个智能规划界的关注，受到许 多学者的强烈推崇。这种方法把按照s t r i p s 规则形成的规划问题翻译成了能 用路径发现方法求解的规划图结构，第一次采用图的方式来解决规划问题，在智 能规划领域中取得了革命性的进展。用这种方式解决规划问题，能使一些动作并 行执行，大大提高了求解效率。 运用智能规划技术解决排课问题，就是在初始状态和结束状态之间找一条 可行的路径规划，这条路径规划就是排课的过程。排课规划的初始状态是未安 排的执行课程( 由同一个老师在同一个课室上课的教学班级称为执行课程) 、未 安排的课室，规划的结束状态是全部执行课程已经安排出去。算法的任务就是 利用学校的教学资源，协调各个老师的需求，理顺课程优先关系，运用智能规 划技术，对排课问题进行认识与分析，然后根据排课所要实现的目标，利用图 规划( g r a p h p l a n ) 算法来选定要执行的动作，综合制定出实现目标的规划 ( p l a n ) 。 本文的研究来源于广东商学院继续教育学院排课系统，它是广商继续教育 学院教务管理系统的子系统，主要完成全校所有课程排课的功能。该系统在实 际使用中具有通用性不高、排课结果还不够理想的问题。本文在参考大量相关 技术文献的基础上，深入细致地分析了排课系统的各种求解技术，结合分析已 开发的广商继续教育学院的排课系统在运行中表现出的不足，提出建立一个基 于智能规划的排课系统的解决方案，并从理论上分析了这个排课系统排出的课 表和原系统相比有更多的优点。 论文最后对所做的工作进行了总结，并指出了进一步的研究方向。 关键词：智能规划；图规划；s t r i p s ；排课系统；人工智能 i 妄奎三些查茎三兰堡圭兰堡丝苎 a b s t r a c t i n t e l l i g e n tp l a n n i n gi sah e a tu pg a t eb r a n c ho ft h ef i e l do f a r t i f i c i a li n t e l l i g e n c er e s e a r c hw h i c hd e v e l o p sq u i c k l yi nr e c e n ty e a r s ， a sw e l la sm o r et h a no n ec r o s s f i e l da r e a so fr e s e a r c h ，w h i c hi n v o l v e s k n o w l e d g er e p r e s e n t a t i o na n dk n o w l e d g er e a s o n i n g ， n o n m o n o t o n i cl o g i c ， s i t u a t i o nc a l c u l u s ，h u m a n c o m p u t e ri n t e r a c t i o na n dk n o w l e d g eo fa l l a s p e c t so fm i n i n g ，e t c i t sd e v e l o p m e n th a sg r e a ts i g n i f i c a n c en o to n l y f o rt h ef i e l do fa r t i f i c i a li n t e l l i g e n c e ，e v e nc a nf u n d a m e n t a l i yc h a n g e t h eh u m a nu s eo ft h et r a d i t i o n a lm e a n so fc o m p u t e r i n1 9 9 5b l u ma n df u r s tm a d ep l a n sb a s e do nt h er a p i dp l a n n i n gm e t h o d g r a p h p l a n 1 ”。i ti st h em o s tn o t a b l e g r a g h p l a n n i n gc a u s ef o rc o n c e r n o ft h ee n t i r ef i e l do fi n t e l l i g e n tp l a n n i n ga n ds t r o n g l ya d v o c a t e db ym a n y s c h o l a r s t h i sw a ym a k e st h ep l a n n i n g p r o b l e m sa c c o r d i n gt ot h e e s t a b l i s h e ds t r i p sr u l e st r a n s l a t e di n t od i s c o v e r ym e t h o dw h i c hc a nb e u s e df o rp a t hp l a n n i n gm a ps t r u c t u r e ，t h i si st h ef i r s tt i m et ou s et h e g r a g hi ns o l v i n gp l a n n i n gp r o b l e m so ft h ei n t e l l i g e n c ep l a n n i n ga r e aa n d i ta c h i e v e dr e v o l u t i o n a r y p r o g r e s s u s i n gs u c ham e t h o dt os o l v e p r o g r a m m i n gp r o b l e m sc a ng r e a t l yi m p r o v et h ee f f i c i e n c yo ft h e s o l u t i o n ，b e c a u s ean u m b e ro fa c t i o n sc a nb ei m p l e m e n t e di np a r a l l e l ， u s i n go fi n t e l l i g e n tp l a n n i n gt e c h n o l o g yi nr e s o l v i n gs c h e d u l ec o u r s e p r o b l e mi st of i n dav i a b l ep a t hp l a n n i n gb e t w e e nt h ei n i t i a ls t a g ea n d t h ee n ds t a t e ，a n dt h i sp a t hp l a n n i n gi st h ew h o l es c h e d u l ec o u r s ep r o c e s s t h ei n i t i a ls t a t eo fs c h e d u l i n gc o u r s ei st h en os c h e d u l e de x e c u t i v e c u r r i c u l u m ( ac l a s sw h i c ht e a c h e db yt h es a m et e a c h e ri nt h es a m ec l a s s r o o m i sc a l l e de x e c u t i v ec u r r i c u l u m ) ，n o ts c h e d u l e dc l a s s r o o m s ，t h ee n ds t a t e o fg r a g hp l a n n i n gi sa l le x e c u t i v ec u r r i c u l u mh a sb e e na r r a n g e do u t t h e t a s ko fa l g o r i t h mi sm a k i n gu s eo ft h es c h o o l st e a c h i n gr e s o u r c e sa n d c o o r d i n a t et h en e e d so fa l lt e a c h e r s ， s t r a i g h t e n i n go u tc u r r i c u l u m p r i o r i t i e s ，u s i n gi n t e l l i g e n tp l a n n i n gt e c h n i q u e s ，a n a l y s i s i n gt h e 工i s c h e d u l ec o u r s ep r o b l e mo nt h eb a s i so ft h ea c h i e v a b l eg o a l s ，a n d s e l e c t i n gt h ei m p l e m e n t a t i o no ft h ea c t i o nt oa c h i e v et h et a r g e tp l a n n i n g t h i s s t u d yc o m e sf r o mt h eg u a n g d o n gb u s i n e s s s c h o o lc o n t i n u i n g e d u c a t i o nc o l l e g ec o u r s es c h e d u l i n gs y s t e mi ti so n es u b s y s t e mo ft h e s c h o o le d u c a t i o nm a n a g e m e n ts y s t e m , w h i c hm a i n l yc o m p l e t e da l lc o u r s e s c o u r s es c h e d u l i n gf u n c t i o n s t h es y s t e mi np r a c t i c a lu s eh a ss o m e p r o b l e m s ，f o re x a m p l e ，n o tv e r yu n i v e r s a l ，s c h e d u l i n gr e s u l ti sn o tv e r y s a t i s f i e d a f t e rr e a d i n gag r e a td e a lo ft e c h n i c a lr e f e r e n c ed o c u m e n t ， t h i sp a p e rg i v e sac o u r s es c h e d u l i n gs y s t e ms o l u t i o n sb a s e do nt h e i n t e l i g e n c ep l a n n i n gt e c h n i q u ew h i c hi so nt h eb a s i s o fd e t a i l e da n a l y s i s o ft h es c h e d u l ec o u r s et e c h n o l o g y ，c o n j o i n ta n a l y s i st h eo r i g i n a lc o u r s e s c h e d u l i n gs y s t e mi np r a c t i c a lr u n n i n gs h o w e dd e f i c i e n c i e s ，a n dg e tt h e r e s u l tt h a tt h i sn e ws y s t e mh a sm o r ea d v a n t a g e st h a nt h eo r i g i n a ls y s t e m f r o mt h e o r e t i c a la n de x p e r i m e n t a lv a l i d a t i o n f i n a l l y ，t h ep a p e rs u m su pw h a th a sd o n e ，a n dp o i n t so u tt h ed i r e c t i o n f o rf u r t h e rr e s e a r c h k e y w o r d s ：i n t e l l i g e n tp l a n n i n g ；p l a n n i n g ；s t r i p s ；c o u r s es c h e d u l i n g s y s t e m ；a r t i f i c i a li n t e l l i g e n c e i i i 附图表耳录 附图表目录 图卜1 经典智能规划系统产生年代及发展情况表5 图2 - 1 图规划的规划图1 7 图2 2 互斥关系1 8 表2 - 1 规划图的动作1 8 图2 3 第一层扩展1 9 图2 4 第二层扩展2 0 图2 5 解规划2 0 图3 - 1 教学管理系统总体功能结构图2 3 图3 2 教务管理系统总体流程图2 8 图3 3 排课系统业务流程图3 0 图3 4 自动排课算法流程图3 2 图3 - 6 手动排课算法流程图3 3 图3 7 手动删除算法流程图3 4 图3 8 第0 层数据流图3 5 图3 - 9 第一层数据流图3 6 图3 - 9 排课系统c s s 体系结构3 9 图3 - 1 0 排课系统b s s 体系结构4 0 表3 - 1 教学计划实施表4 6 表3 - 2 教室信息表4 7 表3 - 3 课室使用信息表4 7 图3 - 1 1 排课系统功能图4 8 图3 1 2 教学任务管理界面5 0 图3 - 1 3 班级合并界5 1 图3 - 1 4 自动排课界面5 2 图4 - 5 图扩展算法流程图7 6 图4 - 6 手动辅助排课流程图7 7 9 3 独创性声明 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人在 导师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢的地方外，论文中不包括其他人已经发表或撰写过的研究成果，不包 含本人或其他用途使用过得成果。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的声明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论 文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 指导教师签字； 论文作者签字： 9 1 奄吞吣 j 杏椭 2 0 0 74 9 岁月j 牛日 第一章绪论 第一章绪论 1 1 课题来源与研究意义 随着连续几年的高校扩招，我国高等学校在校生总规模有了极大的提高“1 。 这就给高校的教务管理工作带来了一些问题，高校的教务管理工作已经不能靠传 统的教务管理模式来完成。随着信息技术的发展，高校也在不断的发展教育信息 化建设工程。高校的持续扩招和各种应用需求的不断增长，对教务管理信息系统 的性能和服务质量又提出了更高的要求，尤其是对于像排课这样工作量比较大， 要综合考虑的因素又比较多的教学管理业务，更是如此四。 排课系统实际上是时间表的优化问题，早在7 0 年代就被证明是一类n p 完全 问题嘲，即算法的计算时间是呈指数增长的。如何根据班级的课程设置、课程 的周内次数、现有教室资源、以及现有教师资源进行科学的合理安排，提供给学 校的教务部门一个自动排课的系统，在实际工作中具有一定的应用价值。有些高 校在排课需求方面的有其特殊性，如课室资源严重不足，全日制与夜大混合排课 等，导致完全自动化的排课极其困难。 本课题来源于广东工业大学计算机工程研发中心与广东商学院继续教育学 院合作研发的“广东商学院继续教育学院教务管理系统”。该项目建设的总目标 是通过教务管理系统，综合利用校园网等基础信息设施来提升高校的教学管理水 平，把管理提高到一个新的水平。通过对广商继续教育学院教务管理业务流的科 学重组，为师生员工提供更为便捷、高效、集成的教学服务。本人在参加了“广 西师范大学继续教育学院教务管理系统”和“广东商学院继续教育学院教务管理 系统”这两个系统的研发过程中发现，现阶段开发的排课系统虽然是自动排课与 手动排课相结合，排课比较灵活，自动排课也能在有效的时间内给课程安排了合 适的教室，但是实际使用中还有一些不足的地方需要改进。因为实际使用的较好 的排课表要考虑的因素很多，最重要的是要以学生和教师为中心，而不能只是 简单的应付了事。原来的系统最主要问题是计算机排出来的课表不够人性化，没 有设身处地的为老师和同学们的实际需求考虑。本文从智能规划的角度出发，引 广东工业大学工学硕士学位论文 用图规划算法的思想来解决排课问题，建立一个基于智能规划的排课系统，使排 课系统有一定的智能性，从老师和学生的角度来科学的安排课表。 智能规划过程是一种问题求解方法，一个规划系统我们可以认为就是一个问 题求解系统，若用它求解复杂一点的问题“1 ，即可求得一个串行或并行或串并行 混合的动作序列，依次执行此动作序列就可以完成某个具体任务。智能规划的研 究较注重具体实际问题的解决，而不单纯是抽象的数学模型。在排课系统中运用 智能规划中的图规划，能提高排课系统的性能，从而获得更广的适用范围。因此， 基于智能规划的排课系统的具有较重要的研究意义。 1 2 国内外研究现状 1 2 1 排课问题的研究现状 从2 0 世纪5 0 年代末，国外就有人开始研究课表的编排问题。1 9 6 2 年g o t l i e b 在他的文章嘲中提出了一个课表问题的数学模型，并用匈牙利算法解决了三维线 性运输问题，它标志着排课问题的研究正式跨入了庄严的科学殿堂。但是后来在 实践中遇到困难，人们对排课问题是否存在解产生了疑问。2 0 世纪7 0 年代中期， 美国人s e v e n 等在论文”1 中论证了课表问题是n p 完全类问题，这就从理论的 角度回答了排课在实践中遇到困难的原因。s e v e n 的论证方式正式确立了排课 问题的学术地位，把人们对课表编排复杂性的认识提高到理论的高度。 进入2 0 世纪9 0 年代后，国外对排课问题的研究仍然活跃。如印度的v a s t a p u r 大学管理学院的a r a b i n d at r i p a t h y 、加拿大m o n t r e a l 大学的j e a na u b i n 和 j a c q u e sa f e r l a n d 以及c h a r l e sf l e u t e n t 等。目前，解决课表方法的问题有： 模拟手工排课法，图论方法，拉格朗日法，二次分配型法等多种方法。 a r a b i n d at r i p a t h y 的工作是针对以“人”为单位进行课表安排的。他运用 拉格朗日松弛法和分支定界技术求解，这种方法的缺点是为了减少变量的个数， 人为造成科目间的冲突。a r a b i n d at r i p a t h y 还研究了研究生课表的编排问题， 他采用多重课组的方法来处理冲突( 根据学生选课的情况，将人数较多的课程在 一星期内开多次) 。j a c q u e sa f e r l a n d 等人则把问题分为两个子问题：时间表 问题和分组问题。在时间表问题中，根据学生、教师和教室的资源情况形成一个 2 第一章绪论 时间表。对于选课人数较多的课程，一个星期要分成几个时间段来上，分组问题 就是将学生分给时间段。两个问题相关联，通过惩罚因子来构造启发函数。它们 研制的s a p h i r 课程调度决策支持系统分为数据处理、自动优化、交互优化等几 个模块。该系统解决矛盾问题的主要方法也是采用多重课组，这与西方的教学管 理体制是不可分的。此外，有些文献试图从图论的角度来求解排课表的问题，但 是图的染色问题也是n p 完全问题，只有在极为简单的情况下才可以将课表编排 转化为二部图匹配问题，这样的数学模型与实际相差太远，所以对于大多数学校 的课表编排问题来说没有实用价值。国外的研究表明，解决大规模的课表编排问 题光靠数学方法是行不通的，而利用运筹学中分层规划的思想将问题分解，将是 一个有希望得到成功的办法。但是国外研究的许多算法大多没有考虑教室的因素， 不太适合我国的高校。 在国内，对排课问题的研究开始于8 0 年代初期，排课系统中具有代表性的 有：南京工学院的u t s s ( au n i v e r s i t yt i m e t a b l es c h e d u l i n gs y s t e m ) 系统， 清华大学的t i s e r ( t i m e t a b l es c h e d u l e r ) 系统，大连理工大学的智能教学组 织管理与课程调度，广东工业大学计算机工程研发中心的高校教学管理系统中的 排课系统等等，这些系统大多数都是模拟手工排课过程，以“班”为单位，运用 启发式函数来进行编排的。但是这些系统课表编排系统往往比较依赖于各个学校 的教学体制，推广时要做大量的修改工作。 从实际使用的情况来看，国内外研制开发的这些软件系统在实用性上仍不尽 如人意。一方面是因为排课系统作为一个很复杂的系统，要想面面俱到是一件很 困难的事；另一方面每个学校由于其各自的特殊性，完完全全的自动排课软件很 难普遍实用，特别是在调度的过程中一个很小的变动，要引起全部课程的大调整， 这意味着全校课程大变动，在实际的应用中这是很难实现的事鳓。所以，大多数 情况下，都还是采用自动排课与手工排课相结合的方式来实现的。 1 2 2 智能规划的研究现状 智能规划是人工智能一个重要的领域，是一个涵盖知识表达、知识推理、非 单调逻辑、情景演算、知识挖掘、人机交互和认知科学等许多方面的多领域交叉 性学科，其发展不仅对于人工智能领域具有重要的意义，甚至会从根本上改变人 3 广东工业大学工学硕士学位论文 类使用计算机的传统方式。 人们对智能规划的研究已经有半个世纪了，最早可以追溯到1 9 5 6 年n e w e l l 、 s h a w 和s i m o n 设计的逻辑理论家( l o g i ct h e o r i s t ) 程序，这个系统采用了启 发式信息和反向搜索技术；随后他们设计的g p s 系统把领域知识与一般的搜索控 制信息相分离。上述两个系统特别是g p s 在人工智能领域中具有非常重要的地 位，但它们还不是真正面向规划问题研制的智能规划系统。 1 9 6 9 年，g r e e n 通过归结定理证明的方法来进行规划求解，并且设计了q a 3 系统嘲；1 9 7 1 年，f i k e s 和n i l s s o n 设计的s t r i p s 系统“”在智能规划的研究中 具有重大的意义，引入了s t r i p s 操作符的概念，使得原来很神秘的规划问题求 解变得明朗清晰起来；此后到1 9 7 7 年先后出现了h a c k e r 、w a r p l a n 、i n t e r p l a n 、 a b s t r i p s 、n o a h 、n o n l i n 等规划系统。在这十年间人们研究智能规划的兴致比 较高，普遍认为规划问题必须用定理证明的理论来解决，直到c h a p m a n 设计的规 划系统t w e a k 出现。c h a p m a n 详细全面地分析了利用定理证明理论解决规划问题 中的关键问题：模型与规划解的对应关系，提出了著名的模态真值标准( m o d a l t r u t hc r i t e r i o n ) 理论。c h a p m a n 的分析使人们认识到简单地利用定理证明的 方法来解决规划问题是很难的，因此这以后到1 9 9 0 年间，对智能规划的研究陷 入了低谷，这期间仅有s i p e 、a b t w e a k 和p r o d i g y 等较少的智能规划系统出现。 1 9 9 1 年，s o d e r l a n d 和w e l d 等人设计了世界上第一个完备、完全、系统的非 线性规划系统s n l p n l “”，奠定了非线性规划系统的基础。1 9 9 2 年，k a u t z 等把 规划问题求解转化为可满足( s a t ) 问题“。”。”，一反定理证明式求解方法，利 用在约束可满足问题算法上的突破，有效地解决了部分规划问题。 最令人瞩目的是1 9 9 5 年b l u m 和f u r s t 提出的基于规划图的快速规划方法 图规划g r a p h p l a n “”。图规划方法引起了整个智能规划界的关注。受到许多 学者的强烈推崇。这种方法把按照s t r i p s 规则形成的规划问题翻译成了能用路 径发现方法求解的规划图结构，第一次采用图的方式来解决规划问题，在智能规 划领域中取得了革命性的进展“”。用这种方式解决规划问题，能使一些动作并行 执行，大大提高了求解效率，它拥有许多重要属性，包括规划长度的最优化、健壮、 稳定、高效、且建立规划图的计算复杂度是多项式时间和多项式空间等，后来很 多算法都采用了图规划的方法，比较著名的规划器b l a c k b o x 、f f “”、l p g “”、 s g 2 p l a n “”这四届国际规划竞赛的世界冠军都或多或少地采用了图规划的技巧。 4 第一章绪论 图1 1 经典智能规划系统产生年代及发展情况表 f i g 卜1c l a s s i c a lp l a n n i n gs y s t e m sp r o d u c i n ga g ea n dd e v e l o p m e n t t a b l e 综上所述，规划问题求解从最初的定理证明方法发展到s t r i p s 方法，之后 又出现了非线性规划系统，非线性规划系统采用目标导向的方式来生成规划：一 方面使得规划的生成速度大大提高；另一方面，由于是目标导向的生成方式，因 此使得生成规划的质量比较好。现在人们又在此基础上加入了启发式信息，迸一 步提高了规划求解的效率和质量，另外，已经有人提出了建造基于知识的规划系 统的设想。 5 广东工业大学工学硕士学位论文 1 3 研究内容与目标 1 3 1 前期工作 在研究生阶段，本人参加了广东工业大学计算机工程研发中心的“广西师范 大学继续教育学院教务管理系统”、以及“广东商学院继续教育学院教务管理系 统”两个项目的研发工作。通过参与需求调研、系统设计、编码、测试等工作， 熟悉了高校教学管理系统的架构和业务流程，特别是对其中的排课管理系统的需 求、功能、算法以及其在实际使用的情况，都有了一定程度的了解。 同时，由于原有排课系统未能很好的适应未来教育的发展需要，特别是随着 高校的扩招，学生人数的增多，排出来的课表不够科学和人性化。因此，在李振 坤老师的指导下，本人做了大量的调查工作，主要集中在国内外研究现状的分析 以及课题的可行性分析上面。因为本人对人工智能中的智能规划很感兴趣，在平 时的学习中就对智能规划方面的知识有了一定的积累，随着对智能规划技术的发 展情况和关键技术的深入的了解，本人想到把智能规划中的图规划算法应用于排 课，将有助子排课问题的较好解决。通过前期的知识积累，本人对于将图规划技 术应用到排课系统中以提高系统性能的可行性有了一定的把握。本文在此基础 上，对图规划技术在排课系统中的应用进行了进一步的研究和探讨。 1 3 2 研究内容与目标 本文以广东工业大学计算机工程研发中心和广东商学院继续教育学院合作 研发的教务管理系统中的排课系统为背景，通过分析已开发的广东商学院继续教 育学院的教务管理系统中的排课系统在运行中出现的问题，提出了基于智能规划 技术的解决方案，讨论了如何建立一个基于智能规划技术的排课系统，并通过性 能分析，对算法的可行性和完备性进行分析，同时总结了这种解决方案排出的课 表和原系统相比具有的优点。 在高校的教务管理系统项目的研发与运行的过程中，我们更加深刻的体会到 排课问题是其中最难的环节之一，如何在课室资源有限的情况下，合理而有序地 6 第一章绪论 安排全校学生正常上课，是排课系统要解决的问题。同时，计算机自动排课还要 考虑到现实生活中的很多问题，比如要尽量把一个班的课安排在相对固定的课 室；要尽量把较难的专业课安排在上课效果较好的时段里；尽量把每个教师的上 课时间安排的更加合理，更加人性化等等。那么，如何合理地安排出以教师和学 生为中心的课表，这是一个较难解决的难题。 一、目前广商继续教育学院的排课系统存在的不足： 总结起来主要有三个方面的不足：通用性、排课效率低和排课效果不够理想。 第一，通用性。大多排课系统都是把排课规则嵌入到了排课算法当中，而不 同学校的人为规则总会有一些不同，要适应不同学校开发教务系统，就需要在排 课算法中去改动。广东工业大学计算机工程研发中心和广商继续教育学院合作开 发的排课系统，是借鉴原来开发的排课系统再二次开发的，根据广商继续教育学 院排课的实际情况再重新开发，虽然能部分的借鉴以前已开发的系统，但开发投 入的成本还是很高。能不能建立一种具有通用性的排课模型，使自动排课算法和 排课的人为规则相分离，是本文要研究的内容之一。 第二，排课效率低。当前的排课算法基本上能顺利地排课，只是在排课时 耗费的时间多了一点，容易使用户失去等待的信心。本文侧重从智能规划的角度 来优化排课算法，大大减少了比较的次数，能提高排课的效率。 第三，排课结果不够人性化。当前系统是自动排课和手动辅助排课相结合 的方式，大多数排课系统也都是采用这种方式。只是自动排课排出来的结果不够 合理和人性化，比如，上课效果最好的时段是每天的上午1 - 2 节课，这段时间内 排的课有时并不是最重要的一些课；一周要上多次的课程可能会被安排在一天或 是连续的两天内上完；一个老师可能某天排满1 2 个课时。这样就需要排课管理 员通过经验找出自动排课的课表中哪些是不合理的，然后再手动辅助调课。要排 出各方面都满意的、质量高的课表，需要经验丰富的教务员耐心细致的做很多工 作。由于种种原因而导致的排课不成功的课程也需要手工辅助排课，这就使得需 要手工排课的课程有不少。 二、解决方案 针对这个排课系统存在的问题，我们提出了基于智能规划技术的解决方案。 首先把排课系统的各种排课规则( 自然规则和人为规定) 与排课算法实现分离， 将它们转化为形式一样的规则，然后把排课算法建立在这种规则的基础上，就能 7 广东工业大学工学硕士学位论文 建立一个具有通用性的排课系统。这样，不管各个学校的排课管理体制有什么不 同，我们就只需要小范围的修改各种约束条件使之转化为无本质区别的规则，而 可以保留排课算法不变。 在具体的排课系统的设计中，先把排课问题的一般情况抽象出来，将问题建 立在基于智能规划技术的状态空间上，然后运用图规划( g r a p h p l a n ) 技术中的图 扩展生成多个命题层和动作层，同时在规划图中加进时间和空间因素，在图规划 中提取最优解。这样就能较好的解决了时间和空间属性给排课算法带来的问题。 因为我们采用的解提取算法是从后向前搜索空间的方法，总是靠后的时段会最先 被搜索。为了解决课程的优先级问题，把重要的课程放在上课效果较好的黄金时 段内，我们把黄金时段放在图规划中层次靠后的位置，同时优先级较高的课程的 动作安排在前面，于是在解提取的过程中优先级别高的课程总是抢先被安排在较 好的时段里。 由于以前的排课系统算法，没有将排课问题分割，在回溯寻找的时候，没有 限制在一个子集合里面的寻找，这样就容易造成问题无限膨胀，导致算法失效。 正是为了改变这种状况，我们引入图规划技术来改进原来的排课算法。由于图规 划有着同层不互斥的这一显著的优点，在算法中我们只需要保持每一层内部无矛 盾，这样就简化了排课问题的复杂性。基于智能技术的排课算法，就是将问题分 割成若干个时间片，先保证每个时间片内的安排方法是无矛盾的，这样就能求到 解集合的一个子集合，如果有矛盾存在，则先通过调整子集合的内部元素来解决， 如果子集合的内部调整也不能达到目的，那就要从上一个子集合开始重新建立， 以次类推。采用这样的方法，和传统的排课算法相比，比较次数能大大减少，增 加了算法的可行性。 1 4 基于智能规划的排课系统的特色 本文的目的是建立一个实用和通用性较高的排课系统，让用户能够在较短的 时间内顺利地完成排课。基于智能规划的排课系统具有以下特色： 1 、具有广泛的适用性 基于智能规划的排课系统采用先进的智能规划的思想来解决排课问题，对于 一般高校的排课具有很大的借鉴和参考意义，特别是针对学生数量多、排课任务 8 第一章绪论 重的情况。通过把排课所要遵循的各种约束条件转化为统一的规则，使这些规则 和排课算法相分离，不同的学校的排课要改变的只是各种约束条件，而排课算法 就不用做大的修改就可以直接套用了，所以具有较广泛的适用性。 2 、算法完备性和可行性高 基于智能规划的排课系统运用智能规划的技术，将排课问题转化成有规整的 状态空间的宽度优先的算法，使得找到规划的机会大大增加，算法具有很高的完 备性和可行性。 3 、资源利用率高 这种排课系统能使课室的使用安排合理，教师的上课时间安排科学、人性化。 基于智能规划的排课系统能使各种教学资源，尤其是像机房、多媒体教室、练功 房等有限的教学资源的利用最大化。 4 、排课速度快、效率高 传统的排课算法多采用随机排课方法，漫无目的的搜索会使算法重复选择， 且因为排课问题涉及到的约束条件很多，就使得排课过程中的比较判断重复很多 次，浪费了很多的时间，导致排课效率低。采用基于智能规划的排课系统采用图 规划的方法，将排课问题转化成有规整的状态空间的宽度优先的完备算法，在有 限的状态空间内搜索可行的路径，减少了无谓的回溯，大大提高了排课的速度， 效率也要高很多。 5 、使排课结果更加的人性化 许多排课系统只是在可行的时间内给课程安排了教室，排课结果还不够人性 化。例如对于一周要上几次的课程，极有可能一天或连续两天内安排上同一门课， 而这样容易导致学习的效果差；每天的上午第一二节课是上课的黄金时间，学生 在这段时间学习的效率更高，应该把较难学或更重要的专业课等安排在此时段； 还有如果同一个教师上的课并不多，但排的课表却分散在每周的四天内，完全可 以改为较为集中的两天内就安排完，这样也就更利于教师有多一点的空余时间做 科研。采用智能规划的排课系统在这些方面比传统的排课系统做得更好。 1 5 论文内容组织 论文总共分为六章。本章主要介绍论文的选题背景、技术现状、主要研究内 9 广东工业大学工学硕士学位论文 容和系统特色。 第二章主要是相关技术的介绍，综述了排课问题的求解技术、智能规划的相 关技术介绍，包括智能规划的主要思想、s t r i p s 表示、图规划方法的求解步骤。 第三章对广东商学院继续教育学院教务管理系统的中排课系统的系统需求、 设计、体系结构、及运行情况进行描述，并分析其性能改进的必要性，探讨解决 问题的相关思路。 第四章基于智能规划技术排课系统的解决方案。首先阐述了本排课系统采用 智能规划算法的原因，接着提出了建立一个具有通用性排课系统结构，然后对具 体地运用图规划技术在广商继续教育学院的排课系统进行分析设计，提出了针对 排课问题的基于智能规划技术的解决方案。基于智能规划技术的排课系统的设 计，包括知识的表示和状态空间模型的建立、运用图扩展来实现时间和空间的分 配、解提取。 第五章主要是基于智能规划技术排课系统性能分析，首先从理论上对这种算 法的完备性和可行性进行分析，然后和原系统相比较，总结了改进算法的优点。 第六章主要是总结论文所做的工作、不足和进一步的研究工作展望。 1 0 第二章相关技术的介绍 第二章相关技术的介绍 这一章将首先介绍排课问题的现有求解技术，接着介绍将在本文排课 系统中用到的智能规划方面的相关技术。 2 1 排课问题的求解技术综述 排课作为高校教务管理中的一项重要而繁重的工作，就一般意义而言， 实质上就是对全校下学期开设的每门课程合理地分配时间资源和教室资 源的过程。其中涉及教师、教室、时间和学生等多种因素，人为要求也比 较多，另外由于这几年的高校扩招，导致教室资源比较紧张，诸多因素更 加增添了课程编排工作的难度和复杂度。如果完全由人工来编排课表， 费时费力，其科学性、方便性更是难以保证，所以利用计算机进行自动排 课的想法自然而生。 事实上，用计算机实现排课的完全自动化所需的时间可用公式2 1 来表示： t i m e = f ( c o u r s e s ，c l a s s e s ，t e a c h e r s ，r o o m s ，t s )( 2 一1 ) 公式( 2 - 1 ) 在计算机科学中称为时间复杂性函数，其中：c o u r s e s 表 示课程数目，c l a s s e s 表示班级数目，t e a c h e r s 表示某一学期能承担教 学任务的教师数目，r o o m s 表示教室及实验室等数目，i s 表示划分的可 用时间片数目，t i m e 是计算机编排课表所需花费的时间。函数f 是一个 指数函数，即：当自变量增大时，其函数值呈指数量级递增，这在计算机 科学中是一个“n p 完全类”问题，也就是所谓的不可解问题拉”。 人们对排课问题的算法作了许多探索，但由于排课问题是n p 完全问 题，而且易受实际问题边界的影响，大多数求解结果都不理想。对于计 算机自动排课，己经研究出了许多种算法，下面是几种常见算法及简介： 1 ) 基于模拟退火法的排课 模拟退火法( s i m u l a t e da n n e a l i n g ) 是k i r k p a t r i c k 等人于1 9 8 3 年首先提出的心”，它是人们从自然界固体退火过程中得到启发并从中抽 广东工业大学工学硕士学位论文 象出来的一种随机优化算法。模拟退火法用于求解优化问题的出发点是 基于物理中固体物质的退火过程与一般优化问题的相似性。在对固体物 质进行退火处理时，常先将它加温使其粒子可自由运动，以后随着温度 的下降，粒子逐渐形成低能态晶格。若在凝点附近的温度下降速率足够 慢，则固体物质会形成最低能量的基态，优化问题也存在类似过程。模 拟退火法被用来解决许多实际应用中优化的问题，取得了不错的效果， 用来解决排课问题，也有了某一些成功的应用。 2 ) 基于遗传算法的排课 遗传算法借鉴于生物界进化思想和遗传机制”，从潜在的解集中的 一个种群( p o p u l a t i o n ) 开始，在每一代中，根据问题域中个体的适应度 ( f i t n e s s ) 大小挑选个体，经过基因( g e n e ) 编码( c o d i n g ) 的一定数目 的个体( i n d i v i d u a l ) 进行组合交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) 。 产生代表新的解集的种群，末代种群中最优个体经过解码( d e c o d i n g ) ， 可以作为问题的近似解”。经过近4 0 年的发展，遗传算法在理论研究 与实际应用中取得了巨大的成功。许多人开始尝试通过对遗传算法进行 改进和优化，用来解决课程表编排问题。 3 ) 基于蚁群算法的排课乜5 1 蚁群算法是2 0 世纪9 0 年代初意大利学者d o r i g o m a n i e z z o 提出来 的，根据蚂蚁觅食的原理，即蚂蚁在寻找到较大食物需要回去求援的时 候，会在其回来的路上留下一种“臭迹外激素”其他蚂蚁嗅到这个激素 的味道，就会沿着该路径奔向目的地，而且当有多条路径的时候，后继 的蚂蚁竟然还会沿着最短的路径奔向食物。将蚂蚁觅食原理应用到排课 系统中，即借鉴于蚂蚁觅食的这种最短路径选择的原理应用到排课算法， 同时通过二分图的理论来简化排课问题求解的复杂度，理论上能最终找 到排课问题的解。 4 ) 基于贪婪法的排课算法 贪婪法乜们在解决问题的策略上不追求最优解，不要回溯，只希望得 到较为满意的解。虽然贪婪法不是对所有问题都能得到整体最优解，但 对范围相当广泛的求最优解问题来说，它是一种直接的算法设计技术， 通过一系列局部最优的选择，即贪婪选择可以产生整体最优解。具体地 1 2 第二章相关技术的介绍 说，通常所求问题的一个整体最优解，是从贪婪选择开始的，每一步只 选出最有希望的对象，而且每作一步贪婪选择后，原问题可简化为一个 规模更小的类似子问题，然后通过多步贪婪选择，最终可得到问题的一 个整体最优解。贪婪法简单、直观、高效、算法容易设计，最典型的应用 是解决优化问题，取得了不错的效果，不少学者尝试应用贪婪法来解决 排课问题，也取得了某一些成功。 5 ) 基于优先级自动排课算法仕 利