基于平行多种群与冗余基因策略的置信规则库优化方法

徐晓滨 朱 伟 徐晓健 侯平智 ,2 常雷雷

置信规则库(Belief rule base,BRB)是一种基于D-S (Dempster-Shafer)证据理论的复杂系统建模、分析与评价的专家系统方法.该方法以置信规则(Belief rule)为基础,能够较好地表示、建模和集成不确定条件下的多种类型信息[1-2].同时,作为一种“白箱(White box)”方法,BRB 还具有较强的可解释性,专家可以更好地参与BRB 的建模、训练以及学习过程.自提出以来,BRB 已成功应用于各个领域,如智慧医疗[3]、多属性决策分析[4]以及军事能力评估[5]等.

然而,BRB 的规模不宜过大,否则将会给建模造成巨大的困难.同时,由于人的认知不完备或者数据缺失,专家给定的初始化BRB 可能面临所筛选关键指标及其取值不准确的情况,因此采用初始BRB 进行建模、评估和预测时,其结果精度可能不高.为了解决这些问题,需要对初始BRB 进行学习优化以明确其规模和提高建模精度.众多研究者在多个领域开展了相关研究,主要可以分为3 类:BRB结构学习、BRB 参数学习以及BRB 结构与参数联合优化.

BRB 结构学习的目的是识别与筛选关键前提属性及其参考值.Chang 等[5]首先提出了基于主成分分析等维度约减技术的BRB 结构学习方法,对装备体系综合能力评估问题开展了相关研究;Wang等[6]提出动态调整BRB 规则的结构学习方法;Li等[7]提出了基于极小方差的前提属性参考值确定方法,并基于此提出了安全性评估方法.

BRB 参数学习的目的是通过优化BRB 相关参数的取值以提高建模精度.Yang 等[8]提出BRB优化模型优化BRB 的参数.Zhou 等[9]基于期望极大估计算法提出了在线参数学习方法,对于时效性有较高要求的复杂决策问题提供了在线建模方法.Chen 等[10]对前提属性参考值存在的约束进行分析,改进了BRB 系统的优化模型,将前提属性参考值作为被训练的参数进行参数学习,并将原优化模型称为局部训练模型,改进后的优化模型称为全局训练模型.Savan 等[11]、Chang 等[12]和马炫等[13]提出了基于演化算法(Evolutionary algorithms,EA)的BRB 参数学习方法.Chang 等[12]对比了多种演化算法的求解效率,包括遗传算法(Genetic algorithm,GA)、差分进化(Differential evolutionary,DE)算法以及粒子群(Particle swarm optimization,PSO)算法等.这些优化算法在解决解空间较大的理论与实践问题方面具有较强的优势.

在结构学习和参数学习的基础上,Chang 等[14-16]进一步提出了对BRB 参数和结构进行优化的BRB联合优化方法,通过构建双层优化模型,在外层模型中优化BRB 结构,在内层模型中优化BRB参数,实现对BRB 参数与结构的联合优化.Yang 等[16]提出BRB 结构和参数的联合优化方法,采用启发式策略(Heuristic strategy)优化BRB 结构,采用差分进化算法优化BRB 参数.

以上有关BRB 结构学习、参数学习的相关工作仅关注单一层面,而文献[14-16]虽然实现了对BRB结构与参数的优化,但是其对BRB 结构和参数的优化仍然是分别开展,更具体而言,在外层模型中仅优化BRB 结构,在内层模型中仅优化BRB 参数.在本质上仍然属于迭代(Iterative)的过程,并未实现对BRB 结构与参数的同时优化.

基于此,本文提出一种基于平行多种群策略和冗余基因策略的BRB 优化方法.该方法中,采用具有不同基因数量的多个种群来编码具有不同数量规则的BRB,多个不同种群共同参与优化过程来实现对BRB 结构与参数进行优化的目的;在优化过程中,为具有较少基因的个体(具有较少规则的BRB)补充部分冗余基因,以确保不同长度个体能够同时参与优化过程.采用该方法,可以一次产生具有不同数量规则BRB 的最优解,并自动生成帕累托前沿,决策者可以根据自身偏好或实际问题需求在帕累托前沿上筛选最优解.最终以某输油管道泄漏检测问题为例对本文提出的方法进行验证.

1 BRB 理论基础及推理过程

1.1 BRB 基础

