（信号与信息处理专业论文）专家系统技术求解课表问题的研究.pdf

专家系统技术求解课表问题的研究 摘要 本文首先对课表问题进行分析给出课表编排问题的一般定义：并通过对用计 算机编排高等学校课程表问题的特点及业务再造问题的深入分析，给出计算机排 课的逻辑模型i 接着着重论述了对课表编排知识工程( 知识的获取、知识的表示、 知识的运用) 的研究；为了进行微机排课和教务管理信息系统的一体化集成设计， 又研究给出了关系型数据库管理系统环境下的课表编排知识系统；最后介绍了课 表编排专家系统的设计与实现。 关键词：专家系统知识工程知识系统数据库课表编排 r e s e a r c ho i lt h es o l u t i o no ft h ec u r r i c u l u ms c h e d u l e p r o b l e mw i t ht h e e x p e r ts y s t e mt e c h n o l o g y a b s t r a c t i nt h i sp a p e r ，f i r s t ，i ti sg i y e nt h a tt h ed e f i n i t i o no f c u r r i c u l u ms c h e d u l ep r o b l e mw i t h t h e a n a l y s e s o fc u r r i c u l u m s c h e d u l i n gp r o b l e m a n dp r o p o s e dt h e l o g i c m o d e lo f c o m p u t e r c u r r i c u l u m s c h e d u l i n g w i t ht h e a n a l y s e s o ft h e u n i v e r s i t y c u r r i c u l u m s c h e d u l i n g ( t h e c o n s t r u c t i o no fc l a s s - t e a c h e r - c l a s s r o o mt i m e - t a b l e ) a n dt h ew o r k r e b u i l dp r o b l e m s t h e n ，t h ew r i t e r p a r t i c u l a r l y d i s c u s sa s t u d y o ft h ec u r r i c u l u m s c h e d u l i n gk n o w l e d g ep r o j e c t 一一k n o w l e d g ee x p r e s s - k n o w l e d g eu s i n g a n d k n o w l e d g ec a p t u r e n e x t ，t h e w r i t e rd i s c u s sas l u d yo ft h ec u r r i c u l u m s c h e d u l i n g k n o w l e d g es y s t e mb y t h er e l a t i o nd a t a b a s e m a n a g e m e n ts y s t e m f o rt h e i n t e g r a l i n t e g r a t i o nd e s i g no ft h ec o m p u t e rc u r r i c u l u ms c h e d u l i n gk n o w l e d g es y s t e mw i t i lt h e e d u c a t i o n a la d m i n i s t r a t i o ni n f o r m a t i o ns y s t e m a f t e rt h a t ，i ti si n t r o d u c e dt h a tt h e d e s i g na n dc o m i n gt r u eo f c u r d c u l u ms c h e d u l i n ge x p e r ts y s t e m k e y w o r d s ：e x p e r ts y s t e mk n o w l e d g ep r o j e c tk n o w l e d g es y s t e m d a t a b a s ec u r r i c u l u m s c h e d u f i n gp r o b l e m r 0 5 33 7 独创性( 或创新性) 声明 本人声明所呈交的论文是我个人在导师指导下进行科研工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外- 论文中不包 含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学譬荸 它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在 本人签名： 解密后遵守此规 本人签名： 关于论文使用授权的说明 导师龆叮鲎兹导师签名：兰盘堕 弧脸舭岛敝骼篡粼藏 黧一 瓤褓肭 第一章绪论 第一章绪论 1 1 课题研究背景及意义 计算机排课问题是人们关注而一直未能满意解决的计算机应用领域的一个具 有一定代表性的信息处理问题。早在6 0 年代国内外就开始了对该课题的探索。6 3 年c c 高特烈伯( c c g o t l i e b ) 给出了课表编排问题的数学模型，使之成为数学 家和计算机应用专家共同研究的课题。由于实际中遇到种种难题，并未能取得满 意成果。7 5 年s 艾温( e v e n s ) 证明了课表编排问题是n p 一完全的( 完全不确定多项 式) ，宣布了这时空组合问题的学术地位和难度o 】 “，使得人们对该问题的求 解失去了信心。 8 0 年代微机的普及发展，其在办工自动化领域的普遍应用，促使人们又萌生 解决课表编排问题的愿望。计算机软件技术的发展也为这个问题的求解提供了新 的技术支持，使该课题的研究出现了勃勃生机。我国自8 4 年清华大学发表了实验 性研究成果起，相继多个院校都开展了研究工作。排课问题虽然是数学上的时间 与空间的组合问题，而排课过程却是人的主观因索作用下的人文决策的过程。要 实现用计算机编排课表，如果试图从数学角度建立模型，研究设计一种计算机算法， 无疑使这个问题的解决陷入困境。 n p 问题有很多类。按其解的不确定性分为完全的、不完全的，按数学求解的 难易程度，完全的n p 问题是最难解的，不完全的n p 问题中，n p h a r d 问题( 如： 图着色问题、移动通信系统频率分配问题等) 则相对难解。当前，对n p h a r d 问 题，人们普遍在研究采用人工智能技术解决的算法( 如：遗传算法) 。至今己取 得很大进展h 】f5 【6 】。而至今人们在数学上尚未找到n p - 完全的这类问题的解法。因 此，对课表编排的研究在理论上具有相当典型的代表性，这个问题的解决，对解 决其他n p h a r d 、n p 一完全的问题，也具有很大的指导意义。 9 0 年代人们开始使用数据库技术、人工智能领域的专家系统技术作为技术支 持解决这一问题，并已有多家推出他们研制的系统。然而，就目前已推出的系统 而言，都还存在一定的局限，未能达到满意解决这一问题的地步，这就是这些系 统都没能推广应用的原因。笔者曾对几个排课系统进行过认真的分析，从其排课 结果看，主要是都没有解决好知识工程的问题。系统设计人员依然按计算机的逻 辑设计系统，没有从根本上摆脱计算机算法求解的设计模式“0 】【1 “。 笔者认为，用计算机解决这个人文决策问题，实现一个具有广泛应用价值的 实用系统，系统设计人员必须按排课专家的思维逻辑来设计系统，也就是解决好 第一章绪论 实，是根据表示数据所用的约定赋予数据的意义。知识是人们人们通过实践认识 到的客观世界的规律性的东西。是信息经过加工整理、解释和改造而形成的，通 过对信息进行概括和推理的方式产生。因此，知识工程的本身就是信息处理，知 识工程所要进行的信息处理是以知识为对象，它比通常以数据为对象的信息处理 涉及的问题要广泛的多、复杂的多，是更高层次信息的处理。此外，尽管专家系 统核心是知识处理系统，但是还必不可少的包括一般的信息处理。因而，该课题 的研究属于信息处理的范畴。 1 2 研究的内容与方法 到目前为止，人们研究课表问题以及开发推出的所有微机排课系统，都是 仅限于班级一教师课表。由计算机排出班级和教师课表后，还需要由人工编排教 室。在教室资源日益紧张的现在大多数高校，还必须由人工调整计算机所排结果， 而且经常改得面目全非后，才能排好教室，这基本上已经失去计算机排课的意义。 因此，非常有必要研究同时排出班级一教师一教室课表的系统。这就是该项目的研 究目标，也是笔者的创新之一。 解决好计算机编排课表问题，首先要基于对课表问题有准确透彻的认识。在 该课题的研究过程中，首先在河北科技大学教务处排课老师的协助下，对计算机 编排课表问题进行了深入细致的分析，并参考有关资料给出了对编排课表问题的 一般定义、高校排课的特点及业务再造问题的分析，由此得出计算机排课的逻辑 模型。在这之前，各参考文献给出的都是限于对班级一教师课表编排问题的定义 “ 3 】 “。人工排课也是先排出班级和教师课表，然后再排教室。笔者对课表编排 问题首次提出了班级一教师一教室课表编排问题的定义和数学模型。设计实现班 级、教师、教室课表同时排的系统可使教室的编排利用更加合理，能支持更高 效的教学资源配置。 业务再造问题的分析、计算机排课的逻辑模型是软件工程的系统分析过程中 必须给出的，在各参考文献中都没有涉及这两个问题。在本文第二章简要地给出 对计算机编排高校课表问题分析的结论。 用专家系统技术解决计算机排课问题的中心研究工作是对课表编排知识工程 的研究。笔者先向教务处排课老师认真细致地学习排课所必备的信息、排课的步 骤和方法、排课规则、经验知识等对课表编排的基本信息、知识进行归纳总结， 提出本人在知识的表示、知识的运用、知识的获取方面的见解。本文在第三章着 重论述了对课表编排知识工程的研究的方法和得出的结论，在对排课专家的知识 归纳方面，提出了新的见解并采用了相应的知识表示和运用方法。这也是笔者的 创新点之二。 专家系统技术求解课袁问题的研究 高等学校教务管理信息系统作为办公自动化和管理信息化的通用手段，使管 理科学化、现代化，提高教务管理水平和办公效率。微机排课系统与教务管理信 息系统应共享信息资源，设计实现微机排课系统时应该和教务管理信息系统进行 一体化的集成设计。高等学校教务管理信息系统一般都在关系型数据库管理系统 环境下设计实现，因此，探索不使用专门的专家系统开发工具以及任何的人工智 能语言而使用关系型数据库管理系统实现课表编排知识系统更具有实用意义。 本文第四章论述在关系型数据库管理系统环境下知识库的构建和推理机的设计实 现进行的研究和设计。 为了对自己的研究结论进行实验验证，并将研究结果应用于实际，开发设计 了“高校课表编排专家系统”。在该系统的实现过程中，用虚拟测试数据进行了 测试试验。并分别用河北科技大学西校区9 8 9 9 ( 2 ) 、9 9 t 2 k ( i ) 和9 9 2 k ( 2 ) z 个学期 的排课数据进行了测试，对存在的问题进行了研究解决，进行了多轮的改进和完 善。第五章简要介绍该系统的设计和特点、测试实验方法和结果。最后又用 2 k 2 k l ( 1 ) 学期的排课数据进行了系统试运行测试，结果令人满意。 本文的第二章、第三章的内容是专家系统技术在课表编排问题上应用研究的 理论分析、论点和结论，第四章、第五章的内容是应用研究结果和软件工程等技 术方法进行开发设计的设计说明。 第二章计算机编排高校课表问题分析 第二章计算机编排高校课表问题分析 要满意地解决计算机编排高校课表问题，研究其可行的技术方法前，对该问题 的全面透彻的分析尤为重要。需要与教务工作者一起携手，深入、全面的对该问题 进行分析。要在对该问题有了准确的把握的前提下，研究达到理想目标的途径和技 术手段。 2 1 问题的定义 课表编排问题就是把笼统的课程设置计划变成具体课程的课时占用安排。对高 校课表编排，具体的说是：在一学期内，按各专业的教学课程设置，对每个班级所 学的每门课程安排上课的时间( 课时单元) 、地点( 教室) 和任课教师。 班级一教师一教室课表编排问题的数学定义如下： 对有限集t = t 。，t 2 ，t h t 表示有效排课课时单元集。n 为一学期总有效 课时单元数，t 、为第h 个课时单元。称t 为学期课时单元，表示一学期内用于教学的 上课时间单元。 有： 集合b = b 。b 。b 。b o ) 表示班级有效课时单元集的集合。0 为班级数， b ；为班级i 的有效课时单元集。称b 为班级课表。它是用于向其内排课的时间 单元。 集合d = f 珥，d 2 一d ”d ， 表示教室有效课时单元集的集合。p 为教室数， d j 为教室j 的有效课时单元集。称d 为教室课表。 集合s = s 。s ：s 。s 。) 表示教师有效课时单元集的集合。q 为教师数， s 。为教室k 的有效课时单元集。称s 为教师课表。 对数组r - f r 。，r 。r 。r u j 表示学期课程学时设置。m 为一学期的各班所有课 程门数，r ，为课程l 的计划学时数。r 是数组属性，它是从整个求解问题空间或称为 求解问题集提取出来的数值属性的部分。 有： 非负矩阵x = x i ，) ( 2 x l ( 0 表示班级课程设置。x 。为班级i 学习课程 1 的学时数。 逻辑矩阵y = y 。y 。y ”y e 表示教室可上课分布( 也即每门课程可排 的教室) 。y j l = 1 ，则课程l 可排在教室j 。 专家系统技术求解课表问题的研究 逻辑矩阵z = z ，z 。z 。z 。) 表示教师任课分布。z 。= l 则教师k 任课程l 于是排课问题就是对所有课程确定交函数集： f ( i ，j ，k ，h ) = ( f l ，f 2 f i 矗)( i b ，j d ，k s ，h e t ) f 。( i ，j k ，h ) ： 1 ，2 i 0 f l ，2 j p ) xf l ，2 k q t f ( i ，j ，k ，h ) 一f 0 ，1 为课程l 的交函数。当且仅当班级i 在教室j 由教师k 在t 、课课时单元上课程1 时，f i = 1 。 必须满足： f 1 ( i ，j ，k h ) = l 专h b i n d j n s ka y h l = l ，z j , = 1 。( 在教师k ，教 室j ，班级i 的交汇空间并受y 、z 约束) 。 h 。tf l = x i l1 i 0 ；1 j p ；l k q 。( 一门课程的交汇课时 数等于计划学时数) 。 1 “i 。8 f l ( i ，j ，k ，h ) 1 ：班级课时无冲突。 1 乱j 。d f l ( i ，j ，k ，h ) l ：教室课时无冲突。 k 。s f l ( i ，j k ，h ) l ：教师课时无冲突。 以上是对课表问题的数学描述，它属于组合数学的时空组合问题 3 。1 9 7 6 年 e v e n ，s 等人在美国s i a mj ，c o m p u t 上发表的“o nt h ec o m p l e x i t yo ft i m e t a b l ea n d m u l t i c o m m o d i t yf l o wp r o b l e m 证明了课表编排问题是n p - 完全的。它的论述确立 了课表编排问题的学术地位，把人们对计算机编排课表的复杂性的认识提高到了理 论的高度。这个问题的求解是典型的时间表与多物流的决策问题的求解。用计算机 解决这个人文决策问题，从数学角度建立模型，研究设计一种计算机算法的尝试都 未能获得满意结果。要实现一个计算机排课的实用系统，系统设计人员必须按排课 专家的思维逻辑来设计系统，研究用专家系统技术解决的途径。 这个人的主观因素作用下的人文决策的问题可以直观描述如下： 首先，由一学期各专业的教学计划安排各课的任课教师( 人工完成) ，将其转 化成教师任课安排表如下格式： 教课班班 周 起结 课优教特 学 始束 程先室殊 师程数级 时类级要要 数 周周 别别求求 第二章计算机编排高校课表问题分析 此表的每一行是门要排的课程，将各上课的合班( 或单班) 班级、任课教师 排出上课的课时单元并排出上课教室。此表的所有课都在要求的约束条件和合理原 则的约束下，排入有限课时单元集、有限有效教室集。更形象的说：就是将此表的 每一门课都在要求的约束条件和合理原则的约束下排入班级课表、教师课表、教室 课袁如下： 班级课表 课时单元 t lt 2t 3t ht n 班级 b b 2 b b n 教师课表： 课时单元 t it 2t 3 t ht n 教师 s ， s 2 s k s o 教室课表 课时单元 t it 2t jt ht n 教室 d l d z d j d 。 8 专家系统技术求解课表问题的研究 每排出一门课，在各课表空间内，填入所排课程信息。 2 2 高校课表问题的特点 有效课时集的周期性：有效课时集具有大小两个周期。小周期为一天每天最 多5 个课时单元。一般称为i 一2 节、3 4 节、5 6 节、7 8 节和晚自习。大周期为 l 周( 7 天) 。根据这个周期性，将排课课表空间的课时单元减缩为一个大周期。此 时各课表格式如下： 班级课表： 课时单元 班八 t 1 1t 1 2t 1 3t 1 4t 2 lt 6 4 b l 艮 b ， 乳 教师课表： 、塑单元 教师 t 1 ii 1 2t 1 3t 1 4 t 2 lt 6 4 s l s 2 s - s 口 教室课表： 元t 1 1t 1 2t 1 3t 1 4t 2 lt 6 4 教室 d i 巩 d j d p 第二章计算机编排高校课表问题分析 9 课时单元课时单元按一个大周期减缩后，对一些具有特殊的周期性以及一些不 完全遵守周期性的课程，如单双周课( 周学时数为奇数，在某课时单元两周上一次) ， 阶段课( 在某几周上) 。则可通过在填课表时加入标志进行标示，排课时判断标志 来实现。 课时单元的优度差异：从教学效果的角度衡量，每天的课时单元的优度不同。 一周之内各天的课时单元优度上也有差异。课时单元对不同性质的课程而言优度差 异亦有所不同。如：对英语、数学课而言，l 一2 节的优度最高，且各课时单元的优 度差异较大；而体育课5 6 节优度最高，晚自习不能排课，其他各课时单元的优度 差异不大，将其排在1 2 节则是对课时资源的浪费。 按教育心理学的基本理论，交函数应均匀分布。每门课程占用的课时单元应具 有合理间隔。有利于学生分散理解和记忆。要编排优秀的课表，就要针对有效时间 内人脑的理解和记忆特点、师生教学心理特点，设置课程的“迁移”因素、使各门 课程的课时占用的均衡处于最优。 交函数的周期性和阶段性：每门课的课时占用须具有稳定的规律性。交函数的 基本周期为1 周，扩展周期为2 周( 分单双周的课) 。交函数还具有阶段性，即只 存在于某一阶段( 例如：只上半学期的课) 。周期性和阶段性取决于教学周数和课 程的计划学时数。根据两者合理安排每门课程交函数划定的阶段( 或全程) ，分配 每周的学时数，因每个课时单元为2 学时，所以每周学时数为奇数时，交函数的周 期为2 周。 合班课：同一教师在同一教室给2 个以上的班级授同一门课程为合班课。合班 数具有上限。 附加约束条件：( 1 ) 特殊课程具有特殊的有效课时集( 为总有效课时集的子集， 如体育课) ，教师有时对课时单元有必须满足的要求，特殊课只能在特定教室上。 ( 2 ) 一门课程的周学时数具有上限每个教师的每周学时数具有上限。给同一课 程上课的教师可不止一个，一般不超过2 个。任一教室上课的合班数不超过该教室 的班容量。 课表合理性原则： 均匀原则：一学期内各周的学时数分布均匀；每班的每门课程的课时间隔分 布均匀；每个教师的课时间隔均匀。 教室相对固定原则：每班的上课教室相对固定，不能固定应就近；每个教师 所任的同一门课程的上课教室相对固定。 优度高的课时单元充分利用原则：优度高的课时单元应尽量不空。重点课、 繁难的课应优先排在优度高的课时单元。 照顾特殊的原则：满足某些教师对课时、教室的合理要求，照顾特殊情况。 卫专家系统技术求解课表问题的研究 照顾例行的要求，如双教师的上课时间尽量错开等。 2 3 计算机编排课表的逻辑模型 2 3 1人工排课操作的基本模型 人工排课操作的基本模型如图2 1 所示： 么匹塑捱亟垂k 刊巫亘母 堕亟 图2 1 ：人工排课操作的基本模型 图中：o ：信息处理；口：处理生成信息集：输入输出信息集。 各步处理和每个信息集描述如下： 教学科从各专业教学计划中抽取本学期各专业的教学课程及其有关信息， 汇总编排各专业的课程设置及学时安排表，包括信息： + ( 课程名称+ 总学时数+ 上课周数+ 周学时数+ 上课周分布+ 考核属性( 考 试、考查等) ) 。 各教研室按课程设置表安排任课教师，填报教师任课安排表。表中包括： ( 教师姓名+ 课程名称+ 上课班级+ 周学时数+ 任课周数+ 总学时数+ 周分布 ( 其始周+ 结束周) + 特殊要求) 。 教务科排课，输出课程表：包括：班级课表、教师课表、教室课表和课程 总表。 23 2 业务再造 计算机排课软件系统的设计应从计算机处理问题的特点出发。既考虑计算机所 解决问题的需要又要充分发挥计算机的特点和优势。不限于用计算机取代某些人 工的劳动，而应使问题的处理更加科学化，提高处理水平，这就是进行业务再造。 计算机排课的业务再造主要应有以下几个方面： 建立信息代码体系：建立便于计算机操作的信息代码体系，这不仅是为了便于 操作，提高计算机操作的准确度，也是科学的教务信息管理所必需的。 台理分配计算机的求解域：就人工排课的全部操作，都可由计算机完成，但并 不是所有的步骤由计算机完成都能提高效率和水平。对于各班级各门课程的任课教 师的安排，包含诸多的人的主观意志，而人的脑力劳动含量较少，人工操作更具优 势。用计算机操作却需要输入大量的有关信息，费时费力。因此，将整个排课分为 三步，第一步由计算机编捧课程设置表，第二步人工填报教师任课表，第三步计算 第二章计算机骗排高校课表问题分析 机编排课程上课时间表( 简称课程课时表) 。 调整信息流及数据结构： 对人工操作的表格形式和数据内容进行调整，以便于计算机操作。其中： 课程设置表= 学期+ ( 专业+ ( 课程代码+ 总学时数+ 参考周学时数+ ( 参 考起始周+ 参考结束周) + 考核属性) ) 。此表的编排除了 依据教学计划外，还依据教学进程信息。 教师任课表= 教师代码+ 课程代码+ 上课班级) + 特殊要求+ 周学时数 + 起始周+ 结束周) 。 重构方法结构：g a m i l l e r 在著名的“奇妙的数字7 2 一人类信息处理能力的 限度”一文中指出“人类的分辨和同时处理一类信息的不同品种和等级的数量不超 过j 9 项。分析人工排课的方法步骤正是遵循着这一原理。在编排课程课时表 过程中，先排班级与教师的时间表，再排教室。而一次操作人工难以完成。这样操 作在教室足够多的情况下可充分完成。在教室资源比较紧张的情况下，往往仅为能 排出教室，也要反复调整教师与班级的课时表。难以实现最佳的教室编排。计算机 解决问题不受信息品种和等级、数量的限制。将班级、教师、教室课表同步编排， 可提高教室利用的优度。 课程设置表编排时增加教学进程信息做为输入，输出的课程设置及学时安 排表提供更具体、更具有明确指导作用的周学时分布信息。 2 3 3 计算机编排课表的逻辑模型 系统逻辑模型说明系统的功能组成及信息流，表示如图2 2 。各信息集的信息 项构成在系统详细设计中说明。 图中： 弋= 二：输入输出信息集： ( 二二) ：存储信息集( 文件) o ：人工加工处理： 口：机器加工处理。 专家系统技术求解课表问题的研究 图2 2 计算机编排课表的逻辑模型 第三章醒表编排知识工程的研究 第三章课表编排知识工程的研究 3 1 专家系统技术概述 专家系统技术是人工智能领域的三大分支之一。它的成就及其深刻影响越来 越受各行各业的普遍关注。在专家系统的实践中，根据人类专家的知识和实践经 验、处理问题的思维方式来编写计算机程序。因此，它是一种高质量的具有知识 结构的程序。专家系统技术近年来发展迅速，并开始在各个领域中得到广泛的应 用。由于专家系统包含了人类专家的丰富知识，又能进行逻辑演绎推理，因而能 够在特定领域内象专家样解决问题。因此，用专家系统解决课表编排问题是一 种有效的途径。并且也只有应用专家系统技术才能使该问题得到比较满意的解 决，但这并不等于说。只要应用了专家系统技术，这个问题就迎刃而解了，关键 还是取决于专家系统技术应用的质量。 专家系统是一种计算机程序，它包含了人类专家解决特定问题的丰富知识， 又模仿专家的思维活动、进行推理和判断，是能象专家那样求解专门问题的计算 机程序系统。因此，专家系统必须具备人类专家的知识和运用这些知识求解问题 的方法和能力。 知识就是力量。专家系统的力量，来自它自己所具有的知识。知识是决定 一个专家系统的性能是否优越的主要因素。 专家系统的方法，尊重每一具体的哪怕是极为繁琐的经验，对人类现有的 知识及如何思考以及利用这些知识的启发方法给以高度的重视，使之条理化、表 示成计算机能够运行的形式。其设计过程是把人类专家的知识条理化、精密化的 过程。 应用专家系统技术解决课表编排问题研究的中心工作是课表编排知识工程一 知识的表示、知识的运用和知识的获取方式和方法的研究。 3 1 1 专家系统的基本结构： 专家系统的基本结构如图3 1 描述。 ( 1 )知识库部分：知识库存储着丰富的特定领域专家的知识，包括书本知 识和实践经验知识。这样专家系统可以处理特定范围内的问题。 ( 2 ) 推理机部分，推理机构依据使用者提供的事实，按照专家的思维规律 进行推理和控制，运用知识的规则，得出解决问题的方案。 图3 1 专家系统的基本结构 ( 3 ) 人机界面部分( 或称为信息输入输出部分) 是使用者与系统的接口， 输入使用者的问题和有关信息，输出推理结论。 3 1 2 专家系统的建立 建立专家系统的的中心工作是：知识的表示、知识的运用和知识的获取， 统称为知识工程。“知识工程”一词最初由斯坦福大学的费根鲍姆教授在1 9 7 7 年 “第五届人工智能国际会议”上提出，他说：“知识工程是人们积极利用知识、 经验解决问题作为前提并与人工智能应用有关的一个研究领域。”。知识工程的 研究和计算机密切相关，它要求问题最终用计算机解决。所以知识工程主要研 究如何在计算机中组织知识，建立高质量的知识库，使用系统时，计算机如何不 断地获取到所需新的知识、进行知识的不断更新、并在系统工作实践中总结产生 经验知识以及使用这些知识来解决所要解决的问题。 知识工程所要进行的信息处理是以知识为对象，它比通常以数据为对象的 信息处理涉及的问题要广泛的多、复杂的多。 3 1 3 知识工程 由于知识在专家系统中的决定性作用，所以一般将建立专家系统的过程称 为知识工程。对知识的处理方法是知识工程研究的中新课题。知识工程研究的内 容主要包括以下三个方面： 知识的表示：用计算机模拟人类专家的智能，解决问题的方法。首先系统 要具备解决问题所必须的知识，必须要解决的一个重要问题就是知识在计算机内 的表达方式的问题。获得人类专家的知识后，如何把这些知识表示成计算机“理 解的”能够方便运用的形式，实质上是需要适当的逻辑结构和数据结构以及表示 信息的符号代码，将工作领域的知识表达清楚，并有效地存储在计算机的存储器 中。或者说：知识的表示是指在专门领域内，把教科书式的事实知识和只有特定 第三章课衰墒排知识工程的研究 专家才具有的经验知识形式化使计算机能够接受它、能够对它操作。因此，知 识的表示就是研究如何用合适的形式来表示知识。人工智能的许多技术，如产生 式规则，框架结构、语义网络及符号模式匹配等，为解决这个问题提供有力的工 具。它涉及知识库的设计和管理，把人类专家解决领域问题所用的专门知识和推 理方法通过归纳总结提取出来，转化为计算机内代表知识的符号和数据结构为系 统所用。 微机排课专家系统的知识主要集中于排课人员的经验知识和排课规则。规 则型的知识相对易于表示和运用，而经验性的知识的表示则相对较难，是该课题 集中力量重点研究的对象。 知识的运用：知识的运用是在某一数据结构的基础上，利用形式化的知识 解决问题。在知识的表示时，要考虑其便于运用。知识的运用就是怎样设计推 理机构以利用知识去解决问题。 知识获取：知识获取是对于假设对象的问题领域，把事实知识和经验知识移 植到知识库。它主要包括：从专家那里抽取知识、维持知识库的完整性、新旧知 识的一致性、知识编辑和机器学习等。 微机排课专家系统的知识的获取主要分为两类形式：一是排课通用知识，是 通过由多年排课经验的专职排课教务工作者传授，如图3 2 所示，通过系统设有 的人机界面，以人的自然语言的方式录入计算机，在由系统内部的专门程序转化 成系统的表示形式，其学习性的维护在排课时实时进行：二是每学期进行排课的 班级、教师、教师等的事实知识。每学期进行排课之前都要对这些知识进行维护。 图3 2 知识获取流程 知识工程所要完成的计算机程序和存储文件可用知识工程的一般组成框图 说明：如图3 3 所示。 其中各部分功能为： 综合数据库；用于存放系统运行过程中所需要的和产生的所有信息、 包括问题的描述、中间结果、解决过程的记录等信息。 解释程序：负责回答用户提出的各种问题，包括与系统运行有关的 问题和与运行无关的关于系统自身的一些问题。它是实现系统透明性的 主要部件 知识获取程序：负责管理知识库中的知识，包括根据需要修改，删 除或添加知识及由此引起的一切必要的改动，维持知识库的一致性、完 整性等。 人机界面：负责把用户输入的信息转换成系统的内部表示形式，然 后把这些内部表示交给相应的部件去处理。系统输出的内部信息也由人 机界面转换成用户易于理解的外部表示形式显示给用户。 知识库及推理机：已在专家系统的基本结构中描述。 图3 3 知识工程的一般组成框图 3 1 4 专家系统的特点 知识性：专家系统可以运用专家的知识进行推理，知识的积聚和应用是其 主要特点。这并不是说以往的计算机程序没有使用知识，而应该说那些程序是以 处理数据、数值分析为核心的，不能很好地使用大量的知识，没有以知识的处理 为核心。专家系统的力量来源于知识，专家系统的三个技术关键全都是围绕着知 识的，显然，专家系统的核心是知识。因此，专家系统技术使计算机的应用范围 大大地扩展了。这一点特别重要，世界上相当大部分的工作不是数据计算性的， 即不是以数学公式为核心的。在这种情况下，专家系统技术具有重要的实用价值 【7 】。 计算机排课问题是人们关注而一直未能满意解决的计算机应用领域的一个具 有一定代表性的信息处理问题。早在6 0 年代国内外就开始了对该课题的探索。从 6 3 年c c c c g o t l i e b 给出了课表编排问题的数学模型7 5 年e v e n s 证明了是n p 一 完全的，从而宣布了这一问题的数学求解是几乎不可能的 第三章课表编排知识工程的研究 排课问题虽然是数学上的时间与空间的组合问题，而排课过程却是人的主观 因素作用下的人文决策的过程。要实现用计算机编排课表，如果试图从数学角度 建立模型，研究设计一种计算机算法，无疑使这个问题的解决陷入困境。因此，必 须从根本上摆脱数学算法求解的途径。 用计算机解决这个人文决笨问题，系统设计人员必须按排课专家的思维逻 辑来设计系统，也就是作为专家系统技术应用研究的对象来研究解决。排课专家 应用的不是写入书本的知识，许多知识是模糊知识，而且这些知识又是元知识： 是关于知识的知识、用来指导如何选择事实和规则的知识，比解决具体问题所需 的知识更高层次的知识。其知识工程具有独特的特色，是典型的时间表与多物流 的决策问题。 对于课表编排这个问题。起初人们探索过寻求一种通用的一系列数学上的 公式来解决的途径都失败了 1 0 j o f l 。这正是一个有力的说明。 需要强调特别注意的是：专家系统所具有的知识是特定领域中特定范围内的 高度专门化的知识。只有这样，专家系统才具有领域专家的水平和能力。 灵活性：专家系统的一个重要特征是知识库与推理机构的分离知识库的修 改并不需要涉及推理机构，这样便于知识库的维护。用户可以完全不涉及专家系 统的复杂的内部结构即可方便地对知识库进行增删和修改，这就增加了系统的 灵活性。课表编排专家系统的设计成功地实现了这一点，在下一节对这一点进行 了详细说明。 透明性：专家系统往往具有很强豹解释功能，能够正确地说明推理过程和理 由，可以向用户提供自学和训练。课表编捧专家系统在设计时尽力使之具有完善 的这种功能。 实用性：短短二十年，专家系统已经受到广泛重视，走出实验室进入实用阶 段，就在于其很好的实用性。其实用性表现在；l 、使专家的知识更广泛更长久 的为人类服务。一个新手人工排课，除了要费很多周折外，所排课表的质量远不 及一个有多年工作经验的人员所排课表；2 、专家系统的工作效率高、可靠性好。 应用计算机排课减轻了人工的繁琐劳动，而且工作速度高、花费时间短。而应用 专家系统技术是实现计算机编排课表的有效途径。 3 2 课表编排知识的表示 3 2 1 研究知识表示的理论基础、方法和过程 在课表编捧知识工程的研究过程中，首先归纳人类专家解决排课问题的方 法和运用知识来排课的思维推理方式与求解方法，然后将其表示成能让计算机理 解、运用的专家系统的知识，在通过专家系统的推理机构运用其求解问题。 排课专家排课时，首先要掌握排课资源的详细信息：教室信息，教师信息， 班级信息，根据教研室填报“教师任课安排计划表”编排课程课时表。在编排过 程中，根据某个班级本学期所上课程的学时分布安排各门课程占用课时单元。在 安排课时单元时，时时考虑教室资源及教室占用情况。通过课表编排操作，排出 班级课表、教师课表，然后再编排教室课表。教室课表编排不下时，在调整班级 和教师课表。 三种课表和教师任课安排计划表构成系统求解问题的状态空间，将它们作为 系统综合数据库的成员。在专家系统设计中，综合数据库的设计是必不可少的内 容，这项内容在下一章论述。 排课资源信息是排课推理过程运用的基本信息。“教师任课安排计划表”是 排课过程的求解问题空间或称为求解问题集。在排课时，专家根据一个班级在本 学期所有课程的学时分布、各门课程的属性( 优度要求程度、考核类别等的分布) ， 并兼顾教室占用情况，来确定每门课程课时单元占用方案。取决于学期所有课程 的学时分布、课程属性的课时占用方案是专家解决问题核心知识，若干具体问题 的处理方式和方法也是一种重要的知识这些知识是具体的明确的知识。一个班 级的各门课程之间占用课时单元优度的平衡、班级之间占用课时单元、教师与教 室优度的平衡处理的方式和方法又是一种重要的知识，而这些知识是不具体的、 模糊的知识。这两类( 具体的、模糊的) 知识的表示、运用、获取的质量是课表 编排知识工程研究工作成败的关键。只有把这些知识完整全面地进行表示、合理 准确地运用、并能不断地获取，系统解决问题才能真正达到人类专家的水平。 人类处理问题的知识是多种多样的。如： 关于对象的有关知识的对象知识，排课专家对所排课程、所用排课资源的 知识属此类知识。而此类知识在本课题的研究过程中，以数据库的表示形式 列入综合数据库中。 关于过去发生、现在发生、将要发生的事件及其规律的知识的事件知识。 行为者之间、行为者和行为对象之间在事件中相互作用时所表现行为的行 为知识。 关于某些工作的操作步骤的工序知识。排课所需知识包括一定量的这类知 识。 元知识：是关于知识的知识、用来指导如何选择事实和规则的知识。这是 比解决具体问题所需的知识更高层次的知识。 在知识工程的研究中，从计算机知识工程的角度，通常把问题求解的知识 分为三类： 第三章镰袭囊排知识工程的研究 陈述型知识；这类知识叙述系统状态、环境和条件以及问题的概念、定义 和事实。此类知识在本课题的研究过程中，作为综合数据库的成员予以处理， 这在下一章中讨论。 过程型知识：过程型知识是有关系统状态变化，问题求解过程的操作、演 算和行为的知识。课表编排的操作步骤，使用课表的对象占用排课资源优度 的平衡以及若干具体问题的处理方式和方法，这些既有具体的、而大部分是 模糊的知识属于这类知识，将其和推理机构一起用代码程序进行研究处理。 控制型知识：是关于如何选择相应的操作、演算和行为的比较，判断、管 理和决策的知识。元知识属此类知识。依据一个班级在本学期所有课程的学 时分布、各门课程的属性( 优度要求程度、考核类别分布等) ，来确定每门课 程课时单元占用方案的知识适合于按这类知识处理。 3 2 2捧课知识的归纳与表示 知识的表示是一个复杂的问题，目前还没有对所有问题都适用的知识表示 方法而且以后也不太可能找到这样一种方法。从不同的角度观察问题产生了不 同的表示观点和方法。当前有三种不同的表示观点： 认识论表示观：认为表示是对自然界的描述，表示自身不显示智能行为， 其唯一的作用是携带知识，表示研究与启发式研究无关。 本体论表示观：表示是对自然界的一种近似，它规定了看待自然世界的方 式，既是一种约定的集合。表示知识描述了在这个世界上观察者所关心的那一部 分，其它部分被忽略。 知识工程表示观：认为知识表示是对自然世界描述的计算机模型，它应满 足计算机这一实体的具体限制，可以说是一类数据结构及在其上的一组操作。 在课表编排专家系统的研究中，采用了也比较适合采用知识工程表示。 下面对专家人工编排课表的知识归纳、对课表编排知识工程中知识表示的 研究结果论述如下： 控制型知识：专家人工排课时是以班级课表为中心，同时编排教师课表， 而后编排教室课表。排课时观察该班级的本学期课程门数和属性分布状态，直接 确定课时占用组合方案。用下面一个最简单的例子说明： 例：3 1设某班本学期开设的课程及它们的有关属性如下： 课时单元 课程名称周学时数考核类优度要求等级 k l6aa k 25ba 垫 童塞墨鉴堇垄塞竖竖塞塑壁鲤堑塞 k 35ab k 44ab k 54bb k 63bc 专家确定的排课方案( 后称课时单元占用组合方案) 如下： 同次四五、 节次 1 2 k 1k 4k 1i ( 5k 2 3 4 k 2 k 3k 6k 3k 4k l 5 6 k 5k 2k 6k 3 7 8 如果在教师每人在一学期中只授课一门次和教室资源足够大的情况下，可只 考虑按班级排课，每个班都选最优的方案组合。而实琢上，一个教师尤其是基础 课教师一学期经常讲授两门次以上的课；更尤其是在高校不断扩招的情况下，学 校的教室资源日益紧张，无论合班的大教室和单班教室都必须充分合理地使用， 才能在限定的可排课时单元集内将所有课顺利排出，完成排课任务。所以，不 可能允许所有班级的所有课程都排在优度最好的课时占用方案上。所以该方案 只是作为首选方案，当课排至一定数量时，要考虑教室资源、教室的课时单元资 源、估计教室的占用状态。合班课需占用合班教室。在合班教室资源比较紧张的 情况下要尽早予以考虑，尽量使先排的班级和后排的班级对教室占用和优度高 的课时单元的占用大致平衡，以免后排的班级无教室可排，因此在首选方案不能 使用时，要使用第二方案，第三方案。 例如：可用的第二方案可以是 周次四五、 节次 1 2k 1k 4 k 3k 4k 2 3 4k 5k 1k 6k 1 5 6k 2 k 3k 2k 5k 3 7 8k 6 第三章澡衰编捧知识工程的研究 第二方案该班的课时占用优度比第一方案要低一个等级。 这类知识用分布式的知识表示：分布式表示的知识不依赖于领域中的具体 问题，是一般性知识。将其抽象归纳成数据结构，以数据库文件形式存储，形成 结构化的知识。该知识库存储按照班级学期课程门数和各门课程属性分布状态的 各级课时单元占用组合方案，形成知识库的主体。而班级学期课程门数和属性分 布状态作为检索条件形成知识库的索 i 。例如上例其相应的知识库内容如下： 班级学期课程门数和属性分布状态检索： 检索代码课程门数属性分布状态代码 木十 $ 爿c 十 6 6 a a ，5 t 3 a ，5 a b ，4 a b ，4 b b 4 1 3 c 课时单元占用组合方案知识库中，获取关于首选方案为各门课程分配的课时 单元组合的6 条知识和第二方案的六条知识如下： 检索号：方案级别课时单元数周占用课时单元组合方案 木爿c 木牛术幸木斗13t 1 lt 3 1t 5 2 牛木球木木木木木 l3t 1 2t 3 3t 5 1 木 十牛$ 十十 l3t 1 3t 3 2t 5 3 木木丰年中幸木木l2t 2 1t 4 2 木 木料料丰 12t 2 3 r 4 1 唪卑木牛牛木木木l2t 2 2t 4 3 十木 木$ 木十牛 23t l lt 3 2t 5 2 十幸$ 车 木 23t 1 3 r 3 3t 5 1 卑 率 23y 1 3t 3 1t 5 3 丰术牛术凇木半木 22t 2 lt 4 1 木牛木牛 幸木木 22t 1 2t 4 3 半木十十木木木车 22t 2 4 t 4 2 _ 。 注：符号1 3 1 表示星期三第l ，2 节这个课时单元。依此类推。 过程型知识：专家人工编排课表时的操作程序、具体问题的处理方式和方法、 编排规则、对排课过程出现的各种可能的状态，怎样做好各优度平衡等都表示成 这种知识。关于优度平衡的知识，是专家的模糊知识，经反复试验探索，证明用 过程型知识予以处理效果比较满意。 上述这些知识与具体学校、具体学期所捧的全体及个体课程属性的具体分