一种改进粒子群算法的测试数据自动生成方法

安新何明祥

摘要：线性递减惯性权重粒子群算法中，搜索后期较小的惯性权重使粒子具有很强的局部搜索能力。但惯性权重太小，容易使所有的粒子聚在一起损失多样性，找到最优解的可能性较低，易产生早熟现象。提出了一种利用方差动态调整惯性权重的方法，引入基于适应度方差的惯性权重调整因子。当出现早熟现象时，通过调整因子适当增大惯性权重的值，以扩大搜索范围，增加找到最优解的可能性。当未出现早熟现象时，继续采用线性递减惯性权重策略，加快收敛速度。实验结果表明，该算法具有较高的搜索成功率。

关键词：惯性权重；早熟收敛；LDWPSO 算法；SPSO算法；搜索成功率

DOIDOI：10.11907/rjdk.161971

中图分类号：TP312

文献标识码：A文章编号文章编号：16727800（2016）009004603

基金项目基金项目：

作者简介作者简介：安新（1990-），女，山东泰安人，山东科技大学计算机科学与工程学院硕士研究生，研究方向为软件项目管理、软件测试；何明祥（1969-），男，安徽合肥人，博士，山东科技大学计算机科学与工程学院副教授、硕士生导师，研究方向为数据库系统、信息处理、人工智能、数字矿山。本文通讯作者为何明祥。

0引言

软件测试是发现软件缺陷的过程，贯穿于软件生命周期的各个阶段，是保证软件质量的重要手段。软件测试中大约40%的时间用在测试数据设计阶段[1]。随着软件复杂度和软件规模的增大，测试开销和工作量也相应增加，传统的手工生成测试数据已不能满足要求，测试数据自动生成对提高测试效率、减少测试开销具有重要意义。在对测试数据自动生成方法的研究中，粒子群算法以其设置参数少、简单易实现、收敛快而受到研究者的青睐。

Shi等[2]提出线性递减惯性权重策略，使得搜索初期，粒子具有较好的全局搜索能力，搜索后期具有较好的局部搜索能力。但后期过小的惯性权重容易使整个粒子群陷入早熟，找到最优解的可能性较小；田甜等[3]提出一种非线性动态调整惯性权重策略，解决了线性递减权重策略中容易出现的早熟现象。

针对粒子群算法中易出现的早熟问题，本文提出一种基于方差的动态调整惯性权重的粒子群优化（FCWPSO）算法。算法思想为：总体上遵循线性递减惯性权重策略，当出现早熟现象时，通过调整因子适当增大惯性权重的值，跳出局部极值，扩大搜索范围，增加找到最优解的可能性。

1基本粒子群算法

粒子群优化（Particle Swarm Optimization，PSO）算法由Eberhart 、Kennedy[3]于1995年提出，基本思想是研究和模拟鸟类的觅食行为。每只鸟相当于一个粒子，属于问题的候选解，飞行空间相当于问题的搜索空间，捕食过程相当于寻找最优解的过程[4]。设粒子总数为N，起始状态为所有粒子被随机分配在D维搜索空间中，每个粒子均有一个D维位置向量Xi=（xi1，xi2，…，xiD）和一个D维速度向量Vi=（vi1，vi2，…，viD），每个粒子通过跟踪个体极值Pbesti=（pi1，pi2，…，piD）和全局极值Gbest=（g1，g2，…，gD）来更新自身的位置速度。个体极值是该粒子自身搜索到的历史最优值，全局极值是粒子群体搜索到的最优值。每个粒子通过不断更新自身位置和速度找到最优解。位置和速度更新见式（1）、式（2）。

Vt+1i=wVti+C1Rand1（）（Pbesti-Xti）+C2Rand2（）（Gbest-Xti）（1）

Xt+1i=Xti+Vt+1i（2）

其中：Vti、Xti分别为第t代中第i个粒子的速度和位置；Vt+1i、Xt+1i分别为第t+1代中第i个粒子的速度和位置；w为惯性权重，是保持原速度的系数；C1为粒子追随自身个体极值的权重，即粒子对自身的认识，一般设为2；C2为粒子追随粒子群全局极值的权重，即粒子对群体的认识，一般设为2；Rand1（）、Rand2（）为0到1之间的随机数；Pbesti为第i个粒子的历史最优值；Gbest为群体的最优值。

