（计算机应用技术专业论文）基于回答集程序的时间表问题研究.pdf

r e s e a r c ho ntim e t a bi in g a b s t r a c t u sin ga n s w e rs e tp r o g r a m min g m a j o r ：c o m p u t e ra p p l i c a t i o nt e c h n o l o g y n a m e ：y o n g q u a n - l u s u p e r v i s o r ：j i a w e i w u t i m e t a b l i n gp r o b l e mw h i c h i sat y p i c a lc o m b i n a t o r i a lo p t i m i z a t i o na n dn p - c o m p l e t e p r o b l e m ，h a sav e r yb r o a dp r a c t i c a la p p l i c a t i o n c o u r s ea r r a n g e m e n tp r o b l e m i sat y p i c a l e x a m p l eo ft i m e t a b l i n gp r o b l e m ，i nt h er e s e a r c hf i e l d ，c o u r s ea r r a n g e m e mp r o b l e mi s o f t e n s y n o n y m o u sw i t ht i m e t a b l i n gp r o b l e m i no r d e rt os o l v et i m e t a b l i n gp r o b l e m ，g e n e t i ca l g o r i t h m s ， s i m u l a t e da n n e a l i n g ，g r e e d ya l g o r i t h m sa n dm u l t i a g e n tn e g o t i a t i o na n do t h e ra l g o r i t h m sa l e u s e db ym a n ys c h o l a r s ，t h e s ea l g o r i t h m ss t a r tf r o md i f f e r e n tm o d e l sa n ds o l u t i o nm e t h o d sa n d h a v er e a c h e dc e r t a i na c m e v e m e n t a n s w e rs e tp r o g r a m m i n gi sn o to n l yan e ww a yo fk n o w l e d g er e p r e s e n t a t i o na n dr e a s o n i n g ， b u ta l s oat o o lf o rp r o b l e m s o l v i n g e f f i c i e n ta n s w e rs e ts o l v e rh a sa c h i e v e dg o o dr e s u l t si n s o l v i n go t h e rn p c o m p l e t ep r o b l e m s i nt h i sp a p e r , a n s w e rs e ts o l v e ri su s e dt os o l v et h ec o u r s e a r r a n g e m e n tp r o b l e m ，i t i sac o m p l e t e l yn e wi m p l e m e n t a t i o n f i r s tw eu s ea n s w e rs e t p r o g r a m m i n g t od e s c r i b ef a c t s ，r u l e sa n dc o n s t r a i n t sa c c o r d i n gt ot i m e m b l i n gp r o b l e m s ；t h e nt h e e f f i c i e n ta n s w e rs e ts o l v e ri su s e dt oa c h i e v et h es o l u t i o no ft h ec o u r s ea r r a n g e m e n tp r o b l e m ； f i n a l l y , i nl i n u xs y s t e m s ，u s e ri n t e r f a c ei si m p l e m e n t e d t oo b t a i na g o o di n t e r a c t i o nw i t hu s e r sb y u s i n gj a v al a n g u a g e e x p e r i m e n t ss h o wt h a tt h i sa p p r o a c hc a na d a mt o t h ec h a n g eo fc o u r s e a r r a n g i n g b e s i d e s ，i tc a na r r a n g eas a t i s f i e dc u r r i c u l u mi na na c c e p t a b l et i m eb e c a u s eo fi t s f l e x i b i l i t ya n ds c a l a b i l i t y k e yw o r d s ：k n o w l e d g er e p r e s e n t a t i o na n dr e a s o n i n g ，l o g i cp r o g r a m ，a n s w e rs e t p r o g r a m m i n g ， a n s w e rs e ts o l v e r ， a l g o r i t h m n i l l l f肼 y 1 7 6 8 1 彳芎 1 3 本文所做的工作和论文结构2 第二章时间表问题4 2 1 时间表问题概述4 2 2 排课问题理论研究4 2 2 1 排课问题的组合爆炸和不确定性4 2 2 2 目前的排课问题研究中所使用的算法6 2 3 时间表问题的分类：6 2 4 排课算法研究7 2 4 1 基于遗传算法的排课算法0 7 2 4 2 基于模拟退火算法的排课算法8 2 4 3 基于多a g e n t 协商技术的排课算法9 2 4 4 基于贪婪算法的排课算法1 0 2 4 5 排课算法小结1 0 第三章回答集程序设计1 1 3 1 概述11 。 3 1 1 背景知识1 1 3 1 2 语法和语义上的扩展1 2 3 1 3 典型的应用形式1 5 3 2 求解器前端1 7 3 2 1 l p a r s e 一18 3 2 2 d l v ( 使用一i n s t a n t i a t e 参数) 2 0 i l l t l t l t l - - 一 u ， 2 2 一 - 3 2 3g r i n g o 2 1 3 2 4 其它前端2 1 3 2 5 各前端所接受的语法小结2 1 3 3 基本的回答集求解算法2 2 3 3 1s m o d e l s 2 3 3 3 2d l v 2 4 3 3 3 基于s a t 的求解器2 4 3 3 4c l a s p 2 7 3 3 5 回答集求解算法小结2 8 第四章基于回答集程序的排课系统设计与实现3 0 4 1系统概述3 0 4 2 排课系统基本要素3 卜 4 3 排课系统约束条件3 卜 4 4 排课系统基本要素的a s p 表示3 2 4 5 排课系统约束条件的a s p 表示3 3 4 5 1 逻辑约束3 4 4 5 2 基本硬约束3 4 4 5 3 硬约束3 5 4 5 4 软约束3 6 4 6 用户界面的实现3 7 4 6 1 程序系统结构3 7 4 6 2 系统流程图3 9 4 6 3 数据输入4 0 4 6 4 数据输出4 5 4 7 实验结果4 6 第五章总结与展望4 8 5 1 本文工作总结4 8 5 2 存在的问题及未来工作展望4 8 参考文献4 9 附录5 3 翌i 【谢。6 8 攻读学位期间发表的学术论文6 9 i v 基丁同答集稃序的时间表问题研究 第一章绪论 1 1 课题背景、研究的目的和意义 1 1 1 课题背景 国外从2 0 世纪5 0 年代术就丌始对排课问题进行研究。1 9 6 3 年g o t h e b 在他的文章【l 】 中提出了排课问题的数学模型，标志着排课问题的研究f 式跨入了庄严的科学殿堂，但由 于在实践中遇到了困难，使人们对排课问题的解是否存在产生了疑问。1 9 7 6 年s e v e n 在 论文中证明了排课问题是n p 完全的【2 】。这虽然回答了排课在实践中遇到困难的原因，但 同时等于宣布计算机解决排课问题将无法实现，因为现代计算机尚未找到解决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 t r i p a t h y 还研究了研究生课表编排问题。j a c q u e s a f e r l a n d 等人则把 排课问题分成两个子问题：时间表问题和分组问题。在时间表问题中，根据学生注册情况、 教师和教室的可利用情况形成一个主时间表。对于选课人数较多的大课，一个星期要分成 几个时间段来上，分组问题就是将学生分给各时间段。 国内对排课问题的研究开始于8 0 年代初期，所用方法从模拟手工排课到运用人工智 能构建专家系统或决策支持系统的都有。基于时间位图迭加匹配的算法【1 4 】定义了教学过程 中的时间位图、课时模式和时间匹配等概念，将排课问题转化为基于时间位图迭加匹配的 课时模式查找问题，给出了相应的抽象和具体的排课过程，并对于排课过程中可能出现的 冲突，探讨了三种通过回溯消除冲突的方式。 目前国内所研究的排课系统有基于多a g e n t 协商技术【2 2 1 、基于遗传算法【引、基于模拟 退火算、法【1 2 1 、基于分组优化与矩阵运算【2 1 1 等方法。 成形的系统有大连理工大学1 9 9 8 年推出的教学调度系统3 0 0 版本【1 9 1 和由清华大学计 基于同答集程序的时间表问题研究 算机与信息管理中心丌发的综合教务管理系统【2 0 】。 目前对排课问题的研究普遍存在以下两个问题： 国内外对排课问题的研究在理论研究上做得很多而实际应用上做得很少。 现有的排课系统通常无法做到既高效地求解排课问题又灵活定义各种用户约束。 1 1 2 研究的目的和意义 本课题研究的目的在于针对目日驴国内外对排课问题在理论研究上在做得很多而在实际 应用上做得很少的事实，通过研究实现一个高效的排课系统；且该排课系统既能高效地求 解排课问题，又能提供灵活定义各种用户约束的方式。 实现该排课系统的意义在于： 排课表问题属于时问表问题的一种。作为一个n p 完全问题，目前一般认为没有有 效的( 即多项式时间复杂度的) 求解时间表问题的算法。常用的实现方法包括启发式求解、 约束程序设计( c o n s t r a i n tp r o g r a m m i n g ) 、模拟退火算法以及遗传算法等，本文采用了 一种新的基于回答集程序的方法来求解排课问题。 对于一个实际的排课表系统而言，能否有效和自由地描述用户的需求也是很重要 的。本研究通过提供对硬约束的灵活定义和实现软约束的方式较好的解决了这一问题。 针对教务管理排课问题，完成课表的生成，有较好的应用价值和学术研究价值。 1 2 课题来源 本课题的来源有：国家自然科学基金“一阶环和环公式在非经典逻辑计算中的理论 与应用 ( n s f c 6 0 7 0 3 0 9 5 ) ；广东省自然科学基金“一阶回答集求解器研究” ( g d s f 0 7 3 0 0 2 3 7 ) ；2 0 0 8 年度华南师范大学校外科研课题基于回答集程序的排课表系 统。 1 3 本文所做的工作和论文结构 本文所做的工作主要有三点，首先，用回答集程序设计语言完整地描述了排课过程中 的约束条件，并把高效的排课算法引入到回答集程序设计中；其次，选择了一个适合排课 算法的回答集求解器及相应的求解器前端，并对回答集求解器所支持的语法及求解算法做 基丁同答集程序的时间表问题研究 2 1 时间表问题概述 第二章时间表问题 时间表问题是典型的组合优化和不确定调度问题，也被证明为是n p 完全问题1 2 j 。时间 表的实际应用非常广泛，如：运输网络的服务调度、人力资源配置管理、输电系统最优规 划问题等，而最突出的莫过于课程表的编排问题。课程表编排问题是一个非常难的优化组 合问题，是时间表问题( t i m et a b l ep r o b l e m s ，t t p ) 的一个典型实例，在研究领域中， 它常常是时间表问题的代名词。课程编排是高校教学管理中一项重要且复杂的基本工作， 其实质就是为学校所设置的课程安排上课的学生和授课的老师，每门课程在某一时间需要 某个上课场地( 教室、实验室、体育场) ，并且要满足一些特殊的需求。然而，由于必 须被考虑的约束条件的多样性，自动排课成为相当困难的问题【3 2 1 。 2 排课问题理论研究 课程表的编排问题在教务工作中处于非常重要的地位，我国各类学校根据教学计划的 要求，在每个新学期开始之前，必须根据本校课程设置以及教师、学生、教室、设备等具 体情况，编排一个教学活动时间表( 俗称课程表) ，以便有序地组织全校的教学活动。 2 2 1 排课问题的组合爆炸和不确定性 经典的组合规划问题的求解，主要依靠约束条件来实现。只要约束条件充分，那么最 优的组合方案就能被唯一确定。因此，从理论角度来说，组合规划作为描述课表问题的数 学模型并无不妥。然而，在实际工作中随着论域范围的膨胀，即组合方案数的增加，规划 问题也就变得十分复杂。 让我们来考察以下一种极其简单的课表情况，假设工作同仅为周一至周五，一天内仅 有6 节课( 上午4 节，下午2 节) ，上课方式都为一个课次2 个相邻的节次，且不能在上、 下午之间跨时段。则从课程安排类似空格填充的角度，该排课问题可以看成是填充一张 3 5 的表格，如表2 1 所示。 基于同答集程序的时间表问题研究 表2 1 一张3 5 课表 设表格的空格数为r l ，某门课程的计划课丌课次数为m ，则该门课程的组合方案数为 钟，考虑m = l ，2 ，3 ，n = l ，2 ，1 5 ，当n 和m 变化时，课程编排方案数变化如表2 2 和图2 1 所示。 表2 2 课表组合方案数量变化表 童 l 234 5 67 8 9l o1 l 1 2 1 31 4 1 5 r l l ll 2 34 5 67891 0l l 1 2 1 3 1 4 1 5 2ol361 01 52 l2 83 64 55 56 67 89 l1 0 5 3oo14l o2 03 55 68 41 2 01 6 52 2 02 8 63 6 44 5 5 图2 1 课表组合方案数量变化图 - 5 基丁同答集程序的时间表问题研究 从表2 2 和图2 1 可以看出： m 不变，1 1 增加，课表组合方案数量增加； 1 1 不变，m 增加，课表组合方案数量增加； n 和m 同时增加，课表组合方案数量急剧增加； 如果还要考虑各门课程在排课计划中的先后次序以及单、双周上的变化，那么组合方 案的可能数目随着问题规模的增长将急剧上升。这种空问向量稍有增加，就引起课表编排 方案数量急剧增加的现象，称为“组合爆炸。因此，如何从实际情况出发，采取适当的 措施，抑制“组合爆炸”，缩小搜索空间，成为排课问题中的一个关键问题。 2 2 2 目前的排课问题研究中所使用的算法 目前对排课问题的研究一般都是基于一定的排课算法的。在 9 1 1 0 1l 】【1 2 】中一批学者 将模拟退火法应用到对排课问题的研究中。模拟退火法( 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 年首先提出的【1 3 j ，它是人们从自然界固体退火过程中得到启发并从中抽象出 来的一种随机优化算法。模拟退火法被用来解决许多实际应用中的优化问题，取得了不错 的效果。 基于优先级自动排课算法【1 5 1 利用了运筹学中分层规划的思想，把排课问题从数学上看 成一个在时间、教师、学生和教室组成的四维空间，并以教学计划和各种特殊要求为约束 条件的组合规划问题。采用了化整为零的思想并提出了优先级的概念，有效地抽象了实际 的排课问题，从而缩小了问题求解的复杂度。 基于专家系统的求解算法【1 6 l 【1 7 】将专家系统知识引入排课问题的求解中，有效组织排 课过程中的知识，使各种排课逻辑从程序中解放出来，能够便于各种排课经验的累计，使 排课结果更加符合实际情况。 基于多a g e n t 系统的排课算法利用系统内部多个a g e n t 成员之间的相互协作、协商， 来共同完成一项复杂的排课任务，把对排课问题的求解转化为对多个a g e n t 的合理设计上 来，取得了较好的排课效果【2 2 1 。 3 时间表问题的分类 结合目前人们对时间表问题的研究成果，根据问题的要求和其他的约束条件，可以把 时间表问题分成三类： 基于同答集稃序的时间表问题研究 中、小学时间表( s c h o o lt i m e t a b l i n g ) ：在满足班级、教师等和对于时间的一致 情况下，对所有的班级安排每一周的授课任务。 大学课程时间表( u n i v e r s i t yc o u r s et i m e t b l i n g ) ：除了满足上述的条件外，还 必须考虑课室问题、选修课问题、教师不同校区上课以及单双周等问题。 考试时间安排表( e x a m i n a t i o nt i m e t a b l i n g ) ：安排除了满足上述两种情况外， 还要求考试科目尽量地分散开，以使学生有充分的复习调整时间。 需要说明的是，上述分类是不严密的，只是一个大概的分类。可能会有一些特殊的问 题居于上述三类问题的某两个分类之间，不能轻易地把它归之于上述三类问题的某一类 中。 2 4 排课算法研究 由于目前国内所使用的排课算法多种多样，在求解方法和求解效率上也存在着显著的 差异，下面目前国内所使用的主要的排课算法总结研究如下。在分析总结过程中主要总结 了各排课算法的基本原理、实用性以及求解效率等方面的问题。 2 4 1 基于遗传算法的排课算法 遗传算法( g e n e t i ca l g o r i t h m s ，g a ) 是一种借鉴生物界自然选择和自然遗传机制的随 机搜索算法，其主要特点是群体搜索策略和种群中个体之间的信息交换。它尤其适用于处 理传统搜索方法难以解决的复杂的和非线性的问题。目前遗传算法已被广泛应用于组合优 化、机器学习、自适应控制、规划设计和人工智能等领域。 遗传算法的基本思想是从问题可能潜在解集的一个种群开始的，一个种群则由经过基 因编码的一定数目的个体( i n d i v i d u a l ) 组成，每个个体实际上是染色体( c h r o m o s o m e ) 带有特征的实体。染色体作为遗传物质的主要载体，其内部表现是某种基因组合，它决定 了个体的性状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决 定的。初始种群产生以后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的 近似解。在每一代里，根据问题域中个体的适应度( f i t n e s s ) 大小挑选个体，并借助于自 然遗传学的遗传算子( g e n e t i co p e r a t o r s ) 进行组合、交叉和变异，产生出代表新的解集的 种群。这一过程将使得种群象自然进化过程一样，后代种群比前代更加适应环境。末代种 群中的最优个体经过解码，可以作为需要求解的问题的近似最优解。 根据确立的排课目标和建立的数学模型，遗传算法解决排课问题的求解过程一般分为 基于同答集程序的时间表问题研究 两个部分来进行，第一部分是根据教学计划将无序的原始数据( 教学任务) 进行随机可行排 课操作，生成有序的最终数据( 课表) ；第二部分是应用遗传算法对产生的排课方案进行“全 局优化”。 随机求解排课方案的过程以开课计划为主线，将教学计划中的教师、班级、课程作为 一个整体绑定，我们定义这个整体为教师元组。即一个教师元组包含三个元素：教师、班 级和课程。给教学任务书中的每门课程随机分配时间和教室，生成可行排课课表。再应用 遗传操作对产生的随机可行方案进行全局优化。由于遗传算法在求解组合优化问题中表现 出智能性、并行性和鲁棒性，而且遗传操作简单，用来求解有约束的、模糊多目标的排课 问题是十分适宜的。根据遗传算法的一般结构，遗传算法一般进行以下工作： 对排课问题进行编码，以基因和染色体的方式来表示排课问题中的各个变量，并 对遗传、交叉和变异的遗传操作算子进行设计。 计算适应度函数，用适应度函数来判定课表方案的优劣，使之收敛于一个全局最 优解。 排课算法的作用就是将无序的原始数据进行一系列的操作，将时间因素和教室因 素等加入到排课任务中去，从而生成有效的课表。 2 4 2 基于模拟退火算法的排课算法 模拟退火算法是局部搜索算法的扩展，从理论上来说它是一个全局最优算法。模拟退 火算法的思想来源于对固体退火降温过程的模拟：即将固体加热至温度充分高，再让其缓 慢冷却。在加热固体时，固体中原子的热运动不断增强，内能增大，随着温度的不断升高， 固体的长程有序被彻底破坏，固体内部粒子随温度的升高而变为无序状态。冷却时，粒子 逐渐趋于有序，在每个温度下都达到平衡状态，最后在常温下达到基态，同时内能也减为 最小。 在实际应用中，可以将内能e 模拟为目标函数值f ，将温度t 模拟为控制参数，然后 从某一给定解开始，从这一给定解的邻域中随机产生一个新解，接受准则允许目标函数在 一定范围内接受使目标函数恶化的解，算法持续进行“产生新解计算目标函数差 判断是否接受新解接受或舍弃 的迭代过程，对应着固体在某一恒定温度下趋于热平 衡的过程。经过迭代后，可以求得给定控制参数t 值的相对最优解。然后减小控制参数t 的值，重复执行上述迭代过程。当控制参数逐渐减小并趋于零时，系统也越来越趋于平衡 基于同答集程序的时间表问题研究 状态对应于优化问题的整体最优解。 算法实现排课的近似最优解是一种比较简单的方法，收敛速度很快，最大 分配均匀。实际应用中也可以没有终止条件，可以依次提供不同的可行解 。如果只考虑最优解的问题，可以多次实验选择较好的迭代控制参数。用 难之处在于控制参数的选择，选择不恰当的参数可能使迭代不收敛或运行 多a g e n t 协商技术的排课算法 统( m u l t i a g e n ts y s e t i l l ) 是由异构、分步、动念、大规模、自治a g e n t 构成 的系统，即多a g e n t 系统是由多个可计算的a g e n t 组成的集合。其中每个a g e n t 是一个物 理或抽象的实体，可作用于自身和环境，并与其他的a g n e t 通信。各a g n e t 之间活动是自 治的和独立的，行为和意图不受其他a g e m 限制，他们之问通过竞争、协商、协作等手段 来共同完成系统设定的目标。 对于怎样将有限的资源在多个a g e m 之间进行最大效益的分配是解决问题的关键，其 中最主要的一个难点和重点是如何在多个a g e m 中进行协商，使得能够解除冲突，达到资 源共享。在人类现实生活中，很多计算机应用问题都是通过协商来解决的，如资源分配 ( r e s o u r e ea l l o c a t i o n ) 、任务分配( t a s ka l l o c a t i o n ) 、规划和时间调度( p l a n n i n ga n ds c h e d u l i n g ) 、 路由选择( r o u t i n g ) 等。在计算机系统的资源分配中，多个系统需要共享现有的系统资源来 实现自己不同的目的，资源如何分配就取决于系统之间的协商。 基于多a g e m 协商技术的排课系统采用目前最热门的多a g e n t 系统技术来解决排课资 源冲突和教师满意度问题，建立一个拟人化的多a g e n t 系统的智能排课系统，重点强调考 虑授课教师的个人期望，每一个a g e n t 代表一个教师来建立一个多a g e m 环境。基于多a g e n t 协商技术的排课系统的关键在于不同教师a g e n t 在资源冲突过程中的协商。这个协商的过 程可以解决排课过程中的资源冲突和改善教师对课表的满意度。多a g e n t 技术能够使排课 系统适应不断变化的动态环境，通过多a g e n t 之间的协商能够更好的分配动念资源，利用 多a g e n t 之间的协商来代替教师之间的实际协调，降低了行政单位与教师之间以及教师与 教师之间排课协调的时间。以教师偏好来协商排课能在不违反公平正义的原则下满足多数 教师的个人排课期望，避免教师因排课不公产生不满情绪而影响教育教学质量。 基丁同答集稃序的时间表问题研究 2 4 4 基于贪婪算法的排课算法 贪婪算法( g r e e d ym e t h o d ) 从问题的某一个初始解出发，通过一系列的贪婪选择( 当 前状态下的最优选择) 逐步逼近给定的目标，以尽可能快地求得更好的解。当到达算法中 的某一步不能再继续前进时，算法停止。在贪婪算法中采用逐步构造最优解的方法，在每 个阶段都作出一个看上去最优的决策，决策一旦作出，就不能再更改。作出贪婪决策的依 据称为贪婪准则( g r e e d yc r it e r i o n ) 。 在基于贪婪算法的排课系统中，根据实际情况采用贪婪算法。贪婪算法不追求最优解， 不要回溯，只希望得到较为满意的解。虽然贪婪法不是对所有问题都能得到整体最优解， 但对范围相当广泛的求最优解问题来说，它是一种最直接的算法设计技术。贪婪算法通过 一系列局部最优解的选择( 即贪婪选择) 可以产生整体最优解。具体地说，通常所求问题 的一个整体最优解，是从贪婪选择开始的。并且每作一步贪婪选择后原问题可简化为一个 规模更小的子问题，经过多步贪婪选择，最终可得到问题的整体最优解。 2 4 5 排课算法小结 排课问题是n p 完全问题，许多学者分别在基于遗传算法、模拟退火算法、贪婪算法 及多a g e n t 协商技术等排课应用求解上作了很多研究。各种排课算法都是从不同的模型、 算法和求解方法上入手并取得了一定成效，对后继者有一定的借鉴意义，但仍然存在一些 不足。如基于遗传算法的排课系统能够快速收敛于近似最优解，但却在最优解附近徘徊甚 至停止，这是遗传算法至今还没有很好解决的问题，即遗传算法很难在收敛速度和收敛于 最优解之间取得平衡。现有排课系统重点考虑一般性排课原则，初排后往往需要针对各种 特殊情况进行人工调整。满足各种特殊要求是有效完成课表编排工作的重要指标，过多依 赖于人工调整无法充分体现出计算机排课的优越性，尤其是智能化的特性。现有的排课系 统大多属于教务处的单机封闭作业，且排课策略大多只求排出满足各种实际限制的课表。 现有排课系统少有提供教师直接对系统表达排课偏好的管道，未能体现智能排课系统的人 机互动化、透明化和人性化。 基于同答集程序的时间表问题研究 3 1 概述 第三章回答集程序设计 逻辑程序的回答集( a n s w e rs e t ，也被称为稳定模型，s t a b l em o d e l ) 语义最初是在 【3 3 】中为一般逻辑程序( n o r m a ll o g i cp r o g r a m ) 定义的。随后在 2 8 1 被推广到包含经典 否定的扩展逻辑程序( e x t e n d e dl o g i cp r o g r a m ) 和析取逻辑程序( d i s j u n c t i v el o g i c p r o g r a m ) ，在 3 0 和 3 4 中被推广到嵌套表达( n e s t e de x p r e s s i o n ) 和任意的公式。 回答集语义除了具有理论上的意义之外，从 3 5 开始基于回答集语义的逻辑程序丌始 作为一种问题求解的程序设计方式被加以应用，并且取得许多具体的应用成果，其中包括： 航天飞机【3 6 1 ，程序配置1 3 7 1 ，生物信息【3 8 】，动物学和语言学1 3 9 】等等。 在这些应用的推动下，回答集求解器的研究和开发就成为了一个重要的方向。最近几 年，已经研究出很多的回答集求解器用来计算逻辑程序的回答集，其中包括s m o d e l $ 【2 5 1 ， d l v m o 】， a s s a t 【2 7 1 ，c m o d e l s 【2 9 】，c l a s p l 2 4 1 等。目前的回答集求解器都是设计为计算命题逻 辑程序的回答集的，为了处理包含变量的程序，回答集求解器都采用两层体系结构。第一 层是求解器的前端( f r o n t e n d ，也称为g r o u n d e r s ) ，专门用来进行逻辑程序的实例化( 即 把包含变量的程序转换为命题程序) 。目前绝大多数的求解器都使用l p a r s e 或d 1 v 作为 前端，这两个前端都能用于实例化包含析取和经典否定的程序，另外它们都在各自的语法 和语义上进行了一些扩展。第二层是回答集求解引擎，接收由第一层实例化后得到的命题 程序并计算出回答集。 3 1 1 背景知识 回答集程序由规则、事实、约束和一些说明性的文字组成。规则( r u l e s ) 是回答集程序 设计中常用的语法类型，在规则中可以实现对谓词进行推理。规则形如( 1 ) 所示： h e a d6 - - b o 咖 ( 1 ) 规则( 1 ) 的直观语义是如果规则体( b o d y ) 被满足，则规则头( h e a d ) 相应地也应该得到满 足。事实( f a c t ) 可以表示为c o u r s e ( c ) 、c o u r s e _ t e a c h e r ( c ，g ) 等形式，c o u r s e ( c ) 表示第c 门课程， c o u r s e t e a c h e r ( c ，g ) 表示第c 门课程由g 老师来上。约束( c o n s t r a i n t s ) 是规则头 为空的规则，表达的是回答集程序中一类必须满足或者应当尽可能得到满足的关系。 基于同答集程序的时间表问题研究 命题语言下的析取逻辑程序的回答集语义定义如下。考虑一个命题语言l ，即一个原 子的集合，程序是由如下形式的规则组成的： 啊v v h 女 - - 6 l ，b m ，n o t 既+ 1 ，n o t 以( 2 ) 其中7 j lv v 吃称为规则头，岛，k ，n o t b m 巾，n o t 吃称为规则体，岛，b m 称为正规 贝d j ( p o s i t i v er u l e ) ，n o t 瓦+ l ，n o t 色称为负规则( n e g a t i v er u l e ) 。析取程序的回答集是指 当规则体6 l ，b 埘，n o t6 肌+ ，n o t 屯被满足时所对应的规则头 v v 魄的最小模型。 下面通过一个具体的事例来说明析取程序的回答集：如果房问是明亮的，这时可能的 原因是外面有阳光或是房问里开着灯。该事例可以表达为如下的析取逻辑程序： s u nv t i g h t 卜b r i g h t e n ( 3 ) 对上述规则( 3 ) 而言有三种可能的模型： s u n ， l i g h t ) ， s u n ，l i g h t 。但这三个模 型中只有模型( s u n 或 l i g h t 才是规则( 3 ) 的回答集，模型 s u n ，l i g h t 是模型 s u n 和 l i g h t ) 的超集，不是最小模型，因而 s u i l ，l i g h t 不是程序的回答集。 3 1 2 语法和语义上的扩展 原子p 或p 的否定形式1 p 称为文字，具有文字的逻辑程序称为扩展逻辑程序 ( e x t e n d e dl o g i cp r o g r a m s ) 。在实际的应用中，很多回答集求解器都会为回答集程序的语法 进行扩展，以下是一些主要的扩展。 变量，函数和论域 在实际的回答集程序设计中，程序通常是用一阶语言描述的。给定一个一阶的字母表 仃，常量、变量、函数和项都如一般的一阶逻辑中的定义。程序的原子形如p ( t 。，2 ，r 。) ， 其中p 是一个n 项谓词符号，t it z ，厶为项。给定一个论域d ，一阶程序p 是如下的规则 的集合： r ( r a r ( r ) c ) i ，尸，ced ” 其中，( v a r ( ，) ；是一个替换，v a r ( r ) 茭jr 中出现的所有变量的集合，i l f 为变量的个数。将 一阶程序转化为相应的命题程序的过程称为实例化( i n s t a n t i a t e ) ，实例化后所得到的程序 称为基程序( g r o u n dp r o g r a m ) 。给定一个论域，一阶程序的回答集语义等价于它对应的 基于同答集程序的时间表问题研究 命题程序的回答集语义。 各种回答集求解器的前端都提供了丰富的函数方便程序的编写，其中包括常用的算术 函数和聚集函数。变量的论域可以在程序中显式地定义，也可以通过程序中出现的常量隐 含的给出。由于函数和论域的出现，如果不对程序的语法做出某种约束，将可能导致实例 化的结果是一个无穷的程序。因此不同的求解器前端都对其所接受的语法做出了相应的限 制。 选择规则( c h o i c er u l e ) ：选择规则具有形如规则( 4 ) 和规则( 5 ) 的两种表达形式： l o w e r h l 一， 。 u p p e r ：- b o d y ( 4 ) l o w e r 1 = w l ，吃= w u p p e r ：一b o d y ( 5 ) 如果选择规则( 4 ) 、( 5 ) 中的规则体被满足，则规则头中 ，吃的个数或权重之和 必须处于l o w e r 和u p p e r 之间。例如l a ，b 2 的回答集为 a ) ， b 和 a ，b ) 三个，而l a ， b l 的回答集则只有 a ) 和 b ) 两个。对于程序中缺少边界的情形，如果缺少下边界j 则默 认的下边界为负无穷大。如果缺少上边界，则默认上边界为正无穷大。如果上下边界都缺 少，则规则头中的任意个原子组成的模型都是回答集。例如缺少上边界的程序l a ，b ) 有 三个回答集，分别为 a ) ， b ) ，和 a ，b ) 。 d l v 中的弱约束( w e a kc o n s t r a i n t ) ：d l v 中的弱约束允许我们使用一种更容易和 自然的方式去阐明一些优化问题。完整性约束( 强约束) 总是必须满足的，在程序中如果 完整性约束没有得到满足则程序的回答集不可能建立。而弱约束表达的是一种迫切需要满 足的意思，也就是说如果有可能，弱约束应该得到满足，但弱约束不满足时并不影响回答 集的建立。具有弱约束集合w 的程序p 的回答集是指违反弱约束最少的那些模型，称之 为( p ，w ) 的最佳模型( b e s tm o d e l s ) ，一个程序可能有多个最佳模型，因为这些模型可能都 违反了相同数目的弱约束且数目都是最少的。弱约束的表达既可以根据他们的重要性赋予 不同的权重( 权重越高，约束越强) ，最佳模型是所违反的弱约束的权重之和最小的模型， 也可以赋予弱约束不同的优先次序，最佳模型首先考虑不违反优先级最高的弱约束，然后 以降序依次考虑优先级降低的弱约束，最终建立最佳模型。语法上，弱约束可以表达为约 束( 6 ) 的形式： ： c o n y w e i g h t ：l e v e l 】( 6 ) 在约束( 6 ) 中c o n j 是文字的合取，权重和优先级都是正整数。考虑一个弱约束的程 基于同答集程序的时间表问题研究 序如程序( 1 ) 所示： 程序( 1 ) ： avb c ：b ：a ：b ：c 虽然程序( 1 ) 中省略了弱约束的权重和优先级，但它们都被缺省设置为1 。程序( 1 ) 在d l v 中