第章a测试用例的自动生成.ppt

局部搜索法的基本思想是：从随机选定的解开始，不断对其进行微小的改变(局部改进)，直到满意为止. 所谓的满意是指要么得到一个解，要么改进的次数大于设定的最大值. 对于后一种情况，我们就得不到该约束问题到底是有解还是无解的结论.著名的局部搜索算法包括：顾钧的算法、贪心搜索过程GSAT、禁忌搜索(Tabu search) 和拟人拟物法等. 其它的还包括爬山法、模拟退火等. 数值约束问题的求解方法 数值约束可化为如下的基本形式： fi(x) = 0; i = 1 : : : p hj(x) = 0; j = 1 : : : q 如果数值约束中的等式和不等式约束都是线性的，则称之为线性数值约束问题，否则称之为非线性数值约束问题. 线性数值约束问题的求解可用单纯形法(Simplex method).该方法已经十分成熟. 非线性数值约束问题的求解 1) 数值法：基于高斯- 牛顿法求解非线性方程； 2) 符号计算法：将待求解的非线性代数方程组化为一个或多个等价的三角型方程组. 3) 柱形代数分解：设约束h 中出现的变元个数为r，将r 维欧氏空间剖分成“块”，使得对“块” 中个别点进行检验就可以判定h 成立与否. 4) 区间分析：为了解决计算机只能表示有限位数字，以及其它与此相关的实际问题而产生的. 它的基本思想是对实数的扩展，用一个区间而不是单独的一个数来表示数.例如数a 用区间的表示方法为a = [aI ; aS]，aI =a=aS.它的意义在于，区间[aI ; aS] 中一定包含a 的精确值，而且经过合理的数学运算，这个区间可以足够小. 混合约束问题的求解方法 1) 区间分析法； 2) 逻辑与数值相结合的方法：分为两个步骤替换和还原； 替换：替换是指用一个新的布尔变量来替换混合约束问题中的每个数值约束；从而得到一个布尔约束问题，并对该布尔约束问题进行求解； 还原：将替换阶段结束时获得的布尔值，将相应的布尔变量还原为该数值约束本身并进行约束求解； 替换和还原需要不断进行回溯。 启发式搜索算法。 启发式搜索实际上起源于人工智能的研究。在求解一些很难的问题过程中，往往会把问题转换成为一个在问题空间中进行搜索的问题。 启发式搜索是根据以往搜索的结果所得到的信息，产生下一步搜索动作的一大类算法。 启发式搜索算法是处理NP-hard问题的有效途径。现有的常用的算法有： 爬山法 退火算法 遗传算法 价值函数 x 当前解 邻域 试探解 搜索终止 与爬山法类似，都有价值函数，都从当前解试探邻域，如果有更好的可能，用邻域值代替当前值。 引入概率 t是控制参数，即“温度”。当试探解比当前解好时，p=1;当试探解比当前解差时，1p0。 开始t值较高，活动范围较大，t随时间逐渐下降。 从生物学中的进化借鉴而来的。 基本概念 个体/个体空间 种群/种群空间 适应值函数 选择/杂交/变异/删除 K=0，随机产生初始种群X(0)=(x1(0),…,xn(0)) 独立地从当前种群中选取n对母体； 独立的对n对母体进行杂交得到n个中间个体； 独立的对n个中间个体进行变异得到下一代种群； 检验停止标准，若满足则停止，否则k=k+1，并返回2； K=0，随机产生初始种群X(0)=(x1(0),…,xn(0)) 独立地从当前种群中选取n-1对母体； 独立的对n-1对母体进行杂交得到n-1个中间个体； 独立的对n-1个中间个体进行变异得到下一代种群的前n-1个个体； 即从k代种群中选出最优的个体xi(k)（目标函数最大），令xn(k+1)=xi(k)。 检验停止标准，若满足则停止，否则k=k+1，并返回2； K=0，随机产生初始种群X(0)=(x1(0),…,xn(0)) 从当前种群中选取1个母体； 对所选的母体进行杂交得到1个新个体； 从当前种群中删除一个个体，用新个体替换它，从而得到下一代种群； 检验停止标准，若满足则停止，否则k=k+1，并返回2； 1、编码：把问题转换成为在个体空间进行搜索的问题； 2、设定目标函数（选择函数）、杂交算子、变异算子、删除算子； 3、选定具体的遗传算法； 4、选定初始种群，进行计算； 在进行程序分析的过程中，使用符号而不是实际的值代入到程序中进行运算的过程。从而能够分析出特定路径的约束条件和计算公式。 符号执行技术的用途 测试数据自动生成； 逆向工程； 路径可达性分析 生成被测程序的流程图，该流程图代表目标程序可能的执行路径。 遍历流程图中的某条特定路径，遍历过程中，每一个输入变量用一个符号而不是一个具体的值代替，进行程序的计算。 每一个语句经过计算后，输入变量的值有可能发生改变，成为某个计算表达式，在下一个语句中用这个计算表达式代替该变量进行计算。重复这个过程，直到程序结束。 当符号执行遍历了某条路径后，产生的输出变量将是一个由输入变量