第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]首次提出了带精 英策略的快速非支配排序遗传算法 (简称 NSGA￾II)，该方法是众多求解多目标优化问题方法中应用 最为广泛的一种。NSGA-II 算法是非支配排序遗传 算法 (non-dominated sorting genetic algorithm, NSGA) 的改进，运行速度更快，复杂度更低，且其求 解的 Pareto 最优解集收敛性更好。算法首先随机产 生一定规模数量的初始种群，然后利用非支配排序 方法对种群中所有个体进行分层，接着执行遗传算 法的选择、交叉和变异 3 个操作产生第一代子群。 从第二代子群开始，先将父代种群和子代种群中所 有个体合并在一起，然后利用快速非支配排序方法 对其进行分层，并计算每个非支配分层中所有个体 的拥挤距离，在此基础上从中选出较优的个体组成 新的父代种群，接着执行遗传算法的选择、交叉和 变异 3 个操作产生下一代子群，直至达到程序结束 条件时终止，算法的具体流程如图 1 所示。 第 3 期 林燕清，等：基于 NSGA-II 的扩展置信规则库激活规则多目标优化方法 ·425·