基于搜索的软件工程（SBSE）
- 智能优化方法
- 具体应用方向

基于搜索的软件工程（SBSE）

SBSE 是将传统的软件刚才问题转化为基于搜索的优化问题，并使用现代启发式搜索算法解决问题的研究和实践方法

传统软件工程的解决方法实在问题空间通过算法来构造一个解，而SBSE是在解空间中使用启发式搜索算法以具体问题的适应值函数作为向导搜索最优解，满足以下条件：

设计出问题解决方案表达式
设计出相应的适应度函数

智能优化方法

一些广泛使用的智能优化算法：遗传算法，爬山算法，模拟退火算法，蚁群算法和粒子群算法

遗传算法

遗传算法是一种模拟自然界生物进化过程的启发式搜索算法，可以产生一个针对问题解的群体并对其进行进化和优化。遗传算法属于演化算法的一种，这种算法通过模拟自然选择的过程对产生的解进行优化，优化操作包括选择、变异（概率低）、交叉（概率高）。

演化过程；

由一组随机产生的个体构成初始种群
对种群不断迭代，方法包括选择、交叉、变异
终止条件：达到迭代次数或达到评估函数的目标值

遗传算法可以应用于预测模型和软件测试

爬山算法

是一种局部搜索算法，从某个可行解出发通过每次更改一个解的决策变量以寻找更好的解，分为；

近邻爬山算法
最陡爬山算法

不断迭代最终可以达到一个局部最优解，依赖于算法初始解的选取、选点的规则、算法的终止条件

模拟退火算法

也叫蒙特卡洛退火，源于对热力学退火过程的模拟，可以视为是爬山算法的变种，区别在于允许当前解移动到非最优解来解决爬山算法容易陷入局部最优问题，步骤如下：

当前解经过简单变换产生新的解
计算新解各当前解所对应的目标函数的差
判断新解是否被接受，常用接受准则是 \(Metropolis\) 准则，“温度”越低，接受新的非最优解的概率越低
确定接受新解时，就代替当前解并修正目标函数值

蚁群算法

是一种用来在图中寻找优化路径的几率型算法，一条路径上留下的信息素浓度和这条路径通过对蚂蚁数目成正比。通过的蚂蚁越多，留下的信息素越多，导致后来蚂蚁选择这条路径的概率提高，从而建立最短的移动路径

蚂蚁在路径上释放信息素。
碰到还没走过的路口，就随机挑选一条路走。同时，释放与路径长度有关的信息素。
信息素浓度与路径长度成反比。后来的蚂蚁再次碰到该路口时，就选择信息素浓度较高路径。
最优路径上的信息素浓度越来越大。
最终蚁群找到最优寻食路径。

粒子群算法

每个粒子以一定的速度在解空间运动，并向自身历史最佳位置和邻域历史最佳位置聚集。

有三种前进方向，分别是自身历史前进方向、惯性前进方向、群体历史最佳前进方向，综合三种方向进行搜索

具体应用方向

基于搜索的软件工程在软件工程生命周期中的应用方向

软件测试

在理想情况下，为了对测试的有效性和测试后的软件质量有一个较高的信心，软件测试应该是尽可能穷尽整个待测输入空间的，但是在实际工程中并没有足够多的资源来执行穷尽测试所需的用例。因此传统方式经常强调测试用例的精心设计，然而在实践中，有些精心设计的测试用例不仅不容易自动化，有时甚至“精心”地绕过了软件中存在的故障。

另一方面，高度自动化的随机测试在许多测试场景下表现得并不差，但是纯粹的随机测试难以实现更深层次的测试，比如实现语句覆盖、分支覆盖、路径覆盖等各种覆盖充分性准则测试

测试数据生成

在各种测试方法中，测试数据生成是搜索技术在软件测试领域应用最广泛的场景

例如：在结构测试中

在结构测试中，通过对被测程序进行插桩，并执行一些随机的测试数据
这些测试数据的质量将依据适应值函数进行评估
在搜索机制的作用下，更加接近测试目标的测试数据将不断生成，最后达到预期目的

在这一过程中，适应函数的设计是关键，分支距离和层接近度，以及两者结合是最为常用的方法

分支距离：指在通过改变变量的方法来生成测试数据时，如果一条非指定路径被执行，那么就会产生与指定路径的偏差，而搜索的目的就是尽可能减少这一偏差
层接近度：

在测试数据生成时，除了覆盖程序的某些特定结构外，搜索技术同样可以依据其他不同的标准来为不同的测试方法生成数据。

