基于多目标差异演化算法的软件测试资源动态分配方法
基于多目标差异演化算法的软件测试资源动态分配方法
【技术领域】
[0001] 本发明涉及软件测试方法领域，具体是一种基于多目标差异演化算法的软件测试 资源动态分配方法。
【背景技术】
[0002] 随着软件系统的广泛应用，软件复杂度不断提高，包括的模块越多。在测试过程 中，每个模块都需要经过测试。特别是在软件的单元测试中，不同模块的测试活动都在激烈 争夺有限的测试资源，不同的测试活动也会带来不同的成本的上升与可靠性的增加。软件 工程师必须清楚如何将测试资源分配给不同的模块测试。测试资源分配问题就是如何把有 限的测试资源分配给每一个模块，从而保证软件系统的可靠性最大。
[0003] 测试资源分配问题是系统可靠性优化中的关键和重要问题。自二十世纪九十年代 以来，已经成为研宄的热点问题。目前的研宄大都是基于测试代价、系统可靠性、测试资源 为核心的多目标优化问题。
[0004] 但是已有的测试资源分配模型和分配方法均属于静态分配测试资源的方法，即根 据系统初始时刻各模块的可靠性进行测试资源的分配，很少考虑各模块可靠性随着测试进 程发生变化的情况。这些模型和方法的缺点是会造成测试资源大量浪费在可靠性已经很 高、不在需要测试资源的模块上，导致在测试完成后，有些模块的可靠性远远低于系统的 可靠性，使软件测试的效果不佳。
【发明内容】
[0005] 本发明的目的是提供一种基于多目标差异演化算法的软件测试资源动态分配方 法，以解决现有技术软件测试资源分配方案因不考虑各模块可靠性随着测试进程发生变化 的情况而导致测试资源浪费、测试效果差的问题，。
[0006] 为了达到上述目的，本发明所采用的技术方案为：
[0007] 基于多目标差异演化算法的软件测试资源动态分配方法，其特征在于：包括以下 步骤：
[0008] (1)、对所求问题进行分析，为可行解设计编码方法；
[0009] (2)、对整个测试环节进行划分，划分为若干个测试阶段；
[0010] (3)、对差异演化算法中的种群规模、迭代次数、交叉概率、变异概率等控制参数进 行设置；
[0011](4)、对种群进行初始化操作；
[0012] (5)、对种群中的个体进行变异操作；
[0013] (6)、对变异生成的个体与原种群中的个体进行交叉操作；
[0014](7)、采用非支配排序机制进行选择操作；
[0015] (8)、判断是否达到最大迭代次数，若否，则跳到步骤（5)，继续进化操作；若是，则 跳到步骤（9);
[0016](9)、对pareto解进行解码；
[0017] (10)、判断是否还存在未进行的测试阶段，若存在，跳到步骤（11);若否，则结束 求解过程；
[0018](11)、更新下一测试阶段的测试资源，跳到步骤（4)，进入下一测试阶段。
[0019] 所述的基于多目标差异演化算法的软件测试资源动态分配方法，其特征在于：步 骤（1)中为可行解进行一维整数向量编码；且若软件系统包含m个串联子系统，每个子系统 Sj(j= 1，2,…，m)由rij个并联模块M#，…，Mjk,…组成，贝1」每个个体包含m个整数向 量Fj，…，Fj…，Fm，每个向量包含nj个元素tjl，…，tjk,…，，tjk表不模块Mjk所分配 到的测试资源。
[0020] 所述的基于多目标差异演化算法的软件测试资源动态分配方法，其特征在于：步 骤（2)中，将测试资源T分为p个测试阶段：
[0021] (T0= 0，TJ，...，（ThA]T]〇
[0022] 所述的基于多目标差异演化算法的软件测试资源动态分配方法，其特征在于：步 骤（3)中，对差异演化算法中的种群规模、迭代次数、交叉概率、变异概率等控制参数进行 设置。
[0023] 所述的基于多目标差异演化算法的软件测试资源动态分配方法，其特征在于：步 骤（4)中，对种群进行初始化操作，按照不同测试阶段采用不同的种群初始化方法；
[0024] 在步骤⑷中，对于第i= 1个测试阶段〇；= 0，TJ，由于系统各个模块的可靠 性都较低，采用随机的方法初始化每个子系统中每个模块的测试资源：
[0026] 其中，rand(Ul，u2)函数表示在区间（Ul，u2)内随机取整数；
[0027] 在步骤⑷中，对于第i个（i彡2)测试阶段d，TJ，种群初始化的方法是根据 模块已达到的可靠性rjk分配测试资源：
[0029]其中，0是用户希望达到的模块可靠性阈值rjk是模块Mjk已经达到的可靠性值。[0030] 所述的基于多目标差异演化算法的软件测试资源动态分配方法，其特征在于：步 骤（5)中，对种群中的个体进行变异操作，采用方法是DE/best/2/bin模式。
[0031] 所述的基于多目标差异演化算法的软件测试资源动态分配方法，其特征在于：步 骤（6)中，对变异生成的个体与原种群中的个体进行位交叉操作，生成2个不同的个体。
[0032] 所述的基于多目标差异演化算法的软件测试资源动态分配方法，其特征在于：步 骤（7)中，采用非支配排序机制进行选择操作，选择的对象集合包括原种群个体、变异后的 个体以及交叉产生的个体；
[0033] 步骤（7)中，非支配排序机制是指对种群按照优化目标函数进行分层，并计算个 体拥挤度来衡量个体在每层的优劣，然后根据个体的分层和拥挤度的大小选取较优的个体 组成新的种群；
[0034] 步骤（7)中，优化目标函数为：
[0038] s.t.
[0039] Tia^T
[0040] 0 <tiJk彡T「Th
[0041] 其中，tijk表示模块Mjk在第i个测试阶段所分配到的测试资源，rijk表示模块MJk 在第i个测试阶段的可靠性值，且rijk=rjk (x/tijk)，氏(xATi-Tg))、(；和Tia分别表示软件 系统在第i个测试阶段的总体可靠性、总体测试代价和系统实际消耗的总测试资源，hk(X/ tijk)和qk(i^k)分别表示模块M#在第i个测试阶段的可靠性和测试代价，均为测试资源的 函数。
[0042] 所述的基于多目标差异演化算法的软件测试资源动态分配方法，其特征在于：步 骤（9)中，对pareto解进行解码，具体操作包括：计算每个模块的可靠性rjk，计算每个模块 的测试代价qk，计算软件系统的实际测试时间T，。
[0043] 所述的基于多目标差异演化算法的软件测试资源动态分配方法，其特征在于：步 骤（11)中，更新下一测试阶段的测试资源，方法为：
[0044] 凡―Ti-CTi-TH-Tj)。
[0045] 本发明提出了一种基于多目标差异演化算法的软件测试资源动态分配方法，考虑 各模块可靠性随着测试进程发生变化的情况，在测试进程中动态地为各个模块分配测试资 源，可以节省系统测试资源的消耗，提高测试效率，提高软件系统的可靠性。本发明优点 为：
[0046] (1)本发明采用的是以测试资源为约束、联合优化系统可靠性、系统测试代价和实 际消耗的系统测试资源，不会由于三者分离而产生某一方面性能损失；
[0047] (2)本发明将整个测试环节划分为若干个测试阶段，在每个测试阶段根据前一测 试阶段的可靠性为每个模块动态地分配测试资源，解决了已有测试资源分配方案带来的测 试资源浪费、测试效率低的缺陷；
[0048] (3)本发明中采用的是基于非支配排序机制的多目标差异演化算法，搜索速度快、 解质量高，因此可以在系统可靠性、系统测试代价和实际消耗的系统测试资源之间达到平 衡；
[0049] (4)最后，由于演化算法操作简单，性能好，曾在首届IEEE演化计算大赛中表现超 群，非常适合在实际系统中取得应用，有较好的应用前景。
【附图说明】
[0050] 图1为本发明实施例中基于多目标差异演化算法的软件测试资源动态分配方法 的流程示意图；
[0051]图2为本发明实施对象串并行软件系统结构示意图。
[0052] 图3为本发明采用的一维整数向量编码示意图。
[0053] 图4为软件测试环节划分示意图。
[0054]图5为本发明一个实时实例串并行软件系统结构示意图。
[0055] 图6为本发明的一个实施实例中本发明技术与现有技术结果的对比。
【具体实施方式】
[0056] 本发明为了解决现有技术中软件测试资源分配方案因不考虑各模块可靠性随着 测试进程发生变化的情况而导致测试资源浪费、测试效果差的问题，提供了一种基于多目 标差异演化算法的软件测试资源动态分配方法，该方法主要应用于如图2所示的串并行软 件系统的模块测试中。如图1的流程图所示，本发明中的方法的基本过程为：
[0057] S1，对所求问题进行分析，为可行解设计编码方法；
[0058] S2,对整个测试环节进行划分，划分为若干个测试阶段；
[0059]S3,对差异演化算法中的种群规模、迭代次数、交叉概率、变异概率等控制参数进 行设置；
[0060]S4,对种群进行初始化操作；
[0061] S5，对种群中的个体进行变异操作；
[0062] S6,对变异生成的个体与原种群中的个体进行交叉操作；
[0063] S7,采用非支配排序机制进行选择操作；
[0064]S8,判断是否达到最大迭代次数，若否，则跳到S5,继续进化操作；若是，则跳到 S9；
[0065]S9,对pareto解进行解码；
[0066]S10,判断是否还存在未进行的测试阶段，若存在，跳到S11;若否，则结束求解过 程。
[0067] S11，更新下一测试阶段的测试资源，跳到S4,进入下一测试阶段；
[0068] 下面对本发明的方案做进一步的说明。在本发明的方案中，首先假设串并行软 件系统由m个串联子系统构成，每个子系统Sj(j= 1，2,…，m)由rij个冗余模块Mjp… ，Mjk，并联组成；每个模块的测试是单独进行的；任意模块M#的平均失效次数符合非 齐次泊松过程分布；每次失效（错误）的发生是相互独立的。
[0069] 步骤S1中涉及编码设计：
[0070] 采用一维整数向量编码表示一个个体，如图3所示。在每个编码中，有m个整数向 量，r』，…，r』???，rm，每个向量包含nj个元素t#，…，tjk,…，％。r』表不子系统s』中每 个模块分配到的测试资源向量，且
[0071] r,' =~夕卩，…，、.，tjk> 0,k= 1，2,…，nj
[0072] 其中tjk表示模块Mjk所分配到的测试资源。
[0073] 步骤S2中涉及测试阶段划分：
[0074]如图4所示，将测试资源T分为p个测试阶段：
[0075] (T0= 0,TJ，…，（Th，凡]，…，（V"Tp=T]
[0076] 步骤S3中涉及控制参数设计：包括种群规模、 迭代次数、交叉概率、变异概率、模 块可靠性阈值等进行设置；
[0077] 在本发明的一个实施实例中，种群规模N= 20,迭代次数G= 200,缩放系数F= 0. 5,交叉概率CR= 0. 5,模块可靠性阈值0 = 0. 99。
[0078] 步骤S4中涉及种群初始化设计：种群初始化是按照不同测试阶段采用不同的方 法进行。
[0079] (1)对于第i= 1个测试阶段（TeOJJ，由于系统各个模块的可靠性都较低，采 用随机的方法初始化每个子系统中每个模块的测试资源。
[0081] 其中，rand(Ul，u2)函数表示在区间（Ul，u2)内随机取整数，tjk表示模块Mjk所分配 到的测试资源。
[0082] 在本发明的一个实施实例中，如图5,第i= 1个测试阶段〇；= 0，TJ的种群初 始化过程为：对于模块Mn，在〇；= 0，TJ之间随机生成测试资源数tn;对于子系统S2，分 别对模块M21、M22、M23和M24在剩余的资源区间（0,Trk)内分别生成随机资源数t21、t22、t23 和t24;对于子系统S3，分别对模块M31和M32在剩余的资源区间
内分别 生成随机资源数t31和132;依次类推，为每一个模块生成一个测试资源。
[0083] (2)对于第i个（i多2)测试阶段（Th，TJ，种群初始化的方法是根据模块已达到 的可靠性rjk分配测试资源。
[0085] 其中，0是用户希望达到的模块可靠性阈值rjk是模块Mjk已经达到的可靠性值。
[0086] 步骤S5中涉及变异操作设计：本发明采用的变异操作为
[0088] 其中，F为缩放因子，FG[0,2] 是变异后的个体；乂^^^^肩随机整数， 表示个体在种群中的序号；是当代最优个体。
[0089] 步骤S6中涉及交叉操作设计：交叉操作是对原来个体t 和变异 后的个体毛?為，…，进行的，本发明采用的交叉操作是位交叉。设交叉后的个体
[0092] 其中CR是交叉因子，CRG[0, 1]，控制个体间交叉的程度；rand(0, 1)函数表示在 区间（〇，1)内取得随机数。
[0093] 步骤S7中涉及选择操作设计：本发明采用的是非支配排序机制进行的选择操作， 步骤为：根据目标函数采用快速非支配排序对种群进行分层，并通过计算个体拥挤度的方 式衡量个体在每层的优劣，根据个体的分层和拥挤度的大小选取相应的个体组成新的种 群。
[0094] 本发明采用的目标函数为
[0098] s.t.
[0099] Tia^T
[0100] 0 < tiJk< T「Th
[0101] 其中，表示模块11A在第i个测试阶段所分配到的测试资源，r$表示模块Mjk 在第i个测试阶段的可靠性值，且rijk=rjk (x/tijk)，氏(xATi-Tg))、(；和Tia分别表示软件 系统在第i个测试阶段的总体可靠性、总体测试代价和系统实际消耗的总测试资源，hk(X/ tijk)和qk(i^k)分别表示模块M#在第i个测试阶段的可靠性和测试代价，均为测试资源的 函数，表示为：
[0104] 其中，15、13』15、1』15、7』 15和2』15是是固定的参数。
[0105] 本发明采用的快速非支配排序算法步骤为：
[0106] (1)计算每个个体的np值和sp值，记录np= 0的所有个体为Pareto第一级，其 中np为支配个数，表示在可行解空间中，可以支配解p的所有解的数量，sp为被支配个体 的集合，表示在可行解空间中，被解P所支配的解的集合。
[0107] (2)按顺序访问第一级的sp集合中的所有个体，对其np值执行减一操作，如果得 到np为0,则该个体为Pareto第二级；
[0108] (3)按顺序访问第二级的sp集合中的所有个体，对其np值执行减一操作，如果得 到np为0,则该个体为Pareto第三级；
[0109] (4)重复以上操作，直到将种群中的所有个体分配到Pareto级别。
[0110] 本发明采用的拥挤度计算方法为：
[0111] (1)对于种群中的任意一个个体i，初始化拥挤度的值为〇,即
[0112] (2)对于每个目标函数，根据第t个目标函数值对种群中的所有个体按照升序排 序。
[0113] (3)记录第一个个体和最有一个个体的拥挤度为无穷大，即
第y个个体的拥挤度为第y+1和第y个体的所有目标函数值之差的和，，
[0114] 其中，表示种群中第y个个体的拥挤度，表示种群中第y个个体的第 T个目标函数值的大小，
分别表示种群中第t个目标函数的最大值和最小值。
[0115] 步骤S9中涉及个体解码设计：包括计算每个模块的可靠性hk、每个模块的测试代 价C#和系统的实际测试时间Tia。
[0116] 步骤S11中涉及下一测试阶段测试资源的更新操作设计：下一个测试阶段的测试 资源更新按照：
[0118] 图6为本发明的一个实施实例中本发明技术与现有技术结果的对比。从图6可以 看出，本发明能够在节省测试资源的前提下获得较高的测试代价。
[0119] 本发明为了解决现有技术中软件测试资源分配方案因不考虑各模块可靠性随着 测试进程发生变化的情况而导致测试资源浪费、测试效果差的问题，提供了一种基于多目 标差异演化算法的软件测试资源动态分配方法，该方法可应用于串并行软件系统的模块测 试中。
【主权项】
1. 基于多目标差异演化算法的软件测试资源动态分配方法，其特征在于：包括以下步 骤： (1) 、对所求问题进行分析，为可行解设计编码方法； (2) 、对整个测试环节进行划分，划分为若干个测试阶段； (3) 、对差异演化算法中的种群规模、迭代次数、交叉概率、变异概率等控制参数进行设 置； (4) 、对种群进行初始化操作； (5) 、对种群中的个体进行变异操作； (6) 、对变异生成的个体与原种群中的个体进行交叉操作； (7) 、采用非支配排序机制进行选择操作； (8) 、判断是否达到最大迭代次数，若否，则跳到步骤（5)，继续进化操作；若是，则跳到 步骤（9); (9) 、对pareto解进行解码； (10) 、判断是否还存在未进行的测试阶段，若存在，跳到步骤（11);若否，则结束求解 过程； (11) 、更新下一测试阶段的测试资源，跳到步骤（4)，进入下一测试阶段。2. 根据权利要求1所述的基于多目标差异演化算法的软件测试资源动态分配方法，其 特征在于：步骤（1)中为可行解进行一维整数向量编码；且若软件系统包含m个串联子系 统，每个子系统I (j = 1，2,…，m)由r^_个并联模块组成，则每个个体包含m 个整数向量1\，···，Γ，··，rm，每个向量包含η』个元素 Gi，…，…，〇?；，tjk表示模块Mjk所 分配到的测试资源。3. 根据权利要求1所述的基于多目标差异演化算法的软件测试资源动态分配方法，其 特征在于：步骤（2)中，将测试资源T分为p个测试阶段： (T0= 0, T J，…，（Th, Ti]，…Tp= T] 〇4. 根据权利要求1所述的基于多目标差异演化算法的软件测试资源动态分配方法，其 特征在于：步骤（3)中，对差异演化算法中的种群规模、迭代次数、交叉概率、变异概率这些 控制参数进行设置。5. 根据权利要求1所述的基于多目标差异演化算法的软件测试资源动态分配方法，其 特征在于：步骤（4)中，对种群进行初始化操作，按照不同测试阶段采用不同的种群初始化 方法； 在步骤（4)中，对于第i = 1个测试阶段（Ttl= 0, T1],由于系统各个模块的可靠性都 较低，采用随机的方法初始化每个子系统中每个模块的测试资源：其中，rand(U1, U2)函数表示在区间（UpU2)内随机取整数； 在步骤⑷中，对于第i个（i》2)测试阶段OV1, Ti]，种群初始化的方法是根据模块 已达到的可靠性rjk分配测试资源：其中，Θ是用户希望达到的模块可靠性阈值，rjk是模块Mjk已经达到的可靠性值。6. 根据权利要求1所述的基于多目标差异演化算法的软件测试资源动态分配方法，其 特征在于：步骤（5)中，对种群中的个体进行变异操作，采用方法是DE/best/2/bin模式。7. 根据权利要求1所述的基于多目标差异演化算法的软件测试资源动态分配方法，其 特征在于：步骤（6)中，对变异生成的个体与原种群中的个体进行位交叉操作，生成2个不 同的个体。8. 根据权利要求1所述的基于多目标差异演化算法的软件测试资源动态分配方法，其 特征在于：步骤（7)中，采用非支配排序机制进行选择操作，选择的对象集合包括原种群个 体、变异后的个体以及交叉产生的个体； 步骤（7)中，非支配排序机制是指对种群按照优化目标函数进行分层，并计算个体拥 挤度来衡量个体在每层的优劣，然后根据个体的分层和拥挤度的大小选取较优的个体组成 新的种群； 步骤（7)中，优化目标函数为：s. t. Tia^ T ,-Ti^1 〇 < T 其中，tiA表示模块M Λ在第i个测试阶段所分配到的测试资源，r $表示模块M Λ在第i 个测试阶段的可靠性值，且i^_k= r Λ(X/t$)，Ri (V(Ti-IV1))、(；和T ia分别表示软件系统在 第i个测试阶段的总体可靠性、总体测试代价和系统实际消耗的总测试资源，rA(x/tiA)和 Cjk (rijk)分别表示模块Mjk在第i个测试阶段的可靠性和测试代价，均为测试资源的函数。9. 根据权利要求1所述的基于多目标差异演化算法的软件测试资源动态分配方法，其 特征在于：步骤（9)中，对pareto解进行解码，具体操作包括：计算每个模块的可靠性rjk， 计算每个模块的测试代价，计算软件系统的实际测试时间Ti'10. 根据权利要求1所述的基于多目标差异演化算法的软件测试资源动态分配方法， 其特征在于：步骤（11)中，更新下一测试阶段的测试资源，方法为： T广 HTh-T，)。
【专利摘要】本发明公开了一种基于多目标差异演化算法的软件测试资源动态分配方法，可应用于串并联软件系统的模块化测试。它是针对目前测试资源分配方法不考虑随着测试进程发生变化而导致资源浪费的情况。该方法包括步骤：S1，为可行解编码；S2，测试阶段划分；S3，控制参数设置；S4，初始化种群；S5，变异操作；S6，交叉操作；S7，基于非支配排序的选择操作；S8，判断是否达到最大迭代次数，若否，则跳到S5；若是，则跳到S9；S9，为pareto解解码；S10，判断是否还存在未进行的测试阶段，若否，则结束求解过程；若存在，跳到S11；S11，更新下一测试阶段的测试资源，跳到S4，进入下一测试阶段。
【IPC分类】G06F9/50, G06F11/36
【公开号】CN104899101
【申请号】CN201510320713
【发明人】张国富, 苏兆品, 岳峰, 齐美彬, 蒋建国, 王永奇
【申请人】合肥工业大学
【公开日】2015年9月9日
【申请日】2015年6月10日
【技术领域】
[0001] 本发明涉及软件测试方法领域，具体是一种基于多目标差异演化算法的软件测试 资源动态分配方法。
【背景技术】
[0002] 随着软件系统的广泛应用，软件复杂度不断提高，包括的模块越多。在测试过程 中，每个模块都需要经过测试。特别是在软件的单元测试中，不同模块的测试活动都在激烈 争夺有限的测试资源，不同的测试活动也会带来不同的成本的上升与可靠性的增加。软件 工程师必须清楚如何将测试资源分配给不同的模块测试。测试资源分配问题就是如何把有 限的测试资源分配给每一个模块，从而保证软件系统的可靠性最大。
[0003] 测试资源分配问题是系统可靠性优化中的关键和重要问题。自二十世纪九十年代 以来，已经成为研宄的热点问题。目前的研宄大都是基于测试代价、系统可靠性、测试资源 为核心的多目标优化问题。
[0004] 但是已有的测试资源分配模型和分配方法均属于静态分配测试资源的方法，即根 据系统初始时刻各模块的可靠性进行测试资源的分配，很少考虑各模块可靠性随着测试进 程发生变化的情况。这些模型和方法的缺点是会造成测试资源大量浪费在可靠性已经很 高、不在需要测试资源的模块上，导致在测试完成后，有些模块的可靠性远远低于系统的 可靠性，使软件测试的效果不佳。
【发明内容】
[0005] 本发明的目的是提供一种基于多目标差异演化算法的软件测试资源动态分配方 法，以解决现有技术软件测试资源分配方案因不考虑各模块可靠性随着测试进程发生变化 的情况而导致测试资源浪费、测试效果差的问题，。
[0006] 为了达到上述目的，本发明所采用的技术方案为：
[0007] 基于多目标差异演化算法的软件测试资源动态分配方法，其特征在于：包括以下 步骤：
[0008] (1)、对所求问题进行分析，为可行解设计编码方法；
[0009] (2)、对整个测试环节进行划分，划分为若干个测试阶段；
[0010] (3)、对差异演化算法中的种群规模、迭代次数、交叉概率、变异概率等控制参数进 行设置；
[0011](4)、对种群进行初始化操作；
[0012] (5)、对种群中的个体进行变异操作；
[0013] (6)、对变异生成的个体与原种群中的个体进行交叉操作；
[0014](7)、采用非支配排序机制进行选择操作；
[0015] (8)、判断是否达到最大迭代次数，若否，则跳到步骤（5)，继续进化操作；若是，则 跳到步骤（9);
[0016](9)、对pareto解进行解码；
[0017] (10)、判断是否还存在未进行的测试阶段，若存在，跳到步骤（11);若否，则结束 求解过程；
[0018](11)、更新下一测试阶段的测试资源，跳到步骤（4)，进入下一测试阶段。
[0019] 所述的基于多目标差异演化算法的软件测试资源动态分配方法，其特征在于：步 骤（1)中为可行解进行一维整数向量编码；且若软件系统包含m个串联子系统，每个子系统 Sj(j= 1，2,…，m)由rij个并联模块M#，…，Mjk,…组成，贝1」每个个体包含m个整数向 量Fj，…，Fj…，Fm，每个向量包含nj个元素tjl，…，tjk,…，，tjk表不模块Mjk所分配 到的测试资源。
[0020] 所述的基于多目标差异演化算法的软件测试资源动态分配方法，其特征在于：步 骤（2)中，将测试资源T分为p个测试阶段：
[0021] (T0= 0，TJ，...，（ThA]T]〇
[0022] 所述的基于多目标差异演化算法的软件测试资源动态分配方法，其特征在于：步 骤（3)中，对差异演化算法中的种群规模、迭代次数、交叉概率、变异概率等控制参数进行 设置。
[0023] 所述的基于多目标差异演化算法的软件测试资源动态分配方法，其特征在于：步 骤（4)中，对种群进行初始化操作，按照不同测试阶段采用不同的种群初始化方法；
[0024] 在步骤⑷中，对于第i= 1个测试阶段〇；= 0，TJ，由于系统各个模块的可靠 性都较低，采用随机的方法初始化每个子系统中每个模块的测试资源：
[0026] 其中，rand(Ul，u2)函数表示在区间（Ul，u2)内随机取整数；
[0027] 在步骤⑷中，对于第i个（i彡2)测试阶段d，TJ，种群初始化的方法是根据 模块已达到的可靠性rjk分配测试资源：
[0029]其中，0是用户希望达到的模块可靠性阈值rjk是模块Mjk已经达到的可靠性值。[0030] 所述的基于多目标差异演化算法的软件测试资源动态分配方法，其特征在于：步 骤（5)中，对种群中的个体进行变异操作，采用方法是DE/best/2/bin模式。
[0031] 所述的基于多目标差异演化算法的软件测试资源动态分配方法，其特征在于：步 骤（6)中，对变异生成的个体与原种群中的个体进行位交叉操作，生成2个不同的个体。
[0032] 所述的基于多目标差异演化算法的软件测试资源动态分配方法，其特征在于：步 骤（7)中，采用非支配排序机制进行选择操作，选择的对象集合包括原种群个体、变异后的 个体以及交叉产生的个体；
[0033] 步骤（7)中，非支配排序机制是指对种群按照优化目标函数进行分层，并计算个 体拥挤度来衡量个体在每层的优劣，然后根据个体的分层和拥挤度的大小选取较优的个体 组成新的种群；
[0034] 步骤（7)中，优化目标函数为：
[0038] s.t.
[0039] Tia^T
[0040] 0 <tiJk彡T「Th
[0041] 其中，tijk表示模块Mjk在第i个测试阶段所分配到的测试资源，rijk表示模块MJk 在第i个测试阶段的可靠性值，且rijk=rjk (x/tijk)，氏(xATi-Tg))、(；和Tia分别表示软件 系统在第i个测试阶段的总体可靠性、总体测试代价和系统实际消耗的总测试资源，hk(X/ tijk)和qk(i^k)分别表示模块M#在第i个测试阶段的可靠性和测试代价，均为测试资源的 函数。
[0042] 所述的基于多目标差异演化算法的软件测试资源动态分配方法，其特征在于：步 骤（9)中，对pareto解进行解码，具体操作包括：计算每个模块的可靠性rjk，计算每个模块 的测试代价qk，计算软件系统的实际测试时间T，。
[0043] 所述的基于多目标差异演化算法的软件测试资源动态分配方法，其特征在于：步 骤（11)中，更新下一测试阶段的测试资源，方法为：
[0044] 凡―Ti-CTi-TH-Tj)。
[0045] 本发明提出了一种基于多目标差异演化算法的软件测试资源动态分配方法，考虑 各模块可靠性随着测试进程发生变化的情况，在测试进程中动态地为各个模块分配测试资 源，可以节省系统测试资源的消耗，提高测试效率，提高软件系统的可靠性。本发明优点 为：
[0046] (1)本发明采用的是以测试资源为约束、联合优化系统可靠性、系统测试代价和实 际消耗的系统测试资源，不会由于三者分离而产生某一方面性能损失；
[0047] (2)本发明将整个测试环节划分为若干个测试阶段，在每个测试阶段根据前一测 试阶段的可靠性为每个模块动态地分配测试资源，解决了已有测试资源分配方案带来的测 试资源浪费、测试效率低的缺陷；
[0048] (3)本发明中采用的是基于非支配排序机制的多目标差异演化算法，搜索速度快、 解质量高，因此可以在系统可靠性、系统测试代价和实际消耗的系统测试资源之间达到平 衡；
[0049] (4)最后，由于演化算法操作简单，性能好，曾在首届IEEE演化计算大赛中表现超 群，非常适合在实际系统中取得应用，有较好的应用前景。
【附图说明】
[0050] 图1为本发明实施例中基于多目标差异演化算法的软件测试资源动态分配方法 的流程示意图；
[0051]图2为本发明实施对象串并行软件系统结构示意图。
[0052] 图3为本发明采用的一维整数向量编码示意图。
[0053] 图4为软件测试环节划分示意图。
[0054]图5为本发明一个实时实例串并行软件系统结构示意图。
[0055] 图6为本发明的一个实施实例中本发明技术与现有技术结果的对比。
【具体实施方式】
[0056] 本发明为了解决现有技术中软件测试资源分配方案因不考虑各模块可靠性随着 测试进程发生变化的情况而导致测试资源浪费、测试效果差的问题，提供了一种基于多目 标差异演化算法的软件测试资源动态分配方法，该方法主要应用于如图2所示的串并行软 件系统的模块测试中。如图1的流程图所示，本发明中的方法的基本过程为：
[0057] S1，对所求问题进行分析，为可行解设计编码方法；
[0058] S2,对整个测试环节进行划分，划分为若干个测试阶段；
[0059]S3,对差异演化算法中的种群规模、迭代次数、交叉概率、变异概率等控制参数进 行设置；
[0060]S4,对种群进行初始化操作；
[0061] S5，对种群中的个体进行变异操作；
[0062] S6,对变异生成的个体与原种群中的个体进行交叉操作；
[0063] S7,采用非支配排序机制进行选择操作；
[0064]S8,判断是否达到最大迭代次数，若否，则跳到S5,继续进化操作；若是，则跳到 S9；
[0065]S9,对pareto解进行解码；
[0066]S10,判断是否还存在未进行的测试阶段，若存在，跳到S11;若否，则结束求解过 程。
[0067] S11，更新下一测试阶段的测试资源，跳到S4,进入下一测试阶段；
[0068] 下面对本发明的方案做进一步的说明。在本发明的方案中，首先假设串并行软 件系统由m个串联子系统构成，每个子系统Sj(j= 1，2,…，m)由rij个冗余模块Mjp… ，Mjk，并联组成；每个模块的测试是单独进行的；任意模块M#的平均失效次数符合非 齐次泊松过程分布；每次失效（错误）的发生是相互独立的。
[0069] 步骤S1中涉及编码设计：
[0070] 采用一维整数向量编码表示一个个体，如图3所示。在每个编码中，有m个整数向 量，r』，…，r』???，rm，每个向量包含nj个元素t#，…，tjk,…，％。r』表不子系统s』中每 个模块分配到的测试资源向量，且
[0071] r,' =~夕卩，…，、.，tjk> 0,k= 1，2,…，nj
[0072] 其中tjk表示模块Mjk所分配到的测试资源。
[0073] 步骤S2中涉及测试阶段划分：
[0074]如图4所示，将测试资源T分为p个测试阶段：
[0075] (T0= 0,TJ，…，（Th，凡]，…，（V"Tp=T]
[0076] 步骤S3中涉及控制参数设计：包括种群规模、 迭代次数、交叉概率、变异概率、模 块可靠性阈值等进行设置；
[0077] 在本发明的一个实施实例中，种群规模N= 20,迭代次数G= 200,缩放系数F= 0. 5,交叉概率CR= 0. 5,模块可靠性阈值0 = 0. 99。
[0078] 步骤S4中涉及种群初始化设计：种群初始化是按照不同测试阶段采用不同的方 法进行。
[0079] (1)对于第i= 1个测试阶段（TeOJJ，由于系统各个模块的可靠性都较低，采 用随机的方法初始化每个子系统中每个模块的测试资源。
[0081] 其中，rand(Ul，u2)函数表示在区间（Ul，u2)内随机取整数，tjk表示模块Mjk所分配 到的测试资源。
[0082] 在本发明的一个实施实例中，如图5,第i= 1个测试阶段〇；= 0，TJ的种群初 始化过程为：对于模块Mn，在〇；= 0，TJ之间随机生成测试资源数tn;对于子系统S2，分 别对模块M21、M22、M23和M24在剩余的资源区间（0,Trk)内分别生成随机资源数t21、t22、t23 和t24;对于子系统S3，分别对模块M31和M32在剩余的资源区间
内分别 生成随机资源数t31和132;依次类推，为每一个模块生成一个测试资源。
[0083] (2)对于第i个（i多2)测试阶段（Th，TJ，种群初始化的方法是根据模块已达到 的可靠性rjk分配测试资源。
[0085] 其中，0是用户希望达到的模块可靠性阈值rjk是模块Mjk已经达到的可靠性值。
[0086] 步骤S5中涉及变异操作设计：本发明采用的变异操作为
[0088] 其中，F为缩放因子，FG[0,2] 是变异后的个体；乂^^^^肩随机整数， 表示个体在种群中的序号；是当代最优个体。
[0089] 步骤S6中涉及交叉操作设计：交叉操作是对原来个体t 和变异 后的个体毛?為，…，进行的，本发明采用的交叉操作是位交叉。设交叉后的个体
[0092] 其中CR是交叉因子，CRG[0, 1]，控制个体间交叉的程度；rand(0, 1)函数表示在 区间（〇，1)内取得随机数。
[0093] 步骤S7中涉及选择操作设计：本发明采用的是非支配排序机制进行的选择操作， 步骤为：根据目标函数采用快速非支配排序对种群进行分层，并通过计算个体拥挤度的方 式衡量个体在每层的优劣，根据个体的分层和拥挤度的大小选取相应的个体组成新的种 群。
[0094] 本发明采用的目标函数为
[0098] s.t.
[0099] Tia^T
[0100] 0 < tiJk< T「Th
[0101] 其中，表示模块11A在第i个测试阶段所分配到的测试资源，r$表示模块Mjk 在第i个测试阶段的可靠性值，且rijk=rjk (x/tijk)，氏(xATi-Tg))、(；和Tia分别表示软件 系统在第i个测试阶段的总体可靠性、总体测试代价和系统实际消耗的总测试资源，hk(X/ tijk)和qk(i^k)分别表示模块M#在第i个测试阶段的可靠性和测试代价，均为测试资源的 函数，表示为：
[0104] 其中，15、13』15、1』15、7』 15和2』15是是固定的参数。
[0105] 本发明采用的快速非支配排序算法步骤为：
[0106] (1)计算每个个体的np值和sp值，记录np= 0的所有个体为Pareto第一级，其 中np为支配个数，表示在可行解空间中，可以支配解p的所有解的数量，sp为被支配个体 的集合，表示在可行解空间中，被解P所支配的解的集合。
[0107] (2)按顺序访问第一级的sp集合中的所有个体，对其np值执行减一操作，如果得 到np为0,则该个体为Pareto第二级；
[0108] (3)按顺序访问第二级的sp集合中的所有个体，对其np值执行减一操作，如果得 到np为0,则该个体为Pareto第三级；
[0109] (4)重复以上操作，直到将种群中的所有个体分配到Pareto级别。
[0110] 本发明采用的拥挤度计算方法为：
[0111] (1)对于种群中的任意一个个体i，初始化拥挤度的值为〇,即
[0112] (2)对于每个目标函数，根据第t个目标函数值对种群中的所有个体按照升序排 序。
[0113] (3)记录第一个个体和最有一个个体的拥挤度为无穷大，即
第y个个体的拥挤度为第y+1和第y个体的所有目标函数值之差的和，，
[0114] 其中，表示种群中第y个个体的拥挤度，表示种群中第y个个体的第 T个目标函数值的大小，
分别表示种群中第t个目标函数的最大值和最小值。
[0115] 步骤S9中涉及个体解码设计：包括计算每个模块的可靠性hk、每个模块的测试代 价C#和系统的实际测试时间Tia。
[0116] 步骤S11中涉及下一测试阶段测试资源的更新操作设计：下一个测试阶段的测试 资源更新按照：
[0118] 图6为本发明的一个实施实例中本发明技术与现有技术结果的对比。从图6可以 看出，本发明能够在节省测试资源的前提下获得较高的测试代价。
[0119] 本发明为了解决现有技术中软件测试资源分配方案因不考虑各模块可靠性随着 测试进程发生变化的情况而导致测试资源浪费、测试效果差的问题，提供了一种基于多目 标差异演化算法的软件测试资源动态分配方法，该方法可应用于串并行软件系统的模块测 试中。
【主权项】
1. 基于多目标差异演化算法的软件测试资源动态分配方法，其特征在于：包括以下步 骤： (1) 、对所求问题进行分析，为可行解设计编码方法； (2) 、对整个测试环节进行划分，划分为若干个测试阶段； (3) 、对差异演化算法中的种群规模、迭代次数、交叉概率、变异概率等控制参数进行设 置； (4) 、对种群进行初始化操作； (5) 、对种群中的个体进行变异操作； (6) 、对变异生成的个体与原种群中的个体进行交叉操作； (7) 、采用非支配排序机制进行选择操作； (8) 、判断是否达到最大迭代次数，若否，则跳到步骤（5)，继续进化操作；若是，则跳到 步骤（9); (9) 、对pareto解进行解码； (10) 、判断是否还存在未进行的测试阶段，若存在，跳到步骤（11);若否，则结束求解 过程； (11) 、更新下一测试阶段的测试资源，跳到步骤（4)，进入下一测试阶段。2. 根据权利要求1所述的基于多目标差异演化算法的软件测试资源动态分配方法，其 特征在于：步骤（1)中为可行解进行一维整数向量编码；且若软件系统包含m个串联子系 统，每个子系统I (j = 1，2,…，m)由r^_个并联模块组成，则每个个体包含m 个整数向量1\，···，Γ，··，rm，每个向量包含η』个元素 Gi，…，…，〇?；，tjk表示模块Mjk所 分配到的测试资源。3. 根据权利要求1所述的基于多目标差异演化算法的软件测试资源动态分配方法，其 特征在于：步骤（2)中，将测试资源T分为p个测试阶段： (T0= 0, T J，…，（Th, Ti]，…Tp= T] 〇4. 根据权利要求1所述的基于多目标差异演化算法的软件测试资源动态分配方法，其 特征在于：步骤（3)中，对差异演化算法中的种群规模、迭代次数、交叉概率、变异概率这些 控制参数进行设置。5. 根据权利要求1所述的基于多目标差异演化算法的软件测试资源动态分配方法，其 特征在于：步骤（4)中，对种群进行初始化操作，按照不同测试阶段采用不同的种群初始化 方法； 在步骤（4)中，对于第i = 1个测试阶段（Ttl= 0, T1],由于系统各个模块的可靠性都 较低，采用随机的方法初始化每个子系统中每个模块的测试资源：其中，rand(U1, U2)函数表示在区间（UpU2)内随机取整数； 在步骤⑷中，对于第i个（i》2)测试阶段OV1, Ti]，种群初始化的方法是根据模块 已达到的可靠性rjk分配测试资源：其中，Θ是用户希望达到的模块可靠性阈值，rjk是模块Mjk已经达到的可靠性值。6. 根据权利要求1所述的基于多目标差异演化算法的软件测试资源动态分配方法，其 特征在于：步骤（5)中，对种群中的个体进行变异操作，采用方法是DE/best/2/bin模式。7. 根据权利要求1所述的基于多目标差异演化算法的软件测试资源动态分配方法，其 特征在于：步骤（6)中，对变异生成的个体与原种群中的个体进行位交叉操作，生成2个不 同的个体。8. 根据权利要求1所述的基于多目标差异演化算法的软件测试资源动态分配方法，其 特征在于：步骤（7)中，采用非支配排序机制进行选择操作，选择的对象集合包括原种群个 体、变异后的个体以及交叉产生的个体； 步骤（7)中，非支配排序机制是指对种群按照优化目标函数进行分层，并计算个体拥 挤度来衡量个体在每层的优劣，然后根据个体的分层和拥挤度的大小选取较优的个体组成 新的种群； 步骤（7)中，优化目标函数为：s. t. Tia^ T ,-Ti^1 〇 < T 其中，tiA表示模块M Λ在第i个测试阶段所分配到的测试资源，r $表示模块M Λ在第i 个测试阶段的可靠性值，且i^_k= r Λ(X/t$)，Ri (V(Ti-IV1))、(；和T ia分别表示软件系统在 第i个测试阶段的总体可靠性、总体测试代价和系统实际消耗的总测试资源，rA(x/tiA)和 Cjk (rijk)分别表示模块Mjk在第i个测试阶段的可靠性和测试代价，均为测试资源的函数。9. 根据权利要求1所述的基于多目标差异演化算法的软件测试资源动态分配方法，其 特征在于：步骤（9)中，对pareto解进行解码，具体操作包括：计算每个模块的可靠性rjk， 计算每个模块的测试代价，计算软件系统的实际测试时间Ti'10. 根据权利要求1所述的基于多目标差异演化算法的软件测试资源动态分配方法， 其特征在于：步骤（11)中，更新下一测试阶段的测试资源，方法为： T广 HTh-T，)。
【专利摘要】本发明公开了一种基于多目标差异演化算法的软件测试资源动态分配方法，可应用于串并联软件系统的模块化测试。它是针对目前测试资源分配方法不考虑随着测试进程发生变化而导致资源浪费的情况。该方法包括步骤：S1，为可行解编码；S2，测试阶段划分；S3，控制参数设置；S4，初始化种群；S5，变异操作；S6，交叉操作；S7，基于非支配排序的选择操作；S8，判断是否达到最大迭代次数，若否，则跳到S5；若是，则跳到S9；S9，为pareto解解码；S10，判断是否还存在未进行的测试阶段，若否，则结束求解过程；若存在，跳到S11；S11，更新下一测试阶段的测试资源，跳到S4，进入下一测试阶段。
【IPC分类】G06F9/50, G06F11/36
【公开号】CN104899101
【申请号】CN201510320713
【发明人】张国富, 苏兆品, 岳峰, 齐美彬, 蒋建国, 王永奇
【申请人】合肥工业大学
【公开日】2015年9月9日
【申请日】2015年6月10日
最新回复(0)