基于搜索的機(jī)載軟件需求優(yōu)選技術(shù)研究綜述

張 楠，孟 博，徐玉杰

(航空工業(yè)西安航空計(jì)算技術(shù)研究所，陜西 西安 710065)

0 引言

一直以來(lái)，軟件需求是一個(gè)軟件產(chǎn)品項(xiàng)目的開(kāi)端，也是整個(gè)軟件工程技術(shù)的支撐。軟件需求貫穿整個(gè)軟件開(kāi)發(fā)過(guò)程，一個(gè)軟件產(chǎn)品的架構(gòu)、功能以及演化和發(fā)展均圍繞精確的軟件需求而實(shí)現(xiàn)。因此，在軟件產(chǎn)品的全生命周期中，對(duì)軟件需求的高質(zhì)量管理是保證軟件產(chǎn)品項(xiàng)目成功的關(guān)鍵。

然而，隨著當(dāng)前各領(lǐng)域軟件規(guī)模和復(fù)雜度的不斷增加，軟件需求的數(shù)量也急劇增長(zhǎng)；此外，競(jìng)爭(zhēng)愈發(fā)激烈的市場(chǎng)環(huán)境也不斷刺激著軟件產(chǎn)品功能的快速演進(jìn)，進(jìn)一步導(dǎo)致軟件需求數(shù)量的快速動(dòng)態(tài)增長(zhǎng)。在開(kāi)發(fā)人力增長(zhǎng)有限和軟件需求飛速增長(zhǎng)的矛盾下，軟件需求管理面臨如何從海量具備不同約束條件(預(yù)算限制、技術(shù)能力、開(kāi)發(fā)時(shí)限、功能優(yōu)先級(jí)、干系人重要性等)的需求中，尋找出一組最優(yōu)的可實(shí)現(xiàn)軟件需求子集，既能夠充分利用現(xiàn)有開(kāi)發(fā)資源，又可最大程度滿足干系人需求。這個(gè)問(wèn)題在2001年被Bagnall等人[1,2]定義為“下一個(gè)版本問(wèn)題”(NRP，Next Release Problem)。

針對(duì)上述問(wèn)題，除了傳統(tǒng)的層次分析法(AHP，Analytical Hierarchy process)，成本價(jià)值法(Cost-Value)、多路搜索樹(shù)(B-tree)等方法外[3]，近年來(lái)，一種基于元啟發(fā)式優(yōu)化搜索(SBO，metaheuristic Search Based Optimization)技術(shù)被廣泛研究和應(yīng)用于解決復(fù)雜NRP問(wèn)題，即通過(guò)自動(dòng)化搜索的方式非窮盡的尋找出滿足軟件NRP限制下的最優(yōu)可實(shí)現(xiàn)需求子集[4]?；赟BO的軟件需求優(yōu)選技術(shù)屬于基于搜索的軟件工程(SBSE，Search-Based Software Engineering)方法領(lǐng)域的一個(gè)分支[5]。SBSE方法即致力于采用基于搜索的優(yōu)化算法來(lái)識(shí)別出最佳或接近最佳的軟件工程技術(shù)解決方案。與其它方法相比較，在針對(duì)軟件工程領(lǐng)域具備多目標(biāo)競(jìng)爭(zhēng)和沖突的大型復(fù)雜問(wèn)題時(shí)，SBSE能夠提供一系列適應(yīng)性強(qiáng)的自動(dòng)化或半自動(dòng)化方法有效的解決問(wèn)題。因此，SBSE已被用于解決軟件工程生命周期中的多項(xiàng)問(wèn)題，例如最小測(cè)試用例集覆蓋所有程序分支問(wèn)題，滿足演化和維護(hù)的最佳軟件架構(gòu)設(shè)計(jì)問(wèn)題，軟件項(xiàng)目開(kāi)發(fā)的最佳資源分配問(wèn)題以及用戶滿意度和開(kāi)發(fā)成本平衡問(wèn)題等。

本文則聚焦于將SBO方法應(yīng)用于解決NRP問(wèn)題的軟件需求優(yōu)選技術(shù)，通過(guò)介紹相關(guān)技術(shù)在軟件需求領(lǐng)域的實(shí)現(xiàn)方法、技術(shù)內(nèi)涵，進(jìn)而總結(jié)當(dāng)前技術(shù)的不足和未來(lái)發(fā)展趨勢(shì)，對(duì)基于搜索的軟件需求優(yōu)選技術(shù)進(jìn)行全面的綜合性分析。

1 基于搜索的軟件需求優(yōu)選技術(shù)概念

在基于搜索優(yōu)化算法的軟件需求優(yōu)選技術(shù)中，通常將NRP問(wèn)題進(jìn)行如下定義。R={r1，r2，r3，…，rn}表示軟件涉及的所有可能被實(shí)現(xiàn)的需求；每個(gè)需求擁有一個(gè)成本指標(biāo)Cost={cost1，cost2，cost3，…，costn}，用以表示實(shí)現(xiàn)某一特定需求所需要的資源成本；C={c1，c2，c3，…，cm}表示軟件涉及的所有干系人；每位干系人擁有一個(gè)權(quán)重用以體現(xiàn)其重要程度，用W={w1，w2，w3，…，wm}。

