一种基于改进SA-DPSO的装备测试性优化设计方法

王大为，邵志江，张 健，刘泰涞，朱显明

（上海机电工程研究所，上海 201109）

0 引 言

在武器系统地面装备测试性设计的初始阶段，不可避免地会产生故障检测率和隔离率不高、测试冗余的现象。又因其故障模式及影响传播情况复杂、备选测试点数量多，因此进行测试性优化设计的难度较高。通常优化方式都仅将最优的测试效果为目标，即检测率最高或测试代价最小，但这种方式得到的优化方案往往不是最优的。而且，实际装备应用时，源于电子设备自身电路设计以及测试环境，往往会存在诸多限制。在这种情况下如果没有综合考虑测试效果、实施成本，很大可能会导致对机内测试（BIT）的过高要求。因此，装备的测试优化需要综合考虑故障检测率（FDR）、故障隔离率（FIR）指标要求，并尽量减少系统的冗余测试［1-3］。在此基础上尽可能减少测试所带来的成本，如测试设备成本、测试时间、测试费用等因素［4］。考虑多种因素下的效率、代价，综合权衡来对装备测试点进行优选，能够最大程度满足测试指标要求，同时不会造成无法接受的成本，是装备测试性设计的目标。

1 地面装备测试点优化模型建立

1.1 最优完备测试集

测试优化选择的目的在于确定系统的最优完备测试集，定义如下［5-7］：

定义1：如果可供选择的测试集合T={tj}(j=1，2，…，n)满足这样的条件，即测试能够响应系统设计要求，那么就称T是一个完备测试集。

定义2：进一步地，如果在上述的集合T中，不存在真子集能够满足系统的测试性要求，那么就将T视为一个最小完备测试集。

定义3：从成本最优的角度而言，如果在所有的最小完备测试集当中，存在一个集合T，使得系统在此测试方案当中测试代价是最小的，那么T也被视作是一个最优完备测试集。

通过上述的定义，不难理解，开展系统测试性优化设计的目标就是要从完备测试集当中通过特定的方式识别出系统的最优完备测试集。总体而言，整个过程包括三个方面：首先，根据系统初步方案确定初始测试集；然后，依据测试性建模与分析方法确定该集合能否满足系统指标，在此基础上判断其是否为完备测试集，若不是，那么要结合设备自身调整测试方案以增加测试，构造完备测试集；在最小完备测试集当中，利用优化模型，对系统测试效果、测试成本进行综合权衡，找出最优的完备测试集。

1.2 测试性指标参数

系统测试性定量指标故障检测率（FDR）、故障隔离率（FIR），采用故障率λi表征计算公式如式（1）～（2）所示：

式中：λD为可测故障的总故障率；λ为所有故障的总故障率；F为系统中带监测与隔离的故障集合；FD为系统中可测的故障集合；λi为第i个故障的故障率；λL表示可隔离到小于等于L个可更换单元故障的总故障率，其中L为故障隔离模糊度；λLi表示可隔离到小于等于L个可更换单元故障中的第i个故障的故障率；λDi为第i个可测故障的故障率。

1.3 测试代价

通常将测试过程中除测试结果可靠度以外的所有消耗性属性的综合称为测试代价，如：测试时间、测试任务复杂度和测试费用等。对于给定的备选测试集合TS，在满足系统所给定的故障检测率和隔离率要求时，其测试代价可记为

式中：cj表示第j个测试对应的测试代价。

1.4 测试优化数学模型

对于系统初步确定待检测与隔离的故障集合F={fi}(i=1，2，…，m)及测试集合T，可构造相关性矩阵FTm×n={ftij}(i=1，2，…，m；j=1，2，…，n)，在 此基础上，建立故障诊断策略，求解测试性参数（γFD、γFI），结合相应指标约束，求解最优测试方案。优化模型如下：

式中：cj为各项测试成本；Fti表示测试ti可测试的故障集合。

从优化模型中可以看出，测试性优化的约束条件复杂，且变量之间存在较为严重的耦合，是一种典型的集合覆盖问题，属于经典NP-hard，全局最优对于这类问题而言基本是无解的，只能通过局部最优解得到其全局次优解。传统的优化算法求解此类问题难度较大，并且随着装备系统复杂程度的提高以及集合规模的增大，这些算法的复杂程度以及运算开销都呈指数级增长，搜索最优解的能力也有待进一步提高。随着各类智能优化算法的不断涌现，测试性优化设计领域也在尝试应用，其中以粒子群（PSO）算法为代表的集群智能优化算法以其原理简单、易于实现、优化效果明显的优势得到广泛认可［8-9］。

