基于对象图的事例表示方法及其相似度计算张沛超，王文君，郁惟镛（上海交通大学电气工程系，上海200030）
该文结合电力系统的特点，提出了一种通用的、结构化的事例表示法：对象图表示法。该表示法综合了面向对象技术和图论技术，在表达能力上具有通用性。该文首先给出了对象图的定义，在此基础上给出了相应的相似度计算方法。为解决相似度计算中的组合爆炸问题，引入了模拟退火遗传算法。然后设计了1000组算例以验证算法的有效性。最后，以一个调度运行管理专家系统为例，说明该文提出的事例表示方法具有直观、全面、通用的优点。
关键词：基于事例推理；事例表示；图论；遗传算法
1引言
基于事例推理（Case-basedReasoning，简称CBR）是基于过去求解类似问题的经验获得当前问题求解结果的一种推理模式[1]。CBR是近十几年来AI领域中发展起来的区别于基于规则推理的一种新型推理模式。由于它具有知识的原子化、浅层化以及易于实现自学习等优点，近年来在电力系统调度运行管理[2]、故障诊断[3]与恢复[4]、智能设计[5]、负荷预测[6]等领域都得到了应用。
事例表示方法是CBR技术的研究重点之一。事例表示方法可分为两大类：结构化表示和非结构化表示。所谓事例的结构化表示法，是指该表示法不但可以表示事物和概念，而且可以方便、直观地表示事物和概念之间的联系（如关联、包含、继承、依赖等）。上述系统都采用非结构化的事例表示法，如属性-值表示法（attribute-valuepair，简称AVP）、框架表示法等。
由于电力系统自身的特点，在诸如调度命令、操作票、故障恢复等专家系统中，要求事例能完整描述电网拓扑结构，以及保护、开关、录波通道等和一次设备的关联关系。使用非结构化事例表示法虽然也可以通过设置专门属性来间接地表达结构信息，但往往非常繁琐且不直观。
本文提出了一种面向对象的、结构化的事例表示方法：对象图（object-graph）表示法。该表示方法将面向对象技术和图论技术结合起来，既可以描述电网物理拓扑结构，也可以描述语义网络等抽象结构，因而具有很好的通用性。
2结构化事例表示已有的研究工作
文[7]、[8]提出了面向对象的事例表示法及相应的相似度算法，事例由对象构成，对象拥有属性集。但文中主要考虑了对象之间的继承关系。而对于更为广泛存在的关联、聚集等关系未提出通用的实现方案。
现实世界的大量问题都可以抽象为图结构，因而基于图的事例表示法近年来得到了广泛地重视[9~11]。采用图表示法后，事例的相似度计算问题可转换为子图的同构判定问题（sub-graphisomor-phismdetectionproblem）。文[9]定义了一组基本操作（节点和边的增加/删除/修改等操作），以此进行同构判定。文[10]利用求取图的最大团（maximumclique）方法。比较而言，文[11]则在定义图的映射的基础上，简明直接地给出了图相似度的代数算式。但上述算法都侧重于图形拓扑的比较，而未将节点和边的属性加以展开。
子图的同构判定问题是典型的NP－完全问题。在已有文献中，多采用遗传算法、Tabu搜索等算法加以解决。
本文在上述研究的基础上，结合电力系统实际特点，提出了基于对象图的事例表示法，同时给出其相似度算法及实用计算方法。
3对象图定义
定义1：对象图是一个二元组G={N,E}。
式中N为节点n的有限集；E为边e的有限集；节点n及边e都用对象表示。
节点n是一个二元组{VN,α}。
式中VN是节点对象属性的有限集；α是节点对象的相似度函数；边e是一个二元组{VE,β}。其中：VE是边对象属性的有限集；β是边对象的相似度函数。
NN(G)和NE(G)分别是图G的节点数和边数。W(n)是节点n的权；W(e)是边e的权。
G(n)是图G的子图。该子图由节点n以及与n相连的所有边构成。从图论的角度看，G(n)不能称为图。因为G(n)中未包括各边的非n侧节点。本定义纯粹是为了方便后续论述。
对象的属性采用属性－值表示法。
图1以电力系统主接线为例，说明对象图的一种应用。利用统一建模语言（UML）[13]可以简洁清晰地描述对象图。由图2可见，事例被分为对象层和事例层。在对象层，利用封装和多态机制，对象具有开放的属性集，其相似度计算函数（a、b）可被重新定义；在事例层，利用聚集和关联，可完整地表达对象之间的各种关系。4对象图的相似度计算
4.1基本计算方法
本文将对象图的相似度计算分为两步，首先计算各对象之间的相似度，然后计算整个对象图之间的相似度。前者采用最近邻算法（Nearest-Neighbor），后者基于文[11]的算法，并为适应对象图对其做了修改。
下面给出节点和边的相似度。
定义3：设M为对象图Gt={Nt,Et}到Gs={Ns,Es}的映射。
（2）DSM(et,es)为映射M下边et和es之间的相似度。其值为
本文采用最近邻法计算对象相似度。经典的最近邻模型有欧式距离和Hamming距离[12]等。本文采用如下模型（以节点相似度函数为例）：
式中Vimax、Vimin分别为第i个属性最大值和最小值。定义4：设M为对象图Gt到Gs的映射。DSM(Gt,Gs)为映射M下Gt和Gs之间的相似度。其值为
[1][2][3]下一页
