軟件發(fā)布規(guī)劃的形式化探討

摘 要： 軟件發(fā)布規(guī)劃存在認(rèn)知和計(jì)算困難等問題。多種不確定性因素使問題很難描述和解決。運(yùn)用進(jìn)化方法求解是減輕這些困難的一種途徑。為此探討了這個(gè)過程中的形式化描述，提供了一套解決問題的思路。其基本原理是：確定決策變量及約束參數(shù)；明確規(guī)劃的目標(biāo)模型；在進(jìn)化迭代求解過程中求出合格且多樣化的解決方案組合；從合格的解決方案中運(yùn)用多屬性決策輔助方法協(xié)助選擇最終解決方案。在每一個(gè)過程中專家都參與互動(dòng)和求解。

關(guān)鍵詞： 發(fā)布規(guī)劃； 不良問題； 不確定性； 標(biāo)準(zhǔn)； 進(jìn)化； 決策輔助

中圖分類號(hào)：TP311.52 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2013）12-12-03

Study on formalization of software release planning

Wang Zhigang， Gao Lei

（College of Math and Computer science， Hunan Normal University， Changsha， Hunan 410081， China）

Abstract： Software release planning is known to be a cognitively and computationally difficult problem. Different kinds of uncertainties make it burdensome to formulate and solve the problem. The solution using evolution method is one method to solve these difficulties. After the formalization of the process being discussed， the ideas are provided to solve the problem. The basic principles include： determining the decision variables and the constraints； defining an explicit target of the release planning； obtaining a set of diversified and qualified solutions by the iterations of evolutional process； selecting the final solution from a set of qualified solutions by using the multi-attribute decision aid method. Each step should be finished through the interaction of the experts.

Key words： release planning； wicked problem； uncertainty； criteria； evolution； decision aid

0 引言

Carlshamre[1]將軟件發(fā)布規(guī)劃分類為不良問題。多種不確定性因素使問題很難描述和解決。依據(jù)幾個(gè)特點(diǎn)可以分類問題是不良的：一是沒有明確的形式化方法表達(dá)問題；二是沒有停止規(guī)則。

進(jìn)化是一個(gè)逐步適應(yīng)和多樣化的過程。進(jìn)化計(jì)算是受這個(gè)思想的啟發(fā)而產(chǎn)生的軟計(jì)算方法。它涉及到計(jì)算搜索、學(xué)習(xí)、優(yōu)化和建模方法等[2]。在決策過程中，決策問題的所有元素都是不斷變化的，因此決策問題的演化契合進(jìn)化過程。

Saliu O[7]提出了一種基于進(jìn)化的軟件發(fā)布決策支持方案，該模型的不足是對(duì)軟件發(fā)布中的軟因素考慮不夠全面。Du G[8]研究了解決不良問題的一種交互解析途徑，對(duì)解決軟件發(fā)布問題有一定的參考價(jià)值，但對(duì)硬約束的形式化描述力度不夠。文獻(xiàn)[10]提出了一種基于模糊多目標(biāo)優(yōu)化的軟件最優(yōu)發(fā)布時(shí)間決策模型，決策風(fēng)險(xiǎn)的量化與控制主要關(guān)注軟件測(cè)試費(fèi)用的不確定及其對(duì)軟件最優(yōu)發(fā)布時(shí)間決策的影響，但是它忽視了領(lǐng)域?qū)＜业膮⑴c。文獻(xiàn)[11]對(duì)軟件發(fā)布的關(guān)鍵因素作了分析與研究，在軟件安全生命周期的基礎(chǔ)上提出了一個(gè)改進(jìn)的適合于中小型企業(yè)的軟件安全開發(fā)流程，重點(diǎn)關(guān)注軟件產(chǎn)品的安全性，也使知識(shí)產(chǎn)權(quán)得到了保護(hù)。因此該模型主要針對(duì)的是軟件版權(quán)的安全因素。