2 基于改进SA-DPSO 的测试优化模型求解

2.1 基于模拟退火的离散粒子群算法改进策略

2.1.1粒子群算法基本原理

粒子群（PSO）是一种用于非线性函数优化的集群智能优化算法，它在解决大规模非线性问题中具有更高的优化效率和更好的优化结果。其数学过程描述如下：

首先确定目标函数当中的自变量的个数，即算法搜索空间中解的维数，设为D，所有粒子总的数目用N来标记，第i个粒子的目标定位用向量xi=(xi1，xi2，…，xiD)来表示，而到某一时间为止，第i个粒子寻找得到的最佳目标位置用向量Pib=(pi1，pi2，…，piD)来表示，整个粒子群当前搜索到的最佳目标位置为Gb=(g1，g2，…，gD)，第i个粒子的位置变化率（即速度）为向量vi=(vi1，vi2，…，viD)，则粒子i的d维速度和位置可按照式（5）～（6）进行迭代更新：

式中：c1、c2均大于零，称作加速系数，表征算法在计算过程中的学习方面能力；r1、r2为［0，1］的随机数。c1主要作用是局部调整变化速率，让粒子不断接近自己的最佳目标位置；c2则是与全局最佳目标位置相关的调整系数，作用是让粒子靠近总体上收敛的那个最佳目标的位置和映射。

算法在每一次迭代求解中，粒子的存活与否和自己与目标函数的映射值息息相关。通过比较更新前后各粒子的映射函数值，对每次迭代粒子集合中的最优目标定位及总体最佳目标定位与映射进行实时替换，一直到符合预先设置的终止条件为止。

与其他群体智能算法相比，PSO 算法优化基本原理通俗简洁，在使用程序中进行计算的难度相对较低。但是在优化过程中同样会面临一些难点，比如在系数固定不变且设置不合理的情况下，非常容易出现在寻找到局部最优解就停止计算、结果不准确、算法运转花费时间长等事倍功半的情况。为此引入惯性权重因子ω，对粒子飞行速度进行调节，提高PSO 算法的收敛速度及总体寻优能力，使其能够快速得到全局最优结果。惯性权重因子ω对速度的调节原理为

由式（7）可以看出，引入的ω代表的含义主要为上一代粒子状态对当前粒子状态的影响程度，ω取值越大，则上一代粒子状态对当前粒子状态的影响越大；反之，影响越小。同时，算法的全局搜索能力也会随着ω的增大而提高。因此，通过控制惯性权重因子ω的大小，可以改进粒子群算法的全局搜索能力。当ω值取为常数1时，式（7）即退化为基本粒子群算法的速度更新公式。

为了进一步提升优化性能，并加快粒子群算法的收敛速度，引入距离控制因子C对惯性权重因子及加速系数进行自适应调整，其原理为

式中：D(t)表示各粒子到全局最优值的平均距离；max（D）表示至今平均距离的最大值；C（t）表示距离控制因子，即各粒子到全局最优点的平均距离与平均距离最大值的比值。

2.1.2离散粒子群算法

标准PSO 算法用来处理连续优化问题，并取得了较好的效果，但是对于离散问题，标准PSO 算法有很大的不方便。为了解决这类问题，离散粒子群优化（DPSO）算法应运而生，能够普遍适用于离散优化问题求解。针对DPSO 算法，给出其离散解值集和离散速度值集的定义［10］。

定义1：DPSO算法的离散解值集

对任意有限数目的离散值Si∈R构成的离散值集合S=［s1，s2，…，sn］，称为DPSO算法的离散解值集。

定义2：DPSO算法的离散速度值集

速度值v=（i→j）表示离散值由i变为j。对任意有限数目的速度值构成的速度值集V=［v1，v2，…，vn］，称为DPSO算法的速度值集。

由上述定义可知，离散解值集和离散速度值集相当于定义的数据类型，需要进一步规定对应的四则运算法则，才能满足后续的计算需求。基本算子所构造的公式为

定义3：离散解值集间的减法算子“Θ”

该算子表示粒子的离散解集值的相减运算，如式（9）中的(pi，dΘxd)和(pdΘxd)运算，表征为粒子的离散速度值集。离散值(iΘj)所得结果为粒子的速度值（j→i），表示离散值由j变为i。

定义4：离散速度值集间的加法算子“⊕”

该算子表示粒子的离散速度值集间的相加运算，结果类型无变化。速度值（i→j）⊕（k→m）运算，若j=k，结果为（i→m）；否则结果为（k→m）。

定义5：常数与离散速度值集间的乘法算子“•”

