3.2.3 基于爬山法的求解
爬山法应用于测试用例自动生成由来已久,正如第2章所述,它虽然快速高效,但是具有局部收敛的特性,很容易陷入局部极值或者由于局部无解而导致整体求解失败。本节对于爬山法的应用是对于其优势的一种发挥,并通过分支限界的总体协调极大范围地避免了由于局部无解导致的求解失败。
将分支限界作为全局搜索算法动态建立搜索树,通过3.2.2节中介绍的高效的变量动态排序决策机制后迅速进入局部求解,而爬山法具有快速收敛的特点,在局部有解时可以快速找到局部解,在局部无解时可以快速返回全局算法分支限界进行回溯。具体说来,爬山法用于从其取值区间内为当前变量选取一个确定值进行赋值,将山顶定义为区间运算判断不产生矛盾的赋值,在每次赋值后都通过计算目标函数值来计算是否到达山顶。爬山法与分支限界的关系如图3-9所示。
图3-9 爬山法与分支限界的关系示意图
1.启发式选取初始值
变量初始值的选取对搜索算法能否成功至关重要。一方面,如果搜索本身是无回溯的,则每个变量的初始值就是最终解的一部分;另一方面,如果初始值选取合适,就会引导搜索以无回溯的方式进行。在目前常用的搜索算法中,初始值主要通过以下两种方式选取。
①动态法多随机选取初始值,这样可以多次执行算法返回不同的测试用例,保证了测试用例的多样性,但是这种随机选取的方法没有任何启发式规则的指引,经常会导致大量的迭代。
②很多二分搜索法选取中值作为初始值,这样会导致在无回溯时多次执行算法返回同一组用例,无法保证测试用例的多样性。
因此,对于初始值的需求,有以下几个条件。
a.要保证测试用例的多样性,即不能多次执行算法返回一组相同的用例。
b.根据统计,C程序中出现的线性约束占了绝大多数(大概90%)。
c.二分法对顺序存储的数据结构(区间抽象域在CTS内是顺序存储的)是一种很有效的查找方法。
为了兼顾测试用例的多样性和算法的效率,在使用启发式规则判定初始值选取范围后随机选取初始值。通过符号分析和区间运算技术,可以提取和每个变量相关的表达式,从而对变量在这些表达式中的性质进行分析。为了满足每个表达式,将变量分为3类:正变量(其取值越大越容易满足表达式)、负变量(其取值越小越容易满足表达式)和中性变量(除正变量和负变量之外的变量)。而对于整条路径上的约束,变量也分为3类:正变量(其取值越大越容易满足路径上的所有表达式)、负变量(其取值越小越容易满足路径上的所有表达式)和中性变量(除正变量和负变量之外的变量)。路径上的变量性质是对每个表达式上变量性质进行统计计算的结果。在确定了路径上的变量性质之后,可以有针对性地对每个变量的初始区间进行削减,在削减后的区间内为其选取初始值。
基于以上分析,我们将这两种选取初始赋值的方式结合起来,即在启发式确定初始赋值的范围后,对初始区间进行二分削减,在削减后的区间内随机选取初始值。具体包括以下步骤。
①为了满足条件a,值的选取不能是唯一的,所以选择在一个区间D′内为变量随机选取值,但是这个区间D′应该是发生矛盾前取值区间D的一个子集,即D→D′(D′⊂D)。
②根据条件b和条件c,可以考虑使用二分法对区间D在中点处进行压缩,则有两种可能的选择:
需要确定进行哪种选择,并确定初始区间D′是D中以中值为界偏大的一半还是偏小的一半。
③如何确定是偏大还是偏小的一半?需要知道当前变量x i与每个分支上的约束之间有怎样的联系。我们提出将分支上的约束表示成当前变量的函数,并依据复合函数的单调性来进行区间压缩的方法,如下所示。
定义3-11 令B为布尔值的集合{true,false},Di是变量x i的取值区间,分支函数Br(nqa,nqa+1)(x i):Di→B(nqa是一个分支节点)可以定义如下:
(https://www.daowen.com)
式(3-3)是对式(3-2)的扩展,其中∑j≠ia jx j是除了x i之外其他变量的线性组合,我们认为它对于x i是一个常数,它可以对变量初始值的选取提供一个重要依据,即分支函数和当前变量之间的单调性关系。函数的单调性是对于某个区间而言的,它是一个局部概念,描述了函数的输出与输入的变化之间的关系。具体来说,它给出了这样的信息:输出是与输入的变化同方向还是反方向。在将分支函数分解为基本函数后,如果每个基本函数的单调性可知,那么根据以下命题,作为合成函数的分支函数的单调性也可以得到,从而我们可以知道如果令分支函数取true(单调增加),那么输入变量应该怎样取。
命题3-3 令f 1:X 1→Y 1,f 2:X 2→Y 2,…,f n:X n→Y n是一组分段单调函数,且Y i⊆X i+1,若Fn:X 1→Y n是一个合成函数f n◦f n-1◦…◦f 1,则Fn也是一个分段单调函数。
证明 使用数学归纳法。
当F 1=f 1时,根据已知条件可知F 1是分段单调函数。
假设F i=f i◦F i-1是分段单调函数。当F i+1=f i+1◦F i时,令I为F i定义域上的一个子集,x和x′是I内任意两个元素,且x≤Xx′,则要么Fi(x)≤Yi F i(x′)(当Fi为增函数时),要么Fi(x)≥Yi F i(x′)(当Fi为减函数时)。为了简便,我们统一记作Fi(x)R Fi(x′),其中R∈{≤,≥}。已知f i+1也是分段单调的,则对于Fi+1=f i+1◦Fi=f i+1(Fi),因为Fi(x)R F i(x′),且f i+1单调,可以得到f i+1(F(x))R f i+1(F(x′)),其中R∈{≤,≥}。
定义3-12 路径变量性质Path Tendency∈{positive,negative}是变量在一条路径上的性质,它有利于路径上所有条件的满足,为变量初始区间的选取提供启发信息。性质为positive意味着应选取一个较大的初始值,性质为negative意味着应该选取一个较小的初始值。
计算路径变量性质需要计算变量x i在每个分支(nqa,nqa+1)(a∈[1,k])的权值w i(n qa,n qa+1)以及它的路径权值pw i,并通过式(3-4)和式(3-5)分别计算。
2.爬山过程
爬山法的应用主要是为了解决等式约束的问题,我们也将其扩展到不等式,即爬山法可以解决目前出现的常见关系表达式。爬山法调用区间运算判断当前变量x i的值V ij是否会产生矛盾。换言之,能够令区间运算不矛盾的x i的一个值V ij就是我们要寻找的山顶。为了更好地说明爬山法的工作原理,我们对路径上的分支条件进行了分解,如图3-10所示。
若路径上有k个分支节点,那么所对应的k个分支函数都为true才能保证路径可达;否则少于k个分支条件为true,那么分支函数取值为false的分支需要被定位出来并对矛盾的情况进行分析,进而对当前变量x i的区间D ij进行削减。对分支条件Br(n qa,n qa+1)(a∈[1,k])是否能够为true的判断取决于两个区间的取值,即进入第a个分支的变量区间D a(满足前面的a-1个分支条件)和满足第a个分支条件的变量区间D ~a,后者是将前者代入Br(nqa,n qa+1)计算的结果。如果D a∩D ~a≠∅,则可以确定Da∩D ~a既满足前面的a-1个分支条件,也满足第a个分支条件。区间运算可以继续向下判断剩下的分支条件。
图3-10 分解的区间运算过程
图3-10(a)为一次成功的赋值,k个分支条件都得到了满足,在它完成之后就可以进行剩余变量的排序了;图3-10(b)是一次失败的赋值,第h(1≤h≤k)个分支条件没有得到满足,后续的算法就需要对矛盾的条件进行判断。我们将添加爬山法的BFS-BB称为BB-HC(Branch and Bound-Hill Climbing),其具体过程如算法3-6所示。
目标函数的确定对于一个搜索算法的效率和搜索能否成功至关重要。在某种意义上,若一个解比其他候选解更优,则它应该具有更好的返回值;反之,若一个解比其他候选解更差,则它的返回值也较差。为此依据区间运算的特点和约束求解的需要,给出如下目标函数的定义。
F(V ij)=0说明区间运算没有矛盾,是对应于x i的山顶;否则就需要根据F(V ij)的返回值对D ij进行削减,从削减后的D ij中选取新的V ij。在这个爬山过程中,F(V ij)的绝对值越来越接近0,它就是对应的山顶。也就是说,我们的搜索是一个寻找最小值的过程。其返回值的绝对值越接近0的候选解就越优,则优先选择这样的候选解作为下一步的赋值。当区间运算失败时,F(V ij)的返回值提供了需要削减Dij的上界和下界,这分别由F(V ij)的正负号和绝对值决定。因为对于Dij的削减是从两个方向进行的,所以算法的效率得到了很大的提高。通过这种方式,由分支条件构成的路径约束以越来越精确的方式进行传播。
通过以上分析可以看到,我们采用了两种手段来控制爬山法的收敛,分别是阈值m和目标函数,而且爬山法是双向收敛的。在3.3节的实验中可以看出,绝大部分的被测程序使用爬山法时其区间运算的次数是不会达到阈值m的,也就是说目标函数本身已经提供了足够强大的收敛能力。
