基于搜索的机载软件需求优选技术研究综述

张 楠，孟 博，徐玉杰

(航空工业西安航空计算技术研究所，陕西 西安 710065)

0 引言

一直以来，软件需求是一个软件产品项目的开端，也是整个软件工程技术的支撑。软件需求贯穿整个软件开发过程，一个软件产品的架构、功能以及演化和发展均围绕精确的软件需求而实现。因此，在软件产品的全生命周期中，对软件需求的高质量管理是保证软件产品项目成功的关键。

然而，随着当前各领域软件规模和复杂度的不断增加，软件需求的数量也急剧增长；此外，竞争愈发激烈的市场环境也不断刺激着软件产品功能的快速演进，进一步导致软件需求数量的快速动态增长。在开发人力增长有限和软件需求飞速增长的矛盾下，软件需求管理面临如何从海量具备不同约束条件(预算限制、技术能力、开发时限、功能优先级、干系人重要性等)的需求中，寻找出一组最优的可实现软件需求子集，既能够充分利用现有开发资源，又可最大程度满足干系人需求。这个问题在2001年被Bagnall等人[1,2]定义为“下一个版本问题”(NRP，Next Release Problem)。

针对上述问题，除了传统的层次分析法(AHP，Analytical Hierarchy process)，成本价值法(Cost-Value)、多路搜索树(B-tree)等方法外[3]，近年来，一种基于元启发式优化搜索(SBO，metaheuristic Search Based Optimization)技术被广泛研究和应用于解决复杂NRP问题，即通过自动化搜索的方式非穷尽的寻找出满足软件NRP限制下的最优可实现需求子集[4]。基于SBO的软件需求优选技术属于基于搜索的软件工程(SBSE，Search-Based Software Engineering)方法领域的一个分支[5]。SBSE方法即致力于采用基于搜索的优化算法来识别出最佳或接近最佳的软件工程技术解决方案。与其它方法相比较，在针对软件工程领域具备多目标竞争和冲突的大型复杂问题时，SBSE能够提供一系列适应性强的自动化或半自动化方法有效的解决问题。因此，SBSE已被用于解决软件工程生命周期中的多项问题，例如最小测试用例集覆盖所有程序分支问题，满足演化和维护的最佳软件架构设计问题，软件项目开发的最佳资源分配问题以及用户满意度和开发成本平衡问题等。

本文则聚焦于将SBO方法应用于解决NRP问题的软件需求优选技术，通过介绍相关技术在软件需求领域的实现方法、技术内涵，进而总结当前技术的不足和未来发展趋势，对基于搜索的软件需求优选技术进行全面的综合性分析。

1 基于搜索的软件需求优选技术概念

在基于搜索优化算法的软件需求优选技术中，通常将NRP问题进行如下定义。R={r1，r2，r3，…，rn}表示软件涉及的所有可能被实现的需求；每个需求拥有一个成本指标Cost={cost1，cost2，cost3，…，costn}，用以表示实现某一特定需求所需要的资源成本；C={c1，c2，c3，…，cm}表示软件涉及的所有干系人；每位干系人拥有一个权重用以体现其重要程度，用W={w1，w2，w3，…，wm}。

在多数情况下，一个需求可能会被多个干系人所需要，因此对于一个需求ri针对某一干系人cj的重要性用value(ri，cj)表示。即当value大于0表示干系人cj需要需求ri，为0则相反。这样对于某一需求i的实现满意度得分scorei则由式(1)表示。

(1)

此外，设计方案向量X={x1，x2，x3，…，xn}∈{0,1}，表示选择软件需求的一个子集进行实现，则目标函数可表示为式(2)并约束于式(3)，其中B表示可提供的预算总值，即在预算限制的条件下最大程度获得干系人满意度。

(2)

(3)

上述给出的是最基本的单目标NRP问题的描述，另外可以对目标函数进行增加，例如增加考虑每种方案的可实现评估风险Risk(xi)，并将式(3)变更为目标函数，进一步改变其为多目标NRP问题，如式(2)、式(4)和式(5)所示。

(4)

(5)

在这样的情况下，当需求或需求的目标属性不断增多时，NRP问题将呈现为一种NP难问题，将很难求解出它的一个精确解。因此，针对复杂NRP问题，研究采用基于搜索优化算法的软件需求优选技术予以解决。即利用多种启发式搜索优化算法，如动态规划、线性规划、遗传算法等，实现对问题最优解的搜索式逼近。针对当前软件工程领域需求优化选择问题的研究，通常可以将其分为无约束的(单)多目标优选方法以及带约束的(单)多目标优选方法。后面将重点对这两个类型的软件需求优选技术进行分析说明。

