基于模块软件系统的测试资源分配研究

杨平良

(江苏运时数据软件有限公司，江苏南京 210096)

基于模块软件系统的测试资源分配研究

杨平良

(江苏运时数据软件有限公司，江苏南京 210096)

基于串－并联模块软件系统，研究了单元测试中测试资源分配问题。同时考虑系统可靠性和软件费用，提出一种带约束的多目标优化模型，针对标准粒子群算法收敛速度慢、容易陷入局部极小等缺点，给出了一种杂交粒子群算法。该算法利用迭代局部搜索算法的邻域搜索及其扰动机制进行详细局部搜索并跳出局部最优解，采用“回飞机制”处理约束条件，求解近似最优解。最后通过实例与遗传算法比较，结果表明该方法能有效地分配测试资源，在提高软件测试质量的同时降低软件费用。

测试资源分配;杂交粒子群算法;软件可靠性;模块软件系统

软件测试是软件开发过程中的一个重要环节，是保证软件质量的重要手段，一般包括单元测试、集成测试和系统测试。单元测试中，系统各个模块的具体功能已经确定，根据一定原则，系统可靠性指标可转化为各个模块可靠性指标，项目管理人员根据各模块的可靠性指标来合理分配测试资源，确定合理的开发流程，以提高开发效率，减少开发费用。测试资源主要包括查找缺陷人数、纠正错误人数和计算执行时间。软件测试要求在最小测试资源投入下，合理利用测试资源，尽可能地提高软件可靠性。然而，在实际软件开发中，有限的测试资源是开发团队不得不面对的问题，开发成本与软件可靠性之间存在不可回避的矛盾。因此，如何在有限资源条件下优化软件测试资源分配并实现软件成本与可靠性的平衡，成为软件开发的一个重要课题。

在软件测试资源分配优化的研究中，曾有大量研究人员［1－9］通过研究模块化软件的单元测试过程以试图寻找资源配置优化策略来解决这一问题，希望在对成本作出限制，或是对可靠性作出限制的条件下，对测试资源进行最优化。这些研究中，大多基于可靠性增长的测试资源分配模型，在一定条件下对于一些简单系统可以利用经典数学规划理论求解出精确资源分配方案，然而当系统比较复杂时，这些方法在合理的时间内并不一定能给出精确解。基于此，Dai等［10］研究了具有复杂结构的并联－串联模块软件系统，即当测试时间有限时，以系统可靠性最大和软件费用最少为目标的多目标测试时间分配问题。使用加权因子将多目标问题转化为单目标问题，应用遗传算法能在合理时间内获得次优解。但是，由于各个加权因子取值会直接影响解的质量，加权因子过多在实际应用中难以确定，这样在一定程度上影响测试资源分配的合理性。本文在此基础上对模型作进一步推广，提出一种杂交粒子群算法，求解针对可靠性和测试费用优化测试资源分配的多目标优化问题。利用“回飞机制”解决约束问题，在粒子群算法的迭代过程中嵌入迭代局部搜索算法以加速其全局收敛。

1 测试资源分配模型

假定软件系统由模块串－并联组成，在单元测试阶段，模块的开发和测试活动都是独立的，并且每一个模块的失效均由整个模块软件系统中剩余软件缺陷在任意时刻造成。软件模块i的失效过程为均值函数mi(t)或失效强度函数λi=dmi/dt的非齐次泊松过程(NHPP)。经过Ti个单位时间测试后，模块i的失效强度为λi(Ti)，此时模块i的可靠性为:式中x为测试后模块i的运行时间。注意到测试完成后软件可靠性将不再增长［10］，因此失效率保持为常数λi(Ti)不变。图1给出了串－并联模块软件系统的一般结构。系统由m个子系统串联而成，每个子系统由ni(i=1，2，…，m)个模块并联组成。

图1 串－并联模块软件系统结构

则此系统的可靠性由下式给出:

式中Tij为分配到子系统i中模块j的测试时间。

假定模块i经过测试后可靠性达到Ri时的费用函数 Ci(Ri)［9］为:

式中Hi，Bi，Di为常数。则图1给出的串－并联模块软件系统的软件费用为:

式中Rij为第i个子系统中第j个模块的可靠性。

由此单元测试中串－并联模块软件系统测试资源分配优化问题可以表示为如下带约束的多目标优化问题:

式中T为整个系统单元测试中计划测试总时间。

2 嵌入ILS算法的HPSO算法