軟計(jì)算的不同之處在于，它能容忍數(shù)據(jù)的不精確、不確定性、局部真理和近似值。概率理論、神經(jīng)網(wǎng)絡(luò)、模糊集、粗糙集和貝葉斯網(wǎng)絡(luò)已被成功地應(yīng)用在這些情況下求解問題。這些方法都依賴于特定的模型假設(shè)，重要的是能正確解決問題。然而，不確定的軟件工程決策是不可能完全形式化的。有些軟的因素很難確立模型，這些因素可以來自于組織因素、人的問題或技術(shù)方面的考慮[3]。人類的領(lǐng)域智慧或解決方案專家更可能應(yīng)對(duì)隱藏的影響因素，這也是人在實(shí)際決策中表現(xiàn)出的優(yōu)點(diǎn)所在。真實(shí)的發(fā)布規(guī)劃問題可能有上百個(gè)出現(xiàn)在未來版本中的特征。因此，在這些情況下，僅僅依靠人的直覺和人員的交流是很難解決問題的。綜合上述兩種策略找出解決不確定性問題的方案是較好的選擇：①領(lǐng)域?qū)＜一?dòng)參與實(shí)際問題的形式化這一進(jìn)化過程；②為所有迭代求解過程提供多樣化的且合格的解決方案組合；③運(yùn)用多屬性決策輔助方法ELECTRE IS[4]協(xié)助選擇最終解決方案。

1 軟件發(fā)布規(guī)劃屬性的描述

關(guān)于發(fā)布規(guī)劃問題的構(gòu)成，各種文獻(xiàn)有不同的定義。文獻(xiàn)[5]為之描述了十大關(guān)鍵因素。一般而言，軟件發(fā)布規(guī)劃的關(guān)鍵屬性有如下種類：①?zèng)Q策變量；②硬約束；③目標(biāo)規(guī)劃；④軟（或隱式）約束。

1.1 決策變量

特征是為了滿足一組功能和質(zhì)量要求的外在邏輯單元。假設(shè)有N個(gè)特征的子集Γ={f（1），f（2），…，f（N）}，在一個(gè)時(shí)間期限內(nèi)有K次發(fā)布規(guī)劃目標(biāo)，發(fā)布規(guī)劃的特征用決策向量X描述。

X=（x（1），x（2），…，x（N）），x（i）=k，如果特征f（i）被指定給第k次發(fā)布，k∈{1，2，…K}；其他情況下x（i）=0。

在某些情況下，基于優(yōu)化決策的目的，特征f（i）可以提前指定給第k次發(fā)布，此時(shí)條件x（i）=k可以歸到硬約束中。

1.2 硬約束

在任何發(fā)布規(guī)劃的潛在解決方案中需要按計(jì)劃完成的約束稱為硬約束，這些約束隨項(xiàng)目變化而變化。硬約束的目標(biāo)明確且容易被形式化，硬約束集合用Xhard表示。

硬約束分技術(shù)、資源或預(yù)算方面的約束。用關(guān)系Γ*Γ的子集表示它們之間的耦合情況：

耦合C：x（i）=x（j），?（i，j）∈C?Γ*Γ

弱優(yōu)先WP：x（i）?x（j），?（i，j）∈WP?Γ*Γ

強(qiáng)優(yōu)先SP：x（i）

資源約束是另一類的硬約束。每個(gè)特征需要消耗不同類型的資源。設(shè)有R種不同類型的資源與實(shí)現(xiàn)這些特征相關(guān)，用s（i， r）表示特征f（i）需要消耗資源類型r的數(shù)量。每個(gè)發(fā)布選項(xiàng)k有一定量的資源類型r可供支配，用C（k， r）表示。因此，與發(fā)布k相關(guān)的特征所需的資源需求必須滿足以下條件：

∑i：x（i）=ks（i，r）?C（k，r），k=1…K，r=1…R

除了人力資源，特征也會(huì)消耗財(cái)政資源。從財(cái)政角度考慮，人力資源也可以用貨幣表達(dá)。在一般情況下，假設(shè)資源約束是線性的。例如，一組特征的財(cái)政量定義為所有單個(gè)特征所需財(cái)政量的總和。這非所有實(shí)際情況都需滿足以上條件，但它通常是模型的意義和計(jì)算量之間的一個(gè)很好的妥協(xié)方案。

1.3 軟約束

軟約束很難描述或只需要充分滿足。這些約束條件簡(jiǎn)稱Xsoft?？赡艿能浖s束如下：