2 基于搜索的软件需求优选技术

2.1 基于搜索的软件需求(单)多目标优选技术

基于搜索的软件需求单目标优选技术是在SBSE领域最初被提出的方法，即只针对达成某一最重要目标，例如干系人满意度的最大化。单目标优选技术的优势在于，因为其仅针对单个目标，因此可以直接利用现有的成熟搜索算法进行有效计算，例如遗传算法(GA，Genetic Algorithm)、退火算法(SA，Simulated Annealing)、爬山算法(HC，Hill Climbing)、禁忌搜索算法(TS，Tabu Search)、粒子群优化算法(PSO，Particle Swarm Optimization)等。单目标优选技术因其仅需要确定一个最主要的目标，因此不必进行复杂的建模即可使用，是一种较为简单的优选技术，但也正因如此，它在需求选择执行的效果上有所欠缺。

随着软件规模和复杂度的增加，并为进一步弥补单目标优选技术的不足，软件需求多目标优选技术被不断提出，即在多个目标函数中寻找优化平衡，例如带精英策略的非支配排序遗传算法、多目标粒子群优化算法、基于帕累托包络的选择算法、双归档算法、强度帕累托进化算法等。多目标优选技术相比单目标优选技术也更加符合实际的软件需求NRP问题，但建模和计算过程均较为复杂。

2.2 基于搜索的软件需求带约束(单)多目标优选技术

在上一节讨论的多目标优选技术中，均没有考虑软件需求的约束，例如需求与需求间的交互关系。在实际的软件开发情况下，一些需求可能会在技术、架构、功能、业务等方面的约束下存在相关性，导致需求间相互存在依赖或排斥的关系。因此，在不考虑需求间约束情况得到的软件需求优选方案，很可能是实际无效的。此外，在带约束的多目标优选技术中，尽管复杂了需求优化问题，但通过首先处理需求间的约束关系，可以优先排除掉不可行解，进而减少问题解空间，反而有利于最优解的搜索。在带约束单目标优选技术中，如采用改进的交互遗传算法(IGA，Interactive genetic Algorithm)、蚁群优化(ACO，Ant Colony Optimization)、可满足性模块(SMT，Satisfiability Modulo Theory)排序方法等[12,13]。在带约束多目标优选技术中，常用的搜索方法包括基于归档的带精英策略非支配排序遗传算法(archive-based NSGA-II)、基于修复的带精英策略非支配排序遗传算法(repair method based NSGA-II)、改进的进化算法(BEA，Beyond Evolutionary Algorithms)等。

3 基于搜索的软件需求优选技术发展趋势

当前有众多基于搜索优化方法的软件需求优选技术已被提出，为解决复杂大型软件项目的需求管理难题提供了新的思路。然而，通过分析目前主流基于搜索的软件需求优选技术，除了在自身搜索算法上的优化外仍然存在一些问题值得进一步研究。

1) 基于搜索的软件需求优选技术数据源获取

基于搜索的软件需求优选技术广泛依赖于软件需求相关数据，尤其在近年来逐渐提出的包含不确定性因素的有约束多目标优选技术中，众多研究仅关注于搜索优化算法的改进和实现。但在目前复杂大规模软件项目中，如何将零散的需求数据进行准确有效的信息收集与融合是利用搜索优化方法实现软件需求优选的基础与关键。

2) 基于搜索的软件需求优选技术的智能化发展

当前的软件需求优选技术并未形成一套完整的智能化需求实现子集决策过程，NRP问题的最终解决仍然由人工参与为主导。借鉴目前深度学习和强化学习等智能化技术在决策领域取得的成果，完全可以进一步将其纳入软件需求优选过程，减少人力参与促进智能化的需求决策。

3) 基于搜索的软件需求优选技术与其它软件工程方法的结合

基于搜索的软件工程方法是采用搜索优化的策略解决软件工程中遇到的问题，该套方法是一种比较灵活通用的方法。针对在软件工程中已有的包括面向服务的开发、基于模型驱动的开发、形式化开发以及软件产品线等研究，是否可以将基于搜索的软件需求优选技术与上述软件工程方法进行有效结合，进一步推动软件开发的自动化发展。

4 结束语

本文面向软件需求工程领域的NRP问题，综合介绍了基于搜索的软件需求优选技术，分析对比了目前主流的各类型软件需求优选技术内涵、技术特性及技术挑战，并给出该技术在自身发展以及多领域软件工程方法结合等层面的未来发展趋势分析。希望本文能够为软件需求工程领域及软件工程领域的相关研究和工作人员提供有益的帮助。