软件测试是软件生命周期的重要阶段,是构建安全、稳定、可靠的高质量软件的必要环节^[1].如今,软件自身和软件运行环境都变得越来越复杂,为了能够对一个软件的质量做出全面的测试,往往需要综合使用各种测试方法.

在众多的软件测试方法中,组合测试提供了一种对系统中各个组件交互影响所引发故障的有效检测方法.

组合测试的重要研究内容之一是:如何为待测软件系统(software under test,简称SUT)生成一个满足特定条件的测试集.这个问题也被称为组合测试覆盖表生成问题^[2].所谓覆盖表,就是一个N(行)×k(列)的表,其对应的SUT模型中任意t个参数的任意值组合在表中至少出现一次,其中,N代表了测试用例的数目,k是软件系统参数的数目,t是覆盖表强度.如何生成一个N尽可能小的覆盖表,是覆盖表生成问题的关键所在.目前,已有一系列基于数学方法、贪心方法和搜索方法的算法被应用于求解这一问题,然而这些算法中并没有一种方法能够针对任意情形给出最优解.在这些求解算法中,一类基于演化搜索技术的算法表现出了良好的性能,如遗传算法^[3]、粒子群算法、蚁群算法等.

蚁群算法是一种模仿蚂蚁觅食行为的演化搜索算法,通过群智演化的方法来对一系列组合优化问题进行求解.目前,已有相关工作将蚁群算法应用于求解一般覆盖表生成、变力度覆盖表生成和覆盖表排序中.这些研究工作表明,蚁群算法适于求解覆盖表生成等问题.然而,这些研究工作侧重于应用蚁群算法求解覆盖表生成问题,而没有对算法在这一问题求解中的性能进行深入挖掘.例如:蚁群算法是多变种算法,究竟何种变种更适合求解覆盖表生成问题?蚁群算法性能优劣依赖于参数配置,究竟何种参数配置能够发挥算法性能极限?一次生成一条测试用例的生成方式能否发挥出蚁群算法的潜力?如何解决算法运算时间开销大的问题?

为了回答以上问题,探索与挖掘利用蚁群算法生成覆盖表的潜力,本文进行了以下4个层次的研究工作:第1层,算法变种集成,结合覆盖表生成问题将蚁群算法的3个主要变种整合为一个利用蚁群算法生成覆盖表的框架;第2层,算法参数调优,在第1层的算法框架上对算法参数配置进行调优,给出推荐参数配置,并比较优化后3个变种算法性能上的差距;第3层,演化对象结构调整及演化策略改进,改变原有的一次生成一条测试用例的生成方法,使蚁群算法一次对一个表进行演化,同时对算法策略进行相应研究;第4层,利用并行计算降低算法时间开销.

通过以上4个层次的研究,我们发现:经过优化后的算法在时间开销和生成结果上均得到了显著提升,部分结果甚至接近当前已知最优解.

本文第1节介绍覆盖表生成、蚁群算法的相关概念与研究现状.第2节介绍利用蚁群算法生成覆盖表的集成框架.第3节介绍利用蚁群算法生成覆盖表各种变种算法的参数优化,并比较参数优化后的3个基本变种的优劣.第4节介绍如何使用蚁群算法对一个表进行演化.第5节将算法的某些部分并行化.第6节进行全文总结.

1 背 景 1.1 覆盖表及其生成问题

组合测试是一种特殊的软件测试方法,它的使用一般包括下面几个步骤:参数建模、覆盖表生成、测试用例约简和排序、测试用例执行、故障定位、评估.然而,覆盖表生成是其中的一个重要环节,现有的大部分对组合测试的研究工作是针对覆盖表生成而展开的^[4].

下面我们给出一些常用的定义.

定义 1. 如果一个N×k的二维表满足下列两个条件:

(1) 每一列i(1≤i≤k)中元素的所有取值都取自集合V_i;

(2) 对于它的任意一个N×t(1≤t≤k)的子表,都包含对应t个参数的所有值组合至少一次.

那么这样的表称为覆盖强度为t的覆盖表,也称为t维(t-way)覆盖表.

定义 2. 设T为SUT的一个t维覆盖表:

(1) 若SUT所有参数的取值数目|V_i|均相等,则T可以表示为CA(N;t;|V_i|^k),称这样的覆盖表为水平覆盖表,其中,N为覆盖表规模,即测试用例数目,k为参数的个数;

(2) 若|V_i|不尽相等,则T可以表示为MCA(N;t;k;|V₁|,|V₂|,…,|V_k|),称这样的覆盖表为混合覆盖表.

表 1给出了一个Android应用可能的运行环境,包括Android版本、内存大小、系统分辨率、网络环境,对这个系统的完备测试至少需要配置3×3×3×3=81种运行环境.

若使用组合测试方法对该系统进行测试,令覆盖强度为2,则只需在9种配置下对该系统进行测试.在表 2中,任意两个参数的所有值组合都出现了至少一次,由定义1可知,表 2就是表 1所示系统对应的2-way覆盖表,可以表示为CA(9;2;3⁴).

事实上,构造一个一般的覆盖表不是一件非常困难的事情,而真正的困难在于如何在比较短的时间内生成尽量小的覆盖表.这也是组合测试覆盖表生成问题所研究的重要内容.如何构造最小的覆盖表已被证明是一个NP完全问题^[5].

对于求解覆盖表生成问题,目前已有的方法包括:(1) 数学方法,最为典型的是各种正交表构造方法,如构造拉丁方阵和正交拉丁方阵等,该种方法往往能够快速求得规模非常小的覆盖表,但其缺陷是限制条件多,不适合在各种实际情况下使用;(2) 贪心算法,如AETG,TCG,DDA等算法,这一类是最为常用的覆盖表生成方法,其优点是实现简单、算法时间开销较小,其缺点是算法比较容易陷入局部最优^[6];(3) 搜索算法,如模拟退火、禁忌搜索、蚁群算法、遗传算法、粒子群算法等,这类算法虽然执行时间较长,但是往往可以计算出非常好的结果,很多覆盖表的已知最优解都是由这类方法求得的.

1.2 蚁群算法

蚁群算法是一种启发式算法,由意大利学者Dorigo首先提出^[7].蚁群算法的灵感来源于对自然界中蚂蚁觅食行为的观察.蚂蚁在觅食过程中,总能够找到一条从蚁穴到食物之间的最短路径.虽然蚂蚁个体极其简单并且不具有智能,但是蚂蚁群体在觅食的过程中能够依靠一种叫做信息素的化学物质来实现群体智能.受此启发,蚁群算法模拟自然界蚂蚁觅食行为,以信息素为优化的线索,依靠蚂蚁的群体智能来解决各种组合优化问题.相关研究表明,蚁群算法在旅行商问题、车间作业调度问题等优化问题中均获得了很好的优化效果.

蚁群算法提出20余年以来,出现了各种不同的算法变种,其中最为广泛应用的是蚂蚁系统AS(ant system)算法、蚁群系统ACS(ant colony system)算法以及最大最小蚂蚁系统MMAS(min-max ant system)算法^[8].这些算法都是基于蚁群算法的基本原理的,只是在若干实现细节上有所不同.

2 利用蚁群算法生成覆盖表

