qpso( 最新).doc

基于QPSO算法的软件测试数据自动生成李文瑞，张伟，任洪丽摘要：针对目前进化算法生成测试数据方法存在算法复杂、参数设置不易、易陷入局部最优解等缺陷，提出了一种应用于软件测试中的基于量子粒子群算法(QPSO)的测试数据自动生成算法。该算法是在PSO算法基础上引入量子理论的思想。解决了PSO算法搜索空间有限，容易陷入局部最优解的问题。通过具体实验证明，该方法是有效可行的，其效率也明显高于GA算法和PSO算法。 关键字：软件测试；测试数据生成；粒子群算法；量子粒子群算法0 引言 软件测试是软件开发过程中必须完成的重要活动之一，而测试数据的自动生成是软件测试的最关键的问题，可以有效的提高软件测试的效率。软件测试数据自动生成通常包括功能测试数据自动生成和结构测试数据自动生成，目前通过进化算法生成测试数据方面的研究取得的很大的进展。文献1将遗传算法（GA）应用于面向对象软件的单元测试中，文献2提出“分支函数叠加法”来构造适应值函数。文献3对遗传算法在软件测试用例生成的性能进行研究，并提出了两种提高遗传算法生成测试用例效率的方法。文献4将把量子理论应用于PSO 算法中从而提出一种改进的粒子群优化算法。文献7在传统的遗传算法中注入免疫算子，提出了基于免疫遗传算法生成软件测试数据的方法。文献8提出一种基于PSO算法的软件测试数据生成方法。但是遗传算法及其改进算法都存在算法复杂、参数设置不易等问题，PSO算法具有搜索空间有限、容易陷入局部最优解的缺陷。本文提出一种基于QPSO的软件测试数据生成方法，并通过实验验证，其效率明显优于遗传算法和粒子群算法，解决了PSO算法容易陷入局部最优解的缺陷。1 基本概念1.1 粒子群算法设Xi = ( xi1 , xi2 , xin ) 为粒子i的当前位置；Vi = ( vi1 ,vi2 , vin ) 为粒子i的当前飞行速度；Pi = ( pi1 , pi2 , , pin ) 为粒子i所经历过的具有最好适应值的位置。Pg = ( pg1 , pg2 , ,pgn ) 为群体中所有粒子所经过的最好的位置( gbest)。粒子状态进化方程为：vij (t+1) = wvij(t) + c1r1j(pij(t) - xij(t) + c2r2(t)(pgj(t) - xij(t) (1)xij(t+1) = xij(t) + vij(t+1) (2)其中c1 , c2 为加速常数,w为惯性权重，r1 = ( r11 , r12 , , r1n ) , r2 = ( r21 , r22 , r2n ) 为两两相互独立的0, 1 范围内变化的随机数。1.2 量子粒子群算法文献4从量子力学的角度出发提出了一种新的PSO算法模型,认为粒子具有量子的行为,并根据这种模型提出了量子粒子群算法。在量子空间中,粒子的速度和位置是不能同时确定的,可通过波函数(x t)来描述粒子的状态, 并通过求解薛定谔方程得到粒子在空间某一点出现的概率密度函数。随后通过蒙特卡罗随机模拟的方式得到粒子的位置方程为：X(t) = P (3)P = (4)其中、U是在(0,1)之间产生的随机数，在文献3中L被定义为：L ( t + 1) = 2 * |m best - X ( t) | (5)m best = = (， ，) (6)其中称为收缩扩张系数，可控制算法的收敛速度。M 为群体中所含粒子的数目, D为粒子的维数，Pi为第i个粒子的 pbest。最后得到粒子的位置方程为：X(t+1) = P * |m best - X ( t) | * ln() (7)在迭代过程中，是由u 的大小决定的，当u 大于0.5 时，取-号，其他情况取+号。在QPSO算法中，粒子的状态只需要位置向量来描述，并且算法中只有一个控制参数。2 基于QPSO的软件测试数据自动生成系统基于QPSO算法测试数据生成的系统模型可分为三部分：测试环境构造、量子粒子群算法包、测试运行环境。测试模块输入的是输入空间D的参数集x(x1,x2, xn)，输出用“分支函数叠加法”6构造的分值函数，对分支函数和适应值函数的插装。适应度值是衡量粒子个体优劣的指标，适应值函数的构造直接影响QPSO算法在具体问题的效率。 分支函数的插装是在选定路径上各分支点插入相应的分支函数，设待测路径上有m个分支点，n个参数，则m个分支函数分别为：f1= f1(x1,x2,xn)，f2 = f2(x1,x2, xn)，fn = fn(x1,x2, xn)；该路径的分支函数为： F = F(f1)+ F(f2)+ F(fn) 0，x0其中，F(x) = x，x 0适应度值越小，个体越接近全局最优解。当个体适应度函数值F=0时，即可找到一条指定路径的测试数据。量子粒子群算法包是系统的核心，要根据测试模块的信息确定种群规模及迭代次数，并计算适应度值。根据评价规则应用QPSO算法进化生成新一代的种群，并搜索最佳数据，使适应值函数的值为0或达到最大迭代次数算法终止。QPSO算法包的工作流程如图1所示。图1 QPSO算法包工作流程测试运行主要是调用并运行插装后的被测程序，获得跟踪信息传递给量子粒子群包，根据QPSO中的评价结果决定算法的运行或终止。3 测试数据生成算法量子粒子群算法(Quantum Particle Swarm Optimization)是近年来Jun Sun 等人把量子理论应用于PSO 算法而提出的改进的粒子群优化算法3，较PSO算法更加简单，易实现，且求解速度更优。QPSO 算法不仅参数个数少，随机性强，并且能覆盖所有解空间，保证算法的全局收敛性。应用量子粒子群算法生成测试数据的具体实现过程如下：(1) 分析被测程序，确定适应值函数，对被测程序进行插装。(2) 设定粒子数M，维数Dimension，最大允许迭代次数MAXTIER，和。初始化种群中每个粒子的位置向量。(3) for(t=0；tMAXTIER；t+)(4) 使用量子粒子群中的每个粒子来执行函数插装后的程序。根据粒子运行结果评定粒子的适应度：If ( F(xi) 0.5，xid= P - * |m best - X ( t) | * ln()，当u0.5，xid= P + * |m best - X ( t) | * ln()，直到搜索到最佳测试数据或t=MAXTIER。pi为第i个粒子的最优适应值，pg为量子粒子群的最优适应值。x = (x1,x2,xn)，xi是第i个粒子的位置向量，QPSO算法中唯一的参数随迭代次数线性递减。4 实验结果及分析基于QPSO算法的软件测试数据自动生成实验采用在软件测试数据生成研究文献中广泛使用的三角形判别问题。通过实验验证QPSO算法在测试数据生成方面的效率。在以下试验中，取QPSO算法的参数随迭代次数由1.0线性递减到0.4，xmax = 100,xmin = 0,最大迭代次数为1000；取PSO算法的参数c1 = c2 = 2，w随迭代次数由0.7线性递减到0.3，xmax = 100,xmin = 0,最大迭代次数为1000。4.1 实验1在此试验中，以等边三角形的判别程序为测试对象，分别用PSO算法和QPSO算法生成10次等边三角形测试用例，记录每次找到最优解的迭代次数和迭代时间，计算10次的平均迭代次数和平均迭代时间，并通过图2和图3比较两种算法的实验效率。图2图34.2 实验2 在此实验中，以直角三角形的判别程序为测试对象，按照不同种群数运行10次，分别记录两种算法找到最优解的迭代次数和迭代时间，并计算10次的平均迭代次数和平均迭代时间。通过图4和图5比较两种算法的效率。图4图54.3 结果分析实验1和实验2表明，在等边三角形实验中，通过QPSO算法生成所需测试数据的迭代次数和迭代时间平均只有PSO算法的69%。在直角三角形实验中，通过QPSO算法生成所需测试数据的迭代次数平均是PSO算法的48%，迭代时间是PSO算法的59%。在文献8中验证了PSO生成所需测试数据的迭代次数和迭代时间都比GA算法少，其效率明显高于GA算法。由此可见，本文方法比GA和PSO能更快找到最优解。5 结论遗传算法生成软件测试数据存在算法复杂、参数不易设置的缺陷。基于PSO的软件测试数据自动生成具有搜索空间有限，容易陷入局部最优解的不足。本文提出利用QPSO算法生成测试数据的方法，更加简单易实现，控制参数少。实验证明，此方法是可行的，较遗传算法和PSO算法能更快、更稳定的收敛到全局最优解。参考文献：1 Nirmal Kumar Gupta and Dr. Mukesh Kumar Rohil Using Genetic Algorithm for Unit Testing of Object Oriented SoftwareC.computer society,2008,308-313.2 KOREL B. Automated software test data generatitonJ. IEEE transactions on Software Engineering, 1990, l6 (8) : 870 - 879.3 Donald J. Berndt and Alison Watkins. Investigating the Performance of Genetic Algorithm-Based Software Test Case GenerationC. High Assurance Systems Engineeri-ing , 2004 , 1530-2059. 4 SUN J, FENGB, XUWB. Particle Swarm Optimization with ParticlesHaving Quantum Behavior A . Proceedings of 2004 Congress on Evolutionary ComputationC . 2004. 325 - 331.5 SUN J, XUWB. A Global Search Strategy of Quantum behaved Particle Swarm Op timizationA . Proceedings of IEEE conference on Cybe