（系统工程专业论文）基于CBR的城市供水优化调度.pdf

东北大学硕士论文 摘要 摘要 随着 。固市场经济的发展，自来水公司面临者越来越严峻的竞争环境。对水 资源进行优化调度是提高经济效益的有效途径。然而，由于各种各样的局限，传 统的凋度方法不能真j f 实现优化调度。为此，本文提出了一种基于c b r ( c a s e b a s e dr e a s o n i n g ) 的调度策略。 基案例的推理是近年来发展起来的解决问题和进行学习的人工智能的方 法，并且已经引起了广泛的重视。它起源于美国，其基本思想和理论已经传遍整 个刖+ 界，我们现在正处于c b r 研究最为活跃的时期。 首先，本文对c b r 以及相关的知识进行综述，描述了这一领域中几个先进 的方法。重点提到了一个通用的c b r 循环框架，而后对c b r 循环中的四个基本 方法进行逐一的阐述，包括案例搜索、重用、验证和学习。并且建立了一个基于 c b r 的自来水优化调度系统流程图。 然后，根据城市供水的特征建立了综合解释性预测方珐和时间序列方法的基 于人工神经元阀络模型的动态城市用水量预测模型。把这个水量预测值分配到各 个水厂，再用各厂的水量通过等效管网宏观模型得出各监测点的压力值，这些压 力值是案例的部分特征。 再后，案例库中搜索到的案例的重用是通过重用以前得到解决方案的方法来 实现的，即推导策略。这里所提到的方法就是求解调度模型。对调度模型进行求 解根据决策变量选择的不同可以分为直接优化调度和两级优化调度。本文对这两 种方法进行了对比并且编制了一级优化调度程序。 最后，介绍了一个用j a v a 和s q ls e r v e r 开发的基于c b r 的优化调度软件。 关键词：基于案例的推理案例重用水量预测人工神经元网络b p 算法 管网模型两级优化调度遗传算法 i i 东北大学硕士论文 a b s t r a c t a b s t r a c t w i t ht h ed e v e l o p m e n to f m a r k e te c o n o m y ，w a t e rs u p p l yc o m p a n i e sa r ec o n f r o n t e d w i t hm o r ea n dm o r ed r a s t i cc o m p e t i t i v ee n v i r o n m e n t o p t i m u md i s t r i b u t i o ni so n eo f t h ee f f i c i e n tm e a n st oi n c r e a s ee c o n o m i cb e n e f i t h o w e v e r ，t r a d i t i o nd i s t r i b u t i o n m e t h o d o l o g yc a nn o tr e a c hr e a lo p t i m i z a t i o nf o ra l l k i n d so fl i m i t a t i o n t h i sp a p e r i n t r o d u c e san e w s t r a t e g y b a s e do nc b r c a s eb a s e dr e a s o n i n gi sar e c e n ta p p r o a c ht op r o b l e ms o l v i n ga n dl e a r n i n gt h a th a s g o tal o to fa t t e n t i o no v e rt h el a s tf e wy e a r s ，o r i g i n a t i n gi nt h eu s ，t h eb a s i ci d e aa n d u n d e r l y i n gt h e o r i e sh a v es p r e a dt oo t h e rc o n t i n e n t s ，a n dw e a r en o ww i t h i nap e r i o do f h i 曲l ya c t i v er e s e a r c hi nc a s e - b a s e dr e a s o n i n g i n i t i a l l y ，t h i sp a p e rg i v e s a no v e r v i e wo ft h ef o u n d a t i o n a li s s u e sr e l a t e dt o c a s e - b a s e dr e a s o n i n g ，d e s c r i b e ss o m eo ft h el e a d i n gm e t h o d o l o g i c a la p p r o a c h e sw i t h i n t h ef i e l d ag e n e r a lf r a m e w o r ki sd e f i n e dt h a ti si n f l u e n c e db yr e c e n tm e t h o d o l o g i e sf o r k n o w l e d g el e v e ld e s c r i p t i o n so fi n t e l l i g e n ts y s t e m sa n d t h em e t h o d sf o rc a s er e t r i e v a l r e u s e ，s o l u t i o nt e s t i n g ，a n dl e a r n i n ga r es u m m a r i z e d as y s t e ma r c h i t e c t u r ei s b u i l t b a s e do nt h ef i a m e w o r ka n dt h es y s t e ma c t u a lr e a l i z a t i o ni sd i s c u s s e di nt h en e x t c h a p t e r s n e x t ，b a s e do nb pm o d e lo f t h ea r t i f i c i a ln e u r a ln e t w o r k ，a c c o r d i n gt ot h ef a c t o r a n df e a t u r eo fu r b a nw a t e r - s u p p l y , ad y n a m i cw a t e rc o n s u m p t i o nf o r e c a s t i n gm o d e l w i t ht h ec h a r a c t e r i s t i co fb o t hr e g r e s s i o na n dt i m es e r i e si sd e v e l o p e d t h ep r e d i c t i o n r e s u l t so f t h i s b p m o d e l e a n p r o d u c e e v e r yf a c t o r y s w a t e ra m o u n t s t h r o u g h aw a t e r a m o u n t d i s p a t c hm o d e l ，a n d t h e np r o d u c ee v e r ym o n i t o r i n g p o i n t sp r e s s u r e st h r o u g h a n e q u i v a l e n tn e t w o r k m o d e l t h e s e p r e s s u r e sa r ep a r t s o f t h e d e s c r i p t o r so f a c a s e t h i r d l y , t h er e u s eo f t h er e t r i e v e dc a s es o l u t i o ni nt h ec o n t e x to ft h en e wc a s ei st o t e a s et h e p a s tm e t h o d t h a tc o n s t r u c t e dt h es o l u t i o ni e d e r i v a t i o n a lr e u s e h e r e ，t h ep a s t m e t h o di st os o l v ed i s t r i b u t i o nm o d e l c u r r e n t o p t i m a l c o n t r o l m e t h o d o l o g i e s a r e c l a s s i f i e di n t od i r e c ta n dt w o l e v e lm e t h o d s ，d e p e n d i n go nt h ec h o i c eo ft h ed e c i s i o n v a r i a b l e st h e s et w om e t h o d sa r ed i s c u s s e di nt h ep a p e ra n dap r a c t i c a lp r o g r a mi s d e v e l o p e d o nf i r s t - l e v e lo p t i m u md i s t r i b u t i o n f i n a l l y , a no p t i m u m w a t e rs u p p l yd i s t r i b u t i o ns o f t w a r eb a s e dc b ri si n t r o d u c e d t h a ti sp r o g r a m m e d b yj a v aa n ds q l s e r v e r i i 东北大学硕士论文 a b s t r a c t k e y w o r d s ：c a s eb a s e dr e a s o n i n g ；c a s ea d a p t a t i o n ；w a t e rc o n s u m p t i o nf o r e c a s t ； a r t i f i c i a ln e u r a ln e t w o r k ；b pa l g o r i t h m ；n e t w o r km o d e l ； t w o l e v e ld i s t r i b u t i o n ；g e n e t i ca l g o r i t h m i v 东北大学硕士论文 声明 声明 本人声明所呈交的学位论文是在导师汪定伟教授的指导下完成 的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他 人已经发表或撰写过的研究成果，也不包括本人为获得其他学位而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示谢意。 本人签名： 日期： 新尹孑 厶舻争0 i 争 东北大学硕士论文 第一章导言 1 1 问题的提出 第一章导言 城市供水系统的优化调度是指根据系统获得的历史和实时运行信息，确定系 统今后一个调度周期中各时间段内各种调节装置的运行状况，在保证系统服务质 量的前提下使供水费用最低【1 1 。 我国数以百计的城市给水系统消耗的电能很大，按目前的经验运行方式对电 能浪费甚大【2 】。如果采用优化调度，不仅能节省大量能源，而且使管网能在合理的 状态下运行，既保证供水的要求，也使管网的压力更为合理。根据资料估计，送 水泵站能节电6 1 2 ( 3 】，如以节电5 计，日供水量1 0 0 万m 3 的自来水系统， 每年可节电3 0 0 万4 0 0 万k w h ，这个数字是相当可观的。全国大、中型城市日 供水总量数以亿m 3 计，如能实现优化调度，年节电将达数亿度以上，可见其经济 效益是十分巨大的。面对日益复杂的供水系统，如何在满足供水水量、水压及水 质要求的前提f ，最大限度地提高供水系统的经济效益和社会效益，是摆在所有 供水部门共i 司的重要课题。随着科学技术的不断进步，数学规划、现代控制理论 及计算机技术的发展，有力地促进了大型系统的控制和管理水平的提高，使供水 系统借助计算机工具进行科学的调度管理成为可能。 自6 0 年代起一些发达国家就丌始了以计算机作为供水系统辅助调度管理的探 索，他们一般是采用遥测设备将管网中控制点的压力、水厂出厂压力、出厂流量、 水位、功率及温度等实际运行参数自动实时地传送到中心调度室，并对超常现象 作出自动报警，依此作此为控制人员实际操作的依据。另外国外学者在调度管理 的建模理论上也进行了许多探讨，目前在美国、英国、日本、法国等地的有些城 i 订已基本上实现了供水系统的计算机优化调度管理，并编制了一些较通用的调度 管理软件，如英国的g 1 n a s 4 1 及美国的o p w a d t 5 等。 从7 0 年代起国内的许多专家、学者开始尝试将计算机技术应用于供水系统的 模拟、优化设计及水，一水质控制等方面。在供水系统优化调度管理方面也进行了 很多有益的探索和尝试，制作了一些应用软件，如w n w 6 等。并在大庆、郑州、 济南、深圳、广州、长沙等地进行了实际应用，但由于国内设备条件及技术手段 的限制，在供水的可靠性及经济性方面都较成功的实例尚不多见。但建立供水系 统的优化调度系统是供水行业发展的必然趋势。 东北大擘硕士论文 第一章导言 沈阳市城市供水系统始建于1 9 1 5 年，经过8 8 年的发展，现已成为具有供水 能力1 8 0 余万l n 3 日、供水量1 5 0 万m 3 日、管网长度2 5 0 0 k m 、城市供水面积1 8 5 平方公里、居民用水普及率达1 0 0 的大型高效的现代化体系。 沈阳市的取水水源主要有两种：地下水源和地表水源。其中地下水源的日供 水量为1 1 0 万m 3 f 1 ，地表水源日供水量为4 0 万m 3 同。地下水水源为遍布于城市 周边的近河区的4 0 0 余跟管井，井深小于1 0 0 m ，井径5 0 0 m m ，单井取水量平均约 3 0 0 0 m 3 同。地表水源为大伙房水库。全市水源共计有3 8 个，分属于9 个水厂，其 中只有8 水厂的水源为地表水。全市输配水管网总长度为2 5 0 0 k m ，输水干管为4 0 0 k m ，配水管网为2 1 0 0 k m 。输水干管的7 0 为混凝土管，配水管网的9 8 为铸铁 管。整个供水管网采用的是低压运行方式，典型压力为0 1 4 m p 。大多数居民住宅 楼一般介于6 1 0 层，少数的楼层更高一些。这样，8 5 的供水是靠二次加压泵站 供给，每个二次泵站都有个贮水池，加压泵自贮水池吸水加压送至用户。管网 的运行是依据水压的连续监测，整个管网有4 8 个压力自动监测远传点、，并且在生 产调度中心连续显示读数。另外还有3 5 0 个测压点，由人工每季测量一次水压， 中心调度室根据这些信息来确定每个水厂的制水量以满足管网压力要求。 图1 1 沈阳市水厂制水原理图 f i g1 1f o u n d a i i o nt h e o r yo f w a t e rs u p p l yi ns h e n y a n g 沈阳市供水系统就是由供水泵站( 水厂) 与供水管道按一定的配置方式连接而 成，实现调度的方式就是选择各供水泵站中泵的组合方式及调节变速泵的转速。 供水系统优化调度主要由三部分组成，可表示如下： 东北大学硕士论文第一章导言 忙鳜叫器篇 建立供水系统工况模型 翥翌鬟蓁 1 调度决策 兰豢兰蓑 达到极小化费用和满足服务的要求。在满足服务的前提下极小化费用就是求解一 个调度数学模型。这个调度模型要用到管网的工况模型，这些工况模型或作为约 束条件或作为目标函数的推导。所以工况模型的建立是优化调度的最基础的问题。 工况模型的建立方式主要有两种：微观法和宏观法。微观法是通过管网平差 的方法对管网逐层细化，由水厂的供水量和供水压力确定市街管网各节点的压力 以及各管段的流量。管网平差有两个基本的公式：、质量平衡方程和能量平衡方程【7 i 。 + 9 = o ( 1 + 1 ) h 。一日。= o( 1 2 ) 公式( 1 1 ) 为质量平衡方程，公式( 1 2 ) 为能量平衡方程。式中，i 、j 为节点编号， g 。表示连接在节点i 的各管段流量：q l 表示i 节点流量；鬼，为属于基环k 的管段 水头损失；也表示基环k 的闭合差或减压装置产生的水压差。这种方法运算繁 杂庞大，并且需要知道管网的性能参数，包括管段的摩阻系数、直径以及整个管 网的拓扑结构。这些参数对于当前的沈阳市来说都是不可能获得的，因为整个管 网历时近百年完成，以前埋下的管子甭说参数连具体位置都很难确定，而且随着 沈阳市的发展，管网规模也随之扩大，管道总长度达到数千公里，所以这么庞大 的数据是不可能获得的。所以微观法已不适合沈阳市这种大城市调度的需要。 宏观模型最早是由美国的r o b e r t d e m o y e rj r 在1 9 7 5 年提出的【8 】，之后国内外 许多学者致力丁这项研究。这类模型的主要思想是，利用获取的几利，重要的管网 参数( 如：测压点压力，泵站出厂压力，泵站出水量，水池水位及系统用水量等) ， 以统计分析理论为基础，建立系统工况经验模型，概括可表示为： h 。= f 咿。，h 础，q 州，qj( 1 ，3 ) 其中：1 i i 为泵站个数；】j j 为水池数；1 k k 为管网内配水节点数或测 东北大学硕士论文 第一章导言 压点数；l l l 为系统内除i 泵站外其余泵站个数：日。，第i 个泵站出厂压 力；h r , j 第j 个水池水位；日。，第k 个节点压力；q 州第i 个泵站出 厂流量：q 系统总用水量。( 1 3 ) 式右端一般为多项式形式( ，是可选项) ，通 过回归分析，可确定具体的函数形式。该法所需数据少，建模快，计算效率高， 但适用范围有2 定限制。当系统用水量及其它各已知参数变化幅度较大时，可产 生一明显的误差。 无论是微观模型法还是宏观模型法都不能很好的解决沈阳市城市供水的优化 调度问题，为此作者引入了一种新的人工智能的方法基于案例的推理( c b r ) 。 基于案例的推理就是通过改变过去解决问题的方法来解决新的问题( s c h a n k 1 9 8 9 ) 。下图表示了c b r 的主要步骤【9 l 。 图1 2c b r 循环 f i g 1 2t h ec b rc y c l e 4 东北大学硕士论文 第一章导言 1 1 案例的表示 一个基于案例的推理机的效率很火程度上依赖于案例库的结构和内容。既然 一个新问题通过在案例库中搜索一个适合当前问题的案例来得以解决，那么案例 的搜索和匹配就既要可行又要有效率。另外，既然问题在解决后其经验要被存储 起来，那么经验存储的过程也要应用把新案例集成到案例库的方法。在c b r 巾问 题的描述主要是决定在存储器存些什么、找到一个表示案例的合适的结构，以及 决定案例存储器如何被组织和索引以便高效的检索和重用。 2 1 案例的搜索 案例搜索就是在案例库中搜索可以比较容易解决当前问题的案例，搜索到的 案例与当前的问题有相似的解。这早存在着一个假设：相似的问题有相似的解， 而相似的程度等于解重用的程度。而要度量案例相似的程度就要提到案例的相似 度。相似度的一般性公式如下： s i m ：c a s e xc a s e 寸【o ，l 】 0 ，4 ) 相似度有两种：局部相似度和全局相似度。所谓局部相似度是在特征值的层 次上来度量相似的程度。而全局相似度是在案例或者对象的层次上度量相似度。 高效的案例搜索是大型案例库的关键课题。 3 1 案例重用 案例的重用是指如何改变案例的解以适应当前的情况。案例的重用主要有三 种方法：不进行修改( 完全的拷贝) ，用户人为手动的修改，自动的修改策略。而 自动的修改策i 咯又可以分为三种：转换策略，推导策略和组合策略。 4 ) 案例的验证 案例的验证在当今的c b r 研究中已经不受重视了，甚至在一些系统中已经没 有这一过程。而进行案例的验证既可以通过计算机模拟也可以在现实世界中进行 检验。既验证解的讵确性电验证解的质量。 5 ) 案例的保存 案例的保存就是把经过验证的案例存储在案例库中，这实际是系统的自学习 过程。通过这一过程，系统可以学习到一个新的经验( 新的案例) ，改进相似度的 估计以及特征的权重，获得对案例进行重用的知识，删除已经过时的案例。 这五个子过程既相互联系组成一个有机整体，也相互独立，每一个过程都可 以根据具体问题有各种各样的方法来实现。这种灵活性既是c b r 的魅力所在也是 它的一个缺陷，即没有一种通用的方法可以解决所有的问题。 东北大学硕士论文 第一章导言 1 2 本课题的研究过程 在2 0 0 2 年7 月接到这个课题后，首先，利用暑假的时间重点阅读了一些关于 城市供水调度的书籍和论文，对传统的优化调度和与之相关的基础知识有一个初 步的认识，包括管网平差、特征曲线等。 在学习供水优化调度基础知识的同时，阅读了多篇关于c b r 的文章，有综述 类也有应用类，对c b r 的历史、原理和如何在实践中应用c b r 都有了一定的认 识。 2 0 0 2 年1 0 月2 0 0 2 年1 1 月，本课题小组与沈阳市自来水总公司的有关同 志赴南京、上海、长沙、重庆和武汉五城市进行实地考察，获得了大量的第一手 材料，对国内当前的调度情况有了比较清楚的认识，取人之所长补己之所短，这 为我们开发出切实可行的调度软件提供了有益的借鉴。 。 2 0 0 2 年1 2 月2 0 0 3 年3 月，根据c b r 的框架，开发了个简单的自来水 c b r 系统。这个系统包括案例描述和案例查询。 2 0 0 3 年4 月2 0 0 3 年7 月，研究城市日用水量的预测。阅读了很多关于用 水量预测的文章，并且研究了人工人经元网络，最后建立了一个基于人工神经元 网络日用水量预测模型。同时，研究了优化调度的模型与算法，并应用遗传算法 和单纯形算法对我们所建立的模型进行求解。 2 0 0 3 年8 月2 0 0 3 年1 0 月，开发了基于c b r 的城市供水优化调度软件。 这一软件使用j a v a 语言丌发的，后台数据库使用的是s q ls e r v e r 数掘库。 1 3 本文的主要工作 本文主要包括以下5 个工作： 1 ) 查阅了国内外大量的期刊、书籍、会议文集、研究报告等文献，了解c b r 的 研究现状和未来的研究方向，掌握c b r 的特点以及如何建立实用有效的c b r 系统。 2 ) 研究了人工神经元网络的原理和方法，学习了传统的用水量预测方法，并把两 者相结合，建立了基于人工神经元网络的城市用水量预测模型。并据此在信 息与控制杂志上发表基于人工神经元网络的城市用水量预测一文( 已录 用) 。 3 ) 对传统的水厂出 】水压宏观模型进行了修改，建立了符合沈阳实际的模型，并 用神经元网络进行了模拟。 东北大学硕士论文 第一章导言 4 ) 通过对直接优化调度和二级优化调度的优缺点进行了对比，建立了城市供水优 化调度模型，并用单纯形法和遗传算法进行了求解。 5 ) 设计并开发了基于c b r 的优化调度软件，此软件现正处于测试阶段。 东北大学硕士论文第二章c b r 综述 第二章c b r 综述 在过去的几年里，c b r 已经从原来的默默无闻发展成现在的为世人所瞩目的 研究领域。有关的学术活动迅速发展，这点可以从研究论文、商业产品和应用 的相关报道的增长速率看出来。 基于案例的推理在很多方而与其它的主要人工智能方法有根本性的区别。很 多a i ( a r t i f i c i a li n t e l l i g e n c e ) 方法都非常依赖一个问题领域中的专门知识，或者 在问题描述者和问题解决者之间有不可分割的联系。与此不同，c b r 可以根据具 体问题充分利用以前的经验。一一个新的问题通过找到一个晟相似的旧的案例并且 根据新的情况重用原来的解决方案得以解决。另外一个重要的不同是c b r 也是一 个自学习，自适应的方法。c b r 把每次解决新问题的经验存入案例库以备未来的 使用。 什么是基于案例的推理呢? s c h a n k 给出了一个简单的定义：c b r 就是通过改 变解决旧问题的方法来解决新的问题。让我们来看看几个典型的问题： 1 ) 一个医生在检查完一个病人后，想起了他两周前治疗的一个病人。我们假 设，这种回忆是由于两个病例之间的相似性引起的。那么，这个医生就把先前那 个病人的处方和措施应用到当前这个病人。 2 ) 一个钻探工程师，他曾经经历了两次非常严重的爆裂事件。而当他再次遇 到些测试数据与这两次爆裂案例一致的情况，他就想起了这两次爆裂事件，然 后，他更正了上次的错误，并把前一次的经验应用到现在的情况。 3 ) 一个商务顾问正在做着一项艰巨的信誉决策工作，他使用以前一个与当前 公司有类似经济困难的公司的案例，从而得到结论，应该拒绝这个贷款申请。 2 1c b r 的历史 在人工智能领域，基于案例的推理的根源要追溯到r o g e rs c h a n k 的关于动态 存储的工作】。而另一条c b r 的轨迹来自于类似推理的研究，再往上就是哲学和 心理学关于概念形成、问题解决和经验学习的理论【”1 。举个例子，w i t t g e n s t e i n 观 察自然概念【” ，也就是那些自然界中事物的概念，诸如鸟、橘子、椅子、汽车等 都是多念的。他们的实例可以有各种各样的类别，并且对于这些概念，不可能建 立一个按照一系列特征的有效的典型的概念。解决这个问题的唯一方法是通过一 系列实例或案例表示一个扩展的概念。 东北大学硕士论文 第= 章c b r 综述 第一个基于案例f ：勺推理机的系统是c y r u s 系统，它是由耶鲁大学的j a n e t k 0 1 0 d n e r 开发的。此系统是基于s c h a n k 的动态存储模型】。它是一个具有各种 旅行利会议知识的提问一一回答系统。为这一系统开发的案例存储模型后来已经 作为其他一些基于案例推理系统的服务器，包括：p e r s u a d e r ( s y c a r a - 8 8 ) 1 5 1 c h e f ( h a m m o n d 一8 9 ) 1 1 6 、j l j l i a ( h i n r i c h s 一9 2 ) 【1 7 、c a s e y ( k o t o n 一8 9 ) 1 8 等。 男一个c b r 的基础和模型是由得克萨斯大学的b r u c ep o r t e r 和他领导的小组 开发的 ”】。他们起初想把这台机器设计为解决传统工作概念学习问题的。这导致 了p r o t o s f 2 0 】系统的丌发，它强调把通用知识和专f q 女, h 识集成为联合表现结构。与通 用知识结合的方式在g r e b e t 2 1 1 系统中得到了进一步的发展，它是一个在法律领域 的应用。另一个对c b r 的早期发展作出卓越贡献的是麻省大学的e d w i n a r i s s l a n d 和她所领导的小组。这个小组中有几名法律专家，他们对法律审判中优先推理的 角色感兴趣。这里的案铡( 先例) 不是简单的产生一个结果，雨是解释法庭中的 一种情形，并且产生和估计两方之间的争论。这项研究产生了h y p o 【22 j 系统，并 且后来产生了集成基于案例推理和基于规则推理的c a b a r e t 2 3 1 系统。麻省理工 的p h y l l i s k o t o n 研究了基于案例的推理在优化已存在的基于知识的系统中的应用， 这里的领域知识( 心脏衰竭) 被描述为一个深入的模型。这又导致了基于案例推 理和基于模型推理相结合的c a s e y 系统的产生。 在欧洲，关于c b r 的研究发起的比美国晚一些。但是那里的关于c b r 的研 究与专家系统和知识获取研究比美国有更紧密的联系。关于c b r 的最早的成果是 在m o l t k e 2 4 1 系统中关于复杂技术诊断，它是由m i c h a e lr i c h t e r 与c l a u sd i e t e r a l t h o f f 在凯泽斯劳滕大学共同开发的。而后，在德国各地关于c b r 的系统和研究 成果不断出现。 当今，在荚国和欧洲c b r 活动迅速开展并且在几乎任何一本人工智能的杂志 上的关于c b r 的文章的数目都有快速的增长。考虑到研究者的数目、具有一定规 模研究小组的数目和已经被证实的活动的级别，德国似乎己经处于该领域的领导 地位。在日本和其他亚洲囡家都有c b r 的活动，例如印度。在日本，人们的兴趣 很大程度上集中于c b r 的平行计算方法口”。 2 2 基于案例推理的基础 所有基于案例推理的方法都必须要做的核心的工作是确定当前问题，找到与 新案例相似的过去的案例，使用那个案例根据当前情况对解进行重用，对这个解 进行估计，从这个经验中学习以使系统进行更新。然而，仔细分析后我们不禁要 9 东北大学硕士论文第二章c b r 综递 削：这是如何做到的，这个过程中哪部分最重要，适合这个方法的都是些什么类 型的问题。下面我们努力把各种c b r 方法按照相似的特征进行归类。 2 2 1c b r 方法的主要类型 不同c b r 的范例在组织、搜索、利用和在过去案例库中进行索引等方面均有 不同。案例既可以作为离散的经验保存也可以把一组相似的案例组成一个通用的 案例保存。案例可以作为独立的知识单元存储或者分成子单元并且在知识结构中 分布式存储。案例可以用前束索引或者用开放的词汇表并且有一个平滑的继承的 索引结构。从以前的案例得到的解可以直接应用到当前的问题也可以根据两者的 不同进行修改。案例的匹配、解的重用、案例的学习可以被一个深入的通用领域 的知识模型指导和支持，也可以仅仅基于明显的语义上的相似。c b r 的方法可以 是完全的自适应和自动化，也可以与用户就决策和支持进行交互。一些c b r 方法 在它的案例库中有相当大规模分布式的案例，然而其它的系统却是基于一组相对 有限的典型案例。过去的案例的检索可以顺序进行也可以平行进行。 实际上，“基于案例的推理”恰恰是指这一类系统的各种名词的一种。这已经 引起了一些混淆，特别的，c b r 既被用作是一些类型系统的通用名词也被用来指 一一个特定的方法。就某种程度而言，c b r 也可以说成类似推理。下面我们尽力对 于c b r 相关的各种词汇之间的混淆进行澄清。 基于样本的推理 这个名词来源于“典型观点”、“或然说观点”和“样本观点”对概念进行定 义的各种不同观点。在样本观点中，一个概念被引申定义，如用一系列样本。提 到概念定义的学习的c b r 方法某些时候就是指基于样本的推理。基于样本推理的 例子最早出现在k i b e r 和a h a 的论文中。在这种方法中，解决一个问题就是一个 分类的工作，也就是为一个没有分类的样本找到合适的类。过去相似案例的类成 为分类问题的解决方案。类的集合组成了可能解的集合。因此，找到的解决方案 的修改超出了这个方法的范围。 基于实例的推理 这是基于样本推理的一个高度符号关系c b r 方法的一个特例。为了弥补通用 背景知识的缺乏，为了更加精确的进行概念的定义，一个大量的实例库是必需的。 既然研究的重点是没有人为干预的自动化学习，所以案例的表述通常都很简单。 近来基于实例推理的标志性工作是由k i b l e r 和a h a 以及它们的同事完成的，他们 的月的是使他们的方法与其它的知识相关的基于实例推理的方法相区别。总之， 1 0 东北大学硕士论文第二章c b r 综述 就典型的机器推理学习的方法而言，这不是一个一般的概念学习方法。 基于记忆的推理 这种方法强调把个案例的集合看作是一个大的存储器，并且把推理看作是 在这个存储器中访问和搜索。存储的组织和访问是基于案例方法的焦点所在。平 行处理技术的应用是这些方法的特征，也是它区别于其它方法的所在。访问和存 储方法依赖r 纯粹的语义准则，这一点f 如在m b r t a l k 中的那样，或者它们也可 以努力利用通用领域的知识，例如日本关于大规模平行存储的p a r a d y m e 系统。 基于案例的推理 尽管c b r 在本文巾被用作为一个通用的名词，但是典型的c b r 方法还是有 一些区别于这里所列出的其它方法的特征。首先，一个典型的案例蕴藏了丰富的 信息，并且其内部组织也是相当的复杂。这即是说，一个特征向量保存了一些值， 并且与之对应的类不是我们所晓的典型的案例描述。我们这里指的典型的基于案 例的方法还有其它的特征：当应用于一个不同背景的问题时，他们可以修改或者 适应搜索到的解。典型c b r 系统的核心方法是从认知心理学借来很多理论。 基于类推的推理 这个名词有时候被用作是c b r 的同义词。但是，它总是用来刻画那些基于不 同领域案例来解决新问题的方法。然而 领域案例库中的索引和匹配策略。因此 典型的基于案例的方法侧重于在同一个 类比推理的研究是跨领域推理应用机制 的子领域。这项研究的主要焦点在于过去案例的重用，这是一种被称为映射的问 题：找到一个方法把一个过去的经过验证的推理转换或映射到当前问题。 通篇论文，我们都会继续以通用的意义使用c b r 这个名词，尽管我们的例子、 细节、和讨论都会以更加典型的意义来学习c b r 。 2 2 2 一个描述的框架 我们描述c b r 方法和系统的框架主要有两部分： 1 ) 一个c b r 循环的运行模型。 2 ) 基于案例推理的任务方法结构 这两个模型互为补充并且代表了基于案例推理的两个观点。第一个是一个动 态模型，它验证了c b r 循环的主要子过程以及他们的独立性。第二个是一个面向 仟务的观点，这里一个任务被分解并且每个子任务的解决方法被描述。这个框架 将在随后的部分中使用以验证和讨论c b r 领域中的重要问题，以及处理他们的方 法。 1 1 东北大学硕士论文第二章c b r 综述 2 2 3c b r 循环 以最高级别的一般性，一个通用的c b r 循环可以被描述成下面四个过程： j1 1 在案例库中检索最相近的案例 2 ) 重用用来解决问题的那个案例的信息和知识 3 1 验证建议的解决方案 4 1 存储这个有用的经验以备未来之用 一个新问题的解决是通过检索出一个或多个以前的案例、重用这个案例、验 证重用后案例的解、以及通过把它存储进案例库中实现经验的保存。这四个过程 每一个都包含一系列的步骤，这将在任务模型中进行描述。图1 2 为一个c b r 循 环。 。一个问题的初始描述是定义一个新案例。这个案例被用来在以前的案例集合 中检索一个案例。检索出的案例通过重用与新案例组合成解决的案例，也就是对 于初始问题的一个建议解决方案。这个解决方案通过验证过程检验是否可以成功， 例如可以把它应用到现实世界或者让专家进行估计，并且当失败时对解进行修正。 通过保留，有用的经验被存储以各未来的重新使用，并且案例库也通过学习的案 例或者已存在案例的修改实现案例库的更新。 正如图1 2 所描述的那样，在c b r 循环中，通用的知识支持c b r 的每一个过 程。这种支持因c b r 方法的不同或弱或强。与专门的知识相对，这里的通用知识 指的是一般的领域依赖的知识。举例来说，通过检索和重用以前的案例对病人进 行渗断，各种病理状态的因果关系可以组成一个c b r 系统的通用知识。 2 2 4c b r 任务的层次结构 在c b r 中，这种任务的观点被强调作为一系列连续步骤的循环。为了进一步 分解和描述上面所说的四个步骤，我们转向面向任务的观点，这里的每一步或者 说是子过程都被看作是c b r 推理机必须要完成的任务。个面向过程的观点对即 将发生的事会有一个全局的扩展的观点，而一个面向任务的观点是从c b r 推理机 本身的特点来描述其细节的机制。这与知识级别建模的面向任务的观点是一致的。 在知识的级别，一个系统被看成是一个既有目标又有实现这一目标方法的主体。 一个系统描述可以从三个方面进行：任务、方法和领域知识模型。任务是由一个 系统的目标决定的，个任务可以由一个或多个方法来实现。对于个完成一个 任务的方法，它既需要关于通用应用领域的知识也包括当前问题的信息和它的背 东北大学硕士论文第二章c b r 综述 酲u o ao皇04莒8口口ogo吕立是h_【n兽山 匝霞姆螂牝i球出焉固 o a o l o _ 船 1 鞋茄 渖口袋；oz 8c一缸鱼kmo兰a一_口一 口cm鞠荟兰om五2直 东北大学硕士论文第二章c b r 综述 景。我们的框架和分析方法受知识级的建模方法的强烈影响，特别是受专家系统 的影响。 我们这里所指的任务一方法结构如图2 1 所示f 2 6 l 。任务是由粗体字母命名的节 点，方法则由斜体字书写。任务节点之间的连接是任务的分解，这里联系的方向 是向卜的。顶层的任务是解决问题和经验学习，解决这一任务的方法是c b r 。顶 层任务分解为四个主要的c b r 任务对应于图1 2 的四个过程：检索、重用、验证 和学习。为了完成顶级f i 勺任务这四个任务都是必需的。检索任务以同样的方式分 解为描述、搜索、初始匹配和选择任务。 在这幅图中所有的任务部分都是完整的，也就是说一个任务的子任务的集合 对于完成这个任务是足够的。尽管这些子任务的先后顺序已经粗略地表示出来了， 但是这幅图上没有任何对予任务的控制结构。实际的控制被定义为解决问题方法 中的一部分。连接任务和方法的点划线代表解决一个任务可供选择的方法。一个 方法指定了确定和控制子任务执行的算法以及实现这个方法所必需的知识和信息 的访问和应用。图中所表示出的方法是高层次的方法类，从中一个或多个方法应 该被选择。图中所表示出的方法是不完全的，也就是说表示出的各种方法中的一 个就足以解决这项任务，几个方法也可以组合，或者其他的方法也可以完成这项 工作。图中的方法是任务分解和控制的方法。在任务结构图的最底层，一个任务 可以直接解决。 2 2 5c b r 问题的各个领域 一般来说，对于人工智能，这里没有通用的c b r 方法可以适合所有的应用领 域。c b r 的挑战就是提出适合问题解决的方法，以及在特定专业领域和应用环境 的学习。考虑上面的任务模型，c b r 研究的核心问题可以被归结为5 个领域。这 些问题的解决方案组成了c b r 方法。 知识表示 检索方法 重用方法 验证方法 学习方法 在下面的部分，我们给出一个关于这五个领域相关的主要问题的概览。 1 4 东北大学硕士论文第二章c g r 综述 2 3 案例的表示 一个基于案例的推理机的效率很大程度上依赖于案例库的结构和内容。既然 一个新问题通过在案例库中搜索个适合当前问题的案例来得以解决，那么案例 的搜索和匹配就既要可行又要有效率。另外，既然问题在解决后其经验要被存储 起来，那么经验存储的过程电要应用把新案例集成到案例库的方法。在c b r 中问 题的描述主要是决定在存储器存些什么、找到一个表示案例的合适的结构，以及 决定案例存储器如何被组织和索引以便高效的检索和重用。 接下来，我们将要讨论两个很有影响的案例存储模型：s c h a n k 和k o l o d n e r 的 动态存储模型以及p o r t e r 和b a r e i s s 的类别一样本模型。 2 3 1 动态存储模型 正如我们先前所提到的，第一个称为c b r 推理机的系统是基于s c h a n k 的动 态存储模型由k o l o d n e r 完成的c y r u s 系统。这个模型的案例存储是一个被称为 “片段存储组织包”的层次性结构。这个模型是由s c h a n k 的理论发展而来的，它 的基本思想是以在一个更加通用的片断中共享相似的特征的方式来组织案例。一 个通用的片断包含三个不同类型的对象：规范、案例和索引。规范是在一个通用 片段中索引的所有案例的通用特征，索引是在一个通用片段中各个案例相互区别 的特征。一个索引可以指向一个更加特殊的片断也可以指向一个案例。一个索引 包含两部分：索引名和索引值。 图2 2 描述了这种结构 14 1 。这是一个复杂的通用片段，在它的下面包含了案例 和更加特殊的通用片段。完全的案例存储器是一个鉴别网络，在这罩一个节点既 可以是一个通用片段、索引名一值对，也可以是一个案例。每一个索引值对指向 一个通用片段或者是一个案例。而一个索引值即可指向一个简单的案例也可以是 一个简单的通用片段。因为到达一个特定的案例或者是一个通用片段有多条路径， 所以这个索引方案是丰富的。 当给定一个新的案例描述，即开始搜索最佳匹配。输入的案例从根节点被压 到这个网络结构中。案例的搜索与案例的存储相似。当新案例的一个或多个特征 与个通用片段匹配时，这个案例的进一步区别就要基于它剩余的特征。实际上， 与新案例有最多菇同特征的案例将会被找到。在一个新案例在存储过程中，当新 案例的一个特征与已存在的案例匹配时，一个通用片段将会被创建。这两个案例 在这个通用片段f ，依赖于其它的特征相互区别。因此，这个存储结构是动态的。 东北大学硕士论炙第二章c b r 综述 圈2 2 案例库和通用片段的结构图 f i g 2 2s t r u c t u r eo f c a s e s a n d g e n e r a l i z e de p i s o d e s 案例的搜索先是找到一个与问题描述有最多共同点的通用片段，然后在这个 通用片段下比较其它的特征。存储一个案例以同样的方式实现。因为索引结构是 一个鉴别网络，一个案例在每一个区别于其他案例的特征下存储。这样随着案例 数目的增多，很容易导致索引的