粒子群算法是由 Kennedy等［11］于1995年提出的一种基于种群搜索的自适应演化计算技术。在PSO算法中，用粒子的位置表示待优化问题的解，每个粒子性能的优劣程度取决于待优化问题目标函数确定的适应值，每个粒子由一个速度决定其飞行方向和速率大小。设在一个d维的目标搜索空间中有M个粒子组成一个群体，其中在第t次迭代时粒子i的位置表示为，相应的飞行速度表示为。在每一次迭代中，粒子通过跟踪两个极值来更新自己的速度和位置:一个极值是粒子本身迄今搜索到的最优解pBesti，称为个体极值;另一个极值是整个粒子群到目前为止找到的最优解gBest，称为全局极值。具体地讲，在第(t+1)次迭代计算时，粒子i的速度和位置的更新规则分别为:

式中:ω为惯性权重;c1，c2为两个学习因子;r1，r2为两个均匀分布在(0，1)间的随机数;i=1，2，…，m;j=1，2，…，d。本文采用文献［12］推荐的参数，取 c1=c2=1．49，ω =0．729。

粒子群优化算法是根据全体粒子和自身的搜索经验向着最优解的方向“飞行”，在进化过程中，开始优化速度较快，接近极小点时，优化速度极为缓慢。一旦存在局部最优点，则一般很难突破局部最优点，这是不足之处。为了刺激群体持续进化，避免群体的早熟收敛和停滞现象，在粒子群优化算法的基本框架上，结合迭代局部搜索(ILS)算法［13］的特点，利用其对当前解邻域内的局部详细搜索机制，以及通过在解空间内不断变换解的位置，达到全局最优的扰动机制，增加粒子在局部详细搜索的能力，同时增强其跳出局部最优的能力，从而避免陷入局部最优，得到问题的最优解或近优解。杂交粒子群算法基本流程如下:

Step 1，随机生成粒子群，为所有粒子初始化位置和速度。

Step 2，将粒子的 pBesti设置为当前值，gBest设置为初始群体中的最佳粒子的位置。

Step 3，对种群中的每个粒子i，由式(5)和式(6)更新当前粒子的速度和位置;如果位置不满足约束条件则回飞到上一位置。(1)根据事先设定的邻域结构确定每个粒子的邻域最优解xi;(2)根据某种扰动机制，对xi进行扰动，生成新的可行解，并在其邻域内确定最优解;(3)比较xi和，如果优于xi，则令粒子i当前位置为，否则令其位置为xi。

Step 4，更新当前粒子i的最优位置pBesti。

Step 5，更新种群的最优位置gBest。

Step 6，重复Step 3直到终止条件满足。

3 应用杂交粒子群算法分配测试资源

3.1 粒子表达式与粒子群的初始化

用每个粒子表示测试资源分配问题的一组解，即从粒子表达式直接或间接得到测试资源分配的一种方式。由于测试资源分配问题的最终解是整个系统中各个模块在测试过程中消耗的测试时间，因此粒子i表达式为所有模块消耗测试时间xij(j=1，2，…，d) 组成的一个向量。其中 d=，为软件系统中模块总数。对于给定的测试资源T，采用随机生成具有M个粒子的粒子群，在每个粒子i生成过程中，每个模块j消耗的测试时间xij均在剩余测试资源中随机生成，即对模块j，若剩余测试资源数为，则 xij在［0，Tl］中随机生成，其中为前(j－1)个模块中已分配测试资源之和。

3.2 约束的处理

PSO算法已经成功应用于求解带约束的优化问题，处理约束的最常用方法是使用惩罚函数，然而试验结果表明，这种方法将降低PSO算法的效率。这是因为当出现不可行粒子时，PSO算法将粒子的位置重新设为粒子在此之前的最佳位置pBesti，这样将会阻止粒子朝着全局最优解搜索。最近由Li等［14］引入一种称为“回飞机制”的约束处理方法。对于大多数带约束的优化问题，其全局最优解一般都位于或接近于可行区域的边界。粒子在可行区域内初始化，当寻优过程开始时，粒子在可行空间内搜索解。如果粒子飞入非可行区域，它将被迫飞回到前一位置，以保证解是可行解。粒子飞回的前一位置可能在下一次迭代中更接近于边界，这就使得粒子以更大的概率飞向全局最优解。试验结果表明，这种机制比其他约束处理方法更易搜索到最优解［14］。

3.3 适应值计算

粒子的适应值用来说明粒子所表示解的质量。在串－并联模块软件系统测试资源分配问题中，测试后的软件可靠性和软件费用是同时优化的目标函数，因此适应值函数通过标度因子α合并2个目标函数构成:

其中R(x|Tij)是由式(2)算得的系统可靠性，C(Rij)是由式(4)算得的软件费用。标度因子α主要有2个作用:首先，它标度R(x|Tij)和C(Rij)的值，使适应值不受单个优化目标控制;其次，α可作为一个权重参数来控制每个目标的重要程度。

3.4 ILS的邻域结构与扰动机制