2基于方差的动态调整惯性权重方案

2.1常用粒子群优化算法及存在问题

（1）简化粒子群优化（SPSO）算法。胡旺等[5]指出粒子群的进化过程与速度无关，速度大小可能导致粒子不能沿正确的进化方向运动，最终不能有效地找到最优解。因此，提出了无速度参数的简化粒子群优化（Simple Particle Swarm Optimization，SPSO）算法，如式（3）所示，避免了由速度导致的后期收敛慢、精度低的问题，且简化了粒子进化过程。

Xt+1i=wXti+C1Rand1（）（Pbesti-Xti）+C2Rand2（）（Gbest-Xti）（3）

（2）线性递减惯性权重粒子群优化（LDWPSO）算法。Shi等[2]指出惯性权重较大，能够促进全局搜索；惯性权重较小，则促进局部搜索。提出了线性递减惯性权重的（Linearly Decreasing the inertia weight，LDW）粒子群优化算法，如式（4）所示。寻优过程中，通过LDW策略，使之从相对较大的值减小为一个较小的值，运行初期，粒子具有较强的全局搜索能力，运行后期，具有较强的局部搜索能力。与固定惯性权重设置相比，该算法性能较优。

w=wmax-（wmax-wmin）ttmax（4）

其中：wmax为w的最大值；wmin为w的最小值；t为当前迭代次数；tmax为最大迭代次数。

（3）现有算法存在的问题。早熟收敛或全局收敛时，粒子群都会呈现汇集现象，若此时算法未达到结束条件，由于汇集的多样性丧失，粒子搜索能力下降，导致很难找到最优解，搜索成功率较低，这时称粒子群出现了早熟现象[3，6]。LDWPSO算法后期过小的w使粒子聚集在一起，更易产生早熟现象。

2.2FCWPSO算法

当出现早熟现象时，粒子位置相近，因此其适应度值也很接近，可采用群体适应度方差衡量所有粒子的聚集程度。

本文提出一种基于适应度方差的动态调整惯性权重的粒子群优化（FCWPSO）算法，即在LDWPSO算法的基础上，引入一个基于适应度方差的惯性权重（FCW）调整因子，当发生早熟现象时，通过调整因子适当增大惯性权重w的值，如式（5）、式（6）、式（7）所示。扩大搜索范围，跳出局部极值，增加找到最优解的可能性。当没有出现早熟现象时，继续沿用LDW方案，加快收敛速度。

w=wmax-（wmax-wmin）ttmax+ε（5）

ε=1-σ2（6）

σ2=1N∑Ni=1Fi-FavgFmax（7）

其中：ε为惯性权重调整因子；σ2为粒子群的适应度方差；N为粒子总数；Fi为第i个粒子的适应度值；Favg为所有粒子的适应度平均值；为了限制方差的大小，Fmax取值为：Fmax=max（1，max|Fi-Favg|），（i=1，2，…，N），因此，Fi-FavgFmax∈（0，1），σ2∈（0，1）。

计算出粒子群的适应度方差后，设定一个阈值。当方差小于该阈值且算法还未达到结束条件时，说明出现了早熟现象，需要采取FCW方案，增大惯性权重w的值，扩大搜索范围。

3基于FCWPSO算法的测试数据生成

3.1FCWPSO算法流程

FCWPSO算法流程如图1所示。首先初始化粒子位置、速度，计算其适应值，更新个体极值和全局极值。然后判断是否达到结束条件，若是则算法结束，否则需要继续迭代。计算粒子群体的适应度方差，若方差小于指定阈值，表示粒子聚集在一起，但此时并未达到结束条件，说明粒子群出现了早熟现象，需要使用调整因子调整惯性权重，若方差大于或等于指定阈值，说明未出现早熟现象，继续采用线性递减惯性权重策略更新惯性权重。最后更新粒子位置、速度，开始新一轮迭代，直到满足结束条件。

3.2适应度函数构造

适应度函数用于评价个体位置的优劣，本文采用“分支函数叠加法[7-8]”构造适应度函数。程序中的每个分支都可以用分支谓词来表示，比如判断语句“if（x>y）{…}”中的分支谓词就是x>y，可以把分支谓词抽象成如下形式：

