軟件發布規劃的形式化探討

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

關鍵詞： 發布規劃； 不良問題； 不確定性； 標準； 進化； 決策輔助

中圖分類號：TP311.52 文獻標志碼：A 文章編號：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]將軟件發布規劃分類為不良問題。多種不確定性因素使問題很難描述和解決。依據幾個特點可以分類問題是不良的：一是沒有明確的形式化方法表達問題；二是沒有停止規則。

進化是一個逐步適應和多樣化的過程。進化計算是受這個思想的啟發而產生的軟計算方法。它涉及到計算搜索、學習、優化和建模方法等[2]。在決策過程中，決策問題的所有元素都是不斷變化的，因此決策問題的演化契合進化過程。

Saliu O[7]提出了一種基于進化的軟件發布決策支持方案，該模型的不足是對軟件發布中的軟因素考慮不夠全面。Du G[8]研究了解決不良問題的一種交互解析途徑，對解決軟件發布問題有一定的參考價值，但對硬約束的形式化描述力度不夠。文獻[10]提出了一種基于模糊多目標優化的軟件最優發布時間決策模型，決策風險的量化與控制主要關注軟件測試費用的不確定及其對軟件最優發布時間決策的影響，但是它忽視了領域專家的參與。文獻[11]對軟件發布的關鍵因素作了分析與研究，在軟件安全生命周期的基礎上提出了一個改進的適合于中小型企業的軟件安全開發流程，重點關注軟件產品的安全性，也使知識產權得到了保護。因此該模型主要針對的是軟件版權的安全因素。

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

1 軟件發布規劃屬性的描述

關于發布規劃問題的構成，各種文獻有不同的定義。文獻[5]為之描述了十大關鍵因素。一般而言，軟件發布規劃的關鍵屬性有如下種類：①決策變量；②硬約束；③目標規劃；④軟（或隱式）約束。

1.1 決策變量

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

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

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

1.2 硬約束

在任何發布規劃的潛在解決方案中需要按計劃完成的約束稱為硬約束，這些約束隨項目變化而變化。硬約束的目標明確且容易被形式化，硬約束集合用Xhard表示。

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

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

弱優先WP：x（i）?x（j），?（i，j）∈WP?Γ*Γ

強優先SP：x（i）

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

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

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

1.3 軟約束

軟約束很難描述或只需要充分滿足。這些約束條件簡稱Xsoft。可能的軟約束如下：

⑴ 實施風險（試圖平衡不同發布之間的整體風險，或將風險特征推遲到以后的發布）；

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

⑶ 利益相關者的滿意度（試圖為特定的、優先級最高的利益相關者提供服務）；

⑷ 競爭力（試圖提供規劃以支持產品的競爭力）。

這些條件的實現將由領域專家在評估解決方法的后一階段完成。軟約束也可以采用類似硬約束的方式實現形式化，這些方法同樣可以運用到目標規劃中。

1.4 目標規劃

目標規劃難以形式化的原因有三個方面：①規劃的標準是什么；②怎樣處理這些標準；③組成解決方案的是什么。發布規劃的標準是具體項目。通常，目標規劃與創造商業價值最大化、減少研發產品到上市的時間，以及使利益相關者的利益最大化等因素相關。為了體現實際效用，這里用u函數嘗試平衡這些不同的要求，該函數的實際成分取決于問題的具體特點。下面是一些可能的函數形式，這里的u（i，k）表示為獲得整體效用，特征f（i）被分配到發布選項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表示費用，e表示緊迫性，h表示風險程度，g表示不滿程度，v（i，k）表示特征f（i）分配到發布選項k時預期需要的費用，其他函數意義類似。

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

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

發布規劃問題現在可以表述為：

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

規劃x*要達到這樣一個優秀水平：它既能滿足硬約束條件，也能足夠好的滿足軟標準要求。“足夠好”（值9）是主觀的，最終應該由領域專家決定是否可以接受。

2 解決問題的進化方法

在進化求解問題過程中，一個合適的解決方案是由領域專家和基于問題形式化描述后的算法運算出的結果之間相互作用后進化而來，在決策過程中加入軟約束條件和目標。通過產生一組合格的、多樣化的解決方案，應用多屬性決策方法ELECTRE IS，進化方法可以為領域專家給問題描述排序和選擇最終解決方案提供保證。

進化求解問題方法重點關注“針對問題”的形式化過程。但這不可能是一個完美的方式，需要一種機制在這個過程中評價目前的進展和決定何時終止；這兩個問題可以交給涉及這個過程的領域專家來完成。在迭代中，提供多樣化的解決方案組合，以便從中獲得問題是否妥善解決的見解。這種方法假定領域專家自己無法形式化問題，但是能夠評估解決方案是否解決了各種顯性和隱性的問題。

2.1 合格的解決方案

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

⑴ 有針對問題求解的合格意識。建議的（合格）發布規劃應對原（現實世界）問題有意義。為了實現這一目標，主要依靠領域專家的能力來描述問題和評估建議的解決方案。

⑵ 有正確解決問題的合格意識。建議的（合格）發布規劃應對問題的形式化質量有一定程度的保證。為了實現這一目標，主要依靠計算算法的強度和效率。

考慮一個優化問題max{Ut（x）：x∈Xhard}，設定目標質量級別α∈（0，1]，有最大目標函數值：

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

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

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

2.2 解決方案的多樣化

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

對于認知復雜的發布問題，和結構多樣化的合格解決組合方案相比，單個解決方案是不太可能反映現實里求解問題的真實需要。單個正式最優解也不能改變這一結論。

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

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

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

D（Y）=∑i

因為絕對測量值D（Y）很難單獨評估，故引入相對多樣化量。這種歸一化測量涉及的實際距離可能是最大距離。從這個相對量很容易判斷多樣化獨立于具體情景的程度。

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

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

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

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

2.3 運用ELECTRE IS選擇方案

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

⑴ 按向量化求得關系R的數值：

這一關系使相同屬性的數值具有相同的矢量單元，而不同屬性的測量尺度不相同。

⑵ 規范矩陣加權：

V=[ωjrij]

權重值按比較標準在整體中的相對重要性而確定。

⑶ 利用權重實現從最終的級別高于關系中選擇可替代方案。

因為級別高于關系R（i，j）經過了驗證，故有足夠多的標準支持這個結論。此外，當一致性條件成立，就不會存在標準與結論R（i，j）有很大抵觸的情況。

3 結束語

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

參考文獻：

[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] 胡華軍.軟件最優發布時間決策研究[D].電子科技大學，2009.

[11] 馮博.軟件安全開發關鍵技術的研究和實現[D].北京郵電大學，

2010.