在功能测试中，检查系统的逻辑行为是否和预期的规格说明相一致
软件系统的正确性还依赖于系统的时间属性，尤其在实时系统中，输出产生过早或过晚都会产生故障
- 可以利用遗传算法来进行测试数据生成
- 适应值函数是系统的执行时间
- 而搜索目标是尽可能最大化系统的最长执行时间
也可以为压力测试生成测试数据，测试系统能承受的最大压力

在变异测试中，并行演化两个过程可以改进变异测试的过程：

找出一个较难杀死且不含等价变异体的变异体集合
找出一个尽可能多地撒施变异体的高质量测试用例集合

其他软件测试活动

在集成测试中，测试人员需要依据各构件的依赖关系来确定构件被集成的顺序，但是很多软件构件的依赖关系会使层次结构图中包含一些环，传统集成测试的方法就不再适合。

因此需要找到合适的构件继承顺序，从而尽可能减少所需的桩程序数目，集成所需步骤和时间，可以利用搜索算法在各种集成顺序的候选解中找出最优集成顺序

在回归测试中，由于随着软件功能的不断开发，回归测试集的规模也不断增长，所以是如何选择合适的测试用例执行，以及如何安排测试用例的执行顺序才能更快检测出软件的故障是关键问题。

程序错误自动修复与错误定位（debug）

2012年，研究人员针对百万行软件错误修复代价高昂的问题，从软件自动修复三阶段，即错误定位、补丁生成和补丁验证阶段入手，建立了大型开源软件历史错误分析数据集和错误定位有效性分析比较平台。

错误定位通过对程序失效或异常行为进行分析，寻找导致失效或异常的根源所在，即定位到错误在程序中的位置

需求分析

随着软件规模的日益增长和复杂性增加，每个客户都有自己的优先需求目标，不同的需求之间又通常存在利益冲突，所以，此时就需要在现有资源中权衡满足每个用户的需求做出最优的选择，可以选择启发式优化算法来解决复杂的、多目标的、条件约束的需求分析问题。

随着解决需求的复杂化，传统的单目标优化问题逐步发展成为多目标优化问题。基于多目标的帕累托最优化策略，通过启发式算法挑选出不受其他变量支配的非支配子集，每一个非支配集合表示了一种可能的资源分配，并且在已有资源限制条件下使客户满意度达到最优。

非支配解集合是指在多目标优化问题中，在至少一个目标函数优于其他解的解

帕累托优化：是指在多目标优化问题中，同时优化多个目标函数，以寻找最优解集中的非劣解集合的方法。主要思想是通过解决目标函数的权衡关系，是的多个目标函数得到最优化，而不是单独优化每个目标函数。

帕累托最适的状态就是不可能再有更多的帕累托改善的状态；换句话说，不可能在不使任何其他人受损的情况下再改善某些人的情况。

非劣解是指在所有目标函数上至少有一个函数优于其他解的解
非劣解不一定唯一，是一组在多个目标函数下都具有最优性质的解。在多目标优化问题中，我们通常需要找到一组非劣解，这些解称为Pareto前沿
非劣解可能有多个，可能会存在多个具有不同特征的解，至少有一个函数优于其他解

软件设计

在面向对象的软件设计中，设计人员如何才能确定合适的类和类中的属性和方法，单靠人工来确定往往是很困难的。而SBSE可以根据基于方法和属性的内聚度和耦合度来进行设计。

例如Simons 和 parmee使用多目标优化的遗传算法来从使用案例设计面向对象软件，使用的适应值函数包括类的内聚度、类间的耦合度、类的数量

在面向服务的软件设计中，通过将应用程序的功能作为服务发送给最终用户或其他服务，面向服务的体系结构可以非常灵活地结合不同的服务以提高一些复杂的功能。

由于设计中需要的服务可以在运行时选择多个所需的具体服务，和同一抽象服务相关的具体服务在功能上是等价的，所以人们在选择时通常按照服务质量（QOS）这一非功能性标准来选择，以保证服务可以更好满足用户的需要，并在高水平运行。

给定需要的抽象服务和可选的具体服务，如何进行对应的绑定并使得系统在满足一定约束条件下尽可能优化某些特定目标是面向服务软件设计的关键，也称为QOS的服务组合问题，除了考虑对新的服务进行组合优化外，遗传算法也可以用于服务运行时的重绑定，从而使得原先确定的服务在服务质量和预测值产生偏差时进行服务的重新组合