目前已有利用蚁群算法一次生成一条测试用例(以下简称“一次一条测试用例”)的覆盖表生成算法,由于其生成方法使用了AETG^[9]算法的框架,我们将其称为AETG-ACO算法.Toshiaki等人对遗传算法和蚁群算法在覆盖表生成问题中的应用进行了研究,给出了一些覆盖表生成结果,并与其他算法,如AETG^[10]等进行了对比; Chen等人对蚁群算法在组合测试变强度覆盖表生成中以及测试集优化问题中的应用^{[11, 12]}进行了研究;Nie等人提出了基于搜索的组合测试,其中包括对蚁群算法生成覆盖表性能的研究^[13].

本节将在已有工作的基础上,对蚁群算法一次一条测试用例生成覆盖表的方式进行深入的探究.首先,介绍蚁群算法一次一条测试用例生成覆盖表的基本原理;其次,结合3种主要的蚁群算法变种设计一个用蚁群算法生成覆盖表的框架,通过这个框架可以轻易地实现算法在各个变种之间的转变,同时也可以发现各种算法变种之间的异同点;最后,通过对各个决策点策略的详细介绍来具体展示3种算法变种之间的区别.

2.1 利用蚁群算法生成覆盖表的原理

利用蚁群算法来求解组合优化问题,就需要根据基本原理建立良好的模型,设计有效的算法.

一次一条测试用例的覆盖表生成过程就是通过每次执行蚁群算法来求得覆盖表中的一行,也就是求得一条测试用例,反复执行这个过程,直到所有要求被覆盖的组合对均被覆盖为止.而每次求得的这一条测试用例,恰好可以视为是一条蚂蚁移动的路径,如图 1所示.图 1表示的是一次一条测试生成算法的搜索空间,图中每一个点F_i(1≤i≤k)对应着SUT中的参数P_i,从点F_i引出的各条边分别对应着参数P_i的各个取值.每当蚂蚁移动到一个点上时,就需要按照一定策略选择一条边移动到下一个点,当蚂蚁移动到点F_e时,就完成了一次搜索.F_e仅代表一只蚂蚁的构造结束,不对应SUT中的任何参数.此时,蚂蚁经过的路径对应一个候选解(即候选测试用例).蚂蚁在一个点时,根据概率公式选择路径.由于在早期信息素几乎没有差别,可以引入启发值来进行路径选择指导.最后路径选择公式由信息素和启发值共同决定.

如果一只蚂蚁每次选择最上面一条路径,那么就得到如下所示的一条测试用例:$(V_1.1,V_2.1,...,V_k.1).$

蚁群算法是一种群智算法,在每次迭代过程中,每只蚂蚁都会得到一个解,在整个迭代过程中将会产生很多候选解,需要一个函数来评估这些解的质量.我们称这样的函数为适应值函数F.适应值一方面在迭代过程中控制蚂蚁留下信息素的多少,另一方面用来选择一个质量最好的解加入到覆盖表中来完成一次求解过程.在覆盖表生成问题中,设S为一条测试用例,则F(S)为S覆盖的未被覆盖的组合对的数目.

在蚂蚁构造解的过程中或者构造完毕之后,蚂蚁根据解的质量对信息素进行更新,指导后来的蚂蚁进行路径选择^[14].

2.2 利用蚁群算法生成覆盖表的框架

根据第2.1节的描述,可以给出利用蚁群算法生成覆盖表的基本框架,如算法1所示.在这个框架下,对不同决策点进行相应的选择和设计,就可以得到不同的算法变种^[15].

算法 1. 利用蚁群算法生成覆盖表的框架AETG-ACO.

输入:

1) 算法参数配置;

2) SUT各个参数的取值个数(|V₁|,|V₂|,…,|V_k|)以及覆盖强度(t);

输出:满足输入要求的覆盖表(CA_set).

1: Begin

2: Initial_UncoverList(); //初始化未覆盖组合对

3: 设置CA_set为空

4: 初始化算法参数配置:Nc$ \leftarrow $最大迭代次数;m$ \leftarrow $蚁群规模(蚂蚁数量)等

5: While (uncover_list.size()>0){

6: 初始化信息素为一个常数;

7: Compute_Heuristic(); //计算启发值 (决策点A)

8: For (t=0; t<Nc; t++){

9: For (ant h from 1 to m)

10: For (node F_i from 1 to F_k){ //生成一个解Sh

11: Select_MoveingEdge(); //选择移动路径 (决策点B)

12: Local_Pheromones_Update(); //局部信息素更新策略 (决策点C)

13: }

14: 选择{Sh:1≤h≤m}中F(Sh)值最大的解加入候选测试用例集Candidate

15: Pheromones_Update(); //信息素更新策略 (决策点D)

16: Global_Pheromones_Update(); //应用全局信息素更新策略 (决策点E)

17: }

18: 选择argmax_S$ \in $_CandidateF(S)添加到覆盖表CA_set中

19: Update_UncoverList(); //更新未被覆盖组合对列表uncover_list

20: }

21: 输出覆盖表CA_set

22: END

在算法1所描述的利用蚁群算法生成覆盖表框架中,算法的输入需要给出参数配置、覆盖强度和需要生成的覆盖表的相关信息,而输出则给出满足输入要求的覆盖表.算法中存在如下两个迭代过程:

1) 外层迭代(第5行~第20行).当未被覆盖组合对数目大于0时,令m只蚂蚁运算Nc次,并从中寻找一个最优解加入到CA_set中,直到未被覆盖组合对数目为0时循环终止,算法输出覆盖表.同时,每执行一次外层迭代就会计算一次启发值,并置信息素为初始值,在本文中,各种算法的信息素初始值固定;

2) 内层迭代(第8行~第13行).在每次迭代中,如图 1所示,令每只蚂蚁从点F₁移动到F_e,完成一次蚂蚁寻优过程,其中包含了与不同变种相关的4个决策点.

显然,算法的内层迭代是应用蚁群算法求解的过程,而外层迭代主要关注未被覆盖组合对uncover_list的大小.在外层迭代开始之前,初始化了算法参数,并初始化了未被覆盖组合对,函数Initial_UncoverList()的作用就是统计SUT中t-way组合的个数,并标记这些组合的覆盖状态为“未覆盖”.

2.3 利用蚁群算法基本变种生成覆盖表

在算法1给出的利用蚁群算法生成覆盖表框架中,有A,B,C,D,E这5个决策点.在A决策点,可以采用不同的启发值生成策略.对A,B,C,D,E决策点进行选择和设计,可以得到不同的算法变种.本文主要对蚁群算法的变种进行研究,不考虑多种启发值生成策略,在算法中,使用单一的策略来进行计算.

决策点A:启发值计算Compute_Heuristic().

所谓启发值,就是具有某种直观意义并对算法起到指示作用的值,这种指示作用将避免算法盲目寻优,以加快算法收敛速度,好的启发值还有助于提高解的质量.一般来说,启发值使用贪心方式来构造.对于不同的组合优化问题,启发值的计算方式和所表示的意义有很大差别.对于覆盖表生成问题而言,一般使用的是由公式(1)所示的公式来计算启发值.

${\eta _{i,j}} = \frac{{{C_{i,\max }} - {C_{i,j}} + 1}}{{{C_{i,\max }} - {C_{i,\min }} + 1}}$

(1)