该算子为常量与离散速度值集间的相乘运算，所得结果类型也不会发生变化。c为选取（0，1）间的一个常数，c′为（0，1）间的随机数。如果c′>c，则c⋅（i→j）=（j→i）；如果c′≤c，则c⋅（i→j）=（i→j）。

定义6：离散解值集与离散速度值集间的加法算子“⊗”

该算子为离散解值集与离散速度值集间的相加运算，得到离散解值集。离散值i⊗（k→m）运算，若i=k，结果为m；否则为i。

以上定义的运算算子基本能够满足粒子群算法离散化原理求解的需要。就优化的基本原理而言，基本DPSO 算法与标准PSO 算法是一脉相承的，没有本质区别，因此可以明确DPSO 算法的寻优机理与PSO算法相同，均通过迭代不断向全局最优解靠近。以此类推，DPSO 在优化当中不可避免地会碰到局部极值问题。

也就即是说，基本DPSO 方法虽然经过部分改进，可以有效地解决实际应用中较为广泛的离散问题的优化，但是由于没有改变其优化本质，在初始变量选择不当的时候，同样也非常容易发生早熟收敛、陷入局部最小的缺陷。目前，解决此类问题较为常用的手段之一是增加样本、扩大算法优化的基数（即种群规模），将局部极值出现的概率降低。然而这样的优化方式治标不治本，没有从原理上来避免早熟的缺陷，无法消除局部极值的现象，并且随之而来的是会带来巨大的计算工作量。通过对DPSO 求解离散优化问题时局部收敛现象进行充分剖析，能够得到以下结论：当一些粒子达到离散空间收敛的局部最优解位置时，其余粒子迅速向该位置聚集，此时继续迭代，很大程度上无法跳出该局部最优位置，大量粒子停留在此，离散速度将不再发生变化，从而使这些粒子停止在局部最优解位置并丧失了继续寻优的能力。

由此可得一个算法原理改进的方向，即在记忆粒子群中历史最优之时，加强算法的局部搜索能力，同时增加粒子的多样性，向其他方向进行扩展搜索，提高摆脱局部最优的概率。

2.1.3基于模拟退火的离散粒子群自适应优化策略

模拟退火算法是基于Monte Carlo 迭代求解策略的一种随机寻优算法，算法通过对照金属高温退火中的相变过程进行优化流程设计，整个流程主要包括三个步骤：首先是确定算法的优化目标以及约束边界，也就是适应度函数，作为算法的输入，规定迭代过程中可行解的取舍；然后是初始化，即确定算法的起始状态，初始化内容包含模拟退火算法初始温度以及初始状态，计算初始状态；最后是不断迭代求解，在迭代中值得注意的是，算法对于最优解的选择并非仅仅是简单地对两个可行解对应的适应度值大小进行比较，然后全盘接受更优解，而是在迭代中设计了一种基于概率的较优解取舍方式，即以一定概率保留一次迭代过程中的非极值点，降低找到局部极值之后便停止迭代的风险，直到满足算法最初确定的收敛条件，即表示“系统冷却”。在这种机制下，模拟退火方法在初始参数设置合理的条件下，能够保证收敛到全局极值［11-12］。

将模拟退火思想引入离散PSO 算法的优化过程，改善算法在训练过程中精度降低、容易发散的问题。在最优粒子的取舍中加入Metropolis 准则，在接受更优粒子的同时以一定的概率接受较差粒子，能够从局部极值当中跳出，随着温度的降低逐渐收敛到全局最优位置［13-14］。

引入模拟退火中的跳变和容错思想，对距离因子自适应离散粒子群算法的粒子取舍机制进行改进优化，其过程可以总结为8个步骤，即：

1）设定最初选择的粒子集合中粒子的状态，也就是给定一个最初定位和速率；

2）计算各粒子的适应度值，将当前各粒子位置和适应度值存储在各粒子的pi中，将所有pi中最优个体位置和适应度值存储在pb中；

3）确定初始温度t0：

4）确定当前温度下各pi的适配值：

5）采用轮盘赌策略从所有pi中确定全局最优的某个替代值p′b，然后根据式（6）～（8）适应更新各粒子的速度和位置，完成每步迭代过程中的可行解优选过程；

6）计算各粒子新的适应度值，更新各粒子的pi值及群体的pb值；

7）采用衰减系数法进行退温操作：

8）如果达到预先设置的终止约束条件，则寻优计算的过程立即停下，将得到的最优粒子相关参数输出，否则将会返回第4个步骤继续进行计算迭代。

2.2 基于改进SA-DPSO 的地面装备测试优化模型求解

将改进SA-DPSO 应用于装备测试点优化，基本流程如图1所示，整个优化过程主要包括以下几点：

