王丽丽， 王 伟2， 单光兴2， 万 贺

(1.北京交通大学 机械与电子控制工程学院，北京 100044； 2.北京航天自动控制研究所，北京 100854)

科技发展所带来的电子系统的结构和功能越来越复杂，信息处理系统复杂的结构和功能使其故障模式呈现出多样性的特点，为了提高其维护检修性能，一般会设计多个测试，在实际测试中可能只需要执行所有测试中的一部分测试就能满足系统故障检测率和故障隔离率等测试性指标[1]。设计的测试项需要进行优化选择，即选择最少的测试项对系统的所有故障进行检测和隔离。所以，设计合理高效的信息处理系统测试优化选择的算法是非常有必要的。本文旨在遗传算法的思想基础上，采取若干有效措施，对遗传算法进行改进，使其能够更好地解决系统的测试优化选择问题，最后通过计算故障检测率和隔离率来验证结果的可靠性。

1 测试优化选择问题数学模型

1.1 问题的描述

根据已经建立的信息处理系统多信号流图模型，计算系统故障-测试相关矩阵，然后基于系统的相关矩阵进行测试优化选择问题研究。

首先根据多信号流图模型的建立方法和步骤，分析信息处理系统的各模型组成元素，最终得到系统的多信号流图模型如图1所示。

图1 信息处理系统的多信号流图模型

由图1，利用图2介绍的方法，计算相关矩阵，进而得到系统的故障-测试相关矩阵如表1所示。

图2 系统相关矩阵的计算流程图

t1t2t3t4t5t6t7t8t9t10t11C1(F)10000000000C2(F)01000000000C3(F)00100000000C4(F)00010000000C5(G)00001000000C6(G)00000100000C7(F)00000010000C8(F)00000001000C9(F)00000000100C10(F)00000000110C11(F)00000001001C12(G)01011111000

表1中行向量表示信息处流系统中可能发生的故障，C(F)表示功能故障模式，C(G)表示完全故障模式；列向量分别表示针对系统的故障源设计的测试。本文的目的就是对这些测试项进行优化选择，期望在系统发生故障时，以最少的测试项对系统故障进行检测和隔离，使产生的测试代价最小。

1.2 测试性指标的计算

系统的测试性能指标不仅包括故障检测率，还包括故障隔离率；基于系统的故障-测试相关矩阵，具体计算方法如下：

① 一般地，用FDR表示故障检测率，计算公式为[2]

(1)

式中，M为非0行的总和；N为所有行的总数。

② 一般地，用FIR表示故障检测率，计算公式为[2]

(2)

式中，m为相关矩阵中故障行的总数；n为所有行的总数。

2 改进的遗传算法

针对测试优化选择问题，目前已经有很多种方法,包括遗传算法、BP神经网络、模拟退火算法，以及对这些算法的融合算法[2]，综合分析已有的这些算法的特点，结合信息处理系统，在传统的遗传算法的思想基础上通过编写C++程序，应用改进的遗传算法选择出了符合测试指标的全局优化测试集合。

2.1 传统的遗传算法的原理

2.1.1 传统的遗传算法的原理

传统的遗传算法(Genetic Algorithm，GA)是一种通过模拟自然进化过程搜索最优解的方法[3]。其算法流程图如图3所示。

图3 算法流程图

2.1.2 传统的遗传算法的特点

与其他测试选择算法相比，遗传算法在求解优化问题上有其自身的优点和成功应用的例子，取得了良好的效果。所选择遗传算法的理由主要有以下几个方面。

① 唯有遗传算法可进行全局搜索，即可对搜索过程中的多个解同时评价分析，这样就可一次性处理多个个体，效率明显提高[4]。

② 群体中个体优劣的评判标准仅由适应度函数来决定，不需要外力。

③ 搜索方式采用启发式，随机去搜索，并没有明确的规定。

④ 遗传算法除以上优势之外，其最大的优势还在于：很多复杂的现象均通过进化机制来实现；在解决复杂问题的时候，快速性和准确率都很高。

基于以上所述，选用遗传算法，并对其进行改进。

2.2 改进的遗传算法的原理

针对传统的遗传算法存在容易陷入局部最优解和交叉、变异导致个体失效等问题，对传统的遗传算法进行改进。

2.2.1 改进的遗传算法的原理

初始种群的优劣决定遗传算法的收敛性。对于在其阈值范围内有多个极值的函数而言，往往会存在随机生成集中在特定范围的初始变量，打破了均匀性，从而算法极易陷入局部最优解[5]。另外，传统的遗传算法在进行交叉时，会对处于劣势的个体的基因序列进行改变，这种改变提高了进化过程中优良个体出现的概率，即会通过交叉出现更优的测试集,但同时也会导致基因片段交叉后出现基因编码相同致使个体失效的情况，导致所选取的整个测试集合在实际应用中没有意义。改进的遗传算法执行过程如图4所示。

图4 信息处理系统遗传算法程序流程图

2.2.2 具体的改进措施

针对以上提出的关于传统的遗传算法存在容易陷入局部最优解和交叉变异导致个体失效等问题，对传统的遗传算法的具体的改进措施主要有以下几点。

(1) 选择合适的种群规模。若规模太小的话，则种群的进化速度会受到影响，这样就极易导致陷入局部最优解的错误之中；但是如果规模太大的话，程序的运算量就会加大，进化速度随之减慢。为了兼顾以上两点，最终选取种群规模为50个，即对包含50个测试集合的群体进行研究，使算法依托于编写好的C++程序运行，进行多次测试，均能快速高效得到最优解[2]。

