（管理科学与工程专业论文）基于事例推理的稿件刊发计划的建模方法研究.pdf

基于事例推理的稿件刊发计划的建模方法研究 摘要 客观条件不断变化要求解决问题的模型也要动态地进行调整，而稿件干u 发计划正是 这样一个问题。本文就是针对这一问题提出的，应用知识工程理论、机器学习理论、专 家系统理论、运筹学理论和数据库理论方法，对稿件刊发计划问题进行了分析、研究， 给出了基于事例学习的稿件刊发计划模型的建模方法，并根据基于事例推理的理论和方 法、稿件刊发计划问题模型的特点，对基于事例推理的稿件干u 发计划的建模方法所包含 的一系列问题进行了研究。 这些研究工作包括： 审事例和问题的知识表示：给出属性集、结构集和目标集的事例表示方法； 夺知识化模型的推理：结构化的模型如何转化为求解系统可识别的属性模型的过 程： 夺最相似事例的确定：两步选择过程，粗选过程按属性相交度，精选按类比转换 的规则驱动的确定最相似事例的原则和方法； 夺类比转换的方法：确定在一定条件下的转换方法； 夺事例库的维护：事例库是可维护的，一方面随着系统解决问题的增多，事例库 也会不断扩大知识领域；另一方面，通过事例库维护模块，可以从用户那里得 到新的建模知识。 最后一部分描述了稿件刊发计划建模子系统的分析和设计，包括系统总体设计、功 能分析、数据库设计等环节，然后通过一个实例来分析用户界面的操作过程。 基于事例学习的稿件干0 发计划模型解决了稿件刊发计划过程中参数和约束条件动态 变化的问题，在运筹学模型的知识化与智能化方面研究做了理论和应用上的研究。同时， 稿件刊发计划问题是调度排序问题的一种，本文对解决这一类问题具有普遍的指导意义。 关键词：基于事例学习：稿件刊发计划；事例表示：事例检索 基于事例推理的稿件刊发计划的建模方洁研究 a b s t r a c t m o d e ls h o u l db ea d j u s t e dd y n a m i c a l l ya ss o o r la st h es i t u a t i o nc h a n g e s ，a n ds c h e d u l e s u b s y s t e mf o rm a n u s c r i p tp u b l i c a t i o ni s s u c hap r o b l e m f 0 rm i sr e a s o n am e t h o do f s c h e d u l ef o rm a n u s c r i p tp u b l i c a t i o nb a s e do nc a s e b a s e d r e a s o n i n g w h i c hi n c l u d e s k n o w l e d g ee n g i n e e r i n g ，m a c h i n el e a r n i n g ，e x p e r ts y s t e m ，o p e r a t i o n r e s e a r c ha n dd a t a b a s e t h e o r yi sr a i s e d a n dt h e ns e v e r a lp r o b l e m sa b o u t i ta c c o r d i n gt oc b r t h e o r ya n d t h ef e a t u r c s o f m a n u s c r i p t p u b l i c a t i o na r es t u d i e d t h e p r o b l e m sf o c u s o n ： 夺t h e r e p r e s e n t a t i o no f c a s ea n dp r o b l e m ：a r e p r e s e n t a t i o nm e t h o di n c l u d i n ga t t r i b u t e s e t ，s t r u c t u r es e ta n dg o a ls e t 夺t h er e a s o n i n go fs t r u c t u r e dm o d e l ：h o wt ot r a n s f e rs t r u c t u r e dm o d e li n t o m a t h e m a t i c a lm o d e lt h a tc a nb es o l v e db ya na r i t h m e t i cs y s t e m ； 夺t h ed e t e r m i n a t i o no ft h em o s ta p p r o p r i a t et a r g e tc a s ei n c l u d e st w os t e p s ：t h ef i r s ti s w i d er e t r i e v a l a n dt h es e c o n di se x t r a c tr e t r i e v a it h a ti sam e m o dd r i v e nb y a d a p t a t i o nr u l e s 夺t h ec a s eb a s em a i n t e n a n c e ：c a s es t o r a g ea n dc a s ek n o w l e d g em a i n t e n a n c e t h el a s tp a r to ft h i sp a p e ri sa b o u tt h er e a li n f o r m a t i o ns y s t e m ，w h i c hi n t r o d u c e st h e a n a l y s i sa n dd e s i g no f t h ei n f o r m a t i o ns y s t e ma n du s e sar e a lc a s et od e s c r i b eh o wt h es y s t e m o p e r a t e s t h es c h e d u l em o d e lf o rm a n u s c r i p tp u b l i c a t i o nb a s e do i lc b rs o l v e st h ep r o b l e m c a u s e db yd y n a m i cc h a n g i n go fp a r a m e t e r sa n ds u b j e c t so fs t a t i cm o d e l i te s t a b l i s h e st h e b a s e st om a k em o d e l so fo p e r a t i o nr e s e a r c hk n o w l e d g e a b l ea n di n t e l l i g e n ta n di t i sa l s o h e l p f u l t os o l v es u c hak i n do fs c h e d u l ep r o b l e m s k e y w o r d s ： c a s e b a s e d l e a r n i n g ；s c h e d u l es u b s y s t e mf o rm a n u s c r i p tp u b l i c a t i o n ， c a s e r e p r e s e n t a t i o n ；c a s er e t r i e v a l 基于事例推理的稿件刊发计划的建模方法研究 1 引言 1 1 问题的提出及研究意义 随着当今社会科学技术的迅速发展，人们生活和工作的节奏也愈来愈快。这就要求 人们针对瞬息万变的环境，能够迅速做出有效的决策。而在面对复杂的决策问题时，定 量的运筹学模型起到了很重要的作用。但是，传统运筹学模型的应用却不够完美，个 主要表现就是在面对动态实时优化控制问题的时候，显得无能为力。这是因为传统的运 筹学模型是一种静态意义上的数学模型，一经建立，它的目标、约束及参数便也随之确 定下来。而俗话说的好，“计划的没有变化的快”，实际问题总是处于动态的发展变化之 中的，这样就决定了定量模型的目标、约束及参数也要随之发生变化，因此这种静态模 型的力不从心也就不足为奇了。而且，由于定量模型是一种纯数学意义上的模型，在计 算机中的表示也是数学意义上的，那么，当问题的结构发生轻微的变化时，都可能导致 这个程序化的模型结构遭致灭顶之灾。因此，迫切需要一种管理模型的方法，能够适应 这种复杂多变的客观环境，动态的、实时的对定量模型进行调整，自动建立定量模型， 自动求解。 因此，运筹学模型的知识化与智能化研究“”“。是运筹学领域的一个很有前途的研 究方向，将人工智能与知识工程的理论和方法引入运筹学模型的建模过程，能够帮助解 决传统运筹学的这些问题，增强模型的灵活性，为在计算机上实现由“实际问题一数学 模型一实施方案”这一问题求解过程奠定理论基础。 稿件刊发计划问题是一个典型的运筹学模型，它是一个“o 1 ”解的目标规划问题， 具体介绍见2 1 节。从1 9 9 9 年起，我们以决策借鉴唧1 编辑部为研究对象设计开发了 “稿件录用决策专家系统”，应用了专家系统理论、数据库技术和知识工程的方法，应 用效果很好。美中不足的是只研究了建立静态的数学模型及对这个模型求解的启发式算 法问题，没有考虑稿件刊发计划问题实际上是一个动态问题。由于不同时期的稿件刊发 要求是动态的，因此它的目标、参数和约束条件都应该是动态确定的，而传统的静态的 数学模型显然不能满足这一要求。同时，稿件刊发计划问题是调度排序问题的一种，该 项研究对解决这一类问题具有普遍意义。这就要求我们研究一种能够实现动态实时的建 模方法，为解决这个问题提出全新的方案。 在建模方法及模型管理的研究领域，早期的研究工作主要集中在利用建模知识库中 拥有的领域知识演绎生成模型，如结构化方法，基于图框架的模型集成与选择方法、基 于p e t r i 网的建模方法等等。但是，这种演绎生成模型的主要缺陷在于过分依赖领域知 幕于事例推理的稿件刊发计划的建模方法研究 识而忽视过去求解类似问题的经验，不仅使建模知识库十分庞大而复杂，而且建稹工作 的智能化水平也较低。同时领域知识获取和修改非常困难，这也是“基于规则”的方法 的瓶颈阀题，而且，当建模系统的规则库达到一定规模的时候，还要面对匹配冲突和组 合爆炸等等复杂问题。 在众多人工智能方法中，“基于事例推理( c b r ) ”是近年来非常流行的一种方法， 它的求解过程非常类似人的思维，并且能够解决“基于规则”的方法的瓶颈问题“知 识获取”这个难题，而且利用了演绎方法经常忽视的过去求解类似问题的经验。近年来， “基于事例推理”这种法方法在规划、设计、法律、医学、争端调解、决策支持以及电 予商务等等领域获得了相当的成功。 本文就是在这种背景下，以稿件刊发计划问题这一目标规划问题为研究对象，将基 于事例推理的理论方法应用到运筹学模型的自动建立上，针对“客观条件变化一数学模 型变化一求解程序以及软件系统的变化”这一连锁反应，以期实现由“实际问题一实际 问题的知识化信息模型一知识化数学模型一知识化求解模型的转化与生成过程”的解决 策略。 1 2 国内外同类研究的分析与综述 1 2 1 基于事例推理的起源 近年来，“基于事例推理”这种机器学习方法在很多领域都得至0 了巨大的发展。基 于事例的推理( c a s e b a s e dr e a s o n i n g ) - - 词来源于认知科学，基础性工作见r o g e rs c h a n k 的动态记忆理论“，这个理论更早可以追溯到存贮组织包( m o p s ) 理论，它围绕着入 类理解与学习新事物时总是对过去经验回忆这样一个基础上来展开的。j k o l o d n e r “” 等人的工作使基于事例推理的研究与系统设计趋向成熟与实用。 基于事例推理是种非常接近于人的思维方式的方法：人们在面临一个新问题时， 往往使用以前处理过的类似问题的经验，根据经验去认识现有事物，进而选择信息、解 释事物。借鉴心理学对人类利用经验解决问题的研究，基于事例推理在规划、设计、法 律、医学、争瑞调解、决策支持以及电子商务等等领域获得了相当的成功。随着对“基 于事例推理”的理论和应用的研究兴趣逐渐增大，全世界越来越多的科学工作者参与到 这方面的理论和应用的研究中来。并成立了许多专门的国际性的研究组织。 基于事例推理的稿件刊发计划的建模方法研究 1 2 2 基于事例推理的模式 基于事例推理是一种自动推理学习的框架，对它的分类有很多种，总体的来说在表 现形式上，基于事例推理的系统有两种类型，即问题求解型与解释型；前者侧重于对过 去策略的适配与修改；而后者强调以旧事例对新事例做出评价与解释。这种分类方式有 一定的作用，但在应用过程中，分类的界限并不很清晰。 a a m o d t 和p l a z a “1 曾经将纯粹的基于事例推理技术概括为四个阶段： 检索( r e t r i e v e ) ：针对系统描述的问题，在事例库中检索相似的事例； 复用( r e u s e ) ：应用检索到的相似事例的解决方案； 调整( r e v i s e ) ：如果有必要的话，还要调整或修改解决方案以便更好的应用于 新问题； 保留( r e t a i n ) ：一旦新的解决方案得以确定，就将其保存到案例库中。 基于事例推理这种方法就是按照4 “r s ”步骤的一个循环过程。几乎所有的c b r 系统都是按照这种模式。 1 2 3 基于事例推理的特点 图1 1 基于事例推理方法流程 f i 9 1 1t h ef l o w o f c b r 总的来说，“基于事例推理”较适用于理论抽象较弱而经验性因素较强的应用领域。 和“基于规则”的推理方法相比，它的优势主要有： 基于事例推理的稿件刊发计划的建模方法研究 夺由于人的主观性和思维认识的有限性，从大量的事例中归纳出来的规则只取出了事 例的共同本质，而事例能够比一组规则提供更多的信息； 夺避免了知识增加时知识库的完整性和一致性问题； 夺它是一种增量式学习方法，随着事例的增加，事例库的覆盖度( 求解问题的范围) 逐渐提高： 夺事例比规则获取容易，不需要完整的领域模型，就可以逐步实用化； 夺直接复用过去的求解经验( 成功和失败的) ，不需要完整的领域模型，也不必像产生 式推理那样从头开始，避免了匹配冲突和组合爆炸问题，求解效率高： 夺它具有类比推理的基本特点，能够发挥人的创造性思维，对难以充分理解领域做出 假设和预测，并指导人们避免重犯过去的错误； 夺从实现角度来讲，它能够兼顾专家的偏好，而产生式系统的柔性不足。 1 2 4 基于事例推理在模型管理方面的应用 基于事例推理应用于模型方面，主要可以归纳成以下几类： ( 1 ) c b r 技术用于模型管理这方面最有代表性的是t p l i a n g “”将c b r 技术用于 模型管理系统，t pl i a n g 提出的以实体、属性和子属性所构成的层次化体系表示问题 的方法，并且在严格的规定下类比推理的建模方法。再有r o b e r t 等也在作这方面研究， 他的方法与t pl i a n g 不同，采用框架表示事例，事例包括五个槽，索引集范围，输入 参数，处理单元，输出参数，同类模型框架和模型框架。该方法不能从建模角度反映模 型事例的本质，并且其检索也以语义为基础，不能作为这方面研究工作的代表。在国内， 大连理工大学系统工程研究所的胡祥培教授等进行了“运筹学规划问题的一种基于知识 的树状表示法”、“生产作业问题的知识表示研究”以及“问题与实例的类似性评价及基 于实例学习的建模方法研究”等相关领域的研究“”“”，在理论和实践方面都走在前沿。 ( 2 ) c b r 技术用于决策分析这方面的研究以属性值事例为基础的研究占有很大比 例。有事例组织结构方面的( 例如：事例的索引结构、事例库的组织) ，也有许多研究 算法方面的( 比如事例分类及检索算法) 。结构型事例用于这方面研究的比较少，值得 一提的是g o v e m 将c b r 技术用于决策理论模型，借助影响图来表示事例，通过对影响 图的结点和连结弧的检索和修改，适应于新问题。 ( 3 ) c b r 技术用于模型求解这方面的研究主要集中在一些n p 问题上，包括用c b r 技术求解t s p 问题，和求解j o b s h o ps c h e d u l i n g 等等。“。 4 基于事例推理的稿件刊发计划的建模方法研究 1 2 5 基于事例推理( c b r ) 的理论研究 作为一种人工智能方法，基于事例推理方法并没有通用的模式来适应各种各样的领 域问题，只能具体问题具体分析。但是基于事例推理方法应用的核心问题主要集中在事 例表示、事例检索、事例复用、事例修改和事例保留5 个部分，下面就介绍这几个方面 的理论进展。 ( 1 ) 事例的表示方法 知识在大脑中是如何记忆的现在仍是个悬而未决的问题，对于基于事例推理系统的 事例表示而言，从本质上可以分成属性值事例和结构化事例。属性值事例的应用范围比 较小，因为它无法表达事例的属性之间的复杂关系，所以无法描述出复杂领域的事例的 全部特性。它只应用于一些简单分类的系统中。对于结构化事例而言，在目前的知识系 统中使用了产生式、图形、语义网、框架、树状、网状、面向对象“”。“、结构化层次模 型”“7 “2 “。”。”和实体属性模型“”“。等等诸多的知识表示方法。这些方法都有各自的特 点，都是针对不同的领域知识提出来的。 以上讨论的主要是将事例作为单个个体保存在事例库中，但是基于事例推理方法的 各个环节是一个整体，如果将事例表示作为一个起点，将事例检索、映射、修改、保存 一系列的环节考虑进去，就形成了一个真正的带有推理和学习能力的记忆体，这就涉及 到事例库的整体组织问题了。下面介绍两种这样的比较典型的事例表示理论。 s c h a n k 的动态记忆理论( d y n a m i c m e m o r y ) “”是近年来讨论和应用较多的一种模型。 这种理论把知识记忆在一些结构中。有四种类型的结构：记忆组织包、场景、剧本、主 题记忆包。一个记忆组织包中可以包含许多场景，每一个场景又可以包含许多剧本。同 时，在记忆组织包的上层还可能包含元记忆组织包等。这些结构按照一定的组织原则形 成一个网络结构，而通过索引来检索它们。优点是利于检索、易于组织( 可以把它们连 接成树形层次或者网状结构) 、易于管理( 知识的改变只对局部产生影响) 、利于知识共 享。 还有一种比较有影响力的表示模型“类模版”模型“4 ( t h ec a t e g o r y e x e m p l a r s ) 是在r a yb a r e i s s 和b r u c ep o r t e r 设计的系统p r o t o s 系统中提出来的，这种模型的理 念基础是把真实世界和自然概念的定义进行外延。事例库嵌入在一个网状结构中，其中 包括类、语义关系、事例和索引指针。每个事例都与一个类相关联，索引或指向一个事 例或指向一个类。指针有3 种：属性指针从问题的属性指向事例的属性或者类的属性： 事例指针从类指向相联系的事例，这些事例都有其典型意义；差异指针从事例指向相邻 事例，也就是大体相类似，只是在个别属性上存在差异的事例。这些类相互连接在一个 语义网络中用于领域知识的表示，并对c b r 系统提供解释支持。 在目前的c b r 应用系统中，事例库的组织形式都是来源于这两种方法的启示。尽管 形式上还比较简单的，但确实是一种记忆体的推理和学习的模型。不过将事例作为整体 基于事例推理的稿件刊发计划的建模方法研究 组织同样也存在相应的问题，事例的推理和学习并不都是将事例作为整体有些应用就 是研究事例部分的推理然后利用各个部分搭建整体，而这样的事例库组织形式无法实现 这样的思路。另外，这种事例库的组织形式，本身就带有分类形式，这就给事例推理和 学习带来了局限。对于事例库分类索引问题，我们将在下面讨论。 ( 2 ) 事例的检索方法 事例的检索也是基于事例推理的关键问题，能否找到合适的相似事例，直接决定了 求解工作的效果。这里涉及到两个关键问题：相似度问题和检索策略。 先介绍几种经典的相似度的形式：最近相邻法、t c 相似法、和改进的t c 相似法“。 最近相邻法认为两个事例之间的属性集是一样的，而且两个事例的属性权值也完全相 同，在应用时，事例的表示和权值的赋予是比较简单的。许多的应用中的事例相似度都 是采用这种方法o “。t c 相似法适用于属性可以用二进制表示的应用领域，同时也很适于 结构化的知识表示的问题。改进tc 相似法考虑了属性集中的各属性对于两个案例具有 不同的权值，这样对于属性集相同权值不同的案例可以用这种方法求相似度。大多数的 相似度的计算都是基于以上的形式或者加以变化。这些方法的优点就是应用简单，结果 直观，以数量确定相似程度。但是这种数量关系反映出的事例之间的相似关系和基于事 例推理系统需要的相似关系并不一致。对此，b a r r ys m y t h 和m a r kt k e a n e “”提出以修 改策略为导向的检索，认为检索的目的就是为了找到适于修改策略的事例。 由于问题领域差异很大，所以和事例之间的详细关系也就很复杂。很多系统的修改 策略未必能够完全反映领域信息，为此，介绍一些其它的检索方法和算法。 首先是关于事例索引的建立。索引的建立可以使得检索索引时不会与过多的事例相 对应。这种方法在很多应用中都有体现”“”o ”。b i r n b a u m 和c o l li n g s 瞄1 提出过建立索 引的4 条原则：1 ) 可预测、2 ) 确定使用事例的目的、3 ) 在保证事例在未来可能应用 的前提下进行抽象、4 ) 具体到保证在未来的情况下可以被识别。不过，由于基于事例 推理和带有类比推理的思想，那么索引作为检索手段，并不利于实现有关记忆的推理， 也相应地削减了事例件的类比可能。 其次，事例检索也是一种搜索策略，因此，可以考虑应用一些成熟的搜索方法，如 神经网络“、遗传算法。、统计算法。“、模糊逻辑“”“2 “3 等等。这些方法对于结构化知 识的检索，以及模糊的知识的检索都起到了一定的作用。 事例的检索和事例的知识表示是相互关联的，而且不同的表示方法的检索算法也存 在很大差别。如针对结构化事例表示，有文献提出了一种聚类、分组、属性探测的基础 性方法。，而也有提出一种基于上下文的检索方法。，还有阐述了如何针对相似度设计 结构化事例表示。“：针对面向对象的表示方法，有文献对此做了相应的详细的阐述。“1 。 ( 3 ) 事例的改写 对于事例的复用主要有两种途径：一是直接重用源事例的结果，另一种是使用源事 例的方法中心构建解决方案。但这两种途径都需要将源事例的结论进行改写。 事例改写是基于事例推理系统中最具特色又是实现中难度最大的部分。它针对问题 基于事例推理的稿件刊发计划的建模方法研究 描述和相关事例，用替换法、变换法或其它特殊方法形成新问题的求解方案。由于改写 过程的困难，现行的很多基于事例推理的系统或避开事例改写而蜕化成简单的事例分类 与检索系统，或在事例改写上强烈地依赖于领域中特殊的启发式改写知识，要求系统对 目标领域有清晰的了解，应用独特的改写技巧，从而丧失了系统性和普遍意义。 大多数现有的基于事例推理系统是将改写知识代码化为改写规则集或领域模型，成 为一个基于规则的改写模块，那么这种改写需要改写规则既包含系统的改写策略又要包 含具体的领域知识两方面内容。但是，基于事例推理方法的一个主要的特点就是能够处 理那些领域知识获取困难的问题，因此要是建立基于规则的修改方法，又要重新面对领 域知识获取这一问题。这也是造成很多基于事例推理系统修改部分功能难以实现的原 因。 ( 4 ) 事例的学习 基于事例推理的一个重要特征就是学习特征，因而也看作是机器学习的一个分支。 作为一种学习框架，基于事例推理的学习体现在几个方面，首先是系统将新事例保存到 事例库中就实现了学习，这里的一个新问题就是事例的评价和事例库的维护，包括选择 什么样的事例保存，事例库大小的控制：同时事例库还需要进行分类或索引，这也是学 习的一种重要体现。有时，当修改策略本身由专家系统实现的时候，规则或者事例的提 取也是学习的重要形式。但需要注意的是，基于事例推理易于从经验中学习是因为它可 以比较容易的从具体问题的解决经验中学习，而并不是因为它擅长归纳。 ( 5 ) 混合型系统 大多数的推理系统是混合的1 4 引，这是因为它们包含了各种不同类型的子系统。一般 认为基于事例推理是类比方法的一种，因此，与其他技术相结合就被视为混合系统。大 多数混合系统是将各种推理技术应用到基于事例推理系统的各个阶段，但也有将基于事 例推理技术应用到其他推理系统中的。“。这些技术主要包括：规则推理“”。7 “”“”1 、模 糊逻辑m “、统计方法。”。“、遗传算法嘲、神经网络3 等等。 但是，i w a t s o n “也论述了基于事例推理是一种思想而不仅仅是一种技术，它并没 有固定的技术方法，可以利用各种各样的基于知识的方法或算法工具来完成基于事例推 理的各个环节的工作，并举例描述了在基于事例推理的系统中，各种方法是如何应用于 各个环节的。 1 3 本文的研究思路及所做的工作 ( 1 ) 本文的研究思路 基于事例学习可以说是类比学习的一种形式。类比和基于事例学习是同一思维方法 的两个方面：两者都要依靠记忆情景知识来指导复杂问题的求解，但前者强调对过去情 况的修改、改写和验证，雨后者注重事例记忆和组织、层次索引和检索。 基于事例推理的稿件刊发计划的建模方法研究 我们可以这样描述类比推理的原理。“： 事例a 能够推出结果a n s w e r ( a ) ，问题b 类似于事例a ，而且问题b 之所以不能 推出a n s w e r ( b ) 的原因是事例b 缺少相应的信息，那么根据问题b 和事例a 的相似 对应关系，补足问题b 推理需要的信息，就可以推出a n s w e r ( b ) 了。但是类比推理的 这种类比是不严格的，且难以实现的。从目前的情况看，基于事例的学习是类比学习向 应用领域迈进的先行者。 对于稿件刊发计划问题这样一个同一领域的问题来说，不存在类比的有效性验证问 题，这也就使得当我们应用基于事例推理的理论方法解决该问题的时候，问题主要集中 在如何补足问题b 实现推理所缺少的信息上。 a a n s w e r f a ) 、 矿a 心b 日觚w e r j 图1 2 类比推理原理图 f i g1 2t h et h e o r yo f a n a l o g i c a li n d u c t i o n 根据“基于事例推理”的4 “r s 步骤是一个循环过程的4 个环节，我们首先要研 究的问题就是a 是什么，b 是什么，a n s w e r ( x ) 是什么和a n s w e r ( x ) 是如何得到的； 接下来的问题是如何在已经解决的的事例所构成的事例库中找到最合适的a 来帮助补 足b 中缺少的信息及如何补足；最后是如何使系统变得越来越聪明，不断增强系统的功 能。 根据以上的分析，在搜集并研究了大量的相关研究材料之后，我们总结得出了设计 一个基于事例推理的建模过程需要重点研究以下几个问题，这也就是本文的主要工作内 容： 夺问题和事例的知识化表示； 夺问题和事例的相似度分析； 夺事例的类比转换方法： 夺基于事例推理的稿件刊发计划的建模系统的设计与实现。 ( 2 ) 主要研究工作 第一步，分析稿件刊发计划的静态数学模型的特点，研究如何用知识工程的方法将 其在计算机中表示出来a 这一部分主要解决我们上面分析到的“a 是什么，b 是什么， a n s w e r ( x ) 是什么和a n s w e r ( x ) 是如何得到的这一系列的问题，这也是整个基于 基于事例推理的稿件刊发计划的建模方法研究 事例推理的建模过程的前提，下面的步骤都是基于这一部分的结果而展开的；这里的具 体问题可以表示为：事例是如何表示的：问题是如何表示的；事例和模型是如何 对应的；事例和问题的关系是怎样的。 针对这些问题，我们首先所做的工作是用 这四元组来表示整个事例。 第二步，在事例库中寻找跟当前问题“最为相似的事例”，这一部分主要为解决上 面分析到的“如何找到最合适的事例a 来帮助补足问题b 中缺少的信息及如何补足” 的问题。我们采用“粗选和精选”两步确定最相似事例的方法。 第三步，根据找到的“最相似的事例”，根据建模知识库中的规则，进行类比转换和 相应的调整，最终获取解决方案，即符合新问题要求的新模型。我们设计了一些要求比 较严格的转换规则，对于系统不能实现的部分，通过一个知识库维护系统来自动或交互 的扩展系统的知识，使系统的覆盖面扩大，系统功能不断增强。 上述研究工作详见第二章。 ( 3 ) 基于事例推理的稿件刊发计划建模系统的设计 稿件录用决策专家系统是我们根据稿件从稿件登记到稿件刊发的业务流程中的三 个主要环节：稿件处理全过程的信息管理；稿件录用决策支持；稿件干口发计划的 制定，应用数据库系统理论、软件工程理论、专家系统理论、运筹学理论、人工智能理 论等对该问题的不同部分有针对性地进行分析、研究、解决，而形成的稿件信息数据库 子系统、稿件录用决策子系统、稿件刊发计划子系统三个大的模块。 这一部分的工作主要是围绕以上的模型，在原有系统的开发平台、数据库平台等等 的基础上，分析并设计了基于事例推理的稿件干u 发计划建模系统。 主要工作包括：( 详见第三章) 夺基于事例推理的建模系统的系统分析 夺系统功能分析与设计； 夺算法流程设计 夺事例库的数据库设计； 夺系统界面设计 基于事例推理的稿件刊发计划的建模方法研究 2 基于事例推理的稿件刊发计划模型的研究 2 1 稿件刊发计划问题的阐述 稿件刊发计划问题是指在期刊编辑部中，以待发表的稿件的属性( 如稿件栏目，加 快程度，版面数和投稿时间) 为考虑对象，以期刊的“总页数”和各栏目计划刊发稿件 的“总页数”等属性为约束，以尽早刊发稿件和充分利用期刊页面资源为目标，研究如 何制定稿件刊发计划。 我们在“稿件录用决策专家系统”中设计了稿件刊发计划子系统。并将该部分成三 个流程进行处理。被录用稿件刊发信息的知识化表示一稿件刊发计划问题的模型表示一 稿件刊发计划模型的求解一稿件刊发计划。被录用稿件刊发信息的知识化表示记录的是 制定稿件刊发计划有关的信息，例如：稿件的登记号、占用的版面数、稿件刊发的等级、 刊发的栏目等等信息。 在稿件刊发计划问题的模型表示方面，我们通过建立一个目标规划模型加以实现。 稿件刊发计划模型的求解是该稿件刊发问题的难点。由于问题本身的复杂程度，稿件刊 发问题对应的目标规划问题难于应用传统的运筹学理论加以求解，于是我们尝试将人工 智能中的基于状态空间的搜索算法应用到模型的求解当中，设计出稿件刊发计划问题的 启发式搜索算法。并应用该算法得到稿件刊发计划。 这个问题的目标和约束可以简单描述为： 夺刊发稿件的“总页数”不能大于期刊的“总页数”限制； 夺总的优先级尽量大( 尽量多发加快级少发普通级) ： 夺栏目篇幅页数有限制，每个栏目刊发的稿件的“总页数”尽量符合栏目 规定的“总页数”。 针对上面的描述，我们可以用以下的形式简单描述相应的数学模型。 其中，w 是目标值：p l 、p 2 、p 3 是权重； x i i 取值是0 或者1 ，0 代表不发表、1 代表发表。 i 代表第i 个栏目，j 代表这个栏目的第j 个待发稿件； a 代表总页数： z 代表第i 个栏目的第j 篇稿件的版面大小； y _ j 代表第i 个栏目的第j 篇稿件的优先级别； l i 代表第i 个栏目的计划所占的版面大小； n 代表一共有n 个栏目；k i 代表第i 个栏目有k 个待发稿件 基于事例推理的稿件刊发计划的建模方法研究 矿代表大于目标的目标变量，町代表小于目标的目标变量。 m i n w = p l + d f + p 2 + d ；+ 只+ ( ( a l l + d 未) ) = i n k ( z 。4x 。) 一一+ d j d j = 0 i # l，= l n k ， ( + 。) + d i d ；= 0 j lt ；l nk ， ( ( z 。4x 。) 一，+ d l d 支) = o ，= 1t = i d 2 , 4d ：? = 0 d i - + d ? = 0d , - 0d i + 0i = l ，2 ，3 x t ? = 0 ，1 本文的目的不在研究这种模型的求解算法，丽是研究如何建立一个计算机系统能够 根据不同情况和用户的不同需求，动态建立这种数学模型。 2 2 事例的知识表示 k o l o d n e r ”“”在“c a s e b a s e dr e a s o n i n g ”一书中给出了事例( c a s e ) 的一个定义：“事 例是一段带有上下文信息的知识，该知识表达了推理机在达到目标的过程中能起到关键 作用的经验”。具体的说，一个事例应该具有如下特性： 冷 事例表示了与某个上下文有关的具体知识，这种知识具有可操作性。 事例可以是各式各样的，可以有不同的形状和粒度，可以涵盖或大或小的时间片， 可带有问题的解答或动作执行后的效应。 夺 事例记录了有用的经验，这种经验能够帮助推理机在未来更容易地达到目标，或提 醒推理机失败发生的可能性有多大。 事例的知识表示一般可以分成属性值事例和结构事例两种。模型是现实世界的反应 与抽象，而现实世界中的问题仅用简单的属性值来表达是不可能的，所以这方面的研究 也基本上都是结构事例。 综合各种研究结论，结合实际问题，前后步骤相联系，本文使用属性集、结构集、 厂fliilj、lfllll 基于事例推理的稿件刊发计划的建模方法研究 问题集和结构化模型 四元组来表示整个事例。下面针对稿件刊发计划的 具体问题，描述事例的知识表示形式。 22 1 事例属性分析 事例是现实问题的抽象，事例的属性是从现实问题中抽象出来的、用于建立反映客 观事例特征的模型的构成要素。稿件刊发计划问题的属性就是用于反映问题本质而构造 的模型的构成要素。 表2 1 稿件刊发计划问题的一部分建模的属性要素列表 t a b l e 2 1a t t r i b u t e so f m a n u s c r i p tp u b l i c a t i o ns c h e d u l e 首先，属性可以分成两大类：类属性和实体属性。 类属性表示这个属性代表一类具有相同特征的属性，这样能简化属性结构；而实体 属性代表类属性的一个具体化形式。 举例来说，栏目页数就是一个类属性。因为一期稿件有若干个栏目，如经济类栏目、 管理类栏目、金融类栏目、信息系统类栏目等等，但它们具有共同的特征，可以抽象为 一类属性，对这一类属性的处理过程都是一样的。同理，栏目优先级、稿件页数等等属 性也是同样的道理。 而总页数属性就是一个实体属性，因为一期期刊只有一个总页数。这样分类是为了 实体属性处理比较容易。但当多期期刊的时候，实体属性也可以转化为类属性处理。 其次，属性还要分成4 种不同意义的类型，表示这个属性在问题和结构中特定意义。 包括目标和约束属性、决策属性、中间属性和值属性。 目标和约束属性是指在目标和约束结构中出现的属性，用户能够具体描述的属性， 直接对应模型的目标约束和一般约束。例如，总页数就是一个目标属性，因为在目标约 束中有对总页数的约束，尽量大但不能超过规定的总页数。 决策属性是未知的属性，对应模型的变量。这个模型的决策属性就是稿件刊发标志， 也就是我们最终要求解的变量。 值属性是已知值的属性。例如总页数，这是个已知值的属性，它在模型中是一个 基于事例推理的稿件刊发计划的建模方法研究 已知参数。 中间属性是其他3 种属性之间的属性，用于构建属性结构，模型中没有相对应的部 分。例如栏目的规定页数这个属性，它在刊发稿件页数和期刊的规定总页数之间起过渡 的作用，用于描述它们的内在关系，而在模型中并不出现。 这些属性类别的特征详见以下的两小节。这里要说明的是，问题的属性集和事例的 属性集并不相同。事例的属性集是完整的事例描述，而闳题的属性集是用户定义的不完 整的描述。我们下面还要继续分析这个问题。 2 2 2 事例属性结构分析 事例是一个带有语义关系的有机整体，那么属性结构就是用于描述这种属性之间的 关系。 属性结构的顶层是目标属性，因为问题中每一个目标属性的描述都对应一个目标或 者约束的表达，定义这个结构的目的，就是为了使这个表达具体化。例如第一个属性结 构的顶层属性是“总页数”属性，这就是因为在目标约束中存在对“总页数”的目标约 束：“尽量大但不能超过规定的总页数”。 在属性结构中，既有上层属性又有下层属性的属性是“中间属性”，它是为了符合用 户理解问题的习惯，具体化决策和目标属性过程中的中间形式。如“栏目页数”这个属 性，由于“总页数”由“栏目页数构成”，而“栏目页数”由“稿件页数”构成，“总页 数”是目标属性，“稿件页数”是决策属性，“栏目页数”则是描述它们之间的关系的属 性，但在实际的数学模型中却没有体现。 底层属性是值属性和决策属性，一个是定义问题时就已知具体值的属性，一个是我 们求解过程中的变量，这也是具体化的最终目标。 a k “ r r r z i + x iy i x 图2 1 属性结构图 f i g2 1 t h es t r u c t u r eo f a t t r i b u t e s 除酞，f 基于事例推理的稿件刊发计划的建模方法研究 期刊的总页数( a ) 是由各个栏目的总页数( l j ) 相加构成的( l i ) ；每个栏目的 总页数( l 。) 是由该栏目刊发的稿件的页数相加构成的( z 。，x 。，) ，刊发稿件的页数由 待发的稿件的页数( z l i ) 和稿件的刊发标志决定( x 。) ； 期刊的总优先度( k j ) 是由各个栏目的总优先度( l y 。) 相加构成的( 1 2 l 。y i ) 每个栏目的总优先度( l _ y i ) 是由该栏目刊发的稿件的优先度相加构成的( y 。+ x 。) 刊发稿件的优先度是由待发的稿件的优先度( y ：。) 和稿件的刊发标志( x t ，) 决定； 期刊的稿件刊发总数量( k 。n ) 是由各个栏目的刊发总数量( l 。_ n i ) 相加构成的( e l _ n ，) ；每个栏目的刊发总数量( l - n ，) 是由该栏目刊发的稿件的稿件的刊发标志( x 。) 决定的； 2 2 3 问题集分析 问题集是用户定义属性、目标和约束要求的描述，我们也称之为目标、约束集。“问 题”的属性就是从问题集抽取出来的。 根据对稿件刊发计划模型的分析我们发现，这个“o 1 ，j 解的目标规划问题的模型 是有迹可循的： 首先，它的决策变量就是稿件的刊发标志： 其次，它是一个典型的运筹学模型，由目标和约束构成。 第三，它的目标很有特点，是由各个目标约束构成； 最后，它的一般约束和目标约束也只有几种情况。 这些规律是我们很容易将我们这种事例表示转换成可以用运筹学求解过程识别的 模型形式。 问题结构 i 页数优先级刊发数量其他约束 总页数栏目页数总优先级 口口口 小于a 同时尽量接近尽量大 要尽量大 总稿件数量 口 尽量多 图2 2 目标结构图 f i g2 2t h es t r u c t u r eo fg o a l 1 4 基于事例推理的稿件刊发计划的建模方法研究 问题集的特征是：根节点是问题名称，第一层子节点是问题种类，子节点是约束和 目标，底层是目标描述。 首先是问题分类，原则上按照目标属性的单位进行分类，如“总页数”和“栏目页 数”属性的单位都是“页数” 第二，每个最终的分支都是由“用户要求”和目标属性构成，而且是可分解的结构 化的。如用户对总页数属性的要求是，尽量大的同时不能大于规定的总页数( a ) 。 2 2 4 知识化模型的生成 属性集、结构集和目标集，已经基本上描述出整个问题，下面介绍这3 个集合跟知 识化的静态数学模型之间的关系，同时也要说明跟求解算法之间的关系。 这个推理过程分成3 个步骤： 夺首先在事例属性集中找到决策属性； 夺根据决策结构确定目标和约束的形式 夺根据事例的结构集确定具体的模型； 模型生成实例： 根据属性集确定决策变量是刊发标志：x 。i 取值为0 l ； 举决策结构中的稿件数量问题为例：尽量大( 总数量) ：目标规划中对 应的形式应该是：k n + d 。一d + = 0 ，根据谓词尽量大的描述，其中d 一的值应该 为0 ，目标函数中也应该加上p 。td + 一项了； 根据事例结构集中属性关系得到：总稿件数量是栏目稿件数量之和，而 栏目稿件数量是各栏目的稿件刊发标志之和。 因此，目标规划中对应的表达式就推导出来了，在下图中可以清楚地看到整个推理 过程： 图2 3 模型生成实例图 f i 9 2 3a c a s eo fm o d e lc o n s t r u c t i o n 基于事例推理的稿件刊发计划的建模方法研究 22 5 事例和问题 以上的实例表示是针对整个的完整的事例，而用户面对的问题却是不完整的。那么 问题究竟是事例的那一部分，它需要补充的部分又是什么呢? 问题的描述来源于用户的定义，那么我们首先来看用户能提供那些信息，而同时需 要我们的系统补充那些信息，补充之后就成为完整的事例，继而达到解决问题的目的。 用户的描述主要对应属性集和目标集。属性集对应的是用户需要提供一些属性信息 如属性值。目标集对应的是用户用来提出对问题的要求。 结果是，问题所包含的信息就是1 7 1 标集和从目标集中包含的属性集的一部分，主要 是决策属性、目标和问题属性。 那么，问题所缺少的信息就是结构集，那么我们的目标就转化成找到一个尽量包含 问题所缺少信息的事例，然后将问题补足信息。这样我们就可以通过以上描述的推理机 制，建立起问题求解所需的模型了。 2 3 最相似事例的选择 2 3 1 事例检索方法分析 事例之间的相似可以分成几个层次“：语义相似性、结构相似性，目标相似性和个 体相似性。对于我们这个问题而言，问题集本身属于一个问题域，有相同的结构特征和 目标特征，因此，可以直接考虑根据属