对于串－联模块软件系统的测试资源分配问题，迭代局部搜索算法的邻域结构采用互换式邻域结构交换(Swap)［14］，即随机交换粒子任意两维的位置。如1→4→3→5→2是1→2→3→5→4的一个邻域解，则每个状态的邻域解有=M(M－1)/2个，其中M为决策变量个数。通过这种互换式邻域结构生成的粒子位置总能满足约束条件。

ILS算法的扰动机制，对粒子新生成位置x的每一维以概率p=1/d进行扰动，这样可增加粒子的组件随机性，具体实现为:对于粒子i的每一维j，在［0，1］中生成随机数 r，当 r≤ 1/d 时，用［0，Tl］内的随机数替换对应模块的测试时间xij，其中

4 实验及算法性能比较

本节将以文献［10］中2个串－并联模块软件系统为例，与遗传算法(GA)比较本文给出的杂交粒子群(HPSO)优化算法的性能。

各个模块的可靠性增长模型采用Goel－Okumoto可靠性增长模型［10］，其均值函数mi(t)和失效强 度 函 数 λi(t) 分 别 为 mi(t) = ai［1 －exp(－ bit)］，λi(t)=aibiexp(－ bit)，i=1，2，…，m。

实验1:引用文献［10］的两模块并联软件系统结构，如图2所示。

图2 两模块并联系统

计划10位测试人员测试2个模块，每人可用测试时间为1 000h，则总的测试资源为10×1 000=10 000h，假定x=200h，各个模块可靠性增长模型及费用函数的参数采用文献［10］中的参数，见表1。

算法中参数如下:粒子群规模大小为M=100，最大迭代次数为100，学习因子c1=c2=1．49，惯性权重 ω =0．729，标度因子 α =35。

由HPSO算法可以得到对于10人的1 000h的可用时间分配，可对模块1分配9 400.8h的测试时间，对模块2分配599.2h的测试时间，这样可使系统可靠性达到0.895 2，总费用C=7.350 6单位。由HPSO算法与遗传算法(GA)［9］和Y_X算法［9］给出的结果对比见表2。

表1 两模块并联系统中各模块参数

表2 HPSO算法与遗传算法和Y_X算法比较算法

适应值函数中，参数α(标度因子)大小对各个模块分配测试资源的系统可靠性与测试费用的影响见表3。

表3 参数α的灵敏度分析

实验2:引用文献［10］的复杂串－并联软件模块软件系统结构，如图3所示。

图3 复杂串－并联模块软件系统

计划23位测试人员测试2个模块，每人可用测试时间为1 000h，则总测试资源为23×1 000=23 000h，假定x=200h，各个模块参数采用文献［10］的参数，见表4。

表4 复杂串－并联模块软件系统中各模块参数

算法中参数如下:粒子群规模大小为M=100，最大迭代次数为100，学习因子c1=c2=1．49，惯性权重 ω =0．729，标度因子 α =150。

在模块1中分配21h，模块2中分配10 752h，模块3，4，5均不进行测试，即测试时间为0，模块6分配9 394h，模块 7分配 1 686h，模块8分配1 147h，测试后系统可靠性为0.889 1，软件费用为51.149 5单位。由HPSO算法与遗传算法(GA)［9］和 T_M 算法［15］给出的结果对比见表 5。

从表5可以看出，T_M算法在没有考虑软件费用因素的条件下使软件系统可靠性最大，其可靠性比HPSO算法和GA算法得出的可靠性高0.021，但费用却比HPSO算法给出的软件费高接近4单位，比GA算法给出的软件费用高3单位。如果单位软件费用为10 000$，则由HPSO算法给出的测试策略在牺牲大约0.021的可靠性的条件下可节约费用40 000$，比GA算法给出的策略要低15 000$。HPSO算法中当标度因子α取不同值时，整个软件系统平均可靠性和平均软件费用随α变化曲线分别如图4和图5所示。

图4 参数α相对于可靠性的灵敏度

图5 参数α相对于费用的灵敏度

由图4和图5可以看出，当α接近于0时，系统平均可靠性和平均软件费用都接近于0，这意味着此时不考虑软件可靠性因素，不需要对软件进行任何测试，这时软件费用最小。当α逐渐变大时，系统可靠性相对于软件费用而言，其重要程度逐渐变大，软件可靠性和软件费用都在逐渐增加。因此标度因子α对于适应值函数式(7)是重要的，并且是灵敏的。

5 结束语