公式(1)给出的是利用蚁群算法生成覆盖表的一种常用的启发值计算公式,其中各个符号的含义是:$\eta $_i,j代表参数P_i的取值j所对应的启发值,C_i,j代表的是参数P_i的取值j在CA_set中出现的次数,C_i,max代表的是参数P_i的所有取值在CA_set出现次数的最大值,而C_i,min则是相应的最小值.由于可能存在C_i,max=C_i,min=C_i,j(1≤i≤k,1≤j≤|V_i|)的情况,因此,公式(1)为分子分母同时加1,避免出现分母为0的情形.

这样计算启发值具有非常直观的意义:当一个值在覆盖表中出现的次数越少,那么选择该值就有可能覆盖更多的未被覆盖对,从而得到比较好的解.此外,在生成一个解的迭代过程中,启发值始终不会发生改变.

图 2具体演示了利用公式(1)计算启发值的过程,其中,覆盖表CA(N;2;5⁴)已经生成了8条测试用例,如图 2中第1列所示.当生成第9条测试用例时,需要计算各个参数的每个取值的启发值,这里以第1个参数P₁为例.此时,P₁的5个取值在已经生成的8条测试用例中,各个取值出现的次数如图 2中第2列所示.因此,由公式(1)可以得到参数P₁的各个取值的启发值,如图 2中第3列所示.

不同算法变种的差别不包括启发值的计算,于是我们将启发值的计算单独考虑.不同变种的算法体现在两个方面:路径选择策略和信息素更新策略.下面分别考虑各种变种算法对决策点B,C,D,E的选取和设计细节.

蚂蚁系统(AS算法)是较早出现的蚁群优化算法,需要选择决策点B和D.

路径的选择由启发值和信息素共同决定,选择各个边的概率如公式(2)所示.

$P{r_{i,j}} = \frac{{\tau _{i,j}.\alpha \eta _{i,j}.\beta }}{{\sum\limits_{k = 1}.{|{V_i}|} {\tau _{i,j}.\alpha \eta _{i,j}.\beta } }}$

(2)

其中,各个符号的含义是:Pr_i,j表示第i个节点处选择第j条边的概率,$\eta $_i,j代表参数P_i的取值j所对应的启发值,$\tau $_i,j代表第i个节点上第j条边上信息素的含量.参数$\alpha $,$\beta $用来调节启发值和信息素对概率造成影响的大小:当$\alpha $=0时,概率只和启发值有关,算法将接近贪心算法;当$\beta $=0时,概率只与信息素有关,算法很容易陷入局部最优,性能可能很糟糕.

当所有的蚂蚁都构建好路径之后,各条边上的信息素将会更新.信息素的更新分为两部分.

$ \bullet $首先,所有边上的信息素都会减少一个常量因子的大小,只留下一部分.信息素蒸发如公式(3)所示.

${\tau _{i,j}} = \rho {\tau _{i,j}},\forall \left( {i,j} \right) \in \left( {0 < \rho \le 1} \right)$

(3)

其中,$\rho $被称为信息素残留系数,E为所有边的集合.参数$\rho $可以避免信息素无限积累,还能够让算法“忘记”一些不好的路径;

$ \bullet $蒸发步骤完成之后,蚂蚁都会在各自经过的边上释放信息素,如公式(4)所示.

${\tau _{i,j}} = {\tau _{i,j}} + \sum\limits_{k = 1}.m {\Delta \tau _{i,j}.k} ,\forall (i,j) \in E$

(4)

其中,$\Delta \tau _{i,j}.k$代表第k只蚂蚁在路径(i,j)上释放的信息素的大小,取值如公式(5)所示.