在传统D-S 证据理论的基础上,Yang 等[8]进一步提出采用具有置信结构的IF-THEN 规则来表达、建模与推理不确定条件下的多种类型信息,包括定性定量信息、语义数值信息、完备与不完备信息等.由具有同一置信结构的IF-THEN 规则组合而成的规则库即称为置信规则库(BRB),其中第k条规则如式(1)所示:

其中,xm(m=1,···,M)表示第m个前提属性,(m=1,···,M;k=1,···,K)表示第k条规则中第m个前提属性的参考值;βn,k(n=1,···,N)表示第k条规则中第n个评估结果Dn的置信度;“∧”表示规则满足交集假设;θk和δm分别表示第k条规则和第m个前提属性的权重.

相应的,当置信规则建立在并集假设下时,其表述形式如式(2)所示:

其中,“∨”代表规则满足并集假设.

作为一种具有白箱特征的专家系统方法,BRB已经广泛应用于解决多复杂系统问题[17-18].

1.2 BRB 的推理

BRB 系统的规则推理过程主要有4 个步骤.

步骤1.计算前提属性与参考值之间的匹配度.

对于给定前提属性xm的值为,第j条规则中第m个属性的匹配度如式(3)所示:

其中,cm表示第m个属性的置信度.如果没有不完整的信息并且第m个属性的置信度为1,则式(4)可以简化为式(5):

步骤2.计算激活规则权重.

第k条规则的激活规则权重计算如式(6)所示:

其中,θk表示第k条规则的相对权重;表示第k条规则中第m个前提属性与参考值集合xm之间的匹配度.如果wk＞0,表示第k条规则被激活,否则第k条规则未被激活.

步骤3.通过证据推理(Evidential reasoning,ER)算法融合被激活的规则,如式(7)(见本页下方)和式(8)(见下页上方)所示.式(7)和式(8)中,βn表示第n个评估结果的置信度.

步骤4.输出结果.

融合相应的规则后得到评估结果的置信分布形式,如式(9)所示:

当评估结果输出为单一值时,需要对步骤3 中的结果进行集成.假设评估等级Dn对应的效用值为U(Dn),则评估结果的综合效用U可根据式(10)进行计算.

1.3 BRB 学习以及面临的问题

当前BRB 的学习方法可大致分为3 类:

1)BRB 结构学习

BRB 结构学习主要思想是缩减BRB 规模或者是确定BRB 的最佳结构.BRB 规模与前提属性的个数以及前提属性的参考值有关[5-7].因此,BRB结构学习主要从这两方面考虑.BRB 结构学习所解决的是由前提属性的个数或者前提属性的参考值个数过多而导致的组合爆炸的问题.

2)BRB 参数学习

BRB 参数学习主要思想是优化BRB 的参数提高建模精度[8-10].由于人的认知不完备或者数据缺失,专家给定的初始化BRB 可能面临所筛选关键指标及其取值不准确的情况,因此采用初始BRB进行建模、评估和预测时,其结果精度可能不高.因此提出BRB 参数学习以提高对复杂非线性系统的建模能力.BRB 的参数优化模型取均方误差或者绝对误差作为优化目标函数,前提属性的参考值,规则权重以及评估结果的置信度作为决策变量.目前BRB 的优化方法主要有主成分分析法(Principal component analysis,PCA)、牛顿法以及演化算法(Evolutionary algorithm,EA).

3)BRB 联合优化

BRB 联合优化的主要思想是对BRB 结构和参数同时优化以减小建模复杂度和提高建模精度[14-16].当前针对BRB 参数和结构优化的BRB 联合优化方法[14-15]中,首先推导出集成模型精度(由均方差表示)与复杂度(与规则数量相关)的综合优化目标,然后构建双层优化模型,并提出基于演化算法的优化模型求解算法,最终实现对BRB 结构与参数的联合优化.但是该方法对BRB 结构与参数的联合优化是迭代进行,并未实现对BRB 结构与参数的同时优化.

根据弹性层状体系理论，计算得到无机结合料层层底拉应力为0.263MPa。根据气象资料，工程所在地区冻结指数F为1500.0℃·日，季节性冻土地区调整系数ka取0.74。计算得到现场综合修正系数为-1.157。

