基于离散蝙蝠算法的舰船作战系统测试性分析

范苗，许一川，谢定君，彭辉

1中国舰船研究设计中心，湖北武汉430064

2武汉大学电气工程学院，湖北武汉430072

0 引 言

测试性作为装备的一种设计特性，是构成武器装备质量特性的重要组成部分。优良的测试性设计可以提高装备的战备完好性、任务成功性和安全性，减少维修人力和其他保障资源，降低全寿期费用［1］。测试集优化以及测试序列求解是测试性分析的重要研究内容，其正确性和诊断能力的优劣将直接影响到装备维修保障的效率。

对舰船作战系统而言，系统级测试是指针对任务通道的测试，目的是验证作战系统的功能与性能是否满足技术规格书的定义，用以为故障诊断提供信息。目前，舰船作战系统所应用的测试性分析方案主要源自专家经验或启发式函数。随着舰船武器系统的复杂性和集成性的不断提高，舰船设备单元的层级和数量也在大量增加，因此难以保证诊断策略的正确性和优化精度。同时，人工手动测试方法耗时长、测试序列重复度高，其相应的测试性分析结果已无法满足现代舰船系统的维护效率要求。因此，研究适用于舰船作战系统的高效、准确的测试性分析方案以及实用化的工具与技术手段，已成为海军舰船装备能力发展亟待解决的问题。

测试集优化和测试序列求解是测试性分析的关键内容，在减少冗余测试、提高故障检测率和故障隔离率、降低期望测试代价等方面具有重要意义，其正确性和诊断能力的优劣将直接影响装备维修保障的效率。在测试集优化的相关研究中，有关学者提出了基于蚁群算法［2］、Rollout算法［3］、多目标离散粒子群算法［4］、模拟退火算法［5］的优化方案，其中前2种方法存在优化目标单一、优化精度不高等缺点，后2种方法存在初始搜索空间较为庞大、因适应度函数构造不唯一导致的搜索效率较低等问题。而测试序列优化是NP完全问题（Non-deterministic Polynomial complete problem），即在测试集优化的前提下，寻求测试代价最小的诊断策略［6］。为此，Shakeri等［7］提出了基于信息理论概念和启发式函数的AO*算法，即通过启发式评估函数计算各候选测试的优先程度，自顶而下扩展诊断树节点并同时向上回溯修正。在此基础上，相关学者提出了改进信息熵算法以及一步前向回溯的Rollout算法［8］等改进方案，其通过缩小待扩展节点范围、减少回溯次数来降低原有AO*算法的计算复杂度。然而，这些方法仍然存在高效启发式评价函数的选取问题以及不能保证获得全局最优解的问题。在智能算法方面，基于混合粒子群算法和蚁群算法［9］的优化方案已被成功用于求解最优诊断策略。由于适应度函数直接由测试序列所对应的测试代价构造，其优化精度较高、算法运行时间较长，故适用于对计算实时性要求不高的测试性分析。

鉴此，本文将首先通过评估舰船作战系统初始相关性矩阵的隔离能力，确定最小完备测试集所包含的测试数目，构造唯一的适应度函数，从而采用离散蝙蝠算法实现测试集的优化工作；然后，将对优化结果采用离散蝙蝠算法，得到比其他算法平均期望测试代价更小的测试序列，用以为测试性分析方案提供新的思路。

1 舰船作战系统的测试性建模

舰船作战系统是通过警戒、跟踪、目标识别、数据处理、威胁估计以及控制武器实现对敌作战功能的各要素综合体［10］。作为舰船的核心，作战系统集成了大量的先进电子武器装备［11］，包括雷达系统、作战指挥系统、武器系统和综合通信系统等分系统。本文将采用以多信号流图模型为基础的测试性建模理论，选取作战系统中较为典型的故障模式来表述各故障模式之间的关联并进行测试性的初步分析。1994年，美国康涅狄格大学的Pattipati教授和Somnath教授提出了多信号流图模型。该方法基于研究对象的结构和功能，以分层有向图的形式来表示信号流向与各功能单元之间的连接关系，即通过定义信号与组成单元所包含的故障模式、测试点所包含的测试信息，来表示系统组成、故障、信号以及测试点之间相关性的一种模型化表示方法［12］。