$\Delta \tau _{i,j}.k = \left\{ {\begin{array}{*{20}{l}} {Q \cdot |{V_i}| \cdot \frac{{F({S_k})}}{{F({S.*})}},{\rm{ }}(i,j) \in {S_k}}\\ {0,{\rm{ else}}} \end{array}} \right.$

(5)

其中,Q是一个常数,F是适应值函数,S_k为第k条候选解,S为本次迭代得到的最优解.

最大最小蚂蚁系统(MMAS)在AS的基础上进行了4项改进,需要选择决策点B和D.

首先,MMAS强调了最优路径的寻找,只有本次迭代过程中的最优蚂蚁或者从迭代开始到本次迭代的整个过程中的最优蚂蚁才释放信息素;但是这样会让某些边信息素增长过快,于是,MMAS采用了另外一项改进:将信息素取值大小限制在一个区间内;然后将信息素的初始值设定为较大,配合较小的蒸发速率,让算法能够在最初探索到更多的路径;最后,每当MMAS在一定数量的迭代中不再有更优解出现或者算法出现停滞状态(收敛),则重新初始化信息素.

MMAS路径选择公式和AS算法的路径选择公式一样,如公式(2)所示.

MMAS的信息素更新仍然分为两个部分:首先对所有边上的信息素以固定的速率进行蒸发,更新公式如公式(3)所示;蒸发过程结束后,采用公式(6)让当前最优的蚂蚁释放信息素.

${\tau _{i,j}} = [{\tau _{i,j}} + \Delta \tau _{i,j}.{best}]_{{\tau _{\min }}}.{{\tau _{\max }}},\forall (i,j) \in E$

(6)

其中,$\Delta \tau _{i,j}.{best}$为最优蚂蚁在路径(i,j)上释放的信息素的值,其表达式如公式(7)所示.

$\Delta \tau _{i,j}.{best} = \left\{ {\begin{array}{*{20}{l}} {Q \cdot F({S.*}),{\rm{ }}(i,j) \in {S.*}}\\ {0,{\rm{ else}}} \end{array}} \right.$

(7)

其中,S^*为至今最优解.

映射$[x]_{\min }.{\max }$用于将信息素的取值限制在区间范围内,取值如公式(8)所示.

$[x]_{\min }.{\max } = \left\{ {\begin{array}{*{20}{l}} {\max ,{\rm{ }}x > \max }\\ {\min ,{\rm{ }}x < \min }\\ {x,{\rm{ else}}} \end{array}} \right.$

(8)

蚁群系统(ACS)需要选择决策点B,C,E,它和AS的不同体现在3个方面:首先,它采用了另外一种积极的路径选择规则;然后,信息素的挥发和释放动作都只在最优路径上进行;最后,蚂蚁每次走过一条边就会减少边上的信息素,增加其他边被搜索的可能性.

ACS用公式(9)来进行路径选择:

${L_i} = \left\{ {\begin{array}{*{20}{l}} {\mathop {\arg \max }\limits_{1 \le j \le |{V_i}|} \{ \tau _{i,j}.\alpha \eta _{i,j}.\beta \} ,{\rm{ }}q \le {q_0}}\\ {J,{\rm{ else}}} \end{array}} \right.$

(9)

其中,L_i代表蚂蚁在第i个节点所选择的路径的取值;q₀是一个常数,表示概率的阈值,q是生成的随机数;J为根据公式(2)概率分布所生成的随机值.这种路径选择策略以q₀的概率选择最佳移动方式,以1-q₀的概率选择随机的方式.我们可以通过调节q₀的大小来对搜索区间的大小进行控制.

ACS信息素更新分为两种:全局更新和局部更新.

$ \bullet $全局更新策略只允许当前最优蚂蚁或者是此次迭代最优的蚂蚁进行信息素的更新,无论是蒸发还是更新都只在最优路径上进行.这种方法不用让所有路径上的信息素都蒸发,从而降低了算法的时间开销.全局更新用公式(10)来描述.

${\tau _{i,j}} = \rho {\tau _{i,j}} + (1 - \rho )\Delta \tau _{i,j}.{best},\forall (i,j) \in E$

(10)

注意,更新公式在$\Delta \tau _{i,j}.{best}$前面增加了系数1-$\rho $,这将信息素的值控制在原来信息素和释放的信息素之间.

$ \bullet $除了全局更新策略外,ACS还采用了局部更新策略.每次蚂蚁经过一条(i,j)边后,都会立刻用公式(11)更新该边上的信息素的值.

${\tau _{i,j}} = \left( {1 - \varphi } \right){\tau _{i,j}} + \varphi {\tau _{init}}$

(11)

其中,$\varphi $是常数,$\tau $_init是信息素的初始值.这样,每次蚂蚁经过一条边,该边上的信息素将会减少,从而增加了其他边被搜索到的机会.

在接下来的讨论中,我们利用蚁群算法以一次一条的方式生成覆盖表的各种变种算法统称为AETG-ACO,将AS,MMAS,ACS以一次一条的方式生成覆盖表的变种算法分别称为AETG-AS,AETG-MMAS,AETG-ACS.

3 利用蚁群算法生成覆盖表 3.1 实验设计

由于蚁群算法是一种多配置参数的演化搜索算法,且参数的不同取值对算法的性能会产生直接的影响,因此,参数配置调优是应用蚁群算法求解组合优化问题时必须考虑的因素.用蚁群算法生成覆盖表的方法继承了蚁群算法原有的参数,表 3展示了蚁群算法生成覆盖表各种变种算法的参数及其常见取值范围.

由表 3可知,无论何种覆盖表生成算法变种,对其参数进行调优都会面临如下问题:(1) 参数配置空间庞大,若浮点数以0.1为步长,m以10为步长且不大于100,Nc以100为步长且不大于1 000,则由表 3前5个参数构成的参数配置空间至少为50×50×10×10×10=250000个不同的参数配置;(2) 覆盖表的规模不同,生成覆盖表所需要的时间不同,一些覆盖表生成需要耗费大量时间;(3) 利用蚁群算法生成覆盖表是一种随机算法,为了评价其性能,对于每个覆盖表需要至少进行30次重复实验;(4) 需要选取多个各种类型的覆盖表进行实验.综合以上4点,在现有计算条件下对所有参数配置组合进行逐一验证的方法是行不通的.

本文介绍的组合测试不仅是一种软件测试方法,其本身就是一种实验设计方法.因此,本文使用二维实验(即2-way覆盖)进行参数间交互作用的检查,以确定蚁群算法生成覆盖表的各种变种的推荐参数配置^[16].具体方案如下:

第1步:结合蚁群算法已有研究,选取一个参数配置作为基准,在此基础上为每个参数按照一定步长单独修改并进行实验,通过这样的方法先研究单个参数对算法性能的影响;

第2步:在第1步研究的基础上,为蚁群算法生成覆盖表的各种变种算法的每个参数选取若干生成结果较好的参数配置区间;

第3步:对各种算法变种,在由第2步得到的取值区间内选取若干值,并设计二维参数配置表;

第4步:对若干目标实验对象在二维参数配置表下运行蚁群算法生成覆盖表的各种变种算法,并根据结果选择一组推荐参数配置.

通过本节的研究工作,将解决如下3个问题:(1) 单个参数对各蚁群算法生成覆盖表的各种变种算法有怎样的影响;(2) 对于各种变种算法而言,能否给出推荐参数配置,使得该配置下算法的结果较其他参数配置更好;

(3) 在各种算法的推荐配置下,比较各种变种算法的结果,探究何种算法变种更加适合求解覆盖表生成问题.

3.2 单参数配置优化

为了研究上述变种算法中单个参数对算法的影响,首先需要为各种算法变种寻找一组参数配置作为实验基准配置.单参数实验基准配置的选择基于以下两点:(1) 已有研究工作给出的蚁群算法参数配置建议;(2) 利用表 4中的实验对象进行测试,选择比较好的配置.基于以上两点,本文选取了表 5所示的实验默认配置.

表 4给出了单参数优化配置实验使用的5个不同的覆盖需求,这些覆盖需求的计算量有大有小,有水平覆盖表也有混合覆盖表,对这5个表进行运算的结果能够在一定程度上代表各种变种算法配置的一般性.

由于Nc和m都是越大其实验效果越好,在本文的研究中,我们没有对这两个参数进行调节,将它们取为固定值.由于MMAS要求信息素初始值较大,我们将AETG-ACO的$\tau $_init设置为1.0,其他两种算法都为0.4.

3.2.1 参数a与参数b对各种算法变种的影响

参数$\alpha $与参数$\beta $均为路径选择概率公式的两个重要参数,信息素指数$\alpha $的大小表示了信息素对路径选择的重要性,而启发值指数$\beta $表示启发值对路径选择的影响程度.一些关于蚁群算法的研究都给出了$\alpha $与$\beta $的参考取值,然而对于不同的优化问题和具体的算法变种,这两个参数的具体最优取值并不相同.本节分别研究参数$\alpha $和$\beta $对3种算法的影响:对每个参数,在基准配置下从0.1开始取值,并以0.3为步长分别对MCA1,CA2,CA3,MCA4,MCA5这5个覆盖表进行30次实验,并记录实验获得的最小值与均值.平均结果如图 3所示.

需要说明的是,在本节,所有平均值结果图中的数据均为“增量值”,即覆盖表在基本尺寸上“膨胀”的部分,如对MCA1,其二维覆盖表的基本尺寸(取值最多的两个参数取值个数的乘积)为10×9=90条测试用例,如果实际生成100条测试用例,则其“增量值”为100-90=10,而图中图例里括号内的数字给出了各个二维覆盖表的基本尺寸.

由以上参数$\alpha $对3种算法变种的影响的实验结果可以得出如下结论:(1) 对于AETG-AS算法而言,参数$\alpha $对算法结果的影响非常明显,且存在一个明显的最优取值区间,当$\alpha $取值较大时算法结果变差,因此在二维实验中可以令$\alpha $的取值区间为[0.1,1.0];(2) 对AETG-ACS算法而言,对规模较小的覆盖表MCA1、CA3,参数$\alpha $对实验结果的影响有限,但是对于CA2、MCA4、MCA5这类生成规模相对较大的表,可以看出,当$\alpha $的取值在[1.5,3.0]的区间内时算法平均结果较好,可以将这个区间作为下一步二维实验的参考配置区间;(3) 对于AETG-MMAS 算法而言,参数$\alpha $对算法结果的影响并不明显,这意味着参数$\alpha $的选取较为自由,我们为$\alpha $取值0.5、1.0、1.5、2.0 作为二维实验的参考取值.

与对参数$\alpha $所进行的实验类似,对参数$\beta $的实验也是在基准配置下,以0.3为步长,对3种算法变种下5个不同的覆盖表生成30次,并统计实验的最小结果与平均结果,平均结果如图 4所示.

由参数$\beta $对3种AETG-ACO算法变种的实验结果可以得出如下结论:(1) 对于AETG-AS算法而言,参数$\beta $对算法结果的影响较为明显,当$\beta $的取值较大时算法结果变差,因此在二维实验中可以令$\beta $的取值区间为[0.1,1.0];(2) 对于AETG-ACS算法而言,虽然平均结果下不同取值的差异并不明显,但在[0.8,2.0]区间内生成的尺寸相对较小,可以将这个区间作为下一步二维实验的参考配置区间;(3) 对于AETG-MMAS算法而言,从平均值曲线上来看,当$\beta $的取值在[0.5,2.0]之间时,算法生成的覆盖表的平均规模低于其他区间,因此在二维实验中可以用[0.5,2.0]作为参数$\beta $的参考取值区间.

3.2.2 参数r对各种算法变种的影响

参数$\rho $是利用蚁群算法生成覆盖表的信息素残留系数,表示上一代信息素有多少能够保留到下一代,信息素的残留机制使得蚂蚁群体能够依靠已有的搜索信息指导进一步的解空间搜索.另一方面,信息素的挥发也使得蚂蚁群体依赖于已有信息素的程度减弱,这使得蚁群在搜索过程中能够保持“探索”能力,即保证随着算法的进行,蚁群仍然能够有机会探索其他解.本节通过实验研究参数$\rho $的不同取值对3种利用蚁群算法生成覆盖表变种的影响,实验平均结果如图 5所示.

从实验结果可以得出如下结论:(1) 对于AETG-AS算法而言,当信息素残留系数取0.1附近时,算法生成的平均规模较大,而当$\rho $取值较大时,算法生成覆盖表的平均规模有上升趋势,因此,在二维实验中,可令AETG-AS算法的信息素残留系数取[0.2,0.6]之间;(2) 对于AETG-ACS算法而言,当$\rho $的取值在0.6左右时,生成的覆盖表尺寸较小,因此在二维实验中,可令$\rho $取0.5,0.6,0.7,0.8;(3) 对于AETG-MMAS算法而言,$\rho $对算法的影响较小,但当$\rho $的取值较大时(大于0.8),算法的平均结果较好,因此,在二维实验中,可令$\rho $取0.8,0.9,0.95,0.99这4个值.

3.2.3 参数j和q₀对ACS算法的影响

参数q₀是ACS路径选择方式概率,其值的大小表示了AETG-ACS算法选择两种路径转移方式的概率,而参数$\varphi $是AETG-ACS算法局部信息素更新系数,其值越小,一次局部信息素更新后,各个边上的信息素含量将更加接近信息素初始值$\tau $_init.

对参数q₀与参数$\varphi $均为从0.1开始,并以0.1为步长,直到取值为0.9的9种情况下,分别记录5个覆盖表下生成平均结果如图 6所示.

由实验结果可知,AETG-ACS算法的参数q₀的取值越小,覆盖表生成的结果越好,在二维实验中,可令q₀取0.01,0.05,0.1,0.2作为实验参数.而对于参数$\varphi $而言,虽然参数在平均水平上表现比较一致,但在由表 6给出的最小生成规模基础上,当$\varphi $取值较大时,生成的覆盖表的最小规模较小,因此在二维实验中,可令$\varphi $取0.8,0.9,0.95,0.99作为实验参数.表 6中,以“加粗、灰色背景”标记的是一行中的最小值.

3.3 二维参数配置优化

为了对AETG-ACO算法的各个变种进行参数配置二维实验,首先需要确定实验对象.为了保证实验能够充分反映覆盖表的各种情形,在二维实验中,我们在表 4的基础上扩展了5组覆盖表,构成表 7所示的二维实验覆盖表.

3.3.1 AETG-AS算法二维参数配置实验

根据单个参数对AETG-AS算法的影响的实验结果,得到各个参数比较理想的取值区间如下:$\alpha $取0.1~1.0之间,$\beta $取0.1~1.0之间,$\rho $取0.2~0.6之间.为了进行AETG-AS参数配置二维实验,将上述取值区间内各取若干值见表 8,其中,蚂蚁个数取定值20,最大迭代次数取定值200.

表 8中,第1列给出的数值是对应参数在二维实验中的代表符号,为表 8中的参数生成的参数配置二维覆盖表见表 9.

最后,我们利用所生成的参数配置进行实验,得到的结果见表 10.

AETG-AS的二维实验在20组不同的参数配置下,为10个不同的覆盖表分别进行了30次生成实验,表 10给出的是每个参数配置下每个覆盖表生成的最小结果、最小结果总和以及总平均值.

表 10中,以“加粗、灰色背景”标记的是一列中的最小值,从表中的结果可以得到如下结论:

1) 参数配置对AETG-AS的实验结果有一定的影响,一方面,部分参数配置之间的差异非常明显,如参数配置C1与C2代表了两个极端,两者的最小值总和相差50;另一方面,C2与C5两者仅在总均值上存在差异.此外,参数配置C4与C16的结果也相对较好;

2) 对某些覆盖表而言,参数配置对最小值的影响较弱,如对覆盖表CA8,AETG-AS仅在一个配置C18下多生成了一条测试用例,而考虑到算法的随机性,这样的影响几乎可以忽略不计.另一方面,在某些覆盖表,如MCA1上,各个参数配置对实验结果的影响较为明显;

3) AETG-AS参数配置二维实验结果比较好的配置为C2={$\alpha $=0.7,$\beta $=0.1,$\rho $=0.6,m=20,Nc=200}以及C5={$\alpha $=0.1,$\beta $=1.0,$\rho $=0.4,m=20,Nc=200},考虑到参数配置C2的总均值更小,因此本文推荐使用C2配置.从平均结果比较好的配置C2,C4,C5,C17来看,AETG-AS算法中$\rho $应该设置得较小,但也不宜太小.也就是说,AETG-AS算法中信息素需要保持中等的蒸发速率才会有比较好的性能.分析其原因,AS算法是最基本的一种蚁群算法,需要同时考虑算法的收敛性和搜索区间的大小,而蒸发速率越大,算法能够搜索到的解越多,收敛会越慢,综合考虑两个因素,蒸发速率设置在0.5左右比较好.

3.3.2 AETG-ACS算法参数配置二维实验

根据第3.2节对单个参数影响AETG-ACS算法的实验结果,得到AETG-ACS各个参数的参考配置区间如下:$\alpha $取1.5~3.0之间,$\beta $取0.8~2.0之间,$\rho $取0.5~0.8之间,q₀取0.1~0.2之间,$\varphi $取0.8~0.99之间.为了进行AETG-ACS参数配置二维实验,将上述取值区间内各取若干值见表 11,其中,蚂蚁个数取定值20,最大迭代次数取定值200.

表 11中,第1列给出的数值是对应参数在二维实验中的代表符号,为表 11中的参数生成的参数配置二维覆盖表,见表 12.对AETG-ACS的二维实验在30组不同的参数配置下,为10个不同的覆盖表分别进行了30次生成实验,表 13给出的是每个参数配置下每个覆盖表生成的最小结果、最小结果总和以及总平均值.

表 13中,以“加粗、灰色背景”标记的是每组的最小值,从表中的结果可以得到如下结论:

1) 参数配置对AETG-ACS的实验结果有明显的影响,每组生成最小值总和的最大差异为90;

