1.本发明属于软件测试技术领域，尤其是软件回归测试领域，具体涉及一种基于改进粒子群算法的测试用例优先级排序方法。
背景技术：
2.在软件研发过程中，测试用例优先级技术作为一种高效的回归测试技术，通过将测试用例按照某种目标进行排序以获得更高的测试效率，从而降低测试成本和提高缺陷检测效率。
3.粒子群算法是一种启发式随机优化算法，每个粒子追逐自身最优粒子和全局最优位置搜索；粒子群算法具有简单易用、计算迅速、鲁棒性好等优点，但传统粒子群算法存在收敛精度低、容易陷入局部极值、出现早熟收敛或停滞等问题。
4.目前，应用于测试用例排序的粒子群算法有中国专利公布号为cn 109271320 a、名称为“一种上位多目标测试用例优先级排序方法”，以测试用例序列对待测程序的平均分支覆盖率和有效执行时间作为适应度评价函数；然后，采用上位交叉的方法产生新个体，使用非支配解集中的粒子作为全局最优粒子；该排序方法存在的问题是：对测试用例的错误覆盖率进行分析，但在黑盒测试中，很难获取测试用例对代码的覆盖情况，因此面对黑盒测试时需要设计新的适应度函数，对黑盒测试中测试用例排序的可行性差。
技术实现要素：
5.本发明的目的在于解决上述现有技术存在的问题，提供一种基于改进粒子群算法的测试用例优先级排序方法，不依赖缺陷对代码覆盖率的分析，提高在黑盒测试环境下的排序可行性。
6.为实现上述目的，本发明一种基于改进粒子群算法的测试用例优先级排序方法采用的技术方案是包括以下几个步骤：
7.步骤1)：提取各个测试用例在每个回归测试周期内的历史执行通过数据，形成测试用例集t＝{t1，t2，...，tn}，随机生成一个1
×
n的矩阵作为测试用例序列ts，测试用例序列ts中的每个元素对应于t1，t2，
…
，tn，n为测试用例个数；
8.步骤2)：构造适应度函数将一种测试用例序列ts作为一个粒子，并初始化种群参数；k为测试用例序列ts的第k列，1≤k≤n，lf(k)是第k列对应的测试用例最后一次出现执行失效的回归测试周期数，m为回归测试总周期数；
9.步骤3)：计算出每一个粒子的适应度值，对所有的适应度值降序排列，去除全体粒子个体中的适应度值排在后列25％的粒子个体，对全体粒子个体中的适应度值排在前列25％的个体进行复制保留，对全体粒子个体中的适应度值排在前列75％的粒子个体进行位
置和速度更新，最后将更新后的75％的粒子个体加入到所述的复制保留的25％的粒子个体中，组成新种群；
10.步骤4)：重复步骤3)，直到适应度函数aphf(ts)达到或最接近设定的期望适应度值停止，得到最优的测试用例排序序列。
11.进一步地，步骤3)中，每个粒子个体的初始位置为1
×
n的矩阵，每个粒子个体速度为范围在0～1的随机生成的1
×
n矩阵，将速度矩阵中的每一位元素与随机产生的0～1的随机数进行对比，当某一位的值大于所述的随机数时，将粒子个体的位置矩阵中对应的元素与后一列元素对调，再遍历粒子个体速度矩阵中的每一位完成粒子位置更新。
12.进一步地，步骤3)中，根据式进行速度更新，为新一代种群中此粒子的速度，ω为惯性权重，为旧一代种群中此粒子的速度，c1为个体学习因子，c2为群体学习因子，r1和r2为范围在0～1内随机生成的1
×
n的随机数矩阵，为旧一代种群中此粒子的个体历史最佳位置，为旧一代种群的群体历史最佳位置，为旧一代种群中此粒子的位置。
13.更进一步地，计算出改善率当α
t
＞ir2时，增大惯性权重ω，当a
t
≤ir1时，降低惯性权重ω，当ir1＜α
t
≤ir2时，维持惯性权重ω不变；f
g(t-1)
为旧一代种群的群体历史最佳适应度，f
g(t)
为新一代种群的群体历史最佳适应度，ir1为改善率α
t
的最小值，ir2为改善率α
t
的最大值。
14.本发明采用上述技术方案后的技术效果如下：
15.1、本发明是基于回归测试中测试用例最近一次执行失效的位置，设计了一种新的适应度函数，因此不再依赖缺陷对代码覆盖率的分析，不需对代码分析，提高了在黑盒测试环境下的排序可行性。
16.2、通过设计自适应惯性权重更新函数，减少了适应度函数的计算次数，提高粒子群算法种群更新的效率。
附图说明
17.以下结合附图和具体实施方式对本发明作进一步详细说明：
18.图1为本发明一种基于改进粒子群算法的测试用例优先级排序方法的流程图。
具体实施方式
19.参见图1，本发明首先提取测试用例的历史数据，该历史数据为各个测试用例在每个回归测试周期内的历史执行通过情况，记录各个测试的历史执行通过数据，整合这些历史执行通过数据，形成测试用例集t，t＝{t1，t2，...，tn}，其中n为测试用例个数，ti(1≤i≤n)表示第i个测试用例。
20.随机生成一个1
×
n的矩阵，其元素为1至n这n个不重复的自然数，得到一个随机测试用例序列ts。序列ts中的每个元素对应于测试用例集t中下标相同的测试用例，即，序列ts中的1，2，
…
，n对应于测试用例集t中的t1，t2，
…
，tn。
21.在回归测试过程中，近期发生过执行失效的测试用例在下一个回归测试周期中更容易产生执行失效，因此对于一个任意的测试用例序列ts，基于邻近的执行失效，构造适应度函数，用平均邻近失效值(aphf，average proximity historical failure)来衡量一个测试用例序列ts的优劣，其公式为：
[0022][0023]
其中，k表示测试用例序列ts第k列，1≤k≤n，lf(k)是第k列对应的测试用例最后一次出现执行失效的回归测试周期数，n为测试用例个数，m为回归测试总周期数；aphf(ts)的值越高，表示近期发生过执行失效的测试用例在序列中的位置越靠前，排序效果越好，在实际计算中，本发明设定期望适应度值aphf(ts)为0.8。本发明中的适应度函数aphf(ts)与现有的基于粒子群算法的测试用例排序方法相比，不需要分析测试用例对代码的覆盖率，更适用于黑盒测试场景。
[0024]
随机初始化种群参数：包括初始化粒子群的粒子个数为n，其中每一个粒子代表一种随机生成的测试用例序列ts；初始化粒子个体学习因子为c1、群体学习因子为c2、惯性权重ω、最大迭代次数ger、个体历史最佳适应度f
p
、个体历史最佳位置p
id，pbest
、群体历史最佳适应度fg和群体历史最佳位置p
d，gbest
、改善率α
t
的范围为[ir1，ir2]。
[0025]
初始化粒子个体的位置和速度：每个粒子个体的初始位置为1
×
n的矩阵；每个粒子个体速度为范围在0～1的随机生成的1
×
n矩阵。
[0026]
对所述的每一个粒子，即对一种随机生成的测试用例序列ts，根据适应度函数aphf(ts)，计算出每一个粒子的适应度值。对所有的适应度值，按各个粒子的适应度值的大小对粒子个体进行降序排列，适应度值最大的粒子个体排在最前，适应度值最小的粒子个体排在最后。然后，去除全体粒子个体中的适应度值较小的排在后列的25％的粒子个体，对全体粒子个体中的适应度值较大的排在前列的25％的个体进行复制保留，对全体粒子个体中的适应度值较大的排在前列75％的粒子个体进行位置和速度更新，最后将更新后的75％的粒子个体加入到所述的复制保留的25％的粒子个体中，如此组成新的种群，构造出新种群。
[0027]
对排在前列75％的粒子个体进行位置和速度更新时，是更新个体历史最佳适应度和个体历史最佳位置。其中，位置更新方法为：
[0028]
将粒子个体的速度矩阵1
×
n中的每一位元素与随机产生的0～1的随机数进行对比，当速度矩阵中某一位的值大于所述的随机数时，将粒子个体的位置矩阵1
×
n中对应的元素与后一列元素进行对调，若当前元素为最后一位元素，则与第一列的元素进行对调。然后，遍历粒子个体速度矩阵中1
×
n的每一位后，完成粒子的位置更新。
[0029]
其中，速度更新方法为：使用以下公式更新粒子个体的速度：
[0030][0031]
其中，为新一代种群中此粒子的速度，ω为惯性权重，为旧一代种群中此粒子的速度，c1为个体学习因子、c2为群体学习因子，r1和r2为范围在0～1内随机生成的1
×
n的随机数矩阵，为旧一代种群中此粒子的个体历史最佳位置，为旧一代种
群的群体历史最佳位置，为旧一代种群中此粒子的位置。
[0032]
计算改善率α
t
，更新惯性权重ω。通过以下公式计算出改善率α
t
：
[0033][0034]
其中，f
g(t-1)
为旧一代种群的群体历史最佳适应度，f
g(t)
为新一代种群的群体历史最佳适应度；当α
t
＞ir2时，则增大惯性权重ω，当α
t
≤ir1时，则降低惯性权重ω，ir1＜α
t
≤ir2时，维持惯性权重ω不变，其中ir1为改善率α
t
的最小值，ir2为改善率α
t
的最大值，以此实现惯性权重ω的自适应调整，达到减少迭代次数的目的。
[0035]
惯性权重ω的更新公式为：
[0036][0037]
通过对惯性权重ω的自适应更新，更新群体历史最佳适应度和群体历史最佳位置，减少了适应度函数的计算次数，提高了算法的效率。
[0038]
按更新后的惯性权重ω，再重新计算出每一个粒子的适应度值，然后对所有的适应度值再重新进行降序排列、以及对位置和速度重新再更新，最终组成更新的种群。直到某次群体历史最佳适应度的适应度函数值aphf达到或最接近期望适应度值aphf(ts)0.80，或者迭代次数达到上限，得到最优的测试用例排序序列ts
best
。
[0039]
实施例：
[0040]
本实施例以一个简化锅炉系统为例，具体按以下步骤实施：
[0041]
步骤一：提取简化锅炉系统的测试用例历史数据。记录各个测试用例在每个回归测试周期内的历史执行通过情况，整合成测试用例集t，t＝{t1，t2，...，tn}，其中n为测试用例个数，ti(1≤i≤n)表示第i个测试用例。如在简化锅炉系统的某次回归测试过程中，测试用例t1的历史执行通过情况为(1,1,0,0,1,1,0,1,0,1)，其中1表示在这一回归周期，此测试用例t1执行失效，0表示执行通过，则该测试用例在第1、2、5、6、8、10回归周期出现执行失效；测试用例t2的历史执行通过情况为(1,1,0,0,1,0,0,1,1,1)，则该测试用例t2在第1、2、5、8、9、10回归周期出现执行失效。
[0042]
步骤二：构造随机测试用例序列ts。随机生成一个1
×
n的矩阵，其元素为1至n这n个不重复的自然数，得到一个随机测试用例序列ts；ts中每个元素对应步骤一中所述的测试用例集t中下标相同的测试用例；例如某五次随机生成的序列ts为(1,2,3,4,5,6,7,8,9,10)、(3,5,7,1,9,2,4,10,8,6)、(2,6,9,10,4,5,8,1,3,7)、(10,3,9,1,8,2,7,4,6,5)、(10,9,8,7,6,5,4,3,2,1)。
[0043]
步骤三：构造适应度函数并设定期望适应度值。针对其中的任意一个个体，每个测试用例最近一次出现缺陷时在回归测试周期中的位置为lf(k)，若某测试用例最后一次出现执行失败时的回归测试周期为第10周期，则其lf(k)为10，根据lf(k)构建适应度函数为：
其中，k表示测试用例序列ts第k列，lf(k)是第k列对应的测试用例最后一次出现执行失效的回归测试周期数，n为测试用例个数，m为回归测试总周期数；aphf(ts)的值越高，表示近期发生过执行失效的测试用例在序列中的位置越靠前，排序效果越好。设定期望aphf(ts)值为0.80。例如，测试用例t1、t2、t3的lf(k)为10，测试用例t4的lf(k)为7，测试用例t5的lf(k)为5，测试用例t6、t7的lf(k)为8，测试用例t8、t9的lf(k)为2，测试用例t
10
的lf(k)为3，以排序序列ts为(1,2,3,4,5,6,7,8,9,10)为例，则其aphf(ts)值为0.79。
[0044]
步骤四：随机初始化种群；本发明改进粒子群算法参数设置如下：设定粒子个数为100，粒子个体学习因子c1和粒子群体学习因子c2设置为0.8，惯性权重ω的最大值ω
max
为0.4，最小值ω
min
为0.2，最大迭代次数为1000，个体历史最佳适应度为f
p
、个体历史最佳位置为p
id，best
、群体历史最佳适应度为fg和群体历史最佳位置为p
d，gbest
，改善率α
t
的下限ir1为0.001，改善率α
t
的上限ir2为0.002。如某次随机初始化的种群中的粒子为(仅举出前5个粒子编码)：(1,3,4,9,8,7,6,10,2,5)、(6,8,9,4,1,3,2,5,7,10)、(10,9,4,3,6,5,2,1,8,7,)、(9,10,6,7,8,4,5,3,1,2,)、(6,7,1,9,8,3,2,5,4,10)。
[0045]
步骤五：初始化粒子的位置和速度；每个粒子的初始位置为1
×
n的矩阵；每个粒子速度为范围在0～1的随机生成的1
×
n矩阵。如某次初始化的粒子位置为(仅举出前5个粒子编码)：(1,3,4,9,8,7,6,10,2,5)、(6,8,9,4,1,3,2,5,7,10)、(10,9,4,3,6,5,2,1,8,7,)、(9,10,6,7,8,4,5,3,1,2,)、(6,7,1,9,8,3,2,5,4,10)。
[0046]
步骤六：计算粒子适应度；对种群中的每一个粒子，依据步骤三中的适应度函数aphf(ts)的计算式计算每一个粒子的适应度值；以排序序列ts为(1,2,3,4,5,6,7,8,9,10)为例，则其aphf值为0.82。
[0047]
步骤七：构造新种群；以各个粒子的适应度值的大小对粒子进行降序排列，在全体个体中去除掉适应度值较小的后25％的个体，在全体个体中的适应度值前列的25％的个体进行复制保留；对适应度值前列的75％的粒子进行位置和速度更新，并加入复制保留的25％的个体，组成新的种群。
[0048]
步骤7.1：更新粒子位置和速度；位置更新的方法为：将粒子的速度矩阵中的每一位元素与随机产生的0～1的随机数进行对比，当速度矩阵中某一位的值大于随机数时，将粒子的位置矩阵中对应的元素与后一位元素进行对调；遍历粒子速度矩阵中的每一位后，完成粒子的位置更新。用以下公式更新粒子的速度：
[0049]
其中，r1和r2为范围在0～1内随机生成的1
×
n的随机数矩阵，为新一代种群中此粒子的速度，为旧一代种群中此粒子的速度，为旧一代种群中此粒子的位置，为旧一代种群中此粒子的个体历史最佳位置，为旧一代种群的群体历史最佳位置。
[0050]
步骤7.2：更新个体历史最佳适应度和个体历史最佳位置；计算改善率α
t
；更新惯性权重；更新群体历史最佳适应度和群体历史最佳位置；改善率α
t
的计算公式为
其中f
g(t-1)
为旧一代种群的群体历史最佳适应度，f
g(t)
为新一代种群的群体历史最佳适应度；当α
t
＞ir2时增大惯性权重，α
t
≤ir1时降低惯性权重，ir1＜α
t
≤ir2时维持惯性权重不变，以实现惯性权重ω自适应的调整，达到减少迭代次数的目的；惯性权重更新公式为：
[0051]
步骤八：其于更新后的粒子位置和速度，测试用例序列的位置发生了变化，即改变了k列，相应地，改变了回归测试周期lf(k)，因此，要重复步骤六至七，直到某次群体历史最佳适应度的适应度函数值aphf达到或者最接近步骤三中期望的aphf(ts)值的需求，或者迭代次数达到上限。
[0052]
步骤九：得到最优的测试用例序列ts
best
。例如某次实验后，得到的测试用例序列为(3,1,2,7,6,4,5,3,9,8,10)，其aphf值为0.85。
[0053]
以上所述仅为本发明的较佳实施方式，通过以上过程可以实现一种用于回归测试的改进粒子群测试用例优先级排序方法，可以得到较好的测试用例排序，给软件测试工程师提供了一种方案选择。