基于AMCQPSO的测试流程优化方法研究

孙 健，孙钦蕾，李宝晨，连光耀，谢 颖

（1.军械工程学院，河北 石家庄 050003；2.军械技术研究所，河北 石家庄 050003）

0 引 言

测试性设计关系到装备的研制、维修及保障工作，对其维修性、可靠性、可用性、战备完好性、寿命周期费用及系统性能和安全都有直接或间接的影响[1]。其关键技术主要包括测试点的优选、测试流程的优化以及相关测试性参数的评估。由于与诊断效率及测试成本联系紧密，测试流程的优化越来越受到人们的关注。

从数学角度来看，测试流程的优化问题属于组合优化问题，目前主要解决方法有遗传算法（genetic algorithm，GA）、动态规划算法（dynamic programming，DP）和与或图搜索（AND/OR graph search）算法。由于问题固有难度，现有算法的求解效率和精度都不尽如人意，尤其随着装备复杂程度的提高，集合规模的增大，迫切需要寻求新的有效算法，以获得最优测试流程[2-3]。

为此，本文在量子粒子群（QPSO）算法的基础上，提出了带自适应变异的质心量子粒子群优化算法（centroid quantum particle swarm optimization with adaptive mutation，AMCQPSO），以更高的效率和更有效的手段实现测试流程的优化。

1 测试流程优化问题描述

测试流程的优化是指通过对系统的最优测试集中的各个测试进行合理的排序，以使整个测试时间最短、测试成本最低。

由于影响测试流程设计的因素非常多，在本文的研究中，选取其最主要因素。定义五元组（F，p，T，c，D）来对问题进行研究。其中 F=[f1，f2，…，fm]表示系统的故障模式集，p=[p（f0），p（f1），…，p（fm）]T表示系统各个故障模式的先验概率集，Ts=[t1，t2，…，tn]表示经过优选得到的测试集，c=[c1，c2，…，cn]T表示综合考虑时间、测试费用等的测试代价矢量，D表示故障模式-测试相关性矩阵[4]。

不同的测试顺序对应不同的测试流程，并最终以二元诊断树的形式体现，利用诊断树可以得到隔离矩阵A，它的列为按照得到的顺序排列后的各个测试，若测试tj用于隔离fi，则aij为1，否则为0。最终，测试成本可以表示为

因此，测试流程优化的过程就是运用智能优化算法构建合适的诊断树，得到隔离矩阵A，使得测试成本Cost最少。

2 基于AMCQPSO的测试流程优化方法

基于上述分析，本文将测试流程优化问题转换为测试集元素的排序问题，提出AMCQPSO算法，以实现测试流程的优化设计。

2.1 QPSO算法简介

在标准的PSO算法中，粒子的状态由位置和速度两个因素决定，由于粒子的速度有限，因而其搜索空间也受限制，不能保证以概率1搜索到全局最优解。2004年，孙俊等人从量子力学的角度出发，在PSO模型的基础上，提出了QPSO算法。该算法以DELTA势阱为基础，认为粒子具有量子行为，利用波函数φ（x，t）描述粒子状态，通过求解薛定谔方程得到粒子在某点出现的概率密度函数，再利用Monte Carlo随机模拟得到粒子的位置方程[5]。

式中：M——种群中粒子的数目；

d——粒子的维数；

u、φ——在[0，1]上均匀分布的随机数；

mbest——种群中所有粒子的平均最好位置点；

Pi、Pg——粒子所经历的最好位置和种群中所有粒子经历的最好位置；

β——收缩扩张系数。

2.2 QPSO算法的改进

由于QPSO收敛速度快，若粒子群中的某一个粒子较早发现了一个局部最优位置，其他粒子在向它靠拢过程中并未发现更优位置，则会产生“早熟”现象而陷入局部最优。为此，从3方面对QPSO进行改进，提出了带自适应变异的质心量子行为粒子群算法（AMCQPSO）。

2.2.1 质心粒子的构建

物理学上，在直角坐标系中，对由N个质点组成的质点系，其质心可表示为