2) C21配置无论在最小覆盖表规模总和、总均值还是各个覆盖表最小规模上都表现出优于其他配置,因此,AETG-ACS参数配置二维实验的推荐参数配置为C21={$\alpha $=1.5,$\beta $=0.8,$\rho $=0.7,q₀=0.01,$\varphi $=0.9,m=20,Nc=200}.此外,C2,C5,C18的平均规模也比较小,而它们的共性在于$\alpha $的取值大于$\beta $,$\rho $的取值稍微大一点,但是也不能太大,q₀取值要小.这表明,AETG-ACS在选择路径时,信息素占的比重要大于启发值,信息素蒸发的速度要较慢,选择最佳移动方式的概率要较小.蚁群系统是一种更加强调信息素的变种,虽然采用了更加积极的路径选择策略,但是大多数情况下还是需要用概率选择的策略.

3.3.3 AETG-MMAS算法参数配置二维实验

根据第3.2节对单个参数影响AETG-MMAS算法的实验结果,得到各个参数的参考参数配置区间如下:$\beta $取0.5~2.0之间,$\rho $取0.8~0.99之间.为了进行AETG-MMAS参数配置二维实验,将上述取值区间内各取若干值,见表 14,其中,蚂蚁个数取定值20,最大迭代次数取定值200.

