第13卷第3期 智能系统学报 Vol.13 No.3 2018年6月 CAAI Transactions on Intelligent Systems Jun.2018 D0:10.11992/tis.201710012 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20180409.0915.002.html 基于NSGA-Ⅱ的扩展置信规则库激活规则多 目标优化方法 林燕清，傅仰耿 (福州大学数学与计算机科学学院，福建福州350116) 摘要：针对扩展置信规则库(extended belief rule base,EBRB)系统在不一致的激活规则过多时推理准确性不高的问 题，引入带精英策略的快速非支配排序遗传算法(NSGA-I),提出一种基于NSGA-Ⅱ的激活规则多目标优化方法。 该方法首先将激活权重大于零的规则（即激活规则）进行二进制编码，把最终参与合成推理的激活规则集合的不一致 性以及激活权重和作为多目标优化问题的目标函数，通过带精英策略的快速非支配排序遗传算法求解不一致性更小 的激活规则集合，从而降低不一致激活规则对于EBRB系统推理准确性的影响。为了验证本文方法的有效性和可行 性，引入非线性函数和输油管道检漏实例进行测试。实验结果表明，基于NSGA-Ⅱ的扩展置信规则库激活规则多目 标优化方法能够有效提高EBRB系统的推理能力。 关键词：扩展置信规则库；不一致性：激活规则；多目标优化；NSGA-II算法 中图分类号：TP18文献标志码：A文章编号：1673-4785(2018)03-0422-09 中文引用格式：林燕清，仰耿.基于NSGA-Ⅱ的扩展置信规则库激活规则多目标优化方法.智能系统学报，2018,13(3：422-430. 英文引用格式：LIN Yanqing,FU Yanggeng.NSGA-l-based EBRB rules activation multi--objective optimization.CAAI transac- tions on intelligent systems,2018,13(3):422-430. NSGA-II-based EBRB rules activation multi-objective optimization LIN Yanqing,FU Yanggeng (College of Mathematics and Computer Science,Fuzhou University,Fuzhou 350116,China) Abstract:To address the low reasoning accuracy of extended belief rule-base(EBRB)systems with too many inconsist- ent activated rules,this paper introduces a fast elitist non-dominated sorting genetic algorithm(NSGA-II)and proposes a rule activation multi-objective optimization approach based on the NSGA-II algorithm.In this approach,binary coding is carried out for the activated rules whose activation weights are greater than zero.The inconsistent set of activated rules following synthetic reasoning and the sum of activation weights are taken as the objective function of the multi-ob- jective optimization problem.Using the fast elitist non-dominated sorting genetic algorithm,the problem of a set of ac- tivation rules with a small inconsistency is solved,reducing the effect of the inconsistent activated rules on the reason- ing accuracy of EBER systems.To validate the efficiency and feasibility of the proposed method,this paper introduces a nonlinear function and the proposed method was tested against the leak detection of an oil pipeline.The experimental results show that the rule activation multi-objective optimization approach based on NSGA-II can effectively improve the reasoning performance of EBRB systems. Keywords:extended belief rule base(EBRB);inconsistency;activation rules;multi-objective optimization;NSGA-II algorithm 收稿日期：2017-10-17.网络出版日期：2018-04-09 专家系统作为一种人工智能系统，已经被广 基金项目：国家自然科学基金项目(71501047,61773123)；福建省 泛应用于图像处理、医疗检测、地质勘探、石油化工 自然科学基金项目(2015J01248). 通信作者：傅仰耿E-mail:ygiu@qq.com 等领域。利用专家系统进行决策时，需要先将有用
DOI: 10.11992/tis.201710012 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180409.0915.002.html 基于 NSGA-II 的扩展置信规则库激活规则多 目标优化方法 林燕清，傅仰耿 （福州大学 数学与计算机科学学院，福建 福州 350116） 摘 要：针对扩展置信规则库 (extended belief rule base, EBRB) 系统在不一致的激活规则过多时推理准确性不高的问 题，引入带精英策略的快速非支配排序遗传算法 (NSGA-II)，提出一种基于 NSGA-II 的激活规则多目标优化方法。 该方法首先将激活权重大于零的规则 (即激活规则) 进行二进制编码，把最终参与合成推理的激活规则集合的不一致 性以及激活权重和作为多目标优化问题的目标函数，通过带精英策略的快速非支配排序遗传算法求解不一致性更小 的激活规则集合，从而降低不一致激活规则对于 EBRB 系统推理准确性的影响。为了验证本文方法的有效性和可行 性，引入非线性函数和输油管道检漏实例进行测试。实验结果表明，基于 NSGA-II 的扩展置信规则库激活规则多目 标优化方法能够有效提高 EBRB 系统的推理能力。 关键词：扩展置信规则库；不一致性；激活规则；多目标优化；NSGA-II 算法 中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2018)03−0422−09 中文引用格式：林燕清, 傅仰耿. 基于 NSGA-II 的扩展置信规则库激活规则多目标优化方法[J]. 智能系统学报, 2018, 13(3): 422–430. 英文引用格式：LIN Yanqing, FU Yanggeng. NSGA-II-based EBRB rules activation multi-objective optimization[J]. CAAI transactions on intelligent systems, 2018, 13(3): 422–430. NSGA-II-based EBRB rules activation multi-objective optimization LIN Yanqing，FU Yanggeng (College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116, China) Abstract: To address the low reasoning accuracy of extended belief rule-base (EBRB) systems with too many inconsistent activated rules, this paper introduces a fast elitist non-dominated sorting genetic algorithm (NSGA-II) and proposes a rule activation multi-objective optimization approach based on the NSGA-II algorithm. In this approach, binary coding is carried out for the activated rules whose activation weights are greater than zero. The inconsistent set of activated rules following synthetic reasoning and the sum of activation weights are taken as the objective function of the multi-objective optimization problem. Using the fast elitist non-dominated sorting genetic algorithm, the problem of a set of activation rules with a small inconsistency is solved, reducing the effect of the inconsistent activated rules on the reasoning accuracy of EBER systems. To validate the efficiency and feasibility of the proposed method, this paper introduces a nonlinear function and the proposed method was tested against the leak detection of an oil pipeline. The experimental results show that the rule activation multi-objective optimization approach based on NSGA-II can effectively improve the reasoning performance of EBRB systems. Keywords: extended belief rule base (EBRB); inconsistency; activation rules; multi-objective optimization; NSGA-II algorithm 专家系统[1]作为一种人工智能系统，已经被广 泛应用于图像处理、医疗检测、地质勘探、石油化工 等领域。利用专家系统进行决策时，需要先将有用 收稿日期：2017−10−17. 网络出版日期：2018−04−09. 基金项目：国家自然科学基金项目 (71501047，61773123)；福建省 自然科学基金项目 (2015J01248). 通信作者：傅仰耿. E-mail：ygfu@qq.com. 第 13 卷第 3 期 智 能 系 统 学 报 Vol.13 No.3 2018 年 6 月 CAAI Transactions on Intelligent Systems Jun. 2018
第3期 林燕清，等：基于NSGA-Ⅱ的扩展置信规则库激活规则多目标优化方法 ·423· 的信息表示成知识，知识的表示形式有很多种，其 者们提出了各自的降维方法：Zhou等提出“统计 中应用最广泛的是产生式规则，即F-THEN规则。 效用的概念，根据每条规则的统计效用值来确定是 置信规则(belief rule)是在传统F-THEN规则的结 否删减该规则，如果某条规则的统计效用值越小， 果部分加入置信分布转化而来的，由一组置信规则 说明该规则对整体系统的贡献越小，就可以将其删 组成的集合称为置信规则库(belief rule base,BRB)。 除：Chang等u提出利用灰靶理论、多维尺度变换 置信规则对应的是系统的输入信息，而实际工程中 主成分分析来选择关键前提属性，从而减少前提属 包含的信息既可能是定性知识也可能是定量数据， 性的数量；王应明等引入粗糙集理论，提出客观的 同时，信息中往往存在着含糊或模糊不确定性、不 规则约简方法，该方法不需要借助BRB以外的任何 精确性以及不完整性。为了能够有效利用带有这些 先验知识。这些BRB结构优化方法虽然可以在一 不确定性的信息，Yang等l于2006年在D-S证据 定程度上避免组合爆炸问题，但是会降低BRB的推 理论B.、决策理论1、模糊理论6和传统的IF. 理能力。为了从根本上解决BRB参数取值以及组 THEN规则库基础上提出了基于证据理论的置信规 合爆炸问题，Liu等2对原有的置信规则进行扩展， 则库推理方法(belief rule-base inference methodo- 在规则的前件部分也加入置信分布，提高其对含 logy using the evidential reasoning approach, 糊、不完整和不确定信息的表示能力，改进后的规 RIMER)。RIMER方法作为BRB系统的核心，能够 则库被称为扩展置信规则库(extended belief rule 对具有线性或非线性关系的输入和输出进行建模， base,EBRB)。同时，Liu等2还提出了一种简单且 具有处理各种不确定性的能力。目前，BRB系统已 有效直接利用训练数据生成初始扩展置信规则的规 被广泛应用到输油管道泄漏、石墨成分检测、消 则生成机制，数据驱动型的规则生成机制可以详细 费者偏好预测0、军事能力评估山和出租车乘车概 表示出数据中包含的各种信息，不需要进行反复迭 率预测等领域。 代的参数学习过程也不会造成组合爆炸问题。但正 利用BRB系统对实际问题进行建模时，要先确 因为扩展置信规则是根据训练数据集得到的，数据 定其内部参数的取值，各个参数的不同取值会对 集的质量对EBRB系统的推理能力影响要更大，相 BRB系统的推理能力造成一定的影响，传统的参数 互矛盾、不一致的数据容易降低EBRB的推理准确 取值确定方法是专家根据经验给定其值，但当参数 性。在EBRB中，数据的不一致是指两条或多条规 个数较多或系统较复杂时，专家很难确定参数取 则的前提属性取值大致相同，但评价结果却完全不 值。鉴于此，Yang等o最先提出一种通用的BRB 同或与专家知识相冲突。 参数学习模型，该模型以满足各个参数约束条件为 针对EBRB系统中的数据不一致性的问题，AI- 基础，通过最小化由置信规则库推理得出的模拟输 berto等22提出动态规则激活方法，该方法通过调整 出值和真实数据的输出值二者的差值来训练BRB 改进后的相似性度量公式中的参数来选择不一致性 参数。在Yang的基础上，Chen等提出了包括前 最小的激活规则集合，不过，该方法中用于衡量激 提属性参考值在内的全局参数学习方法。不过以上 活规则集合不一致性的公式只考虑了规则数量对其 两种参数学习方法均是建立在MATLAB工具自带 的影响，没有考虑规则激活权重对其的影响。要减 的FMINCON函数的基础上，参数学习效率不高。 小激活规则集合之间的不一致性，最简单的方法就 鉴于此常瑞等、吴伟昆等提出结合梯度下降 是舍弃部分不一致性较高的激活规则，这部分激活 法的BRB参数学习方法，这种方法虽然优于 规则不参与最终的合成推理过程，但这部分激活规 FMINCON函数，但其涉及的公式推导过于复杂，只 则可能带有重要的信息，而且很难确定这部分激活 能训练少量的参数，不适合用来学习大量的参数， 规则的具体数量。为了减小激活规则集合的不一致 且参数学习的收敛速度过慢。为了提高BRB系统 性同时保留激活规则集合中的大部分重要信息，本 参数学习的收敛速度和精度，苏群等6、王韩杰等切 文提出了基于NSGA-Ⅱ的扩展置信规则库激活规 相继提出基于群智能算法的参数学习方法。以上参 则多目标优化方法，将激活规则的不一致性与激活 数学习方法均能够优化BRB参数取值，从而提高 权重和分别作为目标函数，通过求解多目标优化问 BRB的推理能力，但是，这些参数学习方法都是建 题获得相对较优的激活规则集合并用于最终的合成 立在Yang等1o提出的参数学习模型基础上的，无 推理。本文首先介绍扩展置信规则库和多目标优化 法避免重复的搜索过程，需要不断地进行迭代。此 问题的基础知识，然后介绍如何利用NSGA-Ⅱ求解 外，因为BRB系统构建时需要覆盖所有的前提属性 Pareto的最优解，最后通过非线性函数问题和输油 的参考值，当前提属性和前提属性参考值过多时， 管道检漏实例对所提方法进行实验验证，并分析说 会出现“组合爆炸”问题。为了解决该问题，专家学 明所提方法的有效性和可行性
的信息表示成知识，知识的表示形式有很多种，其 中应用最广泛的是产生式规则，即 IF-THEN 规则。 置信规则 (belief rule) 是在传统 IF-THEN 规则的结 果部分加入置信分布转化而来的，由一组置信规则 组成的集合称为置信规则库 (belief rule base, BRB)。 置信规则对应的是系统的输入信息，而实际工程中 包含的信息既可能是定性知识也可能是定量数据， 同时，信息中往往存在着含糊或模糊不确定性、不 精确性以及不完整性。为了能够有效利用带有这些 不确定性的信息，Yang 等 [2]于 2006 年在 D-S 证据 理论[ 3 - 4 ] 、决策理论[ 5 ] 、模糊理论[ 6 ]和传统的 IFTHEN 规则库基础上提出了基于证据理论的置信规 则库推理方法 (belief rule-base inference methodology using the evidential reasoning approach, RIMER)。RIMER 方法作为 BRB 系统的核心，能够 对具有线性或非线性关系的输入和输出进行建模， 具有处理各种不确定性的能力。目前，BRB 系统已 被广泛应用到输油管道泄漏[7-8] 、石墨成分检测[9] 、消 费者偏好预测[10] 、军事能力评估[11]和出租车乘车概 率预测[12]等领域。 利用 BRB 系统对实际问题进行建模时，要先确 定其内部参数的取值，各个参数的不同取值会对 BRB 系统的推理能力造成一定的影响，传统的参数 取值确定方法是专家根据经验给定其值，但当参数 个数较多或系统较复杂时，专家很难确定参数取 值。鉴于此，Yang 等 [10]最先提出一种通用的 BRB 参数学习模型，该模型以满足各个参数约束条件为 基础，通过最小化由置信规则库推理得出的模拟输 出值和真实数据的输出值二者的差值来训练 BRB 参数。在 Yang 的基础上，Chen 等 [13]提出了包括前 提属性参考值在内的全局参数学习方法。不过以上 两种参数学习方法均是建立在 MATLAB 工具自带 的 FMINCON 函数的基础上，参数学习效率不高。 鉴于此，常瑞等[14] 、吴伟昆等[15]提出结合梯度下降 法的 B RB 参数学习方法，这种方法虽然优于 FMINCON 函数，但其涉及的公式推导过于复杂，只 能训练少量的参数，不适合用来学习大量的参数， 且参数学习的收敛速度过慢。为了提高 BRB 系统 参数学习的收敛速度和精度，苏群等[16] 、王韩杰等[17] 相继提出基于群智能算法的参数学习方法。以上参 数学习方法均能够优化 BRB 参数取值，从而提高 BRB 的推理能力，但是，这些参数学习方法都是建 立在 Yang 等 [10]提出的参数学习模型基础上的，无 法避免重复的搜索过程，需要不断地进行迭代。此 外，因为 BRB 系统构建时需要覆盖所有的前提属性 的参考值，当前提属性和前提属性参考值过多时， 会出现“组合爆炸”问题。为了解决该问题，专家学 者们提出了各自的降维方法：Zhou 等 [18]提出“统计 效用”的概念，根据每条规则的统计效用值来确定是 否删减该规则，如果某条规则的统计效用值越小， 说明该规则对整体系统的贡献越小，就可以将其删 除；Chang 等 [19]提出利用灰靶理论、多维尺度变换、 主成分分析来选择关键前提属性，从而减少前提属 性的数量；王应明等[20]引入粗糙集理论，提出客观的 规则约简方法，该方法不需要借助 BRB 以外的任何 先验知识。这些 BRB 结构优化方法虽然可以在一 定程度上避免组合爆炸问题，但是会降低 BRB 的推 理能力。为了从根本上解决 BRB 参数取值以及组 合爆炸问题，Liu 等 [21]对原有的置信规则进行扩展， 在规则的前件部分也加入置信分布，提高其对含 糊、不完整和不确定信息的表示能力，改进后的规 则库被称为扩展置信规则库 (extended belief rule base, EBRB)。同时，Liu 等 [21]还提出了一种简单且 有效直接利用训练数据生成初始扩展置信规则的规 则生成机制，数据驱动型的规则生成机制可以详细 表示出数据中包含的各种信息，不需要进行反复迭 代的参数学习过程也不会造成组合爆炸问题。但正 因为扩展置信规则是根据训练数据集得到的，数据 集的质量对 EBRB 系统的推理能力影响要更大，相 互矛盾、不一致的数据容易降低 EBRB 的推理准确 性。在 EBRB 中，数据的不一致是指两条或多条规 则的前提属性取值大致相同，但评价结果却完全不 同或与专家知识相冲突。 针对 EBRB 系统中的数据不一致性的问题，Alberto 等 [22]提出动态规则激活方法，该方法通过调整 改进后的相似性度量公式中的参数来选择不一致性 最小的激活规则集合，不过，该方法中用于衡量激 活规则集合不一致性的公式只考虑了规则数量对其 的影响，没有考虑规则激活权重对其的影响。要减 小激活规则集合之间的不一致性，最简单的方法就 是舍弃部分不一致性较高的激活规则，这部分激活 规则不参与最终的合成推理过程，但这部分激活规 则可能带有重要的信息，而且很难确定这部分激活 规则的具体数量。为了减小激活规则集合的不一致 性同时保留激活规则集合中的大部分重要信息，本 文提出了基于 NSGA-II 的扩展置信规则库激活规 则多目标优化方法，将激活规则的不一致性与激活 权重和分别作为目标函数，通过求解多目标优化问 题获得相对较优的激活规则集合并用于最终的合成 推理。本文首先介绍扩展置信规则库和多目标优化 问题的基础知识，然后介绍如何利用 NSGA-II 求解 Pareto 的最优解，最后通过非线性函数问题和输油 管道检漏实例对所提方法进行实验验证，并分析说 明所提方法的有效性和可行性。 第 3 期 林燕清，等：基于 NSGA-II 的扩展置信规则库激活规则多目标优化方法 ·423·
·424· 智能系统学报 第13卷 1扩展置信规则库系统与问题提出 S=1-d (8) 第k条置信规则的激活权重可由式(9)得 1.1扩展置信规则生成 扩展置信规则库由一系列扩展置信规则(ex tended belief rule)组成，其中第k条扩展置信规则的 max(6) (9) 表示为 i=1,2..Te R:ifIA.a]thenB).D:B).(Dx.B) with a rule weight and attribute weight 式中：0≤w4≤1k=1,2,…,L),d=1,如果w=0, 式中：(A,a)表示扩展置信规则前件部分的置信分 则说明第k条规则未被激活。 布，可表示成{(4，j=1,2,…,Ji=1,2,…,T, 1.2.2激活规则的合成 A表示第个前提属性的第j个参考值，且第个前提 用证据推理方法(evidential reasoning,ER)2得 属性的参考值总数为，a表示第k条规则的第i个 到推理结果前，要先按式(10)~(13)计算评价结果 前提属性输入值相对该属性的第j个参考值A,的置 置信度的基本可信值： 信度，T表示第k条规则前提属性总数；6，表示第i个 mn.i WiB (10) 前提属性的属性权重；：表示第k条规则的规则权 重；U=1,2,…,N:k=1,2,…,L)表示第k条规则第 m=1-4户B4=m4+ma (11) 1=1 j个评价结果D,的置信度，每条置信规则的所有评价 结果置信度需满足立≤1，如果立=1则称第k条 (12) 规则是完整的，否则称第k条规则是不完整的。 mH=1-ω (13) 与BRB系统复杂烦琐的规则生成机制不同， 式中：n=1,2,…,N。在此基础上通过ER解析公式P网 Liu等2提出的规则生成机制简单且有效，可直接 计算评价结果的基本可信值，合成公式如式 将训练数据转化为扩展置信规则。假设 (14)~(19: U,(i=1,2,…,T)示第k个样本数据的第i个前提属 门m++m,小-门+m)》 14) 性，其输入值为，首先决策者或专家需要将第个前 提属性的参考值A,与数值量建立起对应关系： Yi;means Ai. (2) C. (15) 然后，将输入x转化成式(3)所示的期望形式： S(x)={(y,a,i=1,2,…,Tk,j=1,2,…,J}(3) Cy-kITin (16 式中a,的计算公式为 a=1 Y≤&≤Yt1,j=1,2…,J-1(4) Yij+1-Yij a1=1-Y≤≤Y+1,j=1,2,…,J-1(⑤) (17) as=0,5≠j+1,s=1,2,…,J (6) Cn 通过式(4)~(6)可得到a的具体取值从而生成 Bn= 1-CH n=1,2,…,N (18) 规则的前件部分，相应输出的评价结果置信分布可 CH BH=1-CH (19) 采用同样的方法产生。 1.2扩展置信规则库推理方法 根据式(14)~(19)可得到式(20)所示的具有置 1.2.1激活权重的计算 信分布形式的BRB推理输出： 假设第i个前提属性取值x已经被表示成式 fx)={(Dn,fn),n=1,2,…,N (20) (3)所示的形式，则x相对第k条规则的第个前提属 基于上述ER解析算法，Wang等进一步推导 性的个体匹配度S可通过两个置信分布的距离值来 出了组合所有的置信规则的计算公式，即 衡量，因为EBRB前件部分的置信分布实质上是概 率分布，故S可借助式(7所示的欧氏距离来计算： Bi= -a吃) (7) (21) 则S计算方法为
1 扩展置信规则库系统与问题提出 1.1 扩展置信规则生成 k 扩展置信规则库由一系列扩展置信规则 (extended belief rule) 组成，其中第 条扩展置信规则的 表示为 Rk : if{ A,αk } then{( D1 , β1 k ) , ( D2 , β2 k ) ,··· , ( DN, βN k )} with a rule weight θk and attribute weight δi (1) (A,αk ) {(Ai, j ,αk i, j ), j = 1,2,··· , Ji}|i = 1,2,··· ,Tk} Ai, j i j i Ji α k i, j k i j Ai, j Tk k δi i θk k β k j (j = 1,2,··· ,N; k = 1,2,··· ,L) k j Dj ∑N j=1 β k j ⩽ 1 ∑N j=1 β k j = 1 k k 式中： 表示扩展置信规则前件部分的置信分 布，可表示成 ， 表示第 个前提属性的第 个参考值，且第 个前提 属性的参考值总数为 ， 表示第 条规则的第 个 前提属性输入值相对该属性的第 个参考值 的置 信度， 表示第 条规则前提属性总数； 表示第 个 前提属性的属性权重； 表示第 条规则的规则权 重； 表示第 条规则第 个评价结果 的置信度，每条置信规则的所有评价 结果置信度需满足 ，如果 则称第 条 规则是完整的，否则称第 条规则是不完整的。 Ui(i = 1,2,···,Tk) k i xi i Ai, j 与 BRB 系统复杂烦琐的规则生成机制不同， Liu 等 [21]提出的规则生成机制简单且有效，可直接 将训练数据转化为扩展置信规则。假设 示第 个样本数据的第 个前提属 性，其输入值为 ，首先决策者或专家需要将第 个前 提属性的参考值 与数值量建立起对应关系： γi, j means Ai, j (2) 然后，将输入xi转化成式 (3) 所示的期望形式： S (xi) = {(γi, j ,αi, j),i = 1,2,··· ,Tk , j = 1,2,··· , Ji} (3) 式中αi, j 的计算公式为 αi, j = γi, j+1 − xi γi, j+1 −γi, j , γi, j ⩽ xi ⩽ γi, j+1, j = 1,2,··· , Ji −1 (4) αi, j+1 = 1−αi, j , γi, j ⩽ xi ⩽ γi, j+1, j = 1,2,··· , Ji −1 (5) αi,s = 0,s , j, j+1,s = 1,2,··· , Ji (6) 通过式 (4)～(6) 可得到αi, j 的具体取值从而生成 规则的前件部分，相应输出的评价结果置信分布可 采用同样的方法产生。 1.2 扩展置信规则库推理方法 1.2.1 激活权重的计算 i xi xi k i S k i S k i 假设第 个前提属性取值 已经被表示成式 (3) 所示的形式，则 相对第 条规则的第 个前提属 性的个体匹配度 可通过两个置信分布的距离值来 衡量，因为 EBRB 前件部分的置信分布实质上是概 率分布，故 可借助式 (7) 所示的欧氏距离来计算： d k i = vut∑Ji j=1 (αi, j −α k i, j ) 2 (7) S k 则 i 计算方法为 S k i = 1−d k i (8) 第 k 条置信规则的激活权重可由式 (9) 得 ωk = θk ∏Tk i=1 (S k i ) δi ∑L l=1 θl ∏Tk i=1 (S l i ) δi δi = δi max{δi} i=1,2,···,Tk (9) 0 ⩽ ωk ⩽ 1(k = 1,2,··· ,L), ∑L i=1 ωi = 1 ωk = 0 k 式中： ，如果 ， 则说明第 条规则未被激活。 1.2.2 激活规则的合成 用证据推理方法 (evidential reasoning, ER)[23]得 到推理结果前，要先按式 (10)～(13) 计算评价结果 置信度的基本可信值： mn,i = ωiβn,i (10) mH,i = 1−ωi ∑N n=1 βn,i = mH,i +m˜ H,i (11) m˜ H,i = ωi(1− ∑N n=1 βn,i) (12) mH,i = 1−ωi (13) 式中：n = 1,2,··· ,N 。在此基础上通过 ER 解析公式[24] 计算评价结果的基本可信值，合成公式如 式 (14)～(19)： Cn = k ∏L j=1 (mn, j +mH, j +m˜ H, j)− ∏L j=1 (mH, j +m˜ H, j) (14) C˜ H = k ∏L j=1 (mH, j +m˜ H, j)− ∏L j=1 mH, j (15) CH = k ∏L j=1 mH, j (16) k −1 = ∑N n=1 ∏L j=1 (mn, j +mH, j +m˜ H, j)−(N −1)∏L j=1 (mH, j +m˜ H, j) (17) βn = Cn 1−CH , n = 1,2,··· ,N (18) βH = C˜ H 1−CH (19) 根据式 (14)～(19) 可得到式 (20) 所示的具有置 信分布形式的 BRB 推理输出： f(x) = {(Dn, βn),n = 1,2,··· ,N} (20) 基于上述 ER 解析算法，Wang 等 [25]进一步推导 出了组合所有的置信规则的计算公式，即 βj = µ× ∏L k=1 (ωkβj,k +1−ωk ∑N i=1 βi,k)− ∏L k=1 (1−ωk ∑N i=1 βi,k) 1−µ× ∏L k=1 (1−ωk) (21) ·424· 智 能 系 统 学 报 第 13 卷
第3期 林燕清，等：基于NSGA-Ⅱ的扩展置信规则库激活规则多目标优化方法 ·425· (wB+1-wk∑B) 含多个，且它们之间经常是相互矛盾、冲突的。也 =1k=1 1 22) 就是说，对于这一类问题，几乎找不到一个可以同 (N-1)Π( -k∑B) 时满足所有优化目标的最优解。一个由m个决策 =1 参数和n个目标变量组成的多目标优化问题的数学 1.3 问题提出 表达式2为 Liu等2提出的EBRB规则生成机制虽然简单 Min/Max y=F(x)=(fi(x),f(x),.f(x)) 且有效，但也使得EBRB系统的推理性能容易受训 sub to:g(X)≤0，i=1,2,…,k 练数据的质量影响，由于训练数据生成的扩展置信 h.(X)=0,i=1,2.…,k (23) 规则库可能存在不一致的规则即规则相互矛盾的问 where:x=(m,x2,…,xm)∈XcR 题，这些不一致的规则会降低EBRB系统的推理准 y=y1,2,…,ym)∈YCR 确性，尤其当这些不一致规则同时成为激活规则。 式中：x=(x,2,…,xm)表示m维的决策参数；y=y, 在EBRB中，这些激活权重大于零的规则被称为激 2,…y)表示n维的目标变量；F()=(f(x,f(x,… 活规则，激活规则是用来进行ER合成推理的，即 f(x)表示所有的目标函数；g(X)≤0表示所有的不 EBRB系统的推理结果就是依靠这些激活规则侧得到 等式约束条件；h.(X)=0表示所有的等式约束条件。 的。由此可见，激活规则对于最终推理结果的重要 定义1（可行解）如果存在一个决策参数x它 性，而相互矛盾的、不一致的激活规则会对最终的 满足所有不等式约束条件和等式约束条件，则称x为 BRB系统推理结果造成一定的干扰，进而影响BRB 可行解。 系统的推理能力。为此，Alberto等2l对式(8)进行 定义2（可行解集合）可行解集合是指所有可 改进，提出动态规则激活方法，通过不断重复的搜 行解组成的集合，记作x(x二X)。 索过程以找到不一致性最小的激活规则集合，该方 定义3(Pareto占优)假设xA,xs(xA,seX)是 法能够有效减小激活规则之间的不一致性，但其参 多目标优化问题的两个可行解，若xa相对xs是Pareto 数取值需要不断迭代，而且参数增加和减小幅度也 占优（或称xA支配xB,记作xA>xB),则xAxB需要同时 较难确定。此外，实际工程应用中，训练数据总数 满足以下两个条件： 都比较多，当采用Liu等2提出的规则激活方法时， 1)i=1,2,…,n,fxs)≥fxA) 多数规则的激活权重都会大于零，激活规则数量的 2)3j=1,2,…,n,f(xs)>fxa)o 增多，意味着规则间的不一致性增大。要减小激活 定义4(Pareto最优解)若多目标优化问题的 规则之间的不一致性，最简单的方法就是尽可能多 一个可行解xc(xc∈X)是Pareto最优解，则xc需要满 地减少激活规则的数量，不一致性较高的这部分激 足条件3xeX:x>xco 活规则不参与最终的合成推理过程，但这种方法不 2.2带精英策略的快速非支配排序遗传算法 一定有效，因为激活规则数量一旦减少，原有激活 2000年Kalyanmoy Deb等2首次提出了带精 规则集合中包含的信息就会减少，如果这些不参与 最终合成推理过程的激活规则包含了原有激活规则 英策略的快速非支配排序遗传算法（简称NSGA- 中绝大部分重要信息，则EBRB的推理准确性也会 Ⅲ)该方法是众多求解多目标优化问题方法中应用 受到一定程度的影响。在EBRB中，激活规则的激 最为广泛的一种。NSGA-IⅡ算法是非支配排序遗传 活权重代表激活规则的重要性，激活权重越大，说 (non-dominated sorting genetic algorithm, 明该激活规则越重要，其中包含的重要信息越多。 NSGA)的改进，运行速度更快，复杂度更低，且其求 鉴于此，为了减小激活规则之间的不一致性，同时 解的Pareto最优解集收敛性更好。算法首先随机产 保留住原有激活规则集合的绝大部分重要信息，本 生一定规模数量的初始种群，然后利用非支配排序 文提出激活规则多目标优化方法，把激活规则之间 方法对种群中所有个体进行分层，接着执行遗传算 的不一致性以及激活规则的激活权重总和作为优化 法的选择、交叉和变异3个操作产生第一代子群。 目标，通过NSGA-IⅡ来求解较优的激活规则集合用 从第二代子群开始，先将父代种群和子代种群中所 于最终的合成推理。 有个体合并在一起，然后利用快速非支配排序方法 对其进行分层，并计算每个非支配分层中所有个体 2 基于NSGA-II的EBRB激活规则 的拥挤距离，在此基础上从中选出较优的个体组成 多目标优化方法 新的父代种群，接着执行遗传算法的选择、交叉和 2.1 多目标优化问题 变异3个操作产生下一代子群，直至达到程序结束 在实际应用问题中，所求解的优化目标通常包 条件时终止，算法的具体流程如图1所示
µ = [ ∑N j=1 ∏L k=1 (ωkβj,k +1−ωk ∑N i=1 βi,k)− (N −1)∏L k=1 (1−ωk ∑N i=1 βi,k) ]−1 (22) 1.3 问题提出 Liu 等 [21]提出的 EBRB 规则生成机制虽然简单 且有效，但也使得 EBRB 系统的推理性能容易受训 练数据的质量影响，由于训练数据生成的扩展置信 规则库可能存在不一致的规则即规则相互矛盾的问 题，这些不一致的规则会降低 EBRB 系统的推理准 确性，尤其当这些不一致规则同时成为激活规则。 在 EBRB 中，这些激活权重大于零的规则被称为激 活规则，激活规则是用来进行 ER 合成推理的，即 EBRB 系统的推理结果就是依靠这些激活规则得到 的。由此可见，激活规则对于最终推理结果的重要 性，而相互矛盾的、不一致的激活规则会对最终的 BRB 系统推理结果造成一定的干扰，进而影响 BRB 系统的推理能力。为此，Alberto 等 [22]对式 (8) 进行 改进，提出动态规则激活方法，通过不断重复的搜 索过程以找到不一致性最小的激活规则集合，该方 法能够有效减小激活规则之间的不一致性，但其参 数取值需要不断迭代，而且参数增加和减小幅度也 较难确定。此外，实际工程应用中，训练数据总数 都比较多，当采用 Liu 等 [21]提出的规则激活方法时， 多数规则的激活权重都会大于零，激活规则数量的 增多，意味着规则间的不一致性增大。要减小激活 规则之间的不一致性，最简单的方法就是尽可能多 地减少激活规则的数量，不一致性较高的这部分激 活规则不参与最终的合成推理过程，但这种方法不 一定有效，因为激活规则数量一旦减少，原有激活 规则集合中包含的信息就会减少，如果这些不参与 最终合成推理过程的激活规则包含了原有激活规则 中绝大部分重要信息，则 EBRB的推理准确性也会 受到一定程度的影响。在 EBRB中，激活规则的激 活权重代表激活规则的重要性，激活权重越大，说 明该激活规则越重要，其中包含的重要信息越多。 鉴于此，为了减小激活规则之间的不一致性，同时 保留住原有激活规则集合的绝大部分重要信息，本 文提出激活规则多目标优化方法，把激活规则之间 的不一致性以及激活规则的激活权重总和作为优化 目标，通过 NSGA-II 来求解较优的激活规则集合用 于最终的合成推理。 2 基于 NSGA-II 的 EBRB 激活规则 多目标优化方法 2.1 多目标优化问题 在实际应用问题中，所求解的优化目标通常包 含多个，且它们之间经常是相互矛盾、冲突的。也 就是说，对于这一类问题，几乎找不到一个可以同 时满足所有优化目标的最优解。一个由 m 个决策 参数和 n 个目标变量组成的多目标优化问题的数学 表达式[26]为 Min/Max y = F(x) = (f1(x), f2(x),··· , fn(x)) sub to: gi(X) ⩽ 0,i = 1,2,··· , kg hi(X) = 0,i = 1,2,··· , kh where: x = (x1, x2,··· , xm) ∈ X ⊆ R y = (y1 , y2 ,··· , ym) ∈ Y ⊆ R (23) x = (x1, x2,··· , xm) m y = (y1, y2,··· , yn) n F(x) = (f1(x), f2(x),··· , fn(x)) gi(X) ⩽ 0 hi(X) = 0 式中： 表示 维的决策参数； 表示 维的目标变量； 表示所有的目标函数； 表示所有的不 等式约束条件； 表示所有的等式约束条件。 x x 定义 1 (可行解) 如果存在一个决策参数 它 满足所有不等式约束条件和等式约束条件，则称 为 可行解。 xf(xf ⊆ X) 定义 2 (可行解集合) 可行解集合是指所有可 行解组成的集合，记作 。 xA, xB(xA, xB ∈ Xf) xA xB xA xB xA ≻ xB xA, xB 定义 3 (Pareto 占优) 假设 是 多目标优化问题的两个可行解，若 相对 是 Pareto 占优 (或称 支配 ，记作 )，则 需要同时 满足以下两个条件： ∀i = 1,2,··· ,n, fi(xB) ⩾ f 1) i(xA) ； ∃ j = 1,2,··· ,n, fj(xB) > f 2) i(xA)。 xC(xC ∈ Xf) xC ¬∃x ∈ Xf : x ≻ xC 定义 4 (Pareto 最优解) 若多目标优化问题的 一个可行解 是 Pareto 最优解，则 需要满 足条件 。 2.2 带精英策略的快速非支配排序遗传算法 2000 年 Kalyanmoy Deb 等 [27]首次提出了带精 英策略的快速非支配排序遗传算法 (简称 NSGAII)，该方法是众多求解多目标优化问题方法中应用 最为广泛的一种。NSGA-II 算法是非支配排序遗传 算法 (non-dominated sorting genetic algorithm, NSGA) 的改进，运行速度更快，复杂度更低，且其求 解的 Pareto 最优解集收敛性更好。算法首先随机产 生一定规模数量的初始种群，然后利用非支配排序 方法对种群中所有个体进行分层，接着执行遗传算 法的选择、交叉和变异 3 个操作产生第一代子群。 从第二代子群开始，先将父代种群和子代种群中所 有个体合并在一起，然后利用快速非支配排序方法 对其进行分层，并计算每个非支配分层中所有个体 的拥挤距离，在此基础上从中选出较优的个体组成 新的父代种群，接着执行遗传算法的选择、交叉和 变异 3 个操作产生下一代子群，直至达到程序结束 条件时终止，算法的具体流程如图 1 所示。 第 3 期 林燕清，等：基于 NSGA-II 的扩展置信规则库激活规则多目标优化方法 ·425·
·426· 智能系统学报 第13卷 开始 初始化种群，Gen=0 进化代数Genjdistance 1/SRA(Rp,R)2 (26) 则称个体优于j,表示成i<nj。 那么，第条规则的不一致性为 2.3基于NSGA-Ⅱ的激活规则多目标优化方法 数据驱动型的EBRB规则数量等于训练数据 Incons(i)= 10-CosR,R】 (27) 集数量，每条置信规则对应一个训练数据，当训练 k=1k村 数据过多时，由式(9)计算得到的激活规则数量也 由此可得NSGA-Ⅱ的优化目标为 会比较多，但很多激活规则之间存在相互矛盾、不
O ( MN3 ) O ( MN2 ) M M NSGA-II 算法中个体的优劣之分主要由个体的 两个属性取值来决定，一个是其所在的非支配分层 级别，另一个是个体的拥挤距离。前者是通过快速 非支配排序方法确定，NSGA-II 的快速非支配方法 与 NSGA 的非支配排序方法相比，计算复杂度从原 先的 减少至 (其中 为种群大小， 为目标函数的个数)。计算处于同一个非支配分 层的个体拥挤距离之前，需要先对所有个体的拥挤 距离进行初始化，然后根据目标函数将其按照升序 进行排序，接着再计算每个个体的拥挤距离。详细 的快速非支配排序算法以及个体拥挤距离的计算过 程可参见文献[27]。 i j irank jrank idistance jdistance 确定完每个个体所在的非支配分层级别以及拥 挤距离之后，就可以确定种群所有个体的优劣，假 设其中两个个体 和 ，其所在非支配分层级别为 和 ，拥挤距离为 和 ，如果这两个个 体满足以下两个条件中的一个条件： irank jdistance； 则称个体 i 优于 j ，表示成 i≺n j。 2.3 基于 NSGA-II 的激活规则多目标优化方法 数据驱动型的 EBRB 规则数量等于训练数据 集数量，每条置信规则对应一个训练数据，当训练 数据过多时，由式 (9) 计算得到的激活规则数量也 会比较多，但很多激活规则之间存在相互矛盾、不 RP,Rq p q 一致的情况，这些激活规则会对推理造成一定的干 扰。为了减少不一致激活规则对 EBRB 推理准确 性的影响，本文提出基于 NSGA-II 的激活规则多目 标优化方法，因此，多目标优化的两个目标函数分 别为激活规则集合的不一致性以及激活权重和，其 中，激活规则集合的不一致性用 Liu 等 [21]提出的方 法来衡量，假设 为扩展置信规则库中的两条规 则，二者的不一致性可通过前提属性相似度 SRA 和 评价结果相似度 SRC 来衡量，规则 和规则 的 SRA 和 SRC 计算公式如下： SRA(RP,Rq) = T min i=1 (1− vut∑Ji j=1 (α p i, j −α q i, j ) 2 ) (24) SRC(RP,Rq) = 1− vt∑N i=1 (β p i −β q i ) 2 ) (25) 根据文献[21]，规则 p 和规则 q 之间的一致性可 根据式 (26) 计算得到： Cons(Rp,Rq) = exp(− (SRA(Rp ,Rq)/SRC(Rp ,Rq)−1.0)2 1/SRA(Rp,Rq) 2 ) (26) 那么，第 i 条规则的不一致性为 Incons(i) = ∑l k=1,k,i [1.0−Cons(Ri ,Rk)] (27) 由此可得 NSGA-II 的优化目标为 ᐬ ݉ࡂ㓐喏Gen=0 䔇ࡂЏGen喟1 Y 䲊ᩛ䙹ᢾᎻ 䔵᠕ȟϐࣵȟऄᐮ Gen=Gen+1 ❢ȟၼЏ㓐ऴᎢ ᔗ䕋䲊ᩛ䙹ᢾᎻ 䃍ッ͖ѿ᠑ᡐᏒ 䔵᠕䒯ф͖ѿ㏰ ⮰❢Џ㓐 ㏿ N Genᄻκᰬ๓Џ Y 䔵᠕ȟϐࣵȟऄᐮ Gen=Gen+1 ⩋⮰❢㓐 N N Y 图 1 NSGA-II 算法流程 Fig. 1 The process of NSGA-II ·426· 智 能 系 统 学 报 第 13 卷
第3期 林燕清，等：基于NSGA-Ⅱ的扩展置信规则库激活规则多日标优化方法 ·427· MinF(R)=(f(R),f(R)) 3实例分析 f(R)= Incons(k) 28) 本文引入非线性函数和输油管道检漏实例为研 究对象以验证本文方法的有效性。实验中用到的 R=1.0-2L NSGA-IⅡ算法的各个参数值分别为：个体交叉概率 式中：R表示最终参与ER合成推理的激活规则集 为0.9，个体变异概率为0.03，种群规模为100，进化 合；I表示参与ER合成推理的激活规则总数。 代数为1000。实验环境为：Inter(R)Core(TM)i- 基于NSGA-I的激活规则多目标优化方法具 4570CPU@3.20GHz;8GB内存；Windows10操 作系统：算法实现平台Visual Studio2010。 体流程如图2所示，该方法根据激活规则集合的不 一致性以及激活权重和来求解最终参与ER合成推 3.1非线性函数问题 理的激活规则集合R。本文方法首先计算每条扩展 为了验证本文方法的有效性，引入一个非线性 函数作为基准测试函数进行测试以说明本文方法的 置信规则的激活权重，激活权重大于零的规则组成 性能。非线性函数的数学表达式为 激活规则集合，然后对激活规则集合进行二进制编 fx)=xsin(x2),0≤x≤3 (29) 码，1表示该激活规则参与最终ER合成推理过程， 在EBRB系统构建中，选取函数的自变量x作 0表示该激活规则不参与ER合成推理，不同的激 为前提属性，并从其定义域中均匀选择7个数值作 活规则集合，其中被标识为1和0的规则不同，根 为其参考值，即0,0.5,1.0,1.5,2.0,2.5,3.01，然后根据 据式(27)计算得到的规则不一致性以及激活权重 函数值设定评价结果等级数及相应效用值为 和也不同，故接下来需要利用NSGA-Ⅱ算法求解最 {-2.5,-1.0,1.0,2.0,3.01。该实验的测试数据是从x的 优化目标（式(28）)的Pareto最优解集，这些Pareto 定义域中均匀选取的500组数据，训练数据是从x的 最优解集中编码为1对应的激活规则之间的不一致 定义域中均匀选取的1000组数据，因此，构建的 性既要最小同时激活权重和也要最大，然后从最优 EBRB系统总共有500条规则，然后根据Liu等2四 解集中选择一个合适的Pareto最优解，该最优解中 提出的方法和本文提出的方法构建EBRB系统，实 编码为1对应的激活规则组成最终的激活规则集合 验结果衡量的指标为系统的推理输出和真实输出之 并用于ER合成推理得出结果。本文方法的整体时 间的均方误差(mean squared error,MSE)、激活规则 间复杂度包括：I)EBRB系统查询激活规则复杂度 总数(Activated rules)、参与合成推理的激活规则 O(MW);2)NSGA-IⅡ算法中非支配排序方法复杂度 数(ER rules,实验结果如表I所示。 OMW);3)NSGA-II算法中拥挤距离计算复杂度 表1非线性函数问题实验结果 O(MNlog N);4)NSGA-Ⅱ算法中个体优劣排序复杂 Table 1 The results on nonlinear function 度O(NIog N)。因此整体复杂度为OMW2)。 衡量指标 Liu EBRB NSGA-II EBRB 开始 MSE 0.296986 0.224212 计算每条规则的激活权重 Activated rules 160043 160043 ER rules 160043 79843 激活权重大于零的规则组成 激活规则集合 从表1可以发现，NSGA-II EBRB系统的推理 准确性要比Liu EBRB系统的推理准确性高，这主 对激活规则进行二进制编码 要是因为Liu EBRB系统中用来参与ER合成推理 基于NSGA-Ⅱ的激活规则 的规则是所有激活权重大于零的激活规则，这部分 多目标优化方法 规则的不一致性较高且会降低EBRB系统的推理 能力，而NSGA-II EBRB通过减少激活规则的不一 ER合成推理 致性，选择不一致性更小同时拥有原来激活规则中 结束 绝大部分信息的激活规则进行ER合成推理，最终 合成推理的激活规则数只占原来激活规则总数的 图2激活规则多目标优化方法 Fig.2 The activated rules multi-objective optimization ap- 49.89%,这些激活规则不一致性较低，从而提高 proach EBRB系统的推理能力
MinF(R) = (f1(R), f2(R)) f1(R) = ∑l k=1 Incons(k) f2(R) = 1.0− ∑l k=1 ωk (28) R l 式中： 表示最终参与 ER 合成推理的激活规则集 合； 表示参与 ER 合成推理的激活规则总数。 O(MN) O(MN2 ) O(MN logN) O(N logN) O(MN2 ) 基于 NSGA-II 的激活规则多目标优化方法具 体流程如图 2 所示，该方法根据激活规则集合的不 一致性以及激活权重和来求解最终参与 ER 合成推 理的激活规则集合 R。本文方法首先计算每条扩展 置信规则的激活权重，激活权重大于零的规则组成 激活规则集合，然后对激活规则集合进行二进制编 码，1 表示该激活规则参与最终 ER 合成推理过程， 0 表示该激活规则不参与 ER 合成推理，不同的激 活规则集合，其中被标识为 1 和 0 的规则不同，根 据式 (27) 计算得到的规则不一致性以及激活权重 和也不同，故接下来需要利用 NSGA-II 算法求解最 优化目标 (式 (28)) 的 Pareto 最优解集，这些 Pareto 最优解集中编码为 1 对应的激活规则之间的不一致 性既要最小同时激活权重和也要最大，然后从最优 解集中选择一个合适的 Pareto 最优解，该最优解中 编码为 1 对应的激活规则组成最终的激活规则集合 并用于 ER 合成推理得出结果。本文方法的整体时 间复杂度包括：1)EBRB 系统查询激活规则复杂度 ；2)NSGA-II 算法中非支配排序方法复杂度 ；3)NSGA-II 算法中拥挤距离计算复杂度 ；4)NSGA-II 算法中个体优劣排序复杂 度 。因此整体复杂度为 。 ᐬ ᄥ⓬≧㻰݅䔇㵸θ䔇ݢ㑂ⴭ ㏿ 䃍ッ㻰݅⮰⓬≧ᱯ䛹 ⓬≧ᱯ䛹๓κ䰢⮰㻰݅㏰ ⓬≧㻰݅䯲ऴ ദκNSGA-II⮰⓬≧㻰݅ ∁ࡂๆⰚᴳф ERऴᣔ⤲ 图 2 激活规则多目标优化方法 Fig. 2 The activated rules multi-objective optimization approach 3 实例分析 本文引入非线性函数和输油管道检漏实例为研 究对象以验证本文方法的有效性。实验中用到的 NSGA-II 算法的各个参数值分别为：个体交叉概率 为 0.9，个体变异概率为 0.03，种群规模为 100，进化 代数为 1 000。实验环境为：Inter(R) Core(TM) i5- 4570 CPU @ 3.20 GHz；8 GB 内存；Windows 10 操 作系统；算法实现平台 Visual Studio 2010。 3.1 非线性函数问题 为了验证本文方法的有效性，引入一个非线性 函数作为基准测试函数进行测试以说明本文方法的 性能。非线性函数的数学表达式为 f(x) = x sin(x 2 ),0 ⩽ x ⩽ 3 (29) x {0,0.5,1.0,1.5,2.0,2.5,3.0} {−2.5,−1.0,1.0,2.0,3.0} x x 在 EBRB 系统构建中，选取函数的自变量 作 为前提属性，并从其定义域中均匀选择 7 个数值作 为其参考值，即 ，然后根据 函数值设定评价结果等级数及相应效用值为 。该实验的测试数据是从 的 定义域中均匀选取的 500 组数据，训练数据是从 的 定义域中均匀选取的 1 000 组数据，因此，构建的 EBRB 系统总共有 500 条规则，然后根据 Liu 等 [21] 提出的方法和本文提出的方法构建 EBRB 系统，实 验结果衡量的指标为系统的推理输出和真实输出之 间的均方误差 (mean squared error，MSE)、激活规则 总数 (Activated_rules)、参与合成推理的激活规则 数 (ER_rules)，实验结果如表 1 所示。 表 1 非线性函数问题实验结果 Table 1 The results on nonlinear function 衡量指标 Liu_EBRB NSGA-II_EBRB MSE 0.296 986 0.224 212 Activated_rules 160 043 160 043 ER_rules 160 043 79 843 从表 1 可以发现，NSGA-II_EBRB 系统的推理 准确性要比 Liu_EBRB 系统的推理准确性高，这主 要是因为 Liu_EBRB 系统中用来参与 ER 合成推理 的规则是所有激活权重大于零的激活规则，这部分 规则的不一致性较高且会降低 EBRB 系统的推理 能力，而 NSGA-II_EBRB 通过减少激活规则的不一 致性，选择不一致性更小同时拥有原来激活规则中 绝大部分信息的激活规则进行 ER 合成推理，最终 合成推理的激活规则数只占原来激活规则总数的 49.89%，这些激活规则不一致性较低，从而提高 EBRB 系统的推理能力。 第 3 期 林燕清，等：基于 NSGA-II 的扩展置信规则库激活规则多目标优化方法 ·427·
·428· 智能系统学报 第13卷 3.2输油管道检漏实例 NSGA-IⅡEBRB系统产生的推理输出和测试数据 为了验证本文所提方法的有效性，引入一个具 的真实输出的MAE值，其中BK EBRB系统是指 体的实际问题一一输油管道泄漏问题作为实例。 根据文献[28]中的方法构建的EBRB系统。如表2 该实例的研究对象为安装在英国的一条1000多米 所示，和Liu EBRB系统的MAE相比，NSGA-II 长的输油管道，当输油管道发生泄漏时，管道的泄 EBRB系统比Liu_EBRB系统的MAE值减小了 漏大小(leak size,LS)会随输油管道输入输出的流 61.61%;和BK EBRB系统相比，NSGA-II EBRB 量差(flow difference,FD)和输油管道内的平均压 系统要比BK EBRB(theta=O.7)的MAE值减小 力差(pressure difference,PD)变化而变化，因此，该 56.92%;和BK EBRB(theta=0.4)的MAE值相差 实例的EBRB系统的前提属性为FD和PD,结果属 无几。 性为LS。其中FD、PD的参考值由专家根据经验 给出，分别为{-10，-5，-3,0,1,2,3)和{-0.042，-0.025， -0.01,0,0.01,0.025,0.042,LS的评价等级为零、很 。真实输出 ·Liu-EBRB系统输出 小、中、高、很高，其数值效用值为0,2,4,6,8}。 该实验的测试数据是发生泄漏的2008组数 据，训练数据按照一定比例分别从3个时间段随机 选取500组数据，因此构建的EBRB系统总共有 2 1500条规则，然后利用本文提出的方法构建NSGA- 0.04 IⅡEBRB系统，并将实验结果和Liu EBRB系统相 0.02 比较，衡量的指标为平均绝对误差(mean absolute 0 difference,MAE) D -0.02-10 Liu EBRB系统、NSGA-IⅡEBRB系统产生的 图4NSGA-ⅡEBRB输出和真实输出 推理输出和测试数据的真实输出对比如图3、4所 Fig.4 NSGA-II EBRB output and real output 示。分析图3、4可以发现，Liu EBRB系统在PD∈ 表2输油管道泄漏实例实验结果 [-0.02,0.04],FDe[-10,0]附近产生的推理输出和测 Table 2 The results on pipeline leak detection 试数据的真实输出有较大差距，尤其是PDe[-0.02, EBRB系统类型 MAE O,FD∈[-1O,5]附近的数据。而NSGA-II EBRB系 Liu EBRB 0.626240 统推理输出总体上和真实输出相接近。这是因为， BK EBRB(theta=1.0) 0.626240 本文方法减少了不一致规则对于推理结果的影响， 从而进一步提高了算法的推理性能。 BK_EBRB(theta-0.7) 0.558087 BK EBRB(theta=0.4) 0.231400 NSGA-II EBRB 0.240443 ·其实输出 +Liu一EBRB系统输出 4 结束语 数据驱动型的扩展置信规则库系统易受数据质 量的影响，其推理能力常因不一致的数据而降低。 因此，本文提出基于NSGAⅡ的扩展置信规则库激 0.04 0.02 活规则多目标优化方法，通过NSGA-Ⅱ来求解不一 PD 致性更小的激活规则集合，该方法既筛选出了不一 -5 FD -0.02-10 致性更小的激活规则，同时又保留了原来激活规则 图3 Liu EBRB输出和真实输出 集合中绝大部分信息，这些最终参与ER合成推理 Fig.3 Liu_EBRB output and real output 的激活规则一致性更高，更具代表性，能有效提高 为了进一步验证本文方法的有效性和可行性， EBRB系统的推理能力。然而，本文方法还有许多 表2列出了Liu EBRB系统、BK EBRB系统和 需要改进的地方，如何从Pareto最优解集中选择一
3.2 输油管道检漏实例 {−10,−5,−3,0,1,2,3} {−0.042,−0.025, −0.01,0,0.01,0.025,0.042} {0,2,4,6,8} 为了验证本文所提方法的有效性，引入一个具 体的实际问题——输油管道泄漏问题[7]作为实例。 该实例的研究对象为安装在英国的一条 1 000 多米 长的输油管道，当输油管道发生泄漏时，管道的泄 漏大小 (leak size，LS) 会随输油管道输入输出的流 量差 (flow difference，FD) 和输油管道内的平均压 力差 (pressure difference，PD) 变化而变化，因此，该 实例的 EBRB 系统的前提属性为 FD 和 PD，结果属 性为 LS。其中 FD、PD 的参考值由专家根据经验 给出，分别为 和 ，LS 的评价等级为零、很 小、中、高、很高，其数值效用值为 。 该实验的测试数据是发生泄漏的 2 008 组数 据，训练数据按照一定比例分别从 3 个时间段随机 选取 500 组数据，因此构建的 EBRB 系统总共有 1 500 条规则，然后利用本文提出的方法构建 NSGAII_EBRB 系统，并将实验结果和 Liu_EBRB 系统相 比较，衡量的指标为平均绝对误差 (mean absolute difference，MAE)。 PD ∈ [ – 0.02,0.04],FD ∈ [ – 10,0] PD ∈ [ – 0.02, 0],FD ∈ [ – 10,5] Liu_EBRB 系统、NSGA-II_EBRB 系统产生的 推理输出和测试数据的真实输出对比如图 3、4 所 示。分析图 3、4 可以发现，Liu_EBRB 系统在 附近产生的推理输出和测 试数据的真实输出有较大差距，尤其是 附近的数据。而 NSGA-II_EBRB 系 统推理输出总体上和真实输出相接近。这是因为， 本文方法减少了不一致规则对于推理结果的影响， 从而进一步提高了算法的推理性能。 8 6 4 2 0 LS 0.04 0.02 0 −0.02 PD FD −10 −5 0 5 ⱋ䒿ܦ Liu−EBRB ㈧㐋䒿ܦ 0.02 0 Liu−EBRB ㈧㐋䒿ܦ 图 3 Liu_EBRB 输出和真实输出 Fig. 3 Liu_EBRB output and real output 为了进一步验证本文方法的有效性和可行性， 表 2 列出了 Liu_EBRB 系统、BK_EBRB 系统和 NSGA-II_EBRB 系统产生的推理输出和测试数据 的真实输出的 MAE 值，其中 BK_EBRB 系统是指 根据文献[28]中的方法构建的 EBRB 系统。如表 2 所示，和 Liu_EBRB 系统的 MAE 相比，NSGA-II_ EBRB 系统比 Liu_EBRB 系统的 MAE 值减小了 61.61%；和 BK_EBRB 系统相比，NSGA-II_EBRB 系统要比 BK_EBRB(theta=0.7) 的 MAE 值减小 56.92%；和 BK_EBRB(theta=0.4) 的 MAE 值相差 无几。 8 6 4 2 0 LS 0.04 0.02 0 −0.02 PD FD −10 −5 0 5 真实输出 Liu−EBRB 系统输出 图 4 NSGA-II_EBRB 输出和真实输出 Fig. 4 NSGA-II_EBRB output and real output 表 2 输油管道泄漏实例实验结果 Table 2 The results on pipeline leak detection EBRB 系统类型 MAE Liu_EBRB 0.626 240 BK_EBRB(theta=1.0) 0.626 240 BK_EBRB(theta=0.7) 0.558 087 BK_EBRB(theta=0.4) 0.231 400 NSGA-II_EBRB 0.240 443 4 结束语 数据驱动型的扩展置信规则库系统易受数据质 量的影响，其推理能力常因不一致的数据而降低。 因此，本文提出基于 NSGA-II 的扩展置信规则库激 活规则多目标优化方法，通过 NSGA-II 来求解不一 致性更小的激活规则集合，该方法既筛选出了不一 致性更小的激活规则，同时又保留了原来激活规则 集合中绝大部分信息，这些最终参与 ER 合成推理 的激活规则一致性更高，更具代表性，能有效提高 EBRB 系统的推理能力。然而，本文方法还有许多 需要改进的地方，如何从 Pareto 最优解集中选择一 ·428· 智 能 系 统 学 报 第 13 卷
第3期 林燕清，等：基于NSGA-Ⅱ的扩展置信规则库激活规则多日标优化方法 ·429· 个最合适的解，如何减少算法的复杂度等，这些都 ence and technology,2015,9(8):985-994. 是将来的研究工作重点。 [13]CHEN Yuwang,YANG Jianbo,XU Dongling,et al.Infer- ence analysis and adaptive training for belief rule based 参考文献： systems[J].Expert systems with applications,2011,38(10): []周志杰，杨剑波，胡昌华，等.置信规则库专家系统与复杂 12845-12860. 系统建模M.北京：科学出版社，2011. [14]常瑞，张速.基于优化步长和梯度法的置信规则库参数 [2]YANG Jianbo,LIU Jun,WANG Jin,et al.Belief rule-base 学习方法.华北水利水电学院学报，2011,32(1)154 inference methodology using the evidential reasoning ap- 157. proach-RIMER[J].IEEE transactions on systems,man,and Chang Rui,Zhang Su.An algorithm for training paramet- cybernetics-part A:systems and humans,2006,36(2): ers in belief rule-bases based on the gradient methods with 266-285. optimization step size[J].Journal of north China institute of [3]DEMPSTER A P.A generalization of Bayesian inference water conservancy and hydroelectric power,2011,32(1): [J].Journal of the royal statistical society.Series B(method- 154157 ological).1968.30(2):205-247. [15]吴伟昆，杨隆浩，傅仰耿，等.基于加速梯度求法的置信 [4]SHAFER G.A mathematical theory of evidence[M].Prin 规则库参数训练方法).计算机科学与探索，2014,8(8) ceton:Princeton University Press,1976. 989-1001. [5]HWANG C L,YOON K.Multiple attribute decision mak- WU Weikun,YANG Longhao,FU Yanggeng,et al.Para- ing:methods and applications a state of the art survey[M]. meter training approach for belief rule base using the accel- New York:Springer,1981:22-34. erating of gradient algorithm[J].Journal of frontiers of [6]ZADEH L A.Fuzzy sets[J].Information and control,1965, computer science and technology,2014,8(8):989-1001. 8(3):338-353. [16]苏群，杨隆浩，傅仰耿，等.基于变速粒子群优化的置信 7]ZHOU Zhijie,HU Changhua,YANG Jianbo,et al.Online 规则库参数训练方法[J].计算机应用，2014,34(8)： updating belief rule based system for pipeline leak detection 2161-2165 under expert intervention[J].Expert systems with applica- SU Qun,YANG Longhao,FU Yanggeng,et al.Parameter tions,2009,36(4):7700-7709 training approach based on variable particle swarm optim- [8]XU Dongling,LIU Jun,YANG Jianbo,et al.Inference and ization for belief rule base[J].Journal of computer applica- learning methodology of belief-rule-based expert system for tion,2014,348):2161-2165. pipeline leak detection[].Expert systems with applications, [17刀王韩杰，杨隆浩，傅仰耿，等.专家干预下置信规则库参 2007,32(1):103-113. 数训练的差分进化算法[.计算机科学，2015,42(5)： 9]YANG Jianbo,LIU Jun,XU Dongling,et al.Optimization 88-93. models for training belief-rule-based systems[J].IEEE trans- WANG Hanjie,YANG Longhao,FU Yanggeng,et al.Dif- actions on systems,man,and cybernetics-part A:systems ferential evolutionary algorithm for parameter training of and humans,2007,37(4):569-585. belief rule base under expert intervention[J.Computer sci- [10]YANG Ying,FU Chao,CHEN Yuwang,et al.A belief rule ence,2015,42(5:88-93 based expert system for predicting consumer preference in [18]ZHOU Zhijie,HU Changhua,YANG Jianbo,et al.A se- new product development[J].Knowledge-based systems, quential learning algorithm for online constructing belief- 2016,94:105-113 rule-based systems[J].Expert systems with applications. [11]JIANG Jiang,LI Xuan,ZHOU Zhijie,et al.Weapon sys- 2010,37(2):1790-1799 tem capability assessment under uncertainty based on the [19]CHANG Leilei,ZHOU Yu,JIANG Jiang,et al.Structure evidential reasoning approach[J].Expert systems with ap- learning for belief rule base expert system:a comparative plications,2011,38(11):13773-13784. study [J].Knowledge-based systems,2013,39:159-172 [12]杨隆浩，蔡芷铃，黄志鑫，等.出租车乘车概率预测的置 [20]王应明，杨隆浩，常雷雷，等.置信规则库规则约简的粗 信规则库推理方法[).计算机科学与探索，2015,9(8)： 糙集方法[).控制与决策，2014,29(11)：1943-1950. 985-994 WANG Yingming,YANG Longhao,CHANG Leilei,et al. YANG Longhao,CAI Zhiling,HUANG Zhixin,et al.Be- Rough set method for rule reduction in belief rule base[J]. lief rule-base inference methodology for predicting probab- Control and decision,2014,29(11):1943-1950. ility of taking taxi[J].Journal of frontiers of computer sci- [21]LIU Jun,MARTINEZ L,CALZADA A,et al.A novel be-
个最合适的解，如何减少算法的复杂度等，这些都 是将来的研究工作重点。 参考文献： 周志杰, 杨剑波, 胡昌华, 等. 置信规则库专家系统与复杂 系统建模[M]. 北京: 科学出版社, 2011. [1] YANG Jianbo, LIU Jun, WANG Jin, et al. Belief rule-base inference methodology using the evidential reasoning approach-RIMER[J]. IEEE transactions on systems, man, and cybernetics-part A: systems and humans, 2006, 36(2): 266–285. [2] DEMPSTER A P. A generalization of Bayesian inference [J]. Journal of the royal statistical society. Series B (methodological), 1968, 30(2): 205–247. [3] SHAFER G. A mathematical theory of evidence[M]. Princeton: Princeton University Press, 1976. [4] HWANG C L, YOON K. Multiple attribute decision making: methods and applications a state of the art survey[M]. New York: Springer, 1981: 22–34. [5] ZADEH L A. Fuzzy sets[J]. Information and control, 1965, 8(3): 338–353. [6] ZHOU Zhijie, HU Changhua, YANG Jianbo, et al. Online updating belief rule based system for pipeline leak detection under expert intervention[J]. Expert systems with applications, 2009, 36(4): 7700–7709. [7] XU Dongling, LIU Jun, YANG Jianbo, et al. Inference and learning methodology of belief-rule-based expert system for pipeline leak detection[J]. Expert systems with applications, 2007, 32(1): 103–113. [8] YANG Jianbo, LIU Jun, XU Dongling, et al. Optimization models for training belief-rule-based systems[J]. IEEE transactions on systems, man, and cybernetics-part A: systems and humans, 2007, 37(4): 569–585. [9] YANG Ying, FU Chao, CHEN Yuwang, et al. A belief rule based expert system for predicting consumer preference in new product development[J]. Knowledge-based systems, 2016, 94: 105–113. [10] JIANG Jiang, LI Xuan, ZHOU Zhijie, et al. Weapon system capability assessment under uncertainty based on the evidential reasoning approach[J]. Expert systems with applications, 2011, 38(11): 13773–13784. [11] 杨隆浩, 蔡芷铃, 黄志鑫, 等. 出租车乘车概率预测的置 信规则库推理方法[J]. 计算机科学与探索, 2015, 9(8): 985–994. YANG Longhao, CAI Zhiling, HUANG Zhixin, et al. Belief rule-base inference methodology for predicting probability of taking taxi[J]. Journal of frontiers of computer sci- [12] ence and technology, 2015, 9(8): 985–994. CHEN Yuwang, YANG Jianbo, XU Dongling, et al. Inference analysis and adaptive training for belief rule based systems[J]. Expert systems with applications, 2011, 38(10): 12845–12860. [13] 常瑞, 张速. 基于优化步长和梯度法的置信规则库参数 学习方法[J]. 华北水利水电学院学报, 2011, 32(1): 154– 157. Chang Rui, Zhang Su. An algorithm for training parameters in belief rule-bases based on the gradient methods with optimization step size[J]. Journal of north China institute of water conservancy and hydroelectric power, 2011, 32(1): 154–157. [14] 吴伟昆, 杨隆浩, 傅仰耿, 等. 基于加速梯度求法的置信 规则库参数训练方法[J]. 计算机科学与探索, 2014, 8(8): 989–1001. WU Weikun, YANG Longhao, FU Yanggeng, et al. Parameter training approach for belief rule base using the accelerating of gradient algorithm[J]. Journal of frontiers of computer science and technology, 2014, 8(8): 989–1001. [15] 苏群, 杨隆浩, 傅仰耿, 等. 基于变速粒子群优化的置信 规则库参数训练方法[J]. 计算机应用, 2014, 34(8): 2161–2165. SU Qun, YANG Longhao, FU Yanggeng, et al. Parameter training approach based on variable particle swarm optimization for belief rule base[J]. Journal of computer application, 2014, 34(8): 2161–2165. [16] 王韩杰, 杨隆浩, 傅仰耿, 等. 专家干预下置信规则库参 数训练的差分进化算法[J]. 计算机科学, 2015, 42(5): 88–93. WANG Hanjie, YANG Longhao, FU Yanggeng, et al. Differential evolutionary algorithm for parameter training of belief rule base under expert intervention[J]. Computer science, 2015, 42(5): 88–93. [17] ZHOU Zhijie, HU Changhua, YANG Jianbo, et al. A sequential learning algorithm for online constructing beliefrule-based systems[J]. Expert systems with applications, 2010, 37(2): 1790–1799. [18] CHANG Leilei, ZHOU Yu, JIANG Jiang, et al. Structure learning for belief rule base expert system: a comparative study[J]. Knowledge-based systems, 2013, 39: 159–172. [19] 王应明, 杨隆浩, 常雷雷, 等. 置信规则库规则约简的粗 糙集方法[J]. 控制与决策, 2014, 29(11): 1943–1950. WANG Yingming, YANG Longhao, CHANG Leilei, et al. Rough set method for rule reduction in belief rule base[J]. Control and decision, 2014, 29(11): 1943–1950. [20] [21] LIU Jun, MARTINEZ L, CALZADA A, et al. A novel be- 第 3 期 林燕清，等：基于 NSGA-II 的扩展置信规则库激活规则多目标优化方法 ·429·
·430· 智能系统学报 第13卷 lief rule base representation,generation and its inference ive optimization:NSGA-II [C]//Proceedings of the 6th In- methodology[J].Knowledge-based systems,2013,53: ternational Conference Paris Parallel Problem Solving from 129-141 Nature PPSN VI.Kanpur,India,2000. [22]CALZADA A,LIU Jun,WANG Hui,et al.A new dynam- [28]苏群，杨隆浩，傅仰耿，等.基于BK树的扩展置信规则库 ic rule activation method for extended belief rule-based 结构优化框架[】.计算机科学与探索，2016,10(2)： systems[J].IEEE Transactions on knowledge and data en- 257-267. gineering,.2015,7(4):880-894. SU Qun,YANG Longhao,FU Yanggeng,et al.Structure [23]YANG Jianbo.Rule and utility based evidential reasoning optimization framework of extended belief rule base based approach for multiattribute decision analysis under uncer- on BK-tree[J].Journal of frontiers of computer science and tainties[J].European journal of operational research,2001, technology,2016,10(2):257-267. 1311:31-61. 作者简介： [24]WANG Yingming,YANG Jianbo,XU Dongling.Environ- 林燕清，女，1992年生，硕士研究 mental impact assessment using the evidential reasoning 生，主要研究方向为智能决策与专家 approach[J].European journal of operational research, 系统。 2006,1743:1885-1913. [25]WANG Yingming,YANG Jianbo,XU Dongling,et al. Consumer preference prediction by using a hybrid eviden- tial reasoning and belief rule-based methodology[].Ex- pert systems with applications,2009,36(4):8421-8430. 傅仰耿，男，1981年生，副教授， [26]ZITZLER E.Evolutionary algorithm for multi-objective 博土，CCF会员，CAAI会员，主要研 究方向为决策理论与方法、数据挖掘。 optimization:methods and applications[D].Zurich:Swiss 机器学习、智能系统。 Federal Institute of Technology,1999. [27]DEB K,AGRAWAL S,PRATAP A,et al.A fast elitist non-dominated sorting genetic algorithm for multi-object-
lief rule base representation, generation and its inference methodology[J]. Knowledge-based systems, 2013, 53: 129–141. CALZADA A, LIU Jun, WANG Hui, et al. A new dynamic rule activation method for extended belief rule-based systems[J]. IEEE Transactions on knowledge and data engineering, 2015, 7(4): 880–894. [22] YANG Jianbo. Rule and utility based evidential reasoning approach for multiattribute decision analysis under uncertainties[J]. European journal of operational research, 2001, 131(1): 31–61. [23] WANG Yingming, YANG Jianbo, XU Dongling. Environmental impact assessment using the evidential reasoning approach[J]. European journal of operational research, 2006, 174(3): 1885–1913. [24] WANG Yingming, YANG Jianbo, XU Dongling, et al. Consumer preference prediction by using a hybrid evidential reasoning and belief rule-based methodology[J]. Expert systems with applications, 2009, 36(4): 8421–8430. [25] ZITZLER E. Evolutionary algorithm for multi-objective optimization: methods and applications[D]. Zurich: Swiss Federal Institute of Technology, 1999. [26] DEB K, AGRAWAL S, PRATAP A, et al. A fast elitist non-dominated sorting genetic algorithm for multi-object- [27] ive optimization: NSGA-Ⅱ[C]//Proceedings of the 6th International Conference Paris Parallel Problem Solving from Nature PPSN VI. Kanpur, India, 2000. 苏群, 杨隆浩, 傅仰耿, 等. 基于 BK 树的扩展置信规则库 结构优化框架[J]. 计算机科学与探索, 2016, 10(2): 257–267. SU Qun, YANG Longhao, FU Yanggeng, et al. Structure optimization framework of extended belief rule base based on BK-tree[J]. Journal of frontiers of computer science and technology, 2016, 10(2): 257–267. [28] 作者简介： 林燕清，女，1992 年生，硕士研究 生，主要研究方向为智能决策与专家 系统。 傅仰耿，男，1981 年生，副教授， 博士，CCF 会员，CAAI 会员，主要研 究方向为决策理论与方法、数据挖掘、 机器学习、智能系统。 ·430· 智 能 系 统 学 报 第 13 卷