在多數(shù)情況下，一個(gè)需求可能會(huì)被多個(gè)干系人所需要，因此對(duì)于一個(gè)需求ri針對(duì)某一干系人cj的重要性用value(ri，cj)表示。即當(dāng)value大于0表示干系人cj需要需求ri，為0則相反。這樣對(duì)于某一需求i的實(shí)現(xiàn)滿意度得分scorei則由式(1)表示。

(1)

此外，設(shè)計(jì)方案向量X={x1，x2，x3，…，xn}∈{0,1}，表示選擇軟件需求的一個(gè)子集進(jìn)行實(shí)現(xiàn)，則目標(biāo)函數(shù)可表示為式(2)并約束于式(3)，其中B表示可提供的預(yù)算總值，即在預(yù)算限制的條件下最大程度獲得干系人滿意度。

(2)

(3)

上述給出的是最基本的單目標(biāo)NRP問(wèn)題的描述，另外可以對(duì)目標(biāo)函數(shù)進(jìn)行增加，例如增加考慮每種方案的可實(shí)現(xiàn)評(píng)估風(fēng)險(xiǎn)Risk(xi)，并將式(3)變更為目標(biāo)函數(shù)，進(jìn)一步改變其為多目標(biāo)NRP問(wèn)題，如式(2)、式(4)和式(5)所示。

(4)

(5)

在這樣的情況下，當(dāng)需求或需求的目標(biāo)屬性不斷增多時(shí)，NRP問(wèn)題將呈現(xiàn)為一種NP難問(wèn)題，將很難求解出它的一個(gè)精確解。因此，針對(duì)復(fù)雜NRP問(wèn)題，研究采用基于搜索優(yōu)化算法的軟件需求優(yōu)選技術(shù)予以解決。即利用多種啟發(fā)式搜索優(yōu)化算法，如動(dòng)態(tài)規(guī)劃、線性規(guī)劃、遺傳算法等，實(shí)現(xiàn)對(duì)問(wèn)題最優(yōu)解的搜索式逼近。針對(duì)當(dāng)前軟件工程領(lǐng)域需求優(yōu)化選擇問(wèn)題的研究，通?？梢詫⑵浞譃闊o(wú)約束的(單)多目標(biāo)優(yōu)選方法以及帶約束的(單)多目標(biāo)優(yōu)選方法。后面將重點(diǎn)對(duì)這兩個(gè)類型的軟件需求優(yōu)選技術(shù)進(jìn)行分析說(shuō)明。

2 基于搜索的軟件需求優(yōu)選技術(shù)

2.1 基于搜索的軟件需求(單)多目標(biāo)優(yōu)選技術(shù)

基于搜索的軟件需求單目標(biāo)優(yōu)選技術(shù)是在SBSE領(lǐng)域最初被提出的方法，即只針對(duì)達(dá)成某一最重要目標(biāo)，例如干系人滿意度的最大化。單目標(biāo)優(yōu)選技術(shù)的優(yōu)勢(shì)在于，因?yàn)槠鋬H針對(duì)單個(gè)目標(biāo)，因此可以直接利用現(xiàn)有的成熟搜索算法進(jìn)行有效計(jì)算，例如遺傳算法(GA，Genetic Algorithm)、退火算法(SA，Simulated Annealing)、爬山算法(HC，Hill Climbing)、禁忌搜索算法(TS，Tabu Search)、粒子群優(yōu)化算法(PSO，Particle Swarm Optimization)等。單目標(biāo)優(yōu)選技術(shù)因其僅需要確定一個(gè)最主要的目標(biāo)，因此不必進(jìn)行復(fù)雜的建模即可使用，是一種較為簡(jiǎn)單的優(yōu)選技術(shù)，但也正因如此，它在需求選擇執(zhí)行的效果上有所欠缺。

隨著軟件規(guī)模和復(fù)雜度的增加，并為進(jìn)一步彌補(bǔ)單目標(biāo)優(yōu)選技術(shù)的不足，軟件需求多目標(biāo)優(yōu)選技術(shù)被不斷提出，即在多個(gè)目標(biāo)函數(shù)中尋找優(yōu)化平衡，例如帶精英策略的非支配排序遺傳算法、多目標(biāo)粒子群優(yōu)化算法、基于帕累托包絡(luò)的選擇算法、雙歸檔算法、強(qiáng)度帕累托進(jìn)化算法等。多目標(biāo)優(yōu)選技術(shù)相比單目標(biāo)優(yōu)選技術(shù)也更加符合實(shí)際的軟件需求NRP問(wèn)題，但建模和計(jì)算過(guò)程均較為復(fù)雜。

2.2 基于搜索的軟件需求帶約束(單)多目標(biāo)優(yōu)選技術(shù)