由于质心的特殊性，其往往具有其他粒子所没有的特性，更能体现全局性；因此，可以从粒子群的空间特征出发，为量子粒子群构建一个质心粒子。参考文献[6]，将粒子的适应度值value（Pi）作为“质量”，对于规模为m，维数为n的粒子群，可得其质心X的位置为

在QPSO进化过程中，利用质心更新部分Pg，在保证群体多样性的同时，可以加快收敛速度。

2.2.2 收缩扩张系数的自适应调节

由于收缩扩张系数β在QPSO中起着很重要的作用，它决定了算法的收敛性能及速度，因此有必要建立合适的系数调节机制。通常的方法是线性减少法，即

为了更好的提高算法的搜索范围及速度，可以引入另一种方法——自适应调节机制[7]。首先，建立误差函数ΔF

通过误差函数，可以得到各个粒子与全局最优位置的接近程度。对于靠近最优位置的粒子，即ΔF小的粒子，β值应取大一些；对于远离最优位置的粒子，即ΔF大的粒子，β值应取小一些。因此，令y=lg（ΔF），可以构建β的自适应调节函数

利用自适应调节机制控制系数β，能够从一定程度上提高算法的收敛速度和全局搜索能力，较第一种线性递减法具有更好的优势。

2.2.3 变异因子的引入

由于种群在不断进化过程中，个体间的差异逐渐减小，可以利用适应度方差σ2和聚集度h来表示种群当前的状态[8]，表达式为

式中：N——种群的规模；

value（Xid）——在第d次进化下第i个粒子的适应度值；

f——归一化因子。

适应度方差σ2反映了粒子群个体的聚集程度，σ2越小，表明个体间差异越小。

其中，分子表示第d次进化下的粒子与当前全局最优位置间的最大距离，分母表示在已进行的d次进化中粒子与其相应的全局最优位置的最大距离。聚集度h反映了个体间的分布情况，h越小，各粒子越靠近。

因此，随着进化次数的增加，σ2趋于0，而h越小的时候，粒子群易陷入局部最优，出现“早熟”。为此，引入变异因子，以一定概率对各粒子极值添加扰动，具体步骤如下：

Step2根据式（8）和（9）分别计算适应度；

Step3计算变异概率p：

Step4产生 0～1的随机数 rand（）；

Step5 比较 rand（）和 p。若 rand（）＜p，则对各粒子的历史最优位置进行变异操作：

通过在一定条件下对粒子进行变异操作，有效地避免了粒子的“扎堆”现象，增加了其全局搜索能力，提高了效率。

2.3 基于AMCQPSO的测试流程优化方法的实现

2.3.1 粒子的编码

粒子的维数为最优测试集中测试的个数n，粒子的规模为待隔离故障模式数m。定义粒子每一维的取值为0～1，根据解空间各维的数值进行排序，即为其所对应测试的顺序。如对于一个5维粒子，结果为[0.3，2，-1，0.6，5]，则解空间为[2，4，1，3，5]，优化的测试流程为 T3→T1→T4→T2→T5。

2.3.2 适应度函数

设Testk为所确定的测试顺序，则根据式（1），可知粒子的适应度函数为

由于适应度函数代表了测试成本，则算法的选取法则为 min（fitness）。

2.3.3 算法的实现步骤

Step1初始化种群规模m、维数n、各粒子位置Xi、历史最优位置Pi、种群最优位置Pg及最大迭代次数 dmax，令 d=0；

Step2根据式（12）计算各粒子的适应度值；

Step3 更新 Pid、Pg；

Step4根据式（4）计算质心位置，并计算其适应度值 fitness（Pc）；

Step5 若 fitness（Pc）优于 fitness（Pg），则更新当前Pg=Pc，并更新当前适应度值最小的粒子的历史最优Pkd=Pc；否则，进行下一步；

Step6根据式（2）、式（7）更新粒子的位置；

Step7根据式（8）、式（9）计算适应度方差 σ2和聚集度h，并由式（10）计算变异概率p；

Step8 生成 0～1 随机数 rand（），若 rand（）＜p，则根据式（11）进行变异操作；否则，进行下一步；