表 14中,第1列给出的数值是对应参数在二维实验中的代表符号,为表 14中的参数生成的参数配置二维覆盖表见表 15.

对AETG-MMAS的二维实验在24组不同的参数配置下,分别为10个不同的覆盖表进行了30次生成实验,表 16给出的是每个参数配置下每个覆盖表生成的最小结果、最小结果总和以及总平均值.

Table 16 Result of AETG-MMAS pair-wise configuration experiments

表 16 AETG-MMAS二维实验结果

表 16中,以“加粗、灰色背景”标记的是每组的最小值,从表中的结果可以得到如下结论:

1) 参数配置对AETG-MMAS的实验结果有一定的影响,从最小值以及平均值来看,有3组参数配置取得了较好的实验结果:C6、C12、C23,其他结果与这3组结果有较为明显的差异;

2) 在C6、C12、C23这3组参数配置中,C6配置无论在最小覆盖表规模总和、总均值还是各个覆盖表最小规模上都优于其他配置,因此,AETG-MMAS参数配置二维实验的推荐参数配置为C6={$\alpha $=2.0,$\beta $=0.5,$\rho $=0.99,m=20,Nc=200}.从实验结果我们可以发现,C6、C12、C23中的$\alpha $和$\rho $的取值都比较大,这表明AETG-MMAS当信息素作用较大、信息素挥发较慢时性能会比较好.分析其原因,最大最小蚂蚁系统强调了信息素的收敛性,于是在选择边时,信息素所起的作用应该大于启发值,为了让算法搜索到更多的解,信息素蒸发速度要缓慢些.

3.4 3种算法在推荐配置下结果的比较

为了研究这3种算法中哪一种生成的覆盖表的规模比较小,我们将它们在推荐配置下的实验结果进行了对比,见表 17.

其中每一行代表该算法生成30次指定规格的覆盖表的最小值,总和表示生成最小表的尺寸之和,总均值表示30次生成10个覆盖表的尺寸总和的平均值.由此我们可以看出,AETG-MMAS生成覆盖表的效果最好.

4 基于解结构调整的蚁群算法生成覆盖表的方法 4.1 为何要调整解的结构

一次一条测试用例生成技术确实是一种简单、有效的覆盖表生成方法.但在生成的过程中,被选定的测试用例将不会发生变化,这样会让算法存在局限性.首先我们观察如表 18所示的例子.假设SUT有4个参数,每个参数都有3个取值,分别用0,1,2表示,覆盖强度是2.我们用一次一条的生成方法得到左边的9条测试用例.这个表并不满足覆盖需求,但是我们如果将表中黑色背景位置上的值用右边表中对应的值替换,就能得到一个满足要求的覆盖表.若继续使用一次一条的生成方式,则更多的测试用例需要被加入到表 18中.

Bryce和Colbourn等人提出一个问题:一次一条测试用例生成方式能否生成最小的覆盖表?他们对这个问题进行了实验.实验步骤如下:首先穷举出所有可能的测试用例,接着每次选择覆盖最多未覆盖对的测试用例,将其加入到测试用例集,直到得到一个覆盖表.如果有多条测试用例都覆盖最多的未被覆盖对,那么等概率地从中选择一条测试用例.对每个覆盖需求,做100次重复的实验^[17].实验结果显示,对于覆盖需求CA(N;4;2⁸),这种实验方法得到的覆盖表规模在31~37之间,而当前已知的最优覆盖表的尺寸为24.对于其他的覆盖需求,这种情况也非常常见.由此我们可以看出,一次一条测试用例生成方式是存在局限性的,下面我们对此进行分析.

覆盖表生成的目标是得到一个覆盖全部未被覆盖对的表.如果想要得到最优表,就需要在所有可能出现的测试用例集中选出行数最少的覆盖表.也就是说,我们的优化目标其实是找到满足公式(12)的表TS.

$TS = \mathop {{\rm{argmin}}}\limits_{ts \in CA} \{ Size(ts)\} $

(12)

其中,Size(T)表示表T的行数,CA是所有满足覆盖需求的表的集合.

然而,我们所用的一次一用例生成方法的目标是每次找到一条最好的测试用例加入到表中,直到所得到的表满足覆盖需求成为一个覆盖表.实际上,一次一用例的生成方法将最终目标进行了分解,将待寻找的目标TS分解成为寻找TS的行.每次优化目标变为满足公式(13)的测试用例TC.

$TC = \mathop {{\rm{argmax}}}\limits_{tc \in T - all} \{ fit(tc)\} $

(13)

其中,T-all表示测试用例所有可能取值的集合,fit(tc)表示测试用例tc覆盖的未被覆盖对的个数.我们发现,这样的变化使得优化目标从一个无限取值范围缩小到的一个有限取值范围.这的确大大降低了优化开销.但是Bryce和Colbourn等人的实验告诉我们,即使一次一用例的生成方式每次都找到了最好的测试用例,到最后得到的覆盖表也不一定是最小的覆盖表.使用上述贪心策略容易让结果陷入局部最优而找不到比较好的结果.于是,我们将优化目标还原成最初的目标,将优化目标从得到一条测试还原成得到一个尺寸足够小的覆盖表.

4.2 调整解的结构后的覆盖表生成算法

利用蚁群算法以一次性生成一个表的覆盖表生成方法(简称“整表演化”)主要有3个决策点,分别为表的演化策略,初始表的生成和表的演化位置的选择.

4.2.1 表的演化策略

表的演化方式有两种.其一是最初选择一个行数比较小的表,然后每次添加一条测试用例,让所得到的表通过整表演化的方法覆盖更多未被覆盖对,直到得到一个覆盖表为止.另一种方法则是反其道而行之,最初生成一个比较大的表(一般是覆盖表),然后每次减少一条测试用例,直到再也得不到更小的覆盖表为止.由于事先估计所要生成的覆盖表的大小有一定的困难(如果估计值过大,那么会得到比较大的覆盖表,这与我们的需求相矛盾;如果估计值过小,那么将要进行大量的计算,影响算法的性能),于是我们采取了后一种生成办法,即首先生成一个较大的表,然后慢慢减少测试用例的条数再进行演化,直到得不到更小的覆盖表为止.本质上来说,这种整表演化的方法是一种后优化的方法,用于优化一个覆盖表.

4.2.2 初始表的生成

对于整表生成算法而言,首先需要解决的问题是如何确定一个N×k的初始表,其中,k由SUT参数个数来确定,而N需要指定.生成初始表主要有两种方式.

1) 方式1:随机表法.此种方法需要手动指定N的值,N的确定可以依赖于已有的经验或各种相关研究资料中的数据,在N确定之后,可以根据SUT参数的形式为N×k的表中每个位置生成一个合法的随机值.