多信号流图模型的主要建模过程［12］如下：

1）熟悉建模对象，明确系统的组成结构，识别和提取模型信息，主要包括系统各组成单元和功能单元的输入/输出信号、故障模式、故障率信息和测试信息等。

2）构建多信号流图模型。首先，根据系统组成建立系统的结构模型（原理图或概念框图）；然后，将功能信号添加至系统各组成单元，并根据信号流向确定组成单元的输入、输出以及各单元之间的连接关系，从而建立有向图；最后，添加测试点位置以及测试点所包含的测试信息，并设置模型中各节点的属性。

3）对模型的测试性能进行初步评估，并结合工程实际对模型进行调整、校验和修改。

本文利用TesLab软件提供的测试性建模与分析工具，对系统的测试性水平进行分析和评估，并选取20种典型的故障模式来完成舰船作战系统的多信号流图建模。故障模式模型和相关性矩阵分别如图1和表1所示。表1中，F0为无故障状态，F1～F20分别为图1中的20种故障模式，t1～t18为测试性建模过程中初步选定的测试方案。表1中的故障概率数据来源于各二级系统的设计数据以及装备实际应用的统计数据（本文中数据仅为示例，并非实船数据）。

图1 舰船作战系统的故障模式模型图Fig.1 Illustration model of ship combat system failure mode

表1 故障—测试的依赖关系矩阵Table 1 Dependency matrix of fault-test

2 离散蝙蝠算法

2010年，提出了一种新的元启发式算法，即蝙蝠算法［13］（Bat Algorithm，BA），其优化机理是模拟自然界微型蝙蝠躲避障碍物并寻找目标的回声定位原理。针对这种已成功应用于连续域函数优化问题的随机搜索优化算法，为了对其进行改进以解决组合优化问题，文献［14-16］以旅行商（TSP）问题为例提出了离散蝙蝠算法（Discrete Bat Algorithm，DBA），仿真结果表明离散蝙蝠算法在寻优能力、偏差率、收敛率、时间耗费等指标上的优势远超其他传统算法。由于测试性分析中的测试序列优化问题仅与旅行商问题的目标函数不同，因此可以采用DBA来完成测试执行顺序的优化求解，并可将该方法应用于测试集优化问题。

在离散蝙蝠算法中，每个蝙蝠的位置表示待优化问题的一个可行解。对于种群规模为m的蝙蝠而言，蝙蝠个体i（i=1，2，…，m）发出声波的频率f(i)为

式中：fmax，fmin分别为声波频率的最大值和最小值；β∈[0，1]，为随机数。

设蝙蝠个体i在t时刻的速度矩阵和位置向量分别为vt(i)，xt(i)，则蝙蝠个体i在t+1时刻的速度vt+1(i)和位置xt+1(i)为：

式中：x*为t时刻搜索过程中蝙蝠的全局最优位置向量。

式（2）中，向量xt(i)与向量x*的差值定义如下：

设xt(i)=(x1，x2，…，xn)，x*=(x*1，x*2，…，x*n)，其中n为蝙蝠搜索空间的维度；设vd为第i个蝙蝠的位置差，初始化矩阵vd为空集。逐一检查xt(i)，x*的每个分量，若xn-x*n≠0 ，则将向量 (xn，x*n)作为矩阵vd的第1列，并以此方式逐列叠加。

式（2）中，vt+1(i)的定义如下：

设速度向量vt(i)为n×2的整数矩阵，且矩阵元 素 为 1～n 的 自 然 数 ；设v=vt(i)∪vd，l=round[f(i)·n)]+1，其中round函数表示向下取整。从矩阵v中随机抽取l行，即可得到蝙蝠个体i在t+1时刻的速度向量vt+1(i)。

式（3）中，xt+1(i)的定义如下：

根据式（2）可知vt+1(i)为l×2的矩阵，设矩阵vt+1(i)中第1列元素为p和q，交换向量xt(i)中第p个元素和第q个元素的位置，如此逐列操作直至vt+1(i)的第l列，即可得到t+1时刻蝙蝠个体i的位置向量xt+1(i)。