(2) 初始化时，保证每一个基因都拥有不同的编码方式，也就是本文在初始化时通过程序的限制，使每个个体的的基因序列不同。因为采用了实数的编码方式对个体基因进行编码，也就是一个个体就是一个测试集合，个体的基因序列就是真实的测试项目，如果个体一旦出现了相同的基因序列，那么就相当于测试集合中有了相同的测试项目，这在实际情况中就意味着个体没有意义，这种情况有可能导致产生局部最优解，因此，通过改进遗传算法，保证每一个基因的编码均不相同，不但避免了产生局部最优解的问题，而且算法的搜索空间也被扩张了，使算法的效率更高、运行时间更短。

(3) 改进的遗传算法中先用冒泡排序按照个体的适应度函数值进行从大到小排列，然后将最优的两个个体的基因片段交叉替换给最差的两个个体的等位基因片段；提高了出现更优的测试集的可能性[6]。

但是交叉还有一个弊端，就是交叉后可能导致个体基因出现相同的基因编码机制，从而使个体失效，由前述可知，改进的遗传算法则会随机变异，直到交叉后的个体没有相同编码机制的基因，从而加速进化。

(4) 其最优个体保护机制，该机制的添加有两方面的作用：一方面，为了使个体不因产生相同基因而失效；另一方面，为了规避优秀的个体因变异变成处于劣势的个体，通过改进遗传算法，不让最优个体参与种群的变异[2]。

(5) 设计特殊的适应度函数。

在传统的遗传算法适应度函数中加入故障检测率、故障隔离率，使得对个体优劣程度的评价更加全面可靠，适应度函数为

(3)

式中，Ci为ti的测试代价。

①hi为ti的评估函数值，计算公式为

(4)

其中，d(ti)为ti中检测到的故障数；k(ti)为所有故障的最小可测度[6]。

由综合故障-测试相关矩阵及式(3)可以看出，测试的评估函数值变化趋势与测试的重要性变化趋势一致，并且适应度函数与评估函数是正相关，从而证明了适应度函数的正确有效性。

②S(Ts)的计算公式为

(5)

式中，D为能检测到的系统故障检测率；I为能检测到的系统障隔离率[7-10]。

3 仿真和验证

3.1 仿真工具

利用C++语言将改进的遗传算法集成到软件中，用于信息处理系统测试优化选择。开发的软件界面如图5所示，该软件通过人机交互界面实时显示算法的运算过程和结果。

图5 信息处理系统测试性优化算法软件界面

3.2 实验验证

3.2.1 改进的遗传算法有效性验证

在算法中分别设定不同的个数进行运算，统计运行的结果如表2所示。为了方便统计，将表中的测试按照从t1～t12的顺序重新编号。

表2 不同测试项个数算法运行结果统计

当测试项的个数确定时，将表2的统计结果绘制成图6所示的折线图会更加直观。

图6 不同测试项个数算法优选测试集的测试性指标

图6中，从图中可以看出，当设定9个或者10个测试项时，尽管故障检测率达到了100%，但系统无法清晰地对所有故障定位并且隔离，有11个测试项时既实现了测试项个数最少，又达到了系统测试性指标。

从11个测试中选择全局优化测试集为{t1,t2,t3,t4,t5,t6,t7,t8,t9,t10,t11,t12}。软件运行结果如图7所示。

图7 遗传算法程序运行结果

从图7中可以看出系统的测试性指标均为百分之百，符合实际要求，进而说明改进的遗传算法在测试选择优化问题上的正确性。

算法优选出的测试集如表3所示，其中灰色部分是算法优选掉的测试项。

表3 遗传算法选择的测试集合

对表3做进一步分析，得表3中所有行均无全0行，也就是说实验过程中不存在没有检测到的故障，检测的覆盖率为没有未检测故障，即检测的覆盖率为100%；且同一行之中列与列均不同；也就是说所有故障都能清晰地被隔离，系统的故障隔离率为100%。进一步说明所设计的遗传算法在测试选择优化问题上的有效性。

3.2.2 传统的遗传算法与改进的遗传算法比较

在编写好的C++程序中注释掉限制每一个基因编码都不相同机制、个体失效保护机制、最优个体保护机制等，得到传统的遗传算法思想下测试集合的选择策略，与改进后的选择策略形成对比组，依托于测试软件，分别对这两种算法进行20次试验。

表4列出了没有改进和改进之后测试集合优化结果，利用测试序列中有无重复的测试项来判断测试选择过程是否陷入局部最优解和个体失效情况，如果有重复的测试项目就在表中计为1，无重复的测试项目就记为0。

从表4中的数据可以看出，20次实验中，没有改进之前的遗传算法选择出的测试集合虽然都满足测试性能指标，但是选择出的测试序列有20次是失效的，对于实际没有任何指导意义，是无效的，改进之后的遗传算法选出来的测试集合不但满足测试性能指标，且没有重复的测试项，对实际应用有很重要的指导意义。

该实验进一步说明针对传统的遗传算法存在容易陷入局部最优解和交叉变异导致个体失效等问题，本文对传统的遗传算法的改进是可靠有效的。

表4 传统的遗传算法与改进的遗传算法个体失效的比较

4 结束语

本文在建立信息处理系统数学模型的基础上，改进了传统的遗传算法，使其高效、快速、准确地得到信息处理系统的全局优化测试集，通过计算测试项指标和实验验证了改进的遗传算法的有效性和正确性。