在上一節(jié)討論的多目標(biāo)優(yōu)選技術(shù)中，均沒(méi)有考慮軟件需求的約束，例如需求與需求間的交互關(guān)系。在實(shí)際的軟件開(kāi)發(fā)情況下，一些需求可能會(huì)在技術(shù)、架構(gòu)、功能、業(yè)務(wù)等方面的約束下存在相關(guān)性，導(dǎo)致需求間相互存在依賴或排斥的關(guān)系。因此，在不考慮需求間約束情況得到的軟件需求優(yōu)選方案，很可能是實(shí)際無(wú)效的。此外，在帶約束的多目標(biāo)優(yōu)選技術(shù)中，盡管復(fù)雜了需求優(yōu)化問(wèn)題，但通過(guò)首先處理需求間的約束關(guān)系，可以優(yōu)先排除掉不可行解，進(jìn)而減少問(wèn)題解空間，反而有利于最優(yōu)解的搜索。在帶約束單目標(biāo)優(yōu)選技術(shù)中，如采用改進(jìn)的交互遺傳算法(IGA，Interactive genetic Algorithm)、蟻群優(yōu)化(ACO，Ant Colony Optimization)、可滿足性模塊(SMT，Satisfiability Modulo Theory)排序方法等[12,13]。在帶約束多目標(biāo)優(yōu)選技術(shù)中，常用的搜索方法包括基于歸檔的帶精英策略非支配排序遺傳算法(archive-based NSGA-II)、基于修復(fù)的帶精英策略非支配排序遺傳算法(repair method based NSGA-II)、改進(jìn)的進(jìn)化算法(BEA，Beyond Evolutionary Algorithms)等。

3 基于搜索的軟件需求優(yōu)選技術(shù)發(fā)展趨勢(shì)

當(dāng)前有眾多基于搜索優(yōu)化方法的軟件需求優(yōu)選技術(shù)已被提出，為解決復(fù)雜大型軟件項(xiàng)目的需求管理難題提供了新的思路。然而，通過(guò)分析目前主流基于搜索的軟件需求優(yōu)選技術(shù)，除了在自身搜索算法上的優(yōu)化外仍然存在一些問(wèn)題值得進(jìn)一步研究。

1) 基于搜索的軟件需求優(yōu)選技術(shù)數(shù)據(jù)源獲取

基于搜索的軟件需求優(yōu)選技術(shù)廣泛依賴于軟件需求相關(guān)數(shù)據(jù)，尤其在近年來(lái)逐漸提出的包含不確定性因素的有約束多目標(biāo)優(yōu)選技術(shù)中，眾多研究?jī)H關(guān)注于搜索優(yōu)化算法的改進(jìn)和實(shí)現(xiàn)。但在目前復(fù)雜大規(guī)模軟件項(xiàng)目中，如何將零散的需求數(shù)據(jù)進(jìn)行準(zhǔn)確有效的信息收集與融合是利用搜索優(yōu)化方法實(shí)現(xiàn)軟件需求優(yōu)選的基礎(chǔ)與關(guān)鍵。

2) 基于搜索的軟件需求優(yōu)選技術(shù)的智能化發(fā)展

當(dāng)前的軟件需求優(yōu)選技術(shù)并未形成一套完整的智能化需求實(shí)現(xiàn)子集決策過(guò)程，NRP問(wèn)題的最終解決仍然由人工參與為主導(dǎo)。借鑒目前深度學(xué)習(xí)和強(qiáng)化學(xué)習(xí)等智能化技術(shù)在決策領(lǐng)域取得的成果，完全可以進(jìn)一步將其納入軟件需求優(yōu)選過(guò)程，減少人力參與促進(jìn)智能化的需求決策。

3) 基于搜索的軟件需求優(yōu)選技術(shù)與其它軟件工程方法的結(jié)合

基于搜索的軟件工程方法是采用搜索優(yōu)化的策略解決軟件工程中遇到的問(wèn)題，該套方法是一種比較靈活通用的方法。針對(duì)在軟件工程中已有的包括面向服務(wù)的開(kāi)發(fā)、基于模型驅(qū)動(dòng)的開(kāi)發(fā)、形式化開(kāi)發(fā)以及軟件產(chǎn)品線等研究，是否可以將基于搜索的軟件需求優(yōu)選技術(shù)與上述軟件工程方法進(jìn)行有效結(jié)合，進(jìn)一步推動(dòng)軟件開(kāi)發(fā)的自動(dòng)化發(fā)展。

4 結(jié)束語(yǔ)

本文面向軟件需求工程領(lǐng)域的NRP問(wèn)題，綜合介紹了基于搜索的軟件需求優(yōu)選技術(shù)，分析對(duì)比了目前主流的各類型軟件需求優(yōu)選技術(shù)內(nèi)涵、技術(shù)特性及技術(shù)挑戰(zhàn)，并給出該技術(shù)在自身發(fā)展以及多領(lǐng)域軟件工程方法結(jié)合等層面的未來(lái)發(fā)展趨勢(shì)分析。希望本文能夠?yàn)檐浖枨蠊こ填I(lǐng)域及軟件工程領(lǐng)域的相關(guān)研究和工作人員提供有益的幫助。