5.1.3　优化问题和目标函数

在动态自动测试方法中,面向路径的自动测试问题被看作一个组合优化问题(Combinatorial Optimization Problem,COP)。组合优化问题的求解过程分为3步:首先确定问题的初始输入、取值域,以及问题所要达到的目标;然后对于问题进行数学抽象,利用化简不相关的过程和近似等手段,将原始问题建模成已有的优化模型以及目标函数;最后利用各种优化算法,求解优化模型的解,使目标函数最优化。

COP被证明是NP问题,因此没有多项式复杂度的算法可以求解。目前对于COP的解法可分为两类:确定性算法和近似算法[4]。确定性算法包括动态规划以及各类分支限界算法,可以看作树搜索算法,先将原始问题划分为小规模的子问题,然后对子问题进行求解,找到局部最优解和全局最优解。确定性算法具有完备性和确定性,能够保证得到最优解,但是算法的复杂度为非多项式,当问题规模很大时的求解时间会大到无法接受,因此确定性算法适合应用于优化问题的规模和搜索空间较小的情况。(https://www.daowen.com)

近似算法利用抽象近似的思想去解决大规模的优化问题,并不保证产生最优解,但是能够在有限的时间内产生“足够好”的解。近年来,由于问题规模不断扩大,近似算法得到了广泛的关注和研究。启发式搜索算法是一种近似算法,将抽象层次较高的思想作为引导策略,对各种优化问题进行求解。

目标函数(Objective Function,OF)是优化问题的目标的数学抽象形式。搜索空间中的每一个解都可以用目标函数来评价,评价得到的值反映了解的优劣,搜索空间的所有解都可以以目标函数的评价值进行排序,得到评价最高(或者最低)的解就是最优解。在搜索算法中,目标函数对于解的评价值是十分重要的引导信息,不同的搜索算法使用各种策略利用引导信息向着更有可能获得最优解的方向进行[5]。如果根据原始问题抽象得到的目标函数选取不合适,那么会导致不论使用哪种搜索策略都无法得到最优解。