第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 进化代数Gen<1 Y非支配排序 N 选择、交叉、变异 父、子代种群合并 Gen=Gen+1 Gen=Gen+1 生成新的父种群 N 快速非支配排序 P 选择、交叉、变异 计算个体拥挤度 选择较优个体组 Gen小于最大代数 成新的父代种群 N 结束 图1NSGA-I算法流程 Fig.1 The process of NSGA-II NSGA-Ⅱ算法中个体的优劣之分主要由个体的 一致的情况，这些激活规则会对推理造成一定的干 两个属性取值来决定，一个是其所在的非支配分层 扰。为了减少不一致激活规则对EBRB推理准确 级别，另一个是个体的拥挤距离。前者是通过快速 性的影响，本文提出基于NSGA-Ⅱ的激活规则多目 非支配排序方法确定，NSGA-Ⅱ的快速非支配方法 标优化方法，因此，多目标优化的两个目标函数分 与NSGA的非支配排序方法相比，计算复杂度从原 别为激活规则集合的不一致性以及激活权重和，其 先的O(MN)减少至O(MN2)(其中M为种群大小， 中，激活规则集合的不一致性用Lu等2提出的方 M为目标函数的个数)。计算处于同一个非支配分 法来衡量，假设R,R为扩展置信规则库中的两条规 层的个体拥挤距离之前，需要先对所有个体的拥挤 则，二者的不一致性可通过前提属性相似度SRA和 距离进行初始化，然后根据目标函数将其按照升序 评价结果相似度SRC来衡量，规则p和规则q的 进行排序，接着再计算每个个体的拥挤距离。详细 SRA和SRC计算公式如下： 的快速非支配排序算法以及个体拥挤距离的计算过 程可参见文献27。 SRA(Rp,Rg)=min(1 (a-a)) (24) =1 确定完每个个体所在的非支配分层级别以及拥 挤距离之后，就可以确定种群所有个体的优劣，假 SRC(Rp.Ra)=1- (25) 设其中两个个体和j,其所在非支配分层级别为 irank和jrnk,拥挤距离为st和jisne,如果这两个个 根据文献[21]，规则p和规则g之间的一致性可 体满足以下两个条件中的一个条件： 根据式(26)计算得到： 1)irank <jranki Cons(Rp.Ra)=exp(- (SRA(Rp:Ra)/SRC(Rp:Rg)-1.0)2 2)irank=jrank并且distance>jdistance 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 < j 1) rank； irank = j 2) rank并且 idistance > 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 卷