（电力系统及其自动化专业论文）基于事例推理的继电保护运行管理专家系统.pdf

t h ep r o t e c t i o n o p e r a t i o nm a n a g e m e n t e x p e r ts y s t e mb a s e d o nc b r a b s t r a c t a st h em o s ta c t i v eb r a n c hi na r t i f i c i a i i n t e l l i g e n c ef i e l d e x p e r ts y s t e mm a d ea w i d e a p p l i c a t i o ni np o w e rs y s t e m d e p e n d i n go na r t i f i c i a li n t e l l i g e n c em e t h o d ，l o t s o f w a r n i n gm e s s a g e c a nb ed e a l tw i t ha u t o m a t i c a l l ya n df a u l te l e m e n tc a n _ b ed e t e c t e d q u i c k l y s o i ti s i m p o r t a n tf o rt h ed i s p a t c h e r t o g u a r a n t e e t h es a f ea n d s t e a d y o p e r a t i o no f t h ee l e c t r i c a ln e t n o w , m o s te x p e r ts y s t e m sa r eb a s e do nr b r ( r u l e b a s e dr e a s o n i n g ) i nw h i c h g e n e r a lk n o w l e d g e i ss t o r e d ，t h e ns e l f - l e a m i n gb e c o m e s v e r yd i 硒c u l t t h i sm a k e st h e c y c l eo f s y s t e m ss h o r ta n dr e s t r i c t st h ed e e p e ra p p l i c a t i o no f t h es y s t e m st ot h ef i e l d s h o w e v e r ，t h et h i n k i n gm e t h o do f e l e c t r i c a le x p e r t sa r ev e r ys i m p l ea n d p r a c t i c a l ，t h a t i s ，b e s i d e st h en e c e s s a r yr u l e b a s e dr e a s o n i n g 。t h e ym o s t l yu s et h ee x i s t i n gf a m i l i a r a n dt y p i c a lp r o j e c ti nt h e i rh e a d a c c o r d i n gt ot h em a t c h i n gt ot h ep r a c t i c a lp r o b l e m t h e ya d j u s tt h ee x i s t i n gp r o j e c ta n de d u c et h ef i n a lp r o j e c t 1 1 1 i st h i n k i n gm e t h o d c o i n c i d e sw i t hc b r ( c a s e b a s e dr e a s o n i n g ) t h ee s s e n t i a li d e ai s ：t h er e a s o n i n g w o r km a yb eb a s e dt h e p r e v i o u ss u c c e s s f u lc a s ea n du n n e c e s s a r y t od of r o mt h es t a r t t h e r e f o r e ，i t s av e r ys i g n i f i c a n tw o r kt o d e v e l o pt h es e l f - l e a r n i n gp r o t e c t i o n o p e r a t i o nm a n a g e m e n te x p e r ts y s t e m b e c a u s e t h es y s t e mc a ne n r i c ht h ek n o w l e d g e l i bi nt h ea p p l i c a t i o n i tc a l lo v e r c o m et h eb o t t l e n e c ko f k n o w l e d g eo b t a i n m e n ta n d p r o l o n g t h es y s t e m r e c y c l e t h sp 印e rf i r s t l ya b s t r a c t st l l ed e t a i l e dp o w e rs y s t e mi n t o “g r a p h ”，t h e nu s et h e g r a p hs i m i l a r i t yf o r m u l at oc a l c u l a t et h es i m i l a r i t ) ，o fq u e r yc a s et ot h el i bc a s e ，a n d t h ec a s ew i t ht h em o s ts i m i l a r i t yi st h er e s u l t w eu s eg e n e t i ca r i t h m e t i ct os o l v et h e c o m b i n a t i o ne x p l o s i o n ”p r o b l e m a n du s es i m u l a t e da n n e a l i n ga r i t h m e t i ct os o l y e t h e “e a r l vm a t u r e ”p r o b l e m ，t h e nf o r i l l ss i m u l a t e da n n e a l i n gg e n e t i ca r i t h m e t i c a c c o r d i n g t ol o t so f t e s t ，i tp m v e st h ef e a s i b i l i t yo f t h ea r i t h m e t i c i no r d e rt oi m p r o v e t h ee f f e c t i v i t y , w ec o m b i n ec b rw i t hr b r k e y w o r d s ：c b r ，r b r ，p r o t e c t i o n ，e x p e r ts y s t e m ，s e l f - l e a r n i n g 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外 本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。 对本文的研究做出重要贡献的个人和集体，均己在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：d 父名 日期：山埘年一月，j 日 l 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅。本人授权上海交通大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存和汇编本学位论文。 保密囱，在三年解密后适用本授权书。 本学位论文属于 不保密口。 ( 请在以上方框内打“4 ”) 学位论文作者签名：也艾另 日期：知识年j 月f 日 指剥币虢研、 嵫强串秽 日期：山咄年，月j 日 第一章概述 1 1 专家系统在电力系统中的应用现状 专家系统作为人工智能领域中最活跃的一个分支，近年来在电力系统中取得 了广泛的应用。利用人工智能方法自动处理大量的报警信息，快速诊断故障元件， 对调度员迅速处理故障，保证电网安全稳定运行具有重要意义。目前大多的专家 系统都是基于规则推理r b r ( r u l e b a s e dr e a s o n i n g ) 的。在这些系统中，知识 库中存储的是一般知识。因此系统中实现自学习功能非常困难。从而使开发出的 系统生命周期很短。这必然大大限制了专家系统在该领域的进一步应用。 而电力系统领域专家在实际工作中的思考方式是非常简洁实用的，这就是除 了采用必要的规则推理以外，他们更多地利用其脑海中已熟知的典型方案，根据 实际问题与之相配，再加以适当修改和调整，从而得到符合实际问题的保护方案。 这种思维方式恰好和智能界近来兴起的基于事例的推理c b r ( c a s e 。b a s e d r e a s o n i n g ) 方法相吻合。 应用c b r 后，在知识库中不存储一般知识，而存储专门知识。我们将继电 保护工程师每次操作记录下来。内容包括：操作的一次设备名称、电压等级、接 线方式、运行状态、操作类型等：操作的二次设备名称、保护范围、保护类型、 设备状态、操作类型等：相应对策；等等。这样，今后再进行操作时，首先到知 识库中查找相似操作，若找到足够相似的操作，则直接应用其对策( 可能同时做 一些修改) ；若找不到，则允许工程师输入对策，向知识库中添加新的知识，从 而实现了自学习的功能。 本课题将对一般知识采用r b r 推理，然后将一般知识推理结果与c b r 推理 相结合，开发基于事例推理的继电保护运行管理专家系统。 1 2 课题来源 本课题是上海市教育委员会重点学科项目具有自学习能力的分布异构的电 力继电保护专家系统的研究的一个子课题。该课题包括两个部分：c b r 和其 它a i 技术的结合以及a i 技术和c o r b a 的结合。在理解了c b r 技术基础上， 我用v c 开发出了“基于事例推理和规则推理相结合的继电保护运行管理专家系 统”软件。 上海交通大学硕士学位论文 1 3 本课题的意义 继电保护在电力系统运行中起着重要的作用。随着电网规模扩大、结构复杂 化，保护装置数量、种类繁多，保护配置方案的确定成为一项极为复杂的工作。 它不仅要从电力系统的结构、运行方式、保护型号等几个方面加以考虑，而且包 含了继电保护工程师丰富的实践经验。对继电保护工程师来说是一项繁琐而责任 重大的工作。因此，研制继电保护运行管理专家系统对提高继电保护运行管理水 平具有重要意义。 然而，知识获取是目前建立专家系统过程中最为困难的阶段之一。由于领域 专家可能无法明确表达他的全部知识，知识库系统往往要经过领域专家和知识工 程师的长期艰苦的反复交换意见的过程。由此获取的知识仍然可能是不全面的、 不准确的。更为不利的是，这些知识往往是静态的，不能适应领域知识不断发展 变化的要求。 因此，研究具有自学习功能的网调继电保护运行管理专家系统是一项极有意 义的工作。该系统研制成功后，必将在继电保护运行管理中发挥重大作用。由于 它可以在应用过程中通过自学习逐渐完善知识库，因而可以有效地克服知识获取 瓶颈问题，同时它也能很好地适应电力系统自身发展变化的需要，大大地延长其 生命周期。本课题在电力系统领域具有基础性和开创性，并具有广阔的应用前景。 第二章基于规则推理( r b r ) 2 1 专家系统概述 专家系统是一类计算机程序，当它运行时，能够像人类专家那样解决有关领 域的专门问题。它的体系结构如下： 1 ) 知识库。其中最主要包含以事实和规则表述的领域知识，还可能包含有 关知识的知识( 元知识) 和有关知识库本身的知识等。 2 ) 推理机。这是对推理过程进行控制的模块。它将具体实施某种控制策略。 3 ) 工作存储器和工作区间。其中包含专家系统运行时所形成的各种数据。 4 ) 知识获取子系统。人类专家或知识工程师将通过这个子系统增加、删除 或更改知识库的内容。 5 ) 解释子系统。这一子系统的主要作用时解释、翻译或说明专家系统和用 户之间交互作用所涉及的问题、结论、推理过程、因果关系等。 6 ) 用户接口。直接面向用户，是专家系统与用户之间交互和对话的窗口、 其中知识库和推理机是专家系统的核心部分，其结构框图如图2 1 示： 图2 1 专家系统的一般体系结构框图 i 海交通大学硕士学位论文 2 2c l ip s 概述 为了实现继电保护专家系统中的“基于规则推理( r b r ) 部分”，在设计中采 用专家系统软件c l i p s 6 0 2 。c l i p s 是由美国国家航天局n a s a 的约翰逊空间中心 ( j o h n s o ns p a c ec e n t e r ) 的人工智能部开发的，主要用于管理、工业、商业、 文教等各种领域的实际专家系统的开发，具有广泛的通用性。它最突出的特点是 具有在不确定性下进行推理的能力，同时又具有学习能力。 c l i p s 程序设计的主要形式就是“事实匹配”，它由两部分组成，一个部分是 已断言的事实，另一部分是为了完成某项任务而制定的规则，规则也分为两个部 分，我们可以用一个简单的规则来说明，下面是这个规则的定义： d e f r u l ef i r e e m e r g e n c y“a ne x a m p l er u l e ” ( d e v i c ei so n ) ( e m e r g e n c yf i r e ) = ( a s s e r t ( a c t i o na c t i v e s p r i n k l e r s y s t e m ) ) 7 p r i n t o u tt “s h u t t i n gd o w nd e v i c e ”e r l f ) 在这个规则里。d e f r u l e 是定义规则的命令，用于定义规则名称和注解，即规则 的第一行，其余的部分被由等号和大于号组成的箭头分成两个部分，箭头前面的 部分是由零个或多个模式( p a t t e r n ) 组成的，也就是规则的左端l h s 条件 部分：箭头后则是规则的右端r h s ，也就是动作部分，给出动作表。 3 1 c b r 简介 第三章基于事例推理( c b r ) c b r 起源于7 0 年代，是人工智能发展过程中涌现出来的区别于r b r 的一种 推理模式。其核心思想是：当求解问题时，在以前类似的求解问题的成功范例基 础上进行推理，而不必一切从头作起。因此，人们常采用基于事例推理来提高解 决问题的效率。 在c b r 中，事例库模拟人脑的记忆，存储了些过去的相关经历( 事例) ， 这些事例按一定的方式组织，以便在需要的时候能及时取出。回忆过程对应了 c b r 中从事例库中检索出相关事例的过程。被检索的候选事例可能与新的情形 不完全一致，这时需要对该候选事例的某些特征进行修改，以适应新的情况。修 正后的事例是否适应实际情况，还需要得到检验。如果经过检验发现不符合实际 情况，还需要进行修改，最后新的事例以一定的策略加入事例库中( 见图3 1 ) 。 这样通过对旧事例的证实和修正。可不断获得新的知识，因此，通过c b r 技术 的应用，就达到了知识动态学习更新的目的。 i 海交通大学硕士学位论文 同r b r 相比，c b r 有下面的特点和优越之处： 第一，c b r 具有自学习功能，这是r b r 所不具有的，而且，c b r 可以“零 事例启动”。 第二，c b r 更接近于人类的决策过程。专家每当遇到一个问题时，他总是首 先在头脑中回想一下过去的类似问题，从中获得对当前求解问题的思路。 第三，c b r 使得将新知识结合到以存在知识库中去的过程能够自动化。对于 一个机遇规则的系统而言，每当无法得到问题所期望的答案的时刻，必须创建新 的规则并加入到知识库中去，但对于c b r 系统来说，由于每个c a s e 都被记录于 库中，因而可以自动的充当解答问题所需要的知识。c b r 可以解决基于规则的 系统中所遇到的知识获取的问题。 第四，创建c a s e 库通常比创建知识库快的多。在基于规则的系统中，知识 工程是通过对专家进行提高，得到专家推理行为的背后所隐含的知识。这是一个 极为化时化力的过程。而对于c b r ，知识工程师只需对过去的问题( 即事例) 的关键特性进行标示、存储并建立索引以便这些特征能被回想起来。对于c b r 系统而言，收集c a s e 不需花太多的时间，因为很多应用领域中都已经将过去的 事例详细的归档存放起来了。 第五，运行c b r 系统的速度要比基于规则的系统快。原因在于：运行大型 的基于规则的系统时，每当从知识库中激发了可应用的规则的时刻，因为符合条 件的规则数很多，困难就来了。在c b r 中，却无需调用规则，只要根据索引， 从c a s e 库中调出相似的c a s e 即可，而且随着高速c a c h e 的发展，c b r 的检查 过程可以达到很快很快。 第六，c b r 提供了更好的解释和决策机制。在基于规则的系统中，解释机制 是对导致结果的推理规则链进行理由说明，而c b r 系统则是通过描述在索引中 产生的规则而达到对解释进行理由说明的目的。 第七，c b r 可用于那些不易理解的领域中的问题。而在基于规则的系统中。 如果有冲突的规则应用于不同的情形，则是不合适的，但这样的领域却适用于 c b r 。 3 。2c b r 中的关键技术 c b r 的关键技术包括：事例表示，事例索引，事例检索，事例修正。 3 2 1 事例表示 c b r 系统的核心是事例库。c b r 系统的性能和效率在很大程度上依赖于事例 的组织和表示方法。它将直接影响事例的检取、应用、修改和存储方法。在设计 和选择事例表示方案时需要考虑的因素有： 1 )c a s e 中应存储哪些内容? 上海交通大学碗士学位论文 2 )如何对c a s e 进行索引? 3 )如何进行c a s e 匹配操作? 4 ) 如何将c a s e 中表达的特殊知识和其他一般知识相集成? 非常好的一点是，事例表示法可广泛采用各种a i 表示法，例如规则、一阶 谓词、语义网络、框架、面向对象，以及关系型数据库等表示法。应根据具体问 题与的特点和要求选择合适的表示法。 目前，在c b r 界遇到的另一个难题是实力的海量存储问题。当事例库急剧增 大时，如何高效的对其进行索引、检索、存储等操作? 理想的方法是利用大型数 据库管理。事实上，国际上已由很多人从事利用关系数据库存储、管理规则，并 利用数据库自身的关系模型实现推理过程的研究。该数据库被称为演绎数据库。 如能将成熟的数据库技术嫁接到c b r 系统中，则可充分的实现两者的优势互补。 3 2 2 事例索引 事例检索和事例存储都需要利用事例索引。正如数据库系统，事例索引对提 高整个系统的推理和学习效率非常关键。在一些简单的系统中，往往选择所有问 题特征作为索引。则对于大型系统会消耗大量的计算机资源。在大型系统中，应 该根据一定的原则正确的选择索引。有两种方法：人工选择和自动选择。自动选 择索引的方法概括起来有： 1 ) 相似法( s i m i l a r i t ya n de x p l a n a t i o n - - b a s e dg e n e r a l i s a t i o n m e t h o d s ) 选择基于事例的公共特性作为主索引，而非公共索引则作为次索引； 2 ) 差异法( d i f f e r e n c e - - b a s e di n d e x i n g ) 选择那些能使一个事例区分于另一个事例的特色作为索引； 3 ) 归纳法( i n d u c t i v el e a r n i n gm e t h o d s ) 通过利用一种决策树算法( 如i d 3 算法) 来寻找最佳的一组特征作为索 引。 虽然由许多索引自动选择算法，j a n e tk o l o n d b n e r 仍认为人工选择索引是最 佳的方法。 3 2 ，3 事例检索 给定问题描述后，c b r 将根据一种事例检索算法，使用事例索引，从事例库 中检索出与该问题描述最为接近的一个事例。这个过程可以进一步划分为三个子 过程： 识别问题特征：从问题描述中识别主要特征，消除噪声，形成评价函数； 初始匹配：利用快速算法，从事例库中检索出一组较为相似的事例； 最终确定；利用更为复杂的算法，从上组事例中最终确定最为相似的一个事 例。 c b r 系统中的事例检索和数据库中的数据查询有着很大的区别。后者总是进 行精确的匹配，而前者则需要进行模糊的或者部分的匹配。这是因为，针对新的 上海交通大学硕士学位论文 问题，般不会在事例库中找到与之完全匹配的旧事例，而总有些差别。这就给 事例检索带来了很大困难。例如：在检索事例时应该评价哪些因素? 这些因素的 权重如何确定? 如何确定相似度门槛值? 归纳起来，检索办法主要分为： 1 ) 利用相似度函数进行检索： 最近邻法( n e a r e s tn e i g h b o r ) ，如式( 3 - i ) m i s i m ( f i * ，8 ) m c 。= 型_ 一 ( 3 - 1 ) q 式中：国，是第i 个问题特征的权重，7 和，。分别是输入事例和输出事例的 第i 个问题特征的值，j 咖7 ，8 ) 是输入事例与输出事例之间的属性相似度， m c 是考虑到权重后的综合相似度。 s i r e ( z7 ，”) 有多种算法。这里简要介绍几种： s z 卅c ，7 ，8 ，= 口 ! 蓄笺易嚣等， c 。一z ， s i r e ( f , 7 ，。) = 钔归一邶i ( 3 3 ) s i m ( f7 ，：8 ) = ( 3 4 ) 问题特征的选择在事例表示中已经解决。但确定每个问题特征的权重则是一 个新问题。可以采用两种办法解决： a ) 由领域专家确定 首先生成一个问题特征权重矩阵，然后后请若干领域专家，让其根据各自 经验填写该矩阵，最后通过求取平均值而得到各个权重。 b ) 人工神经网法 利用人工神经网络进行训练，从而得到各权重。为此，必须精心选择足够数量的 典型事例库。 2 ) 归纳法( i n d u c t i o n ) 。 归纳算法( 例如：i d 3 算法) 通过动态形成决策树( d e c i s i o n t r e e ) 来实现 事例检索。决策树本身就是一种有效的且较为成熟的机器学习算法。 3 ) 基于知识引导的归纳法( 1 ( n o w l e d g eg u i d e d i n d u c t i o n ) a 本方法应用一般知识( 如规则) 来指导事例检索过程，从而得到特殊知识( 事 例) 。 上鹰交通大学硕士学位论文 4 ) 模版检索( t e m p i a t er e t r i e v a l ) 。这是一种类似于s q l 查询语言的检索算 法。 3 2 4 事例修正 前面已经讲过，一般难以在事例库中找到与当前问题( 新事例) 完全匹配的 旧事例。那么，一旦事例检索环节取得了一个最相近的事例后，c b r 系统应当根 据当前问题特征进行调整，以使其适应新的情况。一般认为，有两类事例修正方 法： 1 ) 结构化修j e ( s t r u c t u r a la d a p t a t i o n ) 将一组修难规则直接应用到旧事例的解，从而得到新事例的解a 2 ) 导出法修正( d e r i v a t i o n a la d a p t a t i o n ) 将旧事例中从问题推导出解的规则重新应用到新事例，以新事例的问题特征 为输入，利用该规则重新推导出新问题的解。 上面两类事例修正方法可由图3 2 说明之： a s t r u c t u r a la d a p t a t i o n b d e r i v a t i o n a la d a p t a t i o n 图3 2 事例修正方法 显然，导出法可以得到满意的事例修正结果。但是，这要求在事例库中伴随 每个事例，必须存储由问题到解的推导规则。但在很多问题语种，这些推导规则 是难以得到的。 上海交通j 。学顿士学位论文 第四章遗传算法 对于电力系统的操作，操作时的具体接线方式极为重要，若用规则表示，由 于规则中必须体现接线方式，从而导致规则可能非常复杂。 由于上述原因，电力系统操作对策多为浅知识，且规则之间联系较弱，规则 推理优势不明显： 1 ) 电力系统操作，既要比较元件的属性和操作，又要比较拓扑关系； 2 ) 直接用网络图表示事例，具有巨大的优势：容易修改，容易解释结果等； 3 ) 形成查询事例，可要求用户标出感兴趣的子网络 其实，无论怎么复杂的电力系统，都可以用图来表示。图的节点指母线( 或 虚拟母线) ，而图的边包括线路、变压器、断路器、开关等双端元件，以及发电 机、负荷、电抗器等单端元件，另外，由于保护装置( 如母线保护，线路保护， 发电机保护等) 皆装设于厂站内，因此也可视作图的边。在具体实现时，图中的 节点和边都用对象表示。每个对象都有自己的属性集合( 如电压等级，接线方式， 运行状态等) 以及操作集合( 如投入、退出、检修等) 。这里要指明的是：为了 把双端元件抽象成边。我们这里引入了“虚拟母线”概念。 4 1 图论 4 1 1 结构化事例表示 本论文采用基于加权图( 1 a b e l dg r a p h ) 的事例表示方法。加权图的定义如下： 加权图是一个四元组g = ，e ，口，) 。其中： n 是由图的节点构成的有限集，e 是由图的边构成的有限集，口：n 哼k 是 节点的标注函数，：e 斗l 。是边的标注函数。 n n ( g ) 是图g 节点的个数，n e ( g ) 是图g 边的个数。 g ( n ) 是图g 的子图。该子图由节点n 以及与n 相连的所有边构成。 w ( n ) 是节点n 的权，w ( e ) 是边e 的权。 4 1 2 加权圈的映射 设g ，： n ，e ，口。，屈) ，g 。= 。，e 。，啦，臆 是待比较的加权图，n n ( g t ) 5 r n n n ( g 。) = n ，并假设n = l t l 。容易得出，g t 与g 。节点间的映射关系有m ! 组。 于是可以这样加权图映射： i 海交通大学钡学位论文 g ，= m ，莓，届 ，g ，= 札，毛，0 。，屈 为加权图。m ：q 专g 。是 图q 到g ，的映射( m a p ) 。它满足( 4 1 ) 和( 4 2 ) ( 1 ) v n ，n 。，3 n ，n ，满足：m ( n 1 ) = m ( n 2 ) v n l ，以2 n ，竹1 n 2 ，满足：m ( n i ) m ( n 2 ) ( 4 1 ) ( 2 ) v e 。= ( ”，l ，竹，2 ) e ，m ( n ：2 ) = n s l , m ( n ，2 ) = n ，2 ，满足： ，( e ，) ： ：矿p f = ”n ，n t 2 8 5 。e b e 。, ( 4 - 2 ) 例如，图4 1 就是g f 到g ，的一个映射。 图4 1 加权图之间的映射 两个加权图之间存在映射的判断依据： 加权图g t 与g s 之间存在映射的充要条件是n n ( g t ) n n ( g s ) 。 4 1 3 相似度的计算 首先定义节点和边的相似度计算公式： 设m 为加权图g ： m ，e 。，口，屈 到g s = ，e ，屈 的映射 m n ，n ，已，= ( ，h ：) e e ，p 。= ( k ，丌：) e ；，则有 ( 1 ) d s 。l l t ，n s ) 为映射m 下节点q 和”。之间的相似度。其值为( 4 - 3 ) 上海交通大学碗士学位论文 d s m ，= 仨! 坝啊卜m q 掣 ， ( 2 ) d s m ( e ，e 。) 为映射m 下边e 。和e ，之间的相似度。其值为( 4 4 ) ： 1 1 ，m ( er ) 2 气a f l ( nz ) 2 f l ( n s ) d s 。( 巳，e s ) = 0 5 ，m ( e 。) = p ； f l ( n ，) f l ( n ，) ( 4 4 ) 1 0 ， e l s e 再定义加权图的相似度计算公式： 设m 为加权图q = n ，e ，口，f l , 到g ，= 。，e ，展 的映射， d s 。( g ，g ，) 为映射m 下图g 。和g 。之间的相似度a 其值为( 4 。5 ) ： d s 解g 沪箍 ( 4 _ 5 ) 其中： c ：坠型黜小，脚f ) ) t ：坠掣黜以朋) b e 6 一 m 。= m a x ( 矽( 吣( 怫) ) m 。= m a x ( w ( e ，) ，矽( e 。) ) e t e er e ，e e 。 因为d s ( n ，l ，) 1 ，d s m ( e ，p 。) 1 ，可由上述定义得出d s m ( g t ，g s ) 曼1 。 d s 。( g ，g ；) 为图g t 和g 。的相似度。其值为( 4 6 ) ： d s ( g ，g ，) = m a x d s f ( q ，g ，) 】 4 ，2 统一建模语言( u m l ) ( 4 - 6 ) 42 1l i m l 语言产生的背景 u m l 是一种面向对象的建模语言。在此之前，以论文、专著、报告等形式提 出的面向对象建模语言或方法不下5 0 种。这种“百花齐放”的繁荣局面对面向 对象技术的研究和发展起到了很大的促进作用。然而多种建模语言的同时流行也 上海交通大学弼i 学位论文 带来很大的问题。首先，用户难以区别不同语言之间的差别，并根据其应用特点 选择合适的建模语言；其次，各种建模语言虽各有千秋，各有长短，但用户不可 能同时采用多种建模语言；第三，不同的建模语言在表示法及语义等方面存在差 别，这极大地妨碍了用户之间的交流。因此，在全面总结、比较各种建模语言的 基础上，建立统一建模语言的工作变得极为必要。 自1 9 9 4 年起，由世界著名的面向对象技术专家g r a d yb o o e h ，j i mr u m b a u g h 和i v a rj a c o b s o n ，在著名的b o o c h 方法、o m t 方法和o o s e 方法的基础上，广泛 征求意见，集众家之长，终于完成了统一建模语言u m l 。u m l 是一种定义良好， 易于表达，功能强大，且普遍适应的可视化的建模语言。它融入了软件工程领域 的新思想、新方法和新技术。它不仅可以支持面向对象的分析和设计，更重要的 是能够强有力地支持从需求分析开始的软件开发的全过程。 因此，u m i 。出现便获得了工业界和学术界的广泛支持。1 9 9 6 年底，u m l 已 经稳定地占领了面向对象技术市场的8 5 ，成为可视化建模语言事实上的工业 标准。更重要的是，1 9 9 7 年1 1 月，国际对象管理组织( o b j e c tm a n a g e m e n tg r o u p ， 简称o m g ) 采纳u m l 做为基于面向对象技术的标准建模语言。因此，u m l 代表了 面向对象的软件开发技术的发展方向，具有重大的经济价值和国防价值。 4 2 2u m l 模型 u m l 提供的基本模型包括： ( 1 ) 用例图：展示系统外部的各类执行者与系统提供的各种用例之间的关系。 ( 2 ) 类图：展示系统中类的静态结构。 ( 3 ) 对象图：是类图的一种实例化图。 ( 4 ) 包图：是一种分组机制。 ( 5 ) 状态图：描述一类对象具有的所有可能的状态及其转移关系。 ( 6 ) 顺序图：展示对象之间的一种动态协作关系。 ( 7 ) 合作图：从另一个角度展示对象之间的动态写作关系。 ( 8 ) 活动图：展示系统中各种活动的执行流程。 ( 9 ) 构件图：展示程序代码的物理结构。 ( 1 0 ) 配置图：展示软件在硬件环境中( 特别是在分布式以及网络环境中) 的配 置关系。 由于本论文中大部分都使用了类图，下面我们将着重讨论之a 4 2 3 类图 类图是u m l 中最基本的模型图，如图4 2 ( 1 ) 。利用它，可以非常清晰直观 地表示出系统中的类、类的特征以及类之间的关系。在专家系统分析、设计阶段， 最重要的工作就是研究类的结构、确定类的属性和行为。这是和传统的面向功能、 以函数为中心的开发方法所截然不同的。 常见的四种关系：继承关系、关联关系、实现关系和依赖关系。 兰堑型坚型丝垄苎 继承( i n h e r i t a n c e ) 关系：表示类之间一般一特殊的关系，用三角 符号表示。如图4 2 ( 2 ) 关联( a s s o c i a t i o n ) 关系：表示类之间的数量关系，用带数字的连 线表示，如图4 2 ( 3 ) 。数字表示关联的度( m u l t i p l i c i t y ) 。特殊的 关联包括：聚集( a g g r e g a t i o n ) 和组合( c o m p o s i t i o n ) 。其中，聚集 是表达主体一部分关系的关联，它用在聚集端的菱形符号来表示，如 图4 2 ( 4 ) ；组合是关联的更强的形式，它用组合端的实心菱形来表 示，如图4 2 ( 5 ) 。 实现( r e a l i z a t i o n ) 关系：表示一个类提供了另一个类( 接口) 的 所有方法，它用虚线的三角符号表示，如图4 2 ( 6 ) 。 依赖( d e p e n d e n c y ) 关系：表示一个类的修改影响到另一个类。常见 的依赖关系有：实例化和使用。它用虚线箭头来表示，如图4 2 ( 7 ) 。 ( 4 ) a g g r e g a t i o n( 5 ) c o m p o s i t i o n ( 6 ) r e a l i z a t i o n ( 7 ) d e p e n d e n c y 图4 2 类图 4 2 4 图论应用于实际的网络 我们将实际的电力线路抽象化：将母线和虚拟母线抽象为点，将线路、变压 器、断路器、开关、发电机、电抗器等抽象为边，于是可用图4 3 表示。 这样，我们可以将任意实际的电力线路和专家系统事例库中的事例抽象成 图，然后按照图4 3 写代码求解两个图的相似度，找出相似度最大的一个，就是 ) ) ) ) q 他 甲曼争当 盏一 詈 生堑型望型丝丝苎 推理结果。 图4 3 基于图论的求解相似度类图 这种解法对于节电数小的电力网络是可以的，但是随着节电数的增加，要比 较的次数也成阶乘( n 【) 的增加，如图4 4 所示( n 代表节点数，t i m e s 代表计 算次数) 。这就是所谓的“组合爆炸”，为了解决这个问题，我们引进了遗传算法。 nt i r u e snt i m e s l11 5l3 0 7 6 7 4 3 6 8 0 0 0 361 86 4 0 2 3 7 3 7 0 5 7 2 8 0 0 0 51 2 02 02 4 3 2 9 0 2 0 0 8 1 7 6 6 4 0 0 0 0 75 0 4 0 2 51 5 5 1 1 2 1 0 0 4 3 3 3 0 9 8 5 9 8 4 0 0 0 0 0 0 1 03 6 2 8 8 0 03 02 6 5 2 5 2 8 5 9 8 1 2 1 9 1 0 5 8 6 3 6 3 0 8 4 8 e + 3 2 图4 4 图论求解次数与节电数的关系图 i 海变通大学碗士学位论文 4 3 遗传算法 43 1 遗传算法简介 遗传算法是模拟生物在自然环境中的遗传和进化而形成的一种自适应全局 优化概率搜索算法。它最早由美国密执安大学的h o l l a n d 教授提出，起源于6 0 年代对自然界和人工自适应系统的研究。7 0 年代d ej o n g 基于遗传算法的思想在 计算机上进行了大量的纯数值函数优化计算试验。在一系列研究工作的基础上， 8 0 年代由g o l d b e r g 进行归纳总结，形成了遗传算法的基本框架。 对于一个求函数最大值的优化问题，一般可描述为下述数学规划模型( 4 7 ) ： fm a x ，( x )( 1 ) s t x r( 2 )( 4 - 7 ) lr 互u( 3 ) 式中，x = k ，x ：，h r 为决策变量，f ( x ) 为目标函数，在( 4 7 ) 中，式( 2 ) ( 3 ) 为约束条件，u 是基本空间，r 是u 的一个子集。满足约束条件的解x 成 为可行解，集合r 表示由所有满足约束条件的解所组成的一个集合，叫做可行 解集合。 对于上述最优化问题，目标函数和约束条件种类繁多，有的是线形的，有的 是非线形的：有的是连续的，有的是离散的；有的是单峰值的，有的是多峰值的。 随着研究的深入，人们逐渐认识到在很多复杂情况下要想完全精确地求出最优解 既不可能，也不现实，因而求出其近似最优解或满意解是人们的主要着眼点之一。 总的来说，求最优解或近似最优解的方法主要有三种：枚举法、启发式算法和搜 索算法。 随着问题种类的不同，以及问题规模的扩大，要寻求到一种能以有限的代价 来解决上述最优化问题的通用方法仍是一个难题。而遗传算法却为我们解决这类 问题提供了一个有效的途径和通用框架，开创了一种新的全局优化搜索算法。 遗传算法中，将n 维决策向量x = b 。x ：，k 】2 用1 1 个记号x ，( f = 1 , 2 ，n ) 所组成的符号串x ，如( 4 - 8 ) 来表示： 爿= x l z 2 x 。j x = 防1 ，2 ，x 。r ( 4 8 ) 把每一个z 看作式一个遗传基因，它的所有可能取值称为等位基因，这样，z 就 可看作是由n 个遗传基因组成的一个染色体。一般情况下，染色体的长度r l 是固 定的，但对于一些问题n 也可以是变化的。根据不同的情况，这里的等位基于可 以是一组整数，也可以是某一范围的实数值，或者是纯粹的一个记号。最简单的 等位基因是由0 和1 者两个整数组成的，相应的染色体就可表示为一个二进制符 上海交通大学硕士学位论文 号串。这种编码所形成的排列形式x 是个体的基因型，与它对应的x 值是个体 的表现型。通常个体的表现型和其基因型是一一对应的，但有时也允许基因型和 表现型是多对一的关系。染色体z 也成为个体x ，对于每一个个体，要按照 一定的规则确定出适应度。个体的适应度与其对应的个体表现型x 的目标函数 值相关联，x 越接近目标函数的最优点，其适应度越大；反之，其适应度越小。 遗传算法中，决策变量x 组成了问题的解空间。对问题最优解的搜索是通过 对染色体x 的搜索过程来进行的，从而由所有的染色体x 就组成了问题的搜索 空间。 遗传算法的常用形式是g o l d b e r g 提出的。它是一种基于生物自然选择与遗传 机理的随机搜索算法。和传统搜索算法不同，遗传算法从一组随机产生的初始解， 称为“种群”( p o p u l a t i o n ) ，开始搜索过程。种群中的每个个体是问题的一个解， 称为“染色体”( g e n o m e ) 。染色体是一串符号，比如一个二进制字符串，而每 个字符串称为“基因”( g e n e ) 。这些染色体在后续迭代中不断进化，称为遗传。 在每一代中用“适应度”( f i t n e s s ) 来评价染色体的好坏。生成的下一代染色体“子 代”。子代是由父代通过交叉( c r o s s o v e r ) 和变异( m u t a t e ) 运算形成的。新一 代形成中，根据适应度的大小选择部分后代，淘汰部分后代，从而保持种群大小 是常数。适应度高的染色体被选中的概率较高。这样，经过若干代之后，算法收 敛于最好的染色体，它很可能就是问题的最优解或次优解。 遗传算法的运算过程如图4 5 所示。 图4 5 简单遗传算法基本流程图 现简要介绍一下遗传算法的操作过程： 1 ) 编码 编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的个关键 步骤，它会影响到交叉算子、变异算子等遗传算子的运算方法，在很大程度上， 编码决定了如何进行种群的遗传进化运算以及遗传进化运算的效率。 常见的编码方式有：二进制编码方式，格雷码编码方式，浮点数编码方式以 及符号编码方式。 著名的“背包问题”是采用了二迸制编码方式，由“1 ”表示装入背包，“0 ” 表示没有装进背包，它要解决的问题是：在背包装载重量的允许范围内，选择何 种物品才能使其总价值最高。 f r e e m a n 于1 9 9 4 年给出的“配词问题”则采用了a s c i i 整数码来编码，英 文小写字母的a s c i i 码的范围为 9 7 ，1 2 2 】。它证明了这样个问题：如果随机 产生“t ob eo rn o tt ob e ”这个1 3 个字母的短语，其正确的概率为：( 1 2 6 ) 1 3 = 4 0 3 0 3 0 8 1 0 1 9 ，也就是说一千亿亿次中约有4 次正确的机会；但如果采用遗 传算法，运行2 3 代就得到了正确的结果。 在实际的电力系统中，由于母线编号是不重复的，因此可以直接使用母线编 号编码，这