在获取目标的过程中，为了均衡局部搜索和全局搜索，蝙蝠需要调节发射声波的响度和频率。设蝙蝠个体i在t时刻发出声波的响度为At，初始声波响度为A0，脉冲发射速率为rt，则蝙蝠个体i在t+1时刻的声波响度At+1和脉冲发射速率rt+1为：

式中：α∈[0，1]，为声波响度增强系数；r0为初始脉冲发射速率；γ为脉冲发射速率衰减系数，是一个常量。

局部搜索的主要步骤如下：

1）在［0，1］范围内生成一个随机数rand1，判断rand1＞rt是否成立。若成立，则对当前位置施加随机扰动，得到新解xnew，并计算新解的函数适应值fitness(xnew)，其中fitness为适应度函数。

2）在［0，1］范围内生成另一个随机数rand2，判断rand2＞At和fitness(xnew)＜fitness[xt(i)]是否同时成立。如果成立，则接受新解xnew，同时按照式（4）和式（5）更新At和rt。

3）重复上述步骤不断更新蝙蝠位置向量，直至达到最大迭代次数并输出最优解。

3 测试集优化

首先，通过建立系统的多信号流图模型来得到相关性矩阵；然后，合并模糊组并删除冗余测试。以构建诊断用测试集为例，测试集优化的目的是找到满足系统所要求故障隔离率的测试集，并在满足最大故障隔离率的条件下令测试集中的测试数目最少、测试代价最低，其中所优化的目标按重要性依次为最大故障隔离数、最小测试数目和最低平均测试代价。对于n维蝙蝠搜索空间，初始测试集中的测试数目即为n。本文采用二进制编码来表示相应测试的选取操作，其中编码1表示选取相应序号的测试，编码0表示不选取相应序号的测试。

3.1 最小测试数目

在测试集寻优过程中，为减少离散蝙蝠算法的迭代次数，首先需要确定最优测试集中所包含的测试数量。通过分析系统初始相关性矩阵，可以得到所设计的测试集合能隔离的最大故障数目Imax。理论上，n个测试的最大故障隔离数为2n，当2n＜Imax时，所选择的测试数目不可能使系统故障隔离率最大，故需添加测试数目再次进行测试性分析。

本文采用链长为1的模拟退火方式，按概率接受对测试进行扰动后的故障隔离数目。采用的扰动方式为三变换法，即任选序号U，V，W(U＜V＜W≤n)，将序号U，V及其之间的二进制编码插入序号W之后。同时，与传统优化问题中为避免陷入局部最优而进行的局部搜索步骤不同，该算法的最大故障隔离数目已经确定，因此当找到最优解后无需再添加随机扰动，直接输出测试数目即可。求解最小测试数目的流程如图2所示。其中：N为采用信息熵算法求得的最优完备测试集中所包含的测试数目，用以防止算法避开最优解；I1为随机抽取产生的测试集的故障隔离数目；I2为扰动后所选取测试集的故障隔离数目；e为经测试集优化后所得的最小完备测试集中的测试数目。

图2 确定最小测试数目的实现流程图Fig.2 The realization flow chart for determining the minimum number of tests

3.2 基于离散蝙蝠算法的测试集优化

确定最小完备测试集的测试数目之后，需要构造合理的适应度函数并依据重要性来优化故障隔离数目和平均测试代价。本文采用统一的适应度函数以避免使用条件嵌套语句，从而减少程序的运行时间。

式中：cmax为所选的测试代价列向量中n个最大测试代价之和；cmin为所选的测试代价列向量中n个最小测试代价之和；X为使不等式成立的任一正实数。

为了优先考虑所选测试的故障隔离能力，式（6）实际上表示了2种最不理想的情况：一是故障隔离数目和平均测试代价同时达到最大；二是故障隔离数目第2大，平均测试代价最小。当找到合适的X值时，适应度函数可以简化为

式中：fitness[xt(i)]为适应度函数值；I为所选测试集的故障隔离数目；C为测试代价列向量。