⑴ 實(shí)施風(fēng)險(xiǎn)（試圖平衡不同發(fā)布之間的整體風(fēng)險(xiǎn)，或?qū)L(fēng)險(xiǎn)特征推遲到以后的發(fā)布）；

⑵ 資源消耗（試圖平衡不同版本之間的不同資源類型的消費(fèi)來避免峰值和閑置資源）；

⑶ 利益相關(guān)者的滿意度（試圖為特定的、優(yōu)先級(jí)最高的利益相關(guān)者提供服務(wù)）；

⑷ 競(jìng)爭(zhēng)力（試圖提供規(guī)劃以支持產(chǎn)品的競(jìng)爭(zhēng)力）。

這些條件的實(shí)現(xiàn)將由領(lǐng)域?qū)＜以谠u(píng)估解決方法的后一階段完成。軟約束也可以采用類似硬約束的方式實(shí)現(xiàn)形式化，這些方法同樣可以運(yùn)用到目標(biāo)規(guī)劃中。

1.4 目標(biāo)規(guī)劃

目標(biāo)規(guī)劃難以形式化的原因有三個(gè)方面：①規(guī)劃的標(biāo)準(zhǔn)是什么；②怎樣處理這些標(biāo)準(zhǔn)；③組成解決方案的是什么。發(fā)布規(guī)劃的標(biāo)準(zhǔn)是具體項(xiàng)目。通常，目標(biāo)規(guī)劃與創(chuàng)造商業(yè)價(jià)值最大化、減少研發(fā)產(chǎn)品到上市的時(shí)間，以及使利益相關(guān)者的利益最大化等因素相關(guān)。為了體現(xiàn)實(shí)際效用，這里用u函數(shù)嘗試平衡這些不同的要求，該函數(shù)的實(shí)際成分取決于問題的具體特點(diǎn)。下面是一些可能的函數(shù)形式，這里的u（i，k）表示為獲得整體效用，特征f（i）被分配到發(fā)布選項(xiàng)k。

u（i，k）=v（i，k）*e（i，k）

u（i，k）=w（1）*v（i，k）+w（2）*e（i，k）+w（3）*h（i，k），{w（i）≥0，∑w（i）=1}

u（i，k）=Min{v（i，k），e（i，k），h（i，k），g（i，k）}

這里v表示費(fèi)用，e表示緊迫性，h表示風(fēng)險(xiǎn)程度，g表示不滿程度，v（i，k）表示特征f（i）分配到發(fā)布選項(xiàng)k時(shí)預(yù)期需要的費(fèi)用，其他函數(shù)意義類似。

在所有這些情況下，求得不同的值并加權(quán)平均以體現(xiàn)所有利益相關(guān)者的優(yōu)先級(jí)。將所有這些值在1和9之間量化，1的優(yōu)先級(jí)最低。所謂“正確”目標(biāo)的定義取決于決策者看問題的角度。發(fā)布規(guī)劃x的整體效用稱為Ut（x）。

Ut（x）=∑k=1..K ∑i： x（i）=ku（i，k）

發(fā)布規(guī)劃問題現(xiàn)在可以表述為：

確定x*，Ut（x*）=max*{Ut（x）：x∈Xhard并且x滿足Xsoft充分約束}。

規(guī)劃x*要達(dá)到這樣一個(gè)優(yōu)秀水平：它既能滿足硬約束條件，也能足夠好的滿足軟標(biāo)準(zhǔn)要求。“足夠好”（值9）是主觀的，最終應(yīng)該由領(lǐng)域?qū)＜覜Q定是否可以接受。

2 解決問題的進(jìn)化方法

在進(jìn)化求解問題過程中，一個(gè)合適的解決方案是由領(lǐng)域?qū)＜液突趩栴}形式化描述后的算法運(yùn)算出的結(jié)果之間相互作用后進(jìn)化而來，在決策過程中加入軟約束條件和目標(biāo)。通過產(chǎn)生一組合格的、多樣化的解決方案，應(yīng)用多屬性決策方法ELECTRE IS，進(jìn)化方法可以為領(lǐng)域?qū)＜医o問題描述排序和選擇最終解決方案提供保證。