综上所述,当前BRB 学习相关研究中一般仅局限于结构学习或参数学习,而开展的BRB 结构与参数联合优化的过程本质上也是迭代和分别进行,并未实现对BRB 结构与参数同时进行优化的目的.基于此,本文提出采用平行多种群策略和冗余基因策略的BRB 优化方法,实现对BRB 结构与参数进行同时优化的目的.

2 基于平行多种群策略的BRB 优化模型

2.1 平行多种群策略

当前,一般采用多种群策略来集成不同算子的优势以解决大规模优化问题[19-22].具体而言,在不同种群中分别采用不同算子进行优化,在优化过程中进行对比并将其作为下一代分配优化资源的依据,综合集成多种不同算子的共同优势.这是由于传统优化问题中并不涉及结构优化.因此,在将多种群策略应用于优化算法时,不同种群中的优化算子不同,但个体长度(编码格式)仍是相同的.但这与本文要解决的核心问题有本质区别:本文研究的出发点是实现对BRB 结构和参数的同时优化,因此在本文采用的多种群策略中,不同种群中的个体长度(编码格式)不同.

但是,同时优化BRB 结构与参数所面临的最大挑战在于,具有不同数量规则的BRB 规模不同,而采用演化算法进行求解时,要求种群中所有个体的长度相同.本文提出采用平行多种群策略解决这一问题.将具有不同数量规则的BRB 按照其规则数量划分为多个种群,在单一种群中BRB 具有相同数量规则(个体长度相同),不同种群之间BRB规则数量不同(个体长度不同).换言之,将BRB 中规则数量K,也作为待优化参数之一引入第2.2 节中的优化模型中,以实现对BRB 结构与参数同时优化的目的.

图1 表示平行多种群策略将初始种群划分为具有不同规则数量的种群(种群规则数量相同),但仍不能用于交叉变异,需要添加冗余基因至所有个体长度相等(见第3 节).

图1 平行多种群策略Fig.1 Parallel multiple population strategy

2.2 BRB 优化模型

基于第2.1 节提出的平行多种群策略,建立同时包含BRB 结构与参数的优化模型为

其中,k=1,···,K;n=1,···,N;m=1,···,M;pq∈[1,···,M].式(11b)表示规则数量在预定的最小规则数Kmin和最大规则数Kmax之间.式(11c)表示第m个前件属性的参考值在下界lbm和上界ubm之间.式(11d)和式(11e)表示第m个前件属性的参考值的上下界必须包含在规则中.式(11f)表示初始规则权重应该在 (0,1] 内.式(11g)表示评估结果的置信度应该在 [0,1] 内.式(11h)表示评估结果的置信度之和小于或者等于1 (当信息不完整时)＜1.

3 基于冗余基因策略的BRB 优化算法

为了求解第2.2 节中建立的优化模型,本节提出基于冗余基因策略的BRB 优化算法.基于冗余基因策略,对基因数量较少的个体(规则数量较少的BRB)补全部分冗余基因,至所有个体的长度相等.这样所有个体的长度即一致,也就可以参与优化操作,而并不参与适应度计算.

基于冗余基因策略的BRB 优化求解算法共包括6 个步骤,如图2 所示.

图2 优化算法的6 个步骤Fig.2 Optimization algorithm with six steps

参数识别主要包括演化算法的参数设值和BRB 的参数设值.演化算法的参数包括种群个数、迭代次数等.BRB 的参数包括BRB 的规则个数、前提属性(参考值)的个数、评估结果的置信度个数.

步骤2.初始化(编码)

每一个个体代表一个具体的BRB.个体基因由BRB 的参数组成.BRB 的参数包括前提属性的参考值、规则权重、评估结果的置信度以及表示BRB 中规则数量K.K的取值为离散整数,介于最小规则数Kmin和最大规则数Kmax之间.

不同的BRB 具有不同的规则数量,不同个体之间的基因个数也不相等,这就导致不同种群中的个体长度不同,因此不能进入下一步的交叉变异操作.

步骤3.交叉变异(补全冗余基因)

在进行交叉变异操作之前,首先需要对不同种群中的所有个体补全冗余基因,以确保所有个体的长度相同(所有个体包含基因数量相同),如图3 所示.

图3 添加冗余基因Fig.3 Add redundant genes

向各个个体中补全基因的操作步骤如下:首先识别具有最多基因数量的个体(即具有最多规则数量的BRB),以该个体的长度为标准长度;然后依次对每个个体补全冗余基因,需要注意补全基因应当满足所在位置的上下限要求,且最后一位标志初始规则数量的基因K位置和取值不变.