采用离散蝙蝠算法时，由于二进制编码中蝙蝠位置向量的减法操作与TSP问题有所不同，故需要对第2节中关于蝙蝠位置向量差的操作进行重新定义。设第i个蝙蝠的位置向量为xi=(x1，x2，…，xn)，当前全局最优的蝙蝠位置向量为x*=(x*1，x*2，…，x*n)。定义第 i个蝙蝠位置向量的减法操作为：分别记录向量xi和x*每个分量中编码为0的序号集合矩阵xi0和x*0，则第i个蝙蝠的位置向量差为vd=[xi0；x*0]'。同时，在初始解空间中加入确定最小测试数目过程中最终输出的蝙蝠位置向量，以进一步避免算法陷入局部最优，而其他操作定义、算子设计和算法步骤则与基本离散蝙蝠算法保持一致。

3.3 仿真对比分析

本文将以舰船作战系统测试性模型为研究对象，对初始测试集进行优化。优化算法中的相关参数为：在确定最小测试数目的算法中，设初始温度T0=1，降温速率为0.99，终止温度为6.6×10-3。在离散蝙蝠算法中，设蝙蝠种群规模m=10，fmin=0，fmax=1，A0=1.6，r0=0.000 1。由于测试集优化问题的复杂度较低，α和γ的取值对优化结果的影响很小，所以根据经验取α=0.9，γ=0.9，迭代次数Maxgen=100。将基于离散蝙蝠算法的测试集优化结果分别与混合粒子群—遗传算法（HPSOGA）、改进离散粒子群优化（DPSO）算法、信息熵算法、Rollout算法、蚁群优化（ACO）算法、最大/最小蚁群优化（MMACO）算法和模拟退火算法（SAA）进行比较，对各算法分别运行50次，仿真结果取平均值。其中各算法迭代次数与本文算法保持一致，均为150。

期望测试代价统一采用离散蝙蝠算法，迭代次数为Maxgen'=300。优化过程中的相关统计指标如表2所示。

从仿真结果可知，与其他主流算法相比，本文采用的优化算法在平均故障隔离数、平均测试个数、期望测试代价和最优比例方面均取得了更为理想的结果。其中故障隔离率最多可提高5.5%，平均测试个数、平均测试代价最多可分别下降1.4%和6.35%，达到最优的比例可增至86%。同时，在群智能优化算法中，本文算法的平均收敛时间也较短。仿真结果表明，本文算法可以成功应用于测试集优化问题。

4 测试序列优化

4.1 优化问题描述

在仅考虑发生单一故障的前提下，得到相关性矩阵并对测试集优化后，需要根据可靠性求解测试代价最优的诊断策略。其中，各组成单元的可靠性数据（故障率或故障概率）可从可靠性设计分析资料中获取，而与测试相关的代价则应考虑测试时间、测试点设计费、研制费用和实施测试所需的费用等。因此，测试序列优化的目标即令隔离系统故障状态所需的总期望测试费用J最小，其适应度函数为

表2 诊断测试集优化结果比较Table 2 Comparison of test set optimization for fault diagnosis

式中：P为故障概率向量；I为故障隔离矩阵［17］；a为故障模式数量；b为故障模式序号，b=0，为隔离故障模式Fb所需的测试序列pb的长度；j为测试序列pb的测试序号，j=1，2，…，；为pb所对应测试序号j的代价值；p(Fb)为故障模式Fb发生的概率。

在测试性设计工程中，测试序列优化的目的是找到一组合适的测试执行顺序，使得期望测试费用最低，用以为装备维修保障提供支撑。

4.2 算法基本步骤

基于离散蝙蝠算法的测试序列优化的基本步骤如下：

1）设蝙蝠种群的规模为m，随机生成初始蝙蝠位置集合S，采用反向学习机制求出反向的蝙蝠位置集合S*。根据适应值大小对集合S，S*中的位置进行优劣排序，取适应度函数值前m位的蝙蝠位置作为初始解集。通过将初始解较为均匀地集中在优质解区域中，可以在保证优化精度的同时减少算法运行时间。