Step9判断粒子适应度是否达到收敛条件或d是否达到dmax。若达到二者中的一个，则跳至Step11；否则，跳至Step10；

Step10 d++，跳至 Step2；

Step11 输出 Pg、fitness（Pg），对 Pg各维数值排序，设计出测试流程。

3 实例验证

为考察算法的性能，本文从两方面对AMCQPSO进行验证：

3.1 算法的有效性

选取3个典型函数来求解最小值，其中f1（x）为单峰函数，用来测试算法的收敛速度；f2（x）、f3（x）为多峰函数，是典型的非线性多模态函数，具有广泛的搜索空间、大量的局部极值点，用来测试算法的全局搜索能力。3种类型函数的相关参数见表1。

表1 3种典型函数的相关参数

分别运用QPSO算法和AMCQPSO算法，多次重复实验取平均值，得到的结果如表2。

表2 实验结果

从表2可以看出，较QPSO算法而言，AMCQPSO算法具有较好的收敛速度、求解精度及全局搜索能力。

3.2 算法的实用性

以文献[9]中超外差接受系统为例，对其进行测试流程优化方法的研究。在其优选出的测试集为{T1，T2，T5，T6，T8，T11，T19，T20，T21，T24，T26，T27，T30，T33，T34}的前提下，分别用2种方法优化后的测试流程为：

（1）利用贪婪算法得到的测试流程为

T6→T33→T24→T21→T26→T1→T11→T2→T5→T8→T19→T20→T27→T30→T34

Cost=4.7931

（2）利用改进AO*算法得到的测试流程为

T30→T26→T34→T19→T6→T21→T27→T2→T1→T24→T20→T8→T5→T33→T11

Cost=4.6349

利用改进动态贪婪算法得到的最优测试集为

Tr={T4，T8，T6，T10，T14，T19，T21，T22，T23，T26，T27，T28，T30，T31，T34，T36}

在此基础上，分别利用QPSO算法、混沌粒子群算法及本文所提出的AMCQPSO算法，优化得到的测试流程均为

T30→T34→T28→T27→T8→T31→T19→T26→T4→T21→T36→T10→T22→T14→T23

Cost=3.4435

由此可知，利用AMCQPSO能得到与QPSO和混沌粒子群相同的最优测试流程，但算法运行时间却优于两者，且测试成本仅为贪婪算法的71.84%、改进AO*算法的74.30%，具有较好的实用价值。

4 结束语

本文在QPSO的基础上，提出AMCQPSO算法，利用质心粒子和对收缩扩张系数自适应调节提高了收敛速度，并通过添加变异因子有效地保持了种群的多样性，使得算法能够跳出局部最优，有效避免了“早熟”现象的发生。从实验结果可以看出，AMCQPSO具有较好的收敛速度、求解精度及全局搜索能力，能够实现测试流程的优化，为后续测试性设计的工作奠定了一定基础。

[1]Gould E.Modeling it both ways：hybrid diagnostic modeling and its application to hierarchical system designs[C]∥ IEEE Autotestcon，2004：577-581.

[2]黄考利，连光耀.装备测试性建模与应用[M].北京：兵器工业出版社，2010：16-19.

[3]石君友.测试性设计分析与验证[M].北京：国防工业出版社，2011（4）：15-24.

[4]蒋荣华，王厚军，龙兵.基于DPSO的改进AO*算法在大型复杂电子系统最优序贯测试中的应用[J].计算机学报，2008，31（10）：1836-1840.

[5]孙俊.量子行为粒子群优化算法研究[D].无锡：江南大学，2009（3）：12-29.

[6]汪永生，李均利.质心粒子群优化算法[J].计算机工程与应用，2011，47（3）：34-37.

[7]康燕，孙俊，须文波.具有量子行为的粒子群优化算法的参数选择[J].计算机工程与应用，2007，43（23）：40-42.

[8]刘俊芳，高岳林.带自适应变异的量子粒子群优化算法[J].计算机工程与应用，2011，47（3）：41-43.

[9]苏永定.机电产品测试性辅助分析与决策相关技术研究[D].长沙：国防科技大学，2004.