补全基因后,所有个体长度将会相等,均为初始具有最多基因数量个体的长度.补全基因后个体将进入优化操作.本文采用的是差分进化[19-21]算法作为优化引擎,其优化操作包括交叉和变异.

其中,交叉算子CR=0.9,sn∈[1,2,···,n]是由每一个个体产生的随机整数.

变异操作指出随机选取种群中两个不同个体,将其与待变异的个体进行合成,得到新的个体.第i个新个体可以由式(13)得到

其中,zr1,zr2和zr3是3 个随机产生的个体,并且,变异算子F=0.5.

步骤4.适应度计算(删除冗余基因、解码)

经过交叉,变异操作后的个体中的基因已经得到优化,在进行适应度计算之前需要首先根据每个个体最后一位标志初始长度的基因K删除在步骤3 中添加的冗余基因,换言之,只有与初始BRB 相关的基因才会进入适应度计算当中,步骤3 中添加的冗余基因不参与适应度计算,如图4 所示.

图4 删除冗余基因Fig.4 Remove redundant genes

删除冗余基因之后,根据基因编码方案对剩余个体的基因进行解码操作,然后进入适应度计算,包括输入信息与前提属性的匹配度计算,规则激活权重计算以及激活规则集成(见第1.2 节).

步骤5.选择

通过比较个体的适应度值,选择适应度值最小的个体作为最优个体作.在选择适应度值的过程中,个体适应度值的比较仅局限于具有相同长度的个体或者具有相同规则数量的BRB.最终的最优个体是由不同规则数量的BRB 组成,而不是由特定数量规则的BRB 组成.

对于第i个个体,选择个体的适应度函数获得更低的额定值作为下一代.

其中,f(·)是适应度函数,本文中是指均方差(Mean square error,MSE).

步骤6.权衡分析

在选择最优的个体之后,利用具有不同规则数量的最优BRB 导出帕累托前沿,通过考虑决策者的偏好和具体要求,进行权衡分析以产生最优解.

图5 说明了具有两个属性(x1,x2)问题的权衡分析概念[23].图5 表示包含两个属性(x1,x2)的帕累托前沿;Ⅰ点表示偏好x2的情况下决策者选择的解决方案;Ⅱ点表示偏好x1的情况下决策者选择的解决方案.

图5 权衡分析Fig.5 Tradeoff analysis

4 案例分析

本节以输油管道泄漏检测为例,验证本文中所提出方法的有效性.已知可以根据输油管道进出口的流量差(FlowDiff)和压力差(PressureDiff)推断出输油管道的泄漏尺寸值(Leaksize).流量差和压力差是检测管道中是否存在泄露并且与泄漏尺寸相关的两个重要属性.因此选择流量差和压力差作为BRB 的前提属性,泄露尺寸作为输出结果.为了便于对比分析,本文采用现有BRB 相关文献中多次使用的实验数据[9-10,24],该数据共包括从英国北部某地采集得到的2008 组输油管道泄露数据.

为了与当前方法的进行公平比较,BRB 的参数设置与当前方法保持一致.首先构建BRB 的模型,BRB 采用5 个评估等级评估管道泄漏情况,其效用值分别为

前提属性流量差FlowDiff∈[－10,2],压力差PressureDiff∈[－0.02, 0.04].

本文研究的主要目的是实现BRB 结构和参数的同时优化,平行多种群与冗余基因策略适用于演化算法,如差分进化算法(DE),遗传算法(GA),粒子群算法(PSO)等.在众多优化算法中,DE 算法取得了较好的优势,即其具有优化效率高,求解速度快且不易陷入局部最优解等优点.因此本文采用DE 作为BRB 结构与参数优化模型的求解算法,为了与当前方法进行比较,DE 优化算法的参数值和当前方法使用的参数值一致,其设置如下:

1)BRB 中规则数量取值范围为3～8 条;

2)优化算法中个体数量设定为100;迭代次数为1 000 代;

3)交叉率和突变率设值为0.8 和0.8;

4)算法共运行30 次以验证平行多种群与冗余基因策略方法的稳定性.

表1 给出了算法运行30 次之后具有不同数量规则的BRB 统计结果.通过表1 可以发现,当规则数量为3～8 条时,不同BRB 的最小值/平均值都远小于其方差(小一个数量级),这说明本文提出的方法具有较好的稳定性.

