4.4.3　强化学习模型的构建及算法描述

测试用例生成的强化学习模型TGRLM的构建过程即对上述定义4-11中四元组的状态集S、动作集A和奖赏函数R的抽象建模。对于具体要解决的测试用例生成问题,即求出满足约束条件的一组解。而强化学习模型构建的过程即对测试用例生成过程中的约束求解过程进行抽象建模。

1.构建状态集

在分支限界求解框架中,首先通过路径分析的结果及参数类型对变量区间初始化,如图4-37所示。程序test中的约束集合为{x 1-x 2＞0,x 1+x 2==4},采用启发式策略对变量的取值进行初始化。具体来说,变量x 1和x 2的取值被确定在[-9,9]之间。定义两种状态集:一种是确定性的取值,即每次变量集合的取值对应一个状态。状态的数量Sum=(Value)n,即初始化区间内可取值数量的变量数目次幂,其中n为变量的个数,Value为变量可取值的数量。对于约束集合中只包含两个变量的情况,状态的总数量Sum=(19)2=361个。另一种是非确定的取值区间,即每个变量的取值区间组成一个状态。若设置区间的长度为2,状态的数量Sum=(Value*)n,即初始化区间的区间可取值数量的变量数目次幂,其中n为变量的个数,Value*为可表示的区间数量。对于约束集合中只包含两个变量的情况,状态的总数量Sum=(9)2=81个。如表4-21所示,可以看到两种方式的区别,有效地减少状态集可以加速学习的过程。

表4-21　两种状态集的表述

2.构建动作集

构建动作集的主要目的是从一个状态转移到另外一个状态,例如,确定性的状态集从S 1转移到S 2,即变量x 1增加1,变量x 2保持不变。要表示这个行为,定义两种方式:第一种是模拟多维平面的坐标转移,即从多维平面中的一个坐标点到另一个坐标点,为了简单说明,将其定义为二维平面,如图4-38所示。在图4-38中每个点表示一个状态,状态的切换在平面上表现为上、下、左、右,即动作集被定义为{Up,Down,Left,Right},例如,S 1→S 2的动作为Right,S 1→S 20的动作为Up。对于取值区间式的状态的转移表示为两个区域的转移,如图4-38所示。第二种是基于变量进行状态的转换,具体来说在分支限界求解框架中,通过分析区间的大小、变量相关性、变量出现顺序等方法可以获得排序的变量集合{x 1,x 2,…,x n}(n=约束中变量的个数)。将动作集合定义为每个变量的选取和变量的增减,若约束集合中存在3个变量x 1、x 2和x 3,经过排序的变量集合为{x 1,x 2,x 3},可以将动作集定义为{Left Add,Left Reduce,Current Add,CurrentReduce,Right Add,RightReduce}。若当前变量为x 2,Left Add表示左移到变量x 1并增加x 1的取值;Left Reduce表示左移到变量x 1并减少x 1的取值;Current Add表示增加当前变量x 2的取值;CurrentReduce表示表示减少当前变量x 2的取值;Right Add表示右移到变量x 3并增加x 3的取值;RightReduce表示右移到变量x 3并减少x 3的取值,如表4-22所示。

图4-38　状态转移图

表4-22　基于动作的状态转移表

3.构建奖惩函数

奖惩函数通常是根据对所解决问题的影响程度来定义的,其主要目的是在解决问题中提供指导。根据问题的进一步细化,可以对奖赏函数进一步完善。具体对测试用例生成的过程来说,定义奖惩函数的主要目的是在求解约束的过程中提供求解指导。在这一部分中,定义两种方式:第一种是根据约束满足的个数进行定义,通常来说满足约束的个数越多对求解约束的帮助越大,即可以简单定义的奖惩函数r 1如式(4-20)所示。

其中,n表示满足约束的个数,F 1表示满足约束条件的影响因子,F 2代表不满足约束条件的影响因子,N代表约束的总个数。

第二种是在第一种方式的基础上,通过定义距离L,完善奖惩函数。对于约束表达式Ci(i=1,2,…,N),即Ci表示为a 1 x 1+a 2 x 2+…+a Nx N=*Di(i=1,2,…,N),将约束表达式中关系运算符(约束中可以表现为“=”“＞”“＜”“!=”等)右端的表达式移到左端,转换成L i=a 1 x 1+a 2 x 2+…+a Nx N-D i(i=1,2,…,N),并将当前状态的值带入上式可以得到当前约束Ci的距离L i。例如,对于一组约束:x 1-x 2-x 3＜9,可以表示为L=x 1-x 2-x 3-9。假设当前状态S为{x 1=-9,x 2=-9,x 3=-9},将变量取值代入L的表达式中,可以得到当前约束距离为0,对于整个约束集合的总距离被定义为式(4-21),故定义复杂奖赏函数r 2如式(4-22)所示。