图1 基于改进SA-BPSO的装备测试优化基本流程Fig.1 Basic flow of equipment test optimization based on improved SA-BPSO

1）粒子群编码。确定种群与测试点的映射关系，利用离散粒子群原理对测试点优化集合TS进行编码，第i个粒子的位置可用n维0、1 二进制数进行编码，表示粒子与测试点的联系：

当xij=1 时，表示第i个粒子对应于测试点tj；当xij=0时，表示第i个粒子与测试点tj无联系；

2）位置更新原则。在离散PSO 算法当中，一方面表征粒子位置的向量被固定用0、1 数字来体现，但是优化过程中粒子在速度更新中并未有类似原则。针对这一特点，只有找到能够连接离散点与连续数据的关系式，才能将连续的粒子速度变化转换为新粒子的位置变化，也就是采用离散粒子群方式进行更新。本文采用模糊函数Sigmoid，其形式为

3）适应度函数构造。适应度函数与优化目标直接关联，离散PSO 算法与标准PSO 算法优化机理相同，优化模型当中无需设置约束条件，根据自身算法不断迭代寻优。因此，算法适应度函数需由式（4）所表示的带约束模型进行去约束化，在考虑测试成本的基础上，权衡故障检测率和故障隔离率，函数构造形

式为：

式中：p定义为惩罚因子；C为各测试点对应的测试代价集。

引入惩罚因子是为了避免在不满足测试技术指标的情况下，出现选择了测试费用相对更低的方案而式（16）所示的适应度函数值也更小的极端情况。

3 算例分析

某发控系统的故障及测试相关性矩阵如图2 所示。发控系统总共设置测试点36 处，包含16 处周期BIT 检测以及20 处加电BIT 检测，故障模式共计22种［15］。

图2 发控系统相关性矩阵Fig.2 Correlation matrix of the launching control system

根据测试性建模及分析结果，发控系统测试点存在一定的冗余，并非最优完备测试集，影响系统效费比的提升。因此，采用第2 章所提智能优化算法对发控系统测试点进行优化分配，在满足系统测试性指标的前提下，尽量降低测试成本，提升测试诊断效费比。

发控系统故障模式共计22个，故障发生概率预计值见表1，完备测试集包含36个测试点，将各测试所对应的测试代价进行归一化，结果见表2。

表1 发控系统故障发生概率Tab.1 Failure probability of launching control system

表2 发控系统测试代价Tab.2 Test cost of launching control system

为了充分体现算法改进的优势，将基本DPSO 算法及改进的SA-DPSO 算法在同等输入条件下进行发控系统测试点优化选择，从算法迭代次数、适应度函数值、最终测试代价对优化结果进行综合比较。系统要求的故障检测率为0.95，故障隔离率为0.9。

两种算法初始参数设置相同，种群数量N取30，算法迭代次数最大为100，与系统可用测试点数目相对应，种群粒子的维度n定为36。通过仿真计算，不同算法的优化过程如图3 所示。从中可以看出，改进SA-DPSO 算法在第4 步便达到局部极值，之后能够在第29、38、77 步不断跳出局部极值，向全局最优靠近，适应度函数值最终保持在0.563 2。而基本DPSO 算法在开始达到局部极值后，长期保持，很难跳出，最终保持在0.623 6，要高于改进优化算法。基本DPSO 算法优化结果为T1=｛t1，t7，t10，t12，t13，t15，t18，t19，t20，t21，t26，t27，t28，t29，t33，t34，t35，t36｝，故障检测率为1，故障隔离率达到0.909 1，测试花费为5.65。采用改进SA-DPSO 算法优化结果为T1=｛t1，t2，t3，t9，t11，t15，t18，t19，t20，t21，t26，t27，t28，t29，t33，t34，t35，t36｝，故障检测率为1，故障隔离率达到0.909 1，但测试花费降至4.35。结果表明，改进SA-DPSO 算法较基础DPSO 算法而言有较强的寻优能力。

图3 适应度函数收敛曲线Tab.3 Fitness function convergence curve

4 结束语

针对装备测试优化中的集合覆盖问题求解，通过对粒子群离散化原理的研究，改进粒子优化过程中的搜索策略，并采取模拟退火与改进算法相融合的方式，进一步增强离散粒子群算法在优化过程中的粒子突变概率，解决测试优化过程中基础DPSO 算法的局部收敛问题，给出测试效率与费用综合权衡下的优化策略。对发控系统测试点优选的实例仿真结果表明，经过改进的SA-DPSO 算法与基础算法相比，有效避免了陷入局部最优，全局搜索能力明显提升，在收敛速度方面的优势也较为明显。