2) 方式2:覆盖表法.由于随机表法需要手动指定N,为实际使用带来不便,因此可以为整表演化算法集成一个覆盖表生成算法,用这种算法首先生成一个覆盖表作为初始表.出于对时间和尺寸的考虑,我们选择了贪心算法AETG.

4.2.3 表的演化位置

给定一个表,如何对这个表采用蚁群算法进行演化从而提高表的适应度呢?这就需要确定表的演化位置.位置的选择策略可以有多种,下面介绍两种选择方式.

1) 方式1:随机选择法.此种方法是最直接、最简单的一种方法.但是每次选择多少个位置进行演化合适呢?为了解决这一问题,可以指定选择位置的个数等于参数的个数,在表的每一列随机选择一个位置.但是经过尝试我们发现,这种方式在实际中的应用效果不是很好.

2) 方式2:灵活位置法.由于随机选择的方式具有一定的盲目性.我们引入了随机后优化算法中“灵活位置”这一概念^[18].

定义 3. 对于表中的一个位置,如果修改它的取值不会导致已经被覆盖的组合变为“未被覆盖”,那么我们称这个位置为“灵活位置”.

性质. 表中的某一行某一列的位置是灵活位置当且仅当该位置所在的测试用例中,包含该位置的所有t维组合都被表中的其他测试用例所覆盖.

下面我们给出一个例子来说明灵活位置的概念以及寻找方法.

在图 7中,左边是一个测试用例集.我们对T1这条测试的灵活位置用例进行研究.首先,我们列出所有被T1覆盖的组合以及它们在测试用例集中被覆盖的情况,见表 19.

接着,我们分别观察T1的4个位置的取值.包含第1个位置的组合有c1,c2,c3,由于c2没有被其他测试用例覆盖,故T1的第1个位置不是灵活位置,修改第1个位置上的值会让c2从已被覆盖变为未被覆盖.包含第2个位置的组合有c1,c4,c5,但是它们还分别被T2,T4,T5所覆盖,故T1的第2个位置为灵活位置,我们可以将该位置标记为“*”.c6未被除T1之外的其他测试用例所覆盖,但是c6包含T1的第3,4个位置,故T1的第3,4个位置都不是灵活位置.如果将这个步骤重复下去,我们可以得到一个表中所有的灵活位置.最终结果如图 7右边的测试用例集所示.

在求解灵活位置的过程中,我们只关心一条测试用例中包含某个位置的所有组合是否还被其他测试用例所覆盖,而不关心它们具体被哪些测试用例覆盖.如果一个组合只被当前的测试用例所覆盖,那么它在测试用例集中被覆盖的次数为1.这可以成为我们寻找灵活位置的一个线索.于是我们可以先扫描一次测试用例集,得到测试用例集所覆盖的所有组合被覆盖的次数,然后再遍历表中的所有位置,依次判断每个位置是否为灵活位置.如果包含某个位置的所有组合被覆盖的次数都大于1,那么这个位置为灵活位置.具体过程如算法2所示.

算法 2. 灵活位置FlexiblePosition.

输入:

1) 一个N×k的表Table(N×k);

2) 覆盖强度t;

输出:标出所有灵活位置的flexiblePointTable.

1: Begin

2: 计算Table中所有t维组合被Table覆盖的次数;

3: flexiblePointTable=Table;

4: For (testCase in flexiblePointTable)

5: For (value in testCase)

6: If (testCase所有包含value的t-way组合被覆盖的次数大于1)

7: 将flexiblePointTable中testCase取值为value的位置修改为“*”

8: return flexiblePointTable;

9: End

算法2中,testCase代表Table中的一条测试用例,而value代表testCase中一个位置的取值(形如P_i.j). flexiblePointTable最终为标记了所有灵活位置之后的表.

我们先求出所有灵活位置,然后利用蚁群算法在灵活位置上进行演化,这样会更有助于覆盖更多未被覆盖对.修改一个灵活位置可能会让原先本来是灵活位置的点变成非灵活位置,但是修改同行中任意多个灵活位置的值不会将剩下的灵活位置变成非灵活位置.根据这一点,我们将蚁群算法的演化目标设置为灵活位置最多的那一行上的所有灵活位置.在图 7所示的例子中,我们可以在T2或T5上进行演化.

4.2.4 基于蚁群算法的整表演化算法CA-ACO

我们仍然使用图 1所示的路径图,但是图中各个参数点的含义发生了变化.在一次一条测试用例的生成方式中,每一个点代表一个参数,而在整表生成算法中,F_i代表的则是一个表中的某个位置.由于路径的含义发生了变化,适应值函数也会随之变化.此时,某条路径的适应值变为采用某条路径能够增加的未被覆盖对的数量.此外,启发值的计算公式还是使用式(1)进行计算.

整体的过程如算法3所示.其中,FlexiblePosition(Table)即为算法2中求Table中灵活位置的函数. isCoveringArray(Table)用于判断Table是否为一个覆盖表.算法中有两个循环,外层while循环每次删除一条测试用例,里层For循环用于将删除测试用例之后的表演化为覆盖表.一旦达到最大迭代次数或者是不再存在灵活位置,那么就停止算法,返回覆盖表.

算法 3. 整表演化CA-ACO.

输入:

1) 蚁群算法参数配置;

2) SUT各个参数的取值个数(|V₁|,|V₂|,…,|V_n|)以及覆盖强度(t);

3) 最大尝试次数maxCount;

输出:满足要求的覆盖表(CA).

1: Begin

2: 生成覆盖表CA //可利用AETG,IPO等贪心算法

3: While (True){

4: Table=任意删除一条测试用例所得到的表;

5: For (i=0; i≤maxCount; i++){

6: flexiblePointTable=FlexiblePosition(Table); //利用算法2得到标出所有灵活位置的表

7: If (flexiblePointTable中不含“*”)

8: return CA;

9: 得到flexiblePointTable中含“*”最多的一行,设行标为row;

10: 在Table第row行的灵活位置上利用蚁群算法进行演化;

11: If (isCoveringArray(Table)){

12: CA=Table;

13: break; //若演化得到覆盖表,则进入到下一次while循环中

14: }

15: If (i==maxCount) return CA;

16: }

17: }

18: End

4.3 实验及讨论

为了验证本节给出的利用蚁群算法基于解结构调整的覆盖表生成算法的有效性,本节给出了相关实验数据.

本文设计的整表演化算法是一种后优化算法.算法引入了随机后优化算法中“灵活位置”的概念,下面我们给出基于蚁群算法的整表演化算法和先用AETG-MMAS算法然后再利用随机后优化算法的性能比较,见表 20.其中,AETG-MMASp表示对AETG-MMAS算法生成覆盖表使用随机后优化算法的方法.CA-AS算法表示基于AS算法的整表生成算法.实验选取了10个覆盖表作为实验对象.从表中我们可以看出,除了第10个表CA-AS表现略差于AETG-MMASp外,CA-AS算法所得结果的尺寸以及稳定性都要好于AETG-MMASp.算法采用的是第4节给出的AS算法推荐参数配置,实验中覆盖表CA9与CA10的最大迭代次数为10 000,而其余表的最大迭代次数为1 000.