2）参数初始化。设置初始脉冲发射频率r0、初始声波响度A0、声波频率的最大值fmax和最小值fmin、声波响度增强系数α、脉冲发射速率衰减系数γ、算法迭代次数Maxgen。设随机生成的第i个蝙蝠速度初始矩阵为v0(i)，其中v0(i)是维度为n×2的矩阵，其元素取值范围为自然数1～n。

3）按照式（2）和式（3）分别更新每个蝙蝠的速度与位置。

4）在［0，1］范围内生成一个随机数rand1，判断rand1＞rt是否成立。若成立，则对当前位置采用3变换法施加随机扰动，产生新解xnew，并计算新解对应的函数适应值fitness(xnew)。

5）在［0，1］范围内生成另一个随机数rand2，若rand2＞At且适应度函数满足fitness(xnew)＜fitness[xi]，则接受收步骤 4）中产生的新解xnew，并按式（4）和式（5）更新At和rt。

6）更新当前时刻最优解x*，判断迭代终止条件是否满足。若不满足，则转至步骤3）；若满足，则停止迭代计算过程。

7）输出最优解。

4.3 仿真对比分析

完成测试集优化后，即可采用基于离散蝙蝠算法的优化方案来确定最优测试序列，离散蝙蝠算法的相关参数为：蝙蝠种群规模m=10，fmin=0，fmax=1，A0=1.5，r0=0.000 1，α=0.9，γ=0.99，Maxgen=300。其中参数α和γ的取值由仿真实验确定，分别在0.9～1的范围内每隔0.01取值做100组实验。仿真结果表明，当α=0.9，γ=0.99时，算法运行结果最优。将基于离散蝙蝠算法的优化结果分别与基于信息熵、改进信息熵方案、Rollout算法、HPSO算法、ACO算法、MMA⁃CO算法进行对比，对各智能算法分别运行50次，其平均期望测试代价、最优期望测试代价、最优测试序列结果、算法平均收敛时间、平均偏差和收敛率指标的对比结果如表3所示。其中，平均偏差为算法的最终运算结果与其最优结果之差的平均值，收敛率为算法运行结果成功收敛至本算法最优期望测试代价的比例。

表3 测试序列优化结果对比Table 3 Comparison of test sequence optimization

由表3可知，与其他算法相比，基于离散蝙蝠算法的测试序列优化结果所需的期望测试代价最多可以降低17.01%，且平均期望测试代价最低，平均收敛速度在智能算法中最快，证明了离散蝙蝠算法应用于测试序列优化问题的优势，但离散蝙蝠算法在收敛率方面仍有一定的改进空间。另一方面，与信息熵算法、改进信息熵算法、Rollout算法相比，群智能优化算法用时较长，考虑到本文算法仅应用于测试性设计阶段而非故障的实时隔离诊断阶段，为了获得优化精度更高的结果，所以对算法的时间要求较低。由离散蝙蝠算法确定的最优测试序列所构成的系统诊断策略优化过程如图3所示。

图3 基于离散蝙蝠算法优化的诊断策略Fig.3 Optimizing strategy of fault diagnosis based on discrete bat algorithm optimization

5 结 语

本文采用基于离散蝙蝠算法的优化方案，完成了对舰船作战系统测试性分析中测试集优化和测试序列优化问题的求解，为系统的测试诊断和功能验证提供了新的研究思路。同时，该方法较为简单，可以推广至其他武器装备系统的测试性工程应用中。通过在设计阶段提高测试性分析的优化精度，可对武器装备系统测试性模型的改进和后期的维修保障工作提供更高效的指导。然而，随着测试规模的进一步增加，采用群智能优化算法进行测试性分析时需要以大量的算法运行时间为代价才能获得更高的优化精度，这将为测试性设计工作带来不便。但随着测试手段智能化水平的不断提升，可以结合数据分析对测试信息进行收集、处理，并通过初步确定故障范围来合理缩小诊断策略优化设计过程中的测试范围，从而实现优化精度与算法运行时间的平衡，以进一步改善测试性分析方案。