图6 进一步给出了本文提出方法在1 000代优化过程中帕累托前沿的优化过程.

通过表1 以及图6,可以得出以下结论:

图6 帕累托前沿的优化过程Fig.6 Optimal process of the Pareto frontier

表1 运行30 次的数据结果Table 1 Statistics of 30 runs

1)在1 000 代的优化过程中,帕累托前沿不断向前推进;

2)当优化至100 代时(见图6(b)),具有不同数量规则的BRB 实际上已经达到了比较稳定的可行解;

3)规则数量(即参数数量)对优化结果具有一定影响.当优化到100 代时,由于规则数量较多的BRB 的参数数量较多,此时具有6/7/8 条规则的BRB 并未取得较优解,也未在帕累托前沿上;

4)决策者可以根据自身偏好在帕累托前沿上选择最优BRB.当不考虑偏好时,具有5 条规则BRB具有明显优势,其MSE 明显小于前者,而后续随着规则数量增加,MSE 也并未明显大幅下降,即具有5 条规则的BRB 处于拐点(Elbow point)[25].

表2 给出了具有5 条规则的BRB,图7 给出了模型预测结果与真实值之间的对比以及误差.

表2 具有5 条规则的最优BRB 参数Table 2 Optimal BRB parameters with five rules

图7 输油管道泄漏检测结果与误差对比Fig.7 Pipeline leak detection test results and error comparison

表3 进一步对比了本文所得结果与已有文献中针对该示例的计算结果.通过对比,可以发现:

表3 基于不同BRB 优化方法的实验结果对比分析Table 3 Comparative analysis of experimental results based on different BRB optimization methods

1)与已有仅开展参数学习的研究[9-10,24]相比,根据不同的优化模型,BRB 参数学习的优化参数数量为336～349.其模型误差MSE 均处于较高水平.文献[6]提出动态优化方法,该方法涉及到的优化参数个数从349 降到39.其在降低建模复杂度方面与上述3 种方法相比取得了较好的结果.而本文采用的并行多种群与冗余基因策略的方法取得的模型误差MSE 更小,即本文提出方法相对参数学习具有优势.

2)本文所得结果稍劣于BRB 联合优化方法[14]所得到的结果.原因在于:BRB 联合优化方法属于迭代方法,即在对BRB 参数进行优化时,并不优化其结构,而本文提出的方法在一次优化过程中同时实现对BRB 结构和参数的优化.换言之,在给定资源条件下,BRB 联合优化仍然仅优化其参数(这是由其迭代优化的本质决定的),而本文所提出方法可以同时实现对BRB 结构与参数.在这种情况下,本文提出方法仍能取得与当前最优解(0.267 9)十分接近的结果(0.292 1)验证了本文提出方法的有效性.

3)相比BRB 联合优化方法,本文的另一优势在于最终产生的结果以帕累托前沿的形式表示出来,决策者既可以根据自身需求或问题特点在帕累托前沿上选择恰当的最优解,又可以在不考虑偏好的情况下,根据拐点原则通过权衡分析选择无偏最优解.

5 结束语

为了实现对置信规则库结构和参数同时优化的目的,本文提出一种基于并行多种群与冗余基因策略的置信规则库优化方法.通过输油管道泄漏检测的例子验证本文所提出方法的有效性.主要结论如下:

首先,通过并行多种群策略,具有不同规则数量的BRB 可以同时进入优化操作,因此可以同时优化BRB 的结构和参数.然后,通过提出冗余基因策略,具有不同长度的个体(BRB 具有不同的规则数量)可以进行交叉变异操作.只有与初始BRB 相关的基因才会进入适应度计算当中.最后,输油管道泄漏检测的例子结果表明,基于并行多种群与冗余基因策略的置信规则库优化方法可以同时优化具有不同规则数量的多个BRB,随着BRB 的优化,帕累托前沿不断向前推进.最后可以通过拐点原则识别最佳BRB,也可以根据决策者的偏好来决定最佳BRB.下一步工作,需要对优化算法引擎展开进一步的研究.优化算法引擎需要大量的参数,这将导致优化效率下降.所以迫切需要找到更好的优化技术去解决这些问题.此外,还应当在更多理论和实际问题中对本文提出方法进行验证.