表 21给出了CA-AS和其他算法生成覆盖表最小尺寸的对比.其中,MMAS表示AETG-MMAS算法,IPOs是IPO算法的一种改进,SA表示模拟退火算法^[19].实验对象为表 20中的10个表.根据结果可以发现,CA-AS比AETG-MMAS性能有很大的提升,只在MCA4和MCA5两种输入时生成的尺寸比IPOs要大^[20],但是当前最优结果都是由SA生成的,因此CA-AS算法仍然具有一定的改进空间.

蚁群算法本身非常耗时.在用蚁群算法进行整表演化实验时,这个问题尤为严重.我们对CA(N;2;4^k)(k= 10,20,30,40,50)这5个输入进行了实验.实验结果如图 8所示.从图 8中我们可以看到,随着k的增长,CA-AS算法的时间(s)会显著增加.当k=50时,算法一次运行的时间接近2小时.针对时间开销问题,本文余下部分对算法进行了并行化探索.

5 利用蚁群算法生成覆盖表的并行化探索 5.1 并行化探索

由上述讨论我们可以看到,用蚁群算法生成覆盖表是一个非常耗时的工作.即便仅使用计算速度较快的AETG-ACO,当覆盖表规模达到一定程度时,其计算时间可能仍然是难以承受的.所以,我们尝试从两方面来考虑将利用蚁群算法生成覆盖表的方法并行化.其一是将覆盖表本身的一些步骤并行化,其二是将蚁群算法中的某些步骤并行化.

在整表生成的过程中,需要计算灵活位置.当表的行数较多时,计算灵活位置会花费较大的计算代价.因此,我们提出并行化地寻找灵活位置的方法:将算法2的第4行~第7行以及计算所有t维组合被覆盖次数的过程并行化处理.

蚁群算法本身是一种群智算法,演化学习过程主要是依靠每一代蚂蚁对环境的改变.在AS算法和MMAS算法中,每一代蚂蚁中的个体的行为都具有独立性,因此可以考虑将这两个变种的蚁群算法的蚂蚁迭代过程改为并行过程,从而节约计算时间.但是需要注意的是,每一代蚂蚁的迭代过程都依赖之前所有代蚂蚁的行为,约束性太强,所以不同代的蚂蚁不能并行化.另外,由于在ACS算法中,每次一只蚂蚁经过一条路径都会更新信息素,所以不方便将蚂蚁的演化过程并行化.对于AS和MMAS,算法1中第9行~第13行也可以并行处理.

5.2 实验及讨论

上面我们分析了利用蚁群算法生成覆盖表的过程中的一些可并行的成分,下面我们以并行化的蚂蚁为例设计实验.选取如表 22所示的6个二维覆盖表来进行实验.对于每一个表,分别设置并行的线程数为1~8,每一种线程设置都重复进行10次实验.

我们首先在hadoop集群上进行算法并行化的实验,但是hadoop本身不适合完成计算密集型的任务^[21].在hadoop集群上得到的实验结果还不如单机的实验结果,于是我们放弃了实验hadoop进行并行化实验的想法.由于现在的计算机往往都是多核的,CPU使用率很低,于是我们采取另外一种并行化策略,即利用Java的多线程机制^[22].我们使用了Java版本的OpenMP,将蚂蚁寻找解的过程并行化.实验环境为Java1.7,Windows8.1 64位系统,Intel(R) Core(TM)i7-3840QM CPU(4核8处理器2.8GHz)内存16GB.算法的参数我们固定为如表 23所示.

最后我们得到的实验结果见表 24,将3个水平覆盖表和3个混合覆盖表从左到右分别记为CA1~CA3,MCA1~MCA3.表中记录的数据是不同的表在不同线程数下分别运行10次所需要的平均时间.

为了表现得更加直观,我们将实验结果以折线图的形式表现出来,如图 9所示.

根据结果我们可以看出,并行化后算法的运行速度更快,但是运行时间不是随着线程数的增加而一直变短.当线程个数接近处理器的个数时,算法运行的时间反而变长.在实际的运行过程中,我们要根据自己所拥有的计算资源合理设置并行的尺度.

6 总 结

本文主要对利用蚁群算法生成覆盖表的性能进行深入的探索与挖掘.蚁群算法作为一种常见的演化搜索算法,成功地解决了一系列组合优化问题.而在求解覆盖表生成问题的过程中,虽然已有的研究工作说明了蚁群算法的可用性,但却缺乏对其实际性能的深入探讨.本文在已有工作的基础上,结合对蚁群算法、覆盖表生成算法的相关研究成果,研究了利用蚁群算法生成覆盖表的算法变种、算法参数、解结构调整以及并行化,充分挖掘了蚁群算法生成覆盖表的潜力.主要包括以下几个方面的工作:

1) 对已有的蚁群算法一次一条测试用例生成覆盖表的算法进行了深入挖掘,研究了算法的变种以及参数的配置.研究算法变种时,我们提出利用蚁群算法生成覆盖表的框架,选择了3种算法变种AS,ACS,MMAS来进行覆盖表的生成,并得到相应的AETG-AS,AETG-ACS,AETG-MMAS算法;

2) 进行了单参数配置的研究,然后研究了二维参数覆盖表,最后为每种算法变种提供了一种推荐配置.在推荐配置下,将3种覆盖表生成算法的结果进行比较,发现效果最好的是AETG-MMAS算法;

3) 对蚁群算法生成覆盖表的演化目标进行了调整,从已有的演化一条测试用例调整到演化一个整表,提出了在灵活位置上进行演化的CA-AS算法.该算法能够克服一次一条测试用例生成方法的局限性,得到更好的结果.实验结果表明,CA-AS的实验效果要比AETG-MMAS的实验效果好得多,非常接近已知最优解;

4) 将蚁群算法生成覆盖表的算法中的一些过程(包括灵活位置求解,每一代蚂蚁的演化)进行并行化处理,解决了在表的规模较大时非常耗时的问题.在hadoop平台上的实验失败后,使用Java版本的OpenMP,将蚂蚁寻找解的过程并行化,最后有效地缩短了算法的运行时间.

虽然经过改进的结果未能超越最优解,但是这项工作仍然是有意义的.从蚁群算法的角度来看,该算法作为一种元启发式算法,能够经过小的改动而应用在不同的优化问题中.但是,不同的问题具有不同的特点,所以对特定的问题,对蚁群算法的设计在其性能方面会产生很大的影响.而本文研究了蚁群算法在覆盖表生成问题上的应用,针对这个问题对蚁群算法进行设计,使得在这个问题上的潜力充分发挥出来.从覆盖表生成的角度来看,生成覆盖表有很多种方法,本文对蚁群算法进行了评估,展示了利用蚁群算法来生成覆盖表的优劣.

尽管以上研究探索很好地挖掘了蚁群算法生成覆盖表的潜力,但仍然存在很多不足.例如对算法变种选择而言,蚁群算法的变种有很多,我们却只选择了其中的3种算法进行研究.在参数调优的过程中,一方面,参数的离散程度不够,覆盖强度也不够;另一方面,我们选择的实验对象比较少,实验次数也不充足.整表演化时,我们采取逐渐减小覆盖表尺寸的方法,没有对逐渐增加测试用例条数的方法做过多的讨论.此外,表尺寸减小的方式、演化位置的选择也存在多种策略,我们没有进行过多的讨论.在缩短算法时间方面,我们只是让能够并行执行的步骤并行化执行,没有更加深入地设计更有效的分布式算法,也没有成功地利用分布式平台.针对上述不足,将来会展开,作进一步的研究,让利用蚁群算法生成覆盖表的方法能够发挥出更大的潜力.