進(jìn)化求解問題方法重點(diǎn)關(guān)注“針對(duì)問題”的形式化過程。但這不可能是一個(gè)完美的方式，需要一種機(jī)制在這個(gè)過程中評(píng)價(jià)目前的進(jìn)展和決定何時(shí)終止；這兩個(gè)問題可以交給涉及這個(gè)過程的領(lǐng)域?qū)＜襾硗瓿伞Ｔ诘?，提供多樣化的解決方案組合，以便從中獲得問題是否妥善解決的見解。這種方法假定領(lǐng)域?qū)＜易约簾o法形式化問題，但是能夠評(píng)估解決方案是否解決了各種顯性和隱性的問題。

2.1 合格的解決方案

一個(gè)合格的替代方案包括問題求解的兩個(gè)不同方面。

⑴ 有針對(duì)問題求解的合格意識(shí)。建議的（合格）發(fā)布規(guī)劃應(yīng)對(duì)原（現(xiàn)實(shí)世界）問題有意義。為了實(shí)現(xiàn)這一目標(biāo)，主要依靠領(lǐng)域?qū)＜业哪芰砻枋鰡栴}和評(píng)估建議的解決方案。

⑵ 有正確解決問題的合格意識(shí)。建議的（合格）發(fā)布規(guī)劃應(yīng)對(duì)問題的形式化質(zhì)量有一定程度的保證。為了實(shí)現(xiàn)這一目標(biāo)，主要依靠計(jì)算算法的強(qiáng)度和效率。

考慮一個(gè)優(yōu)化問題max{Ut（x）：x∈Xhard}，設(shè)定目標(biāo)質(zhì)量級(jí)別α∈（0，1]，有最大目標(biāo)函數(shù)值：

Ut*=max{Ut（x）：x∈Xhard}，解決方案x稱為是α合格的，如果：

Ut（x）≥αUt*并且x∈Xhard

這套α合格的解決方案集合用Xα表示。一旦α給定，Xα所有的解決方案都可以被認(rèn)為是足夠好的。原因是可用的數(shù)據(jù)的不確定性以及整個(gè)問題的不確定性，故Xα中的解決方案之間的差異是微不足道的。

2.2 解決方案的多樣化

為發(fā)布引入多樣化的一套替代解決方案，主要是基于如下假設(shè)：

對(duì)于認(rèn)知復(fù)雜的發(fā)布問題，和結(jié)構(gòu)多樣化的合格解決組合方案相比，單個(gè)解決方案是不太可能反映現(xiàn)實(shí)里求解問題的真實(shí)需要。單個(gè)正式最優(yōu)解也不能改變這一結(jié)論。

在多個(gè)替代解決方案中，為了衡量方案的差異程度，引入相似性概念。兩個(gè)解決方案x，y之間相似性的經(jīng)典定義是兩者（自反，對(duì)稱和傳遞）在解空間中的距離（δ（x，y））。

一旦定義了同組兩個(gè)解決方案之間的距離，解集Y的多樣化可以被定義為所有在Y的解決方案之間的距離的總和。

定義1 設(shè)δ（x，y）是基于X的測(cè)量距離，則Y={x1，x2，…，xm}?X的δ多樣化值是：

D（Y）=∑i

因?yàn)榻^對(duì)測(cè)量值D（Y）很難單獨(dú)評(píng)估，故引入相對(duì)多樣化量。這種歸一化測(cè)量涉及的實(shí)際距離可能是最大距離。從這個(gè)相對(duì)量很容易判斷多樣化獨(dú)立于具體情景的程度。

定義2 設(shè)δ（x，y）是X的距離測(cè)量，Dmax（X，m）是X中任取m元的所有子集之中的最大δ多樣化值，大小為m的集合Y的相對(duì)多樣化量Δ（Y）是：

Δ（Y）=D（Y）/Dmax（X，m）。

找到具有最大多樣化值的子集是一個(gè)極端困難的子集選擇問題。即使對(duì)k=2和n=20的發(fā)布特征小問題，其解空間大小是320。然而，并不一定需要確定的子集來保證最大的多樣化水平，建議選擇一組可控且合格的解決方案X'，其|X'|=M>m，并找到最大多樣化集Y?X'：