本文基于串－并联模块软件系统研究了单元测试中资源分配问题，考虑系统可靠性和测试费用建立一种带约束的多目标优化模型，针对标准PSO算法收敛速度慢、容易陷入局部极小等缺点，提出了一种HPSO算法。该算法利用ILS算法进行详细局部搜索并跳出局部最优解，采用“回飞机制”处理约束条件求解近似最优解。最后通过实例与遗传算法进行比较，结果表明该方法能有效地对测试资源进行分配，在保证软件测试质量的同时，提高资源利用率。

表5 HPSO算法与遗传算法和T_M算法比较

由于测试资源分配模型参数估计的精度直接影响到测试资源分配的有效性和合理性，因此如何对测试资源分配模型的各个参数作精确估计是进一步研究的内容。另外，算法收敛性分析以及进一步提高算法搜索效率也是研究的另一方面。

［1］ Wang Z，Tang K，Yan X.A multi－ objective approach to testing resource allocation in modular software systems［C］ //Proceeding of the IEEE World Congress on Computational Intelligence.Hong Kong:IEEE Computer Society，2008:1148－1153.

［2］ Jha P C，Gupta D，Yang B，et al.Optimal testing resource allocation during module testing considering cost testing effort and reliability［J］.Computers ＆ Industrial Engineering，2009，57:1122－1130.

［3］ Khan M G M，Ahmad N ，Rafi L S.Optimal testing resource allocation for modular software based on a software reliability growth model:a dynamic programming approach［C］ //Proceeding of the 2008 International Conference on Computer Science and Software Engineering.Wuhan:IEEE Computer Society，2008:759 －762.

［4］ Huang C Y ，Lo J H.Optimal resource allocation for cost and reliability of modular software systems in the testing phase［J］.Journal of Systems and Software，2006，79(5):653 －664.

［5］ Coit D W.Economic allocation of test times for subsystems－ level reliability growth testing［J］ .IIE Transactions，1998，30:1143－1151.

［6］ Lyu M R，Rangarajan S，Van M A P A.Optimal allocation of test resources for software reliability growth modeling in software development［J］.IEEE Transactions on Reliability，2002，51(2):183－192.

［7］ Berman O，Cutler M.Resource allocation during tests for optimally reliable software［J］.Computers ＆ Operations Research，2004，31:1847－1865.

［8］ Aggarwal A G，Kaur G ，Kapur P K.Optimal testing resource allocation for modular software considering imperfect debugging and change point using Genetic Algorithm［C］ //Proceeding of the 2010 2nd International Conference on Reliability，Safety and Hazard(ICRESH).Mumbai:IEEE Computer Society，2010:535－541.

［9］ Aggarwal A G，Kapur P K，Kaur G，et al.Genetic algorithm based optimal testing effort allocation problem for modular software［J］.BVICAM's International Journal of Information Technology，2012，4(1):1－7.

［10］Dai Y S，Xie M，Poh K L，et al.Optimal testing－resource allocation with genetic algorithm for modular software systems［J］.Journal of Systems and Software，2003，66(1):47 －55.

［11］Sammut C，Webb G I.Encyclopedia of Machine Learning［M］.New York:Springer US，2010:760－766.

［12］Kler M，Kennedy J.The particle swarm －explosion，stability，and convergence in a multidimensional complex space［J］.IEEE Transactions on Evolutionary Computer，2002，6:58 －73.

［13］Cowlinga P I，Keuthenb R.Embedded local search approaches for routing optimization［J］.Computers ＆ Operations Research，2005，32:465－490.

［14］Li L J，Huang Z B，Liu F，et al.A heuristic particle swarm optimizer for optimization of pin connected structures［J］.Computers and Structures，2007，85:340－349.

［15］Tom P A，Murthy C S R.Algorithms for reliability－oriented module allocation in distributed computing systems［J］.Journal of Systems and Software，1998，40(2):125－138.

Development of Testing－resource Allocation System Based on Modular Software

YANG Pingliang
(Jiangsu Yunshi Data Software Co.，Ltd，Jiangsu Nanjing，210096，China)

It describes both system reliability and testing cost in the testing－resource allocation problems for series－parallel modular software systems during testing phase，presents a hybrid particle swarm optimization(HPSO)algorithm for testing－resource allocation problems.It designs the HPSO algorithm for specific constraints with'fly－back mechanism'method，applies the Iterated Local Search(ILS)scheme to the candidate solution of the swarm to help the algorithm escape from local optima.The experimental results show that the HPSO is more effective and efficient than a genetic algorithm.

Testing－resource Allocation;Hybrid Particle Swarm Optimization;Software Reliability;Modular Software System

TP311

A

2095－509X(2013)12－0047－06

10.3969/j.issn.2095－509X.2013.12.012

2013－11－04

杨平良(1977—)，男，江苏南京人，江苏运时数据软件有限公司董事长兼总经理，主要从事数据挖掘、软件测试技术等方面的应用开发、研究工作。