E1 op E2

其中：E1 、E2为算术表达式；op为{<，≤，>，≥，=，≠}中的一个，但不包含and、or、布尔运算符。

分支函数可以将一个分支谓词转换成一个实值，即分支函数值，用以衡量逻辑执行路径和实际执行路径的偏差。几种常见分支谓词的分支函数创建方法如表1所示，表中k为大于0的常数。

分支函数叠加法基本思想为：首先确定目标路径，然后在路径中分支节点前以插桩方式插入分支函数f，最后将各个分支函数相加，得到适应度函数。

假设目标路径中包含m个分支，n个输入参数（x1 ，x2 ，…xn ），则分支函数如式（8）所示。f1=f1（x1，x2，…xn）f2=f2（x1，x2，…xn）…fm=fm（x1，x2，…xn）（8）

以上m个分支函数相加，得到适应度函数F，如式（9）所示。

F=f1+f2+…+fm（9）

4实验研究

4.1实验方案及实验结果

以直角三角形判定程序为例，以覆盖所有分支的路径作为目标路径，分别采用FCWPSO算法、LDWPSO算法和SPSO算法生成测试数据，所生成的测试数据为0-100的3个整数，作为三角形的三条边，统计每种算法的搜索成功率。

测试方法：记录粒子数分别为100、120、140、160、180、200时，3种算法生成的测试数据情况，即是否能够生成构成直角三角形的测试数据，每组试验进行60次，记录3种算法在60次实验中的搜索成功率。

实验参数设置为：C1=C2=2，最大迭代次数为500次，SPSO算法中，w=0.7；LDWPSO算法中，w从0.7到0.4线性递减；FCWPSO算法中，总体上采用w从0.7到0.4线性递减策略，当方差<0.1时使用惯性权重调整因子ε适度增大w值，扩大粒子的搜索范围，消除早熟。实验结果如表2所示。

4.2实验结果分析

根据表2的统计结果，分析3种算法性能，如图2所示。可以看出，FCWPSO算法具有较高的搜索成功率，约为90%，说明其很好地解决了早熟问题，增加了找到最优解的可能性。LDWPSO算法和SPSO算法的搜索成功率较低，约为50%，原因是其无法摆脱早熟现象所致，找到最优解的可能性较小。本文FCWPSO算法较其它两种算法具有较高的效率。

5结语

针对LDWPSO算法搜索后期易产生早熟的问题，本文引入一个基于适应度方差的惯性权重调整因子，出现早熟现象时，通过调整因子适当增大惯性权重，扩大搜索范围，有效解决了早熟问题。未出现早熟现象时，继续沿用线性递减惯性权重策略，缩小搜索范围，加快收敛速度。在生成直角三角形测试数据中，相比LDWPSO算法和SPSO算法，该算法搜索成功率较高，证明了该算法能有效解决早熟问题，跳出局部极值，增加找到最优解的可能性。

参考文献参考文献：

[1]聂鹏，耿技，秦志光.软件测试用例自动生成算法综述[J]. 计算机应用研究，2012，29（2）：401405.

[2]YUHUI SHI， RUSSELL C EBERHART. Empirical study of particle swarm optimization. Proceedings of the 1999 Congress on Evolutionary Computation[C].Washington，1999（3）：19451950.

[3]田甜，毛明志. 基于DWSPSO的软件测试数据自动生成[J]. 计算机工程与设计，2011，32（6）：21342137.

[4]邵楠，周雁舟，惠文涛，等. 基于自适应变异粒子群优化算法的测试数据生成[J]. 计算机应用研究，2015，32（3）：786789.

[5]胡旺，李志蜀. 一种更简化而高效的粒子群优化算法[J].软件学报，2007，18（4）：861868.

[6]董跃华，戴玉倩. 一种改进PSO的软件测试数据自动生成算法[J].小型微型计算机系统，2015，36（9）：20152020.

[7]陈琳玲. 基于简化粒子群算法的测试数据自动生成方法研究[D].重庆：西南大学，2010.

[8]董跃华，戴玉倩. 混合粒子群算法的软件测试数据自动生成[J].计算机应用，2015，35（2）：545549.

责任编辑（责任编辑：杜能钢）