Max{D（Y）：Y?X' and |Y|=m}。

2.3 運(yùn)用ELECTRE IS選擇方案

ELECTRE IS是多屬性決策支持大家庭中的一元。其一般原理是基于級(jí)別高于關(guān)系R，R（i，j）意味i強(qiáng)于或等于j。關(guān)系R不需要完備，例如，存在替代方案i和j，無論選擇i或j只存在評(píng)估的標(biāo)準(zhǔn)不同。簡(jiǎn)化的步驟如下：

⑴ 按向量化求得關(guān)系R的數(shù)值：

這一關(guān)系使相同屬性的數(shù)值具有相同的矢量單元，而不同屬性的測(cè)量尺度不相同。

⑵ 規(guī)范矩陣加權(quán)：

V=[ωjrij]

權(quán)重值按比較標(biāo)準(zhǔn)在整體中的相對(duì)重要性而確定。

⑶ 利用權(quán)重實(shí)現(xiàn)從最終的級(jí)別高于關(guān)系中選擇可替代方案。

因?yàn)榧?jí)別高于關(guān)系R（i，j）經(jīng)過了驗(yàn)證，故有足夠多的標(biāo)準(zhǔn)支持這個(gè)結(jié)論。此外，當(dāng)一致性條件成立，就不會(huì)存在標(biāo)準(zhǔn)與結(jié)論R（i，j）有很大抵觸的情況。

3 結(jié)束語

本文對(duì)軟件發(fā)布規(guī)劃中的硬約束進(jìn)行了形式化描述，對(duì)軟約束的形式化進(jìn)行了探討，明確了規(guī)劃目標(biāo)的模型，給出了求解合格方案的基本條件，結(jié)合ELECTRES從合格方案集中找出最優(yōu)方案，為軟件發(fā)布規(guī)劃的科學(xué)化提供了一個(gè)可行的參考模型。但是軟件發(fā)布規(guī)劃還有許多問題有待深入研究，特別是軟約束的形式化問題相對(duì)困難。后繼工作將對(duì)軟件發(fā)布規(guī)劃形式化進(jìn)行細(xì)化，為解決問題提供更多可選擇的策略，開發(fā)有實(shí)用價(jià)值的軟件工具包。

參考文獻(xiàn)：

[1] Carlshamre P. Release planning in Market-Driven Software Product

Development： provoking an Understanding[J]. Requirements Engineering，2002.3：139-151

[2] Mitchell M. Evolutionary computation： an overview[J]. Annual

review，1999.30：293-295

[3] Ziy H， Richardson D J， Kl?sch R. The Uncertainty Principle in

Software Engineering. Technical Report UCI-TR-96-33， University of California， Irvine， August 1996.

[4] Figueira J， Mousseau V， Roy B. ELECTRE methods. In： J.

Figueira， S. Greco， and M. Ehrgott （eds.）， Multiple Criteria Decision Analysis： State of the Art Surveys. Springer， New York，2005：133-162

[5] Rittel H， Webber M. Planning Problems are Wicked Problems， In

Cross N （ed.） Developments in Design Methodology， Wiley， Chichester， UK，1984：135-144

[6] Ruhe G， Ngo-The A. Hybrid Intelligence in Software Release

Planning[J]. International Journal on Hybrid Intelligent Systems，2004.1：99-110

[7] Saliu O， Ruhe G. Supporting Software Release Planning Decisions

for Evolving Systems， Proceedings of the 29th IEEE/NASA Software Engineering Workshop， Greenbelt， MD， USA， April 2005：14-24

[8] Du G， Richter M M， and Ruhe G. An Explanation Oriented

Dialogue Approach and its Application to Wicked Planning Problems[J]. Journal of Computing and Informatics， 2006.25：1001-1027

[9] Greer D， Ruhe G. Software release planning： An evolutionary and

iterative approach[J]. Information and Software Technology，2004.46（4）：243-253

[10] 胡華軍.軟件最優(yōu)發(fā)布時(shí)間決策研究[D].電子科技大學(xué)，2009.

[11] 馮博.軟件安全開發(fā)關(guān)鍵技術(shù)的研究和實(shí)現(xiàn)[D].北京郵電大學(xué)，

2010.