多雇主軟件需求優(yōu)選的存檔NSGA-II算法

童志祥， 蘇小紅， 丁 效， 李洪祥， 郭 琦

(哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150001)

?

多雇主軟件需求優(yōu)選的存檔NSGA-II算法

童志祥， 蘇小紅， 丁 效， 李洪祥， 郭 琦

(哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150001)

為解決多雇主的軟件系統(tǒng)需求優(yōu)選問題，使得所有雇主同時達(dá)到最優(yōu)滿意度，提出基于存檔的NSGA-II算法，通過將多雇主需求優(yōu)選問題定義為多目標(biāo)優(yōu)化問題，自動而有效地求解滿足數(shù)量較多的雇主需求優(yōu)化目標(biāo)的解集. 實(shí)驗(yàn)結(jié)果表明：本文提出的需求優(yōu)選方法，能夠在資源和成本的限制下，求解一個令盡可能多雇主滿意的需求集，在雇主平均滿意度、最小滿意度、滿意度方差等評價指標(biāo)上均優(yōu)于基線方法. 基于存檔NSGA-II遺傳算法的需求優(yōu)選方法能夠?yàn)檐浖こ绦枨蠓治鎏峁┛茖W(xué)、合理的優(yōu)選方案.

軟件工程；需求分析；多目標(biāo)優(yōu)化；遺傳算法；NSGA-II

隨著軟件產(chǎn)業(yè)的迅速發(fā)展及軟件系統(tǒng)的日益龐大和復(fù)雜，每一個軟件系統(tǒng)往往會涉及多個雇主甚至大量的雇主，每個雇主對于系統(tǒng)的功能特征、性能特征、UI特征、業(yè)務(wù)流程都有自己的理解，往往會產(chǎn)生大量的軟件需求，但是由于受到開發(fā)成本和開發(fā)時間的限制，每一個軟件系統(tǒng)都無法同時滿足所有雇主的需求[1]. 雇主往往會由于現(xiàn)實(shí)生活中的工作職能不同，對需求集合的優(yōu)化選擇具有不同的期望，對需求的優(yōu)先實(shí)現(xiàn)順序持有不同的意見，這些意見甚至可能是彼此沖突的[2]. 如何從龐大的需求集合中優(yōu)選出一個子集，既要盡可能高地保證不同雇主的滿意度，又要確保有足夠的資源來實(shí)現(xiàn)選定的需求，成為需求工程中一個具有挑戰(zhàn)性的問題.

需求優(yōu)選的過程需要同時兼顧多個目標(biāo)，所以在數(shù)學(xué)上多雇主需求優(yōu)選問題可以形式化為一個多目標(biāo)優(yōu)化問題. 非支配排序遺傳算法II(Non-dominated Sorted Genetic Algorithm-II，NSGA-II)是解決多目標(biāo)優(yōu)選問題的經(jīng)典方法[3]，然而傳統(tǒng)的NSGA-II算法存在著精英解易丟失等問題[4]. 因此，本文在傳統(tǒng)的NSGA-II算法基礎(chǔ)上采用基于存檔的NSGA-II算法，將其應(yīng)用于多雇主的需求優(yōu)選中，通過將每一次迭代過程中產(chǎn)生的非支配解保存至文檔的方式，既保持了傳統(tǒng)NSGA-II算法能夠保留優(yōu)良解集、降低計(jì)算復(fù)雜度的優(yōu)勢，又克服了NSGA-II算法精英解丟失的不足. 在大規(guī)模仿真數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本文方法均優(yōu)于基線方法.

1 多雇主需求優(yōu)選的研究現(xiàn)狀

平衡不同雇主之間的不同期望、平衡系統(tǒng)和雇主需求之間的矛盾，是需求優(yōu)選過程中無法回避的難題，通常需要采用基于搜索的尋優(yōu)算法來探索和解決這類復(fù)雜的優(yōu)選問題. 基于搜索的需求優(yōu)選技術(shù)，就是要將問題塑造成基于搜索的優(yōu)化問題，在適應(yīng)度函數(shù)的指導(dǎo)下，尋找最優(yōu)或近似最優(yōu)的解決方案[5]. 研究人員認(rèn)識到了基于搜索的軟件工程(SBSE)方法在貫穿整個軟件工程領(lǐng)域的各個問題中的巨大應(yīng)用價值，單目標(biāo)和多目標(biāo)優(yōu)化方法被廣泛的應(yīng)用到需求優(yōu)選問題中[6-7].

1.1 多目標(biāo)優(yōu)化問題的定義

多目標(biāo)優(yōu)化問題就是存在多個目標(biāo)需要同時優(yōu)化的問題，由于目標(biāo)間是沒有辦法進(jìn)行比較的，又可能存在沖突，所以可能不存在使所有目標(biāo)函數(shù)同時達(dá)到最優(yōu)的解. 一個解可能對某個目標(biāo)函數(shù)來說是最差的解，但是對另外的目標(biāo)問題卻是最好的解，因此求解多目標(biāo)優(yōu)化問題的最優(yōu)解十分困難，它通常不是一個單一的解，而是一個集合，這個集合定義為非劣最優(yōu)解集，或帕累托(Pareto)最優(yōu)解集[8]. 多目標(biāo)優(yōu)化問題的形式化定義為

式中： f(x)為目標(biāo)函數(shù)，g(x)為約束條件. Pareto最優(yōu)解集中的每個解對所有的目標(biāo)函數(shù)來說是沒有好壞之分的，Pareto最優(yōu)解的特征是：沒有辦法再進(jìn)行改進(jìn)，若改進(jìn)一個目標(biāo)函數(shù)，則必然會減弱另外一個目標(biāo)函數(shù). 因此，Pareto最優(yōu)解集中的每一個解，都是多目標(biāo)優(yōu)化問題的一個非劣解，在這個解集中，根據(jù)不同目標(biāo)的權(quán)重或其他信息進(jìn)行選擇，可以得到滿意解.

Srinivas和Deb在1995年，基于Pareto最優(yōu)概念，將非支配排序遺傳算法NSGA運(yùn)用于多目標(biāo)優(yōu)化[9]，在基本遺傳算法的基礎(chǔ)上，對選擇再生方法進(jìn)行改進(jìn)，將每個個體按照它們的支配與非支配關(guān)系進(jìn)行分層，再做選擇操作，從而使得算法在多目標(biāo)優(yōu)化方面得到非常滿意的結(jié)果.

1.2 基于多目標(biāo)優(yōu)化的需求優(yōu)選技術(shù)

隨著系統(tǒng)復(fù)雜度的提高，單個目標(biāo)的優(yōu)化不能充分滿足所有目標(biāo)的利益，無法滿足多個雇主的期望. Finkelstein等[10]的研究表明多目標(biāo)優(yōu)化技術(shù)可應(yīng)用于解決需求分配的公平性，他們將不同定義的公平性作為不同的優(yōu)化目標(biāo)，利用多目標(biāo)優(yōu)化技術(shù)來同時優(yōu)化不同的公平性目標(biāo). Zhang等[11]同時考慮最小化供應(yīng)商的成本和最大化雇主滿意度的雙重目標(biāo). Saliu等[12]同時考慮了實(shí)施和需求這兩個層面的優(yōu)化目標(biāo)，依據(jù)商業(yè)需求滿足和實(shí)施效益兩個角度，來優(yōu)化軟件的發(fā)布計(jì)劃. Zhang等[13]2007年首次將NRP問題概括為多目標(biāo)NRP(Multi-Object Next Release Problem, MONRP)問題，提出了基于多目標(biāo)優(yōu)化的NRP問題模型，將“成本”限制和“價值”追求作為兩個獨(dú)立的目標(biāo)進(jìn)行優(yōu)化，來平衡和優(yōu)化價值和成本之間的矛盾. Zhang等[11]提出將每個雇主的滿意度作為單獨(dú)的優(yōu)化目標(biāo)，將基于非支配遺傳算法(NSGA)的改進(jìn)算法NSGA-II算法應(yīng)用到了需求優(yōu)選的問題中. 此外，一些多目標(biāo)進(jìn)化算法及雜合算法也被應(yīng)用來解決MONRP問題[14-17].

盡管現(xiàn)有的基于搜索的需求優(yōu)選方法為優(yōu)選問題提供了很好的解決方案，能夠自動搜索最優(yōu)或近似最優(yōu)的需求集合來平衡相互競爭的多個雇主，然而基于多目標(biāo)優(yōu)化的需求優(yōu)選方法對無約束或簡單約束的優(yōu)化問題可以找到很好的解決方案，但當(dāng)解決高約束問題，或者優(yōu)化目標(biāo)急劇增多時，會導(dǎo)致效率大幅降低，無法達(dá)到理想的優(yōu)選效果. 在所有應(yīng)用于需求優(yōu)選的SBSE搜索方法中，NSGA-II算法是最常用的方法[18]. 一些研究人員認(rèn)為NSGA-II是求解大規(guī)模復(fù)雜的多目標(biāo)優(yōu)化問題的最快、最有效的算法[13，19]. 然而傳統(tǒng)的NSGA-II算法存在著精英解易丟失等問題[4]. 本文將在前人研究的基礎(chǔ)之上，提出基于存檔NSGA-II算法的多雇主需求優(yōu)選方法. 針對以往多目標(biāo)優(yōu)化方法計(jì)算復(fù)雜度高、搜索效率低的弊病，通過引入NSGA-II算法降低了多雇主優(yōu)化目標(biāo)帶來的高計(jì)算復(fù)雜度，并通過文檔記錄每一次迭代的非支配性解集的方式，大幅度減少精英解集在迭代過程中的流失，取得了較好的需求優(yōu)選效果.

2 基于存檔NSGA-II算法的多雇主需求優(yōu)選方法

2.1 多雇主需求優(yōu)選問題的形式化描述

令S={S1,S2,…,SM}表示包含M個雇主的集合，R={R1,R2,…,Rn}表示包含n個需求的集合，C={cost1,cost2,…,costn}表示實(shí)現(xiàn)每個需求所需要的代價，costi為實(shí)現(xiàn)Ri所需要的代價. 雇主Si對需求Ri的打分記為v(Ri,Si)，v(Ri,Si)=0表示雇主Si不期望實(shí)現(xiàn)需求Ri，v(Ri,Si)>0表示雇主Si期望實(shí)現(xiàn)需求Ri，v的取值越大，表示雇主越希望實(shí)現(xiàn)該需求. 定義決策向量x=[x1,x2,…,xn]，xi∈{0，1}表示雇主對于集合R中需求的選取情況，xi=1表示需求Ri被選取，xi=0表示需求Ri未被選取.

M個雇主對應(yīng)了M個滿意度，其中第j個雇主對應(yīng)的滿意度計(jì)算函數(shù)fj(x)為

式中：xi表示第j個雇主對第i個需求選擇的決策分量，v(Ri,Sj)表示第j個雇主對第i個需求的打分. 對于任一決策變量x，實(shí)現(xiàn)需求的代價函數(shù)為

多雇主的需求優(yōu)選問題可以看成一個多目標(biāo)優(yōu)化問題，將雇主的滿意度f1(x),f2(x),…,fM(x)作為優(yōu)化目標(biāo)，需求的實(shí)現(xiàn)代價cost(x)作為約束條件，B為代價閾值，即所能提供的最大需求實(shí)現(xiàn)代價，優(yōu)化的目的就是在代價不超過B的基礎(chǔ)上，最大限度地使M個目標(biāo)函數(shù)達(dá)到最優(yōu)，求解出盡可能使所有雇主滿意度最大的需求決策向量x，即

2.2 基于存檔NSGA-II遺傳算法的需求優(yōu)選方法

遺傳算法將要解決的問題模擬成一個生物進(jìn)化的過程，通過復(fù)制、交叉、突變等操作產(chǎn)生下一代的解，并逐步淘汰掉適應(yīng)度函數(shù)值低的解，增加適應(yīng)度函數(shù)值高的解，進(jìn)化多代后就很有可能會進(jìn)化出適應(yīng)度函數(shù)值很高的個體. 但在進(jìn)化的過程中，由于交叉和突變操作的存在，精英解可能會丟失. NSGA-II算法將最后一次迭代產(chǎn)生的種群作為非支配解集，雖然在進(jìn)化過程中采用了精英策略，但還是會導(dǎo)致精英解的丟失. 針對NSGA-II算法可能會導(dǎo)致精英解丟失的問題，提出了基于存檔的NSGA-II算法，通過將每一次迭代過程中產(chǎn)生的非支配解保存至文檔，來達(dá)到保留精英解的目的. 基于存檔的NSGA-II算法原理圖如圖1所示.

算法的具體執(zhí)行步驟如下(見算法1)：

1)獲取參數(shù)信息，包括種群規(guī)模N、迭代次數(shù)T、交叉率、變異率，然后根據(jù)種群規(guī)模，隨機(jī)生成一定數(shù)量的個體，即決策向量x，設(shè)初始種群為P0.

2)計(jì)算種群中個體的代價，即根據(jù)代價計(jì)算函數(shù)cost(x)計(jì)算個體的代價，并判斷是否超過代價閾值B，若超過閾值，則隨機(jī)生成新的個體替換該個體，若不超過閾值，則繼續(xù)執(zhí)行.

3)根據(jù)雇主對需求的打分，計(jì)算種群中所有個體對不同雇主的滿意度，即傳統(tǒng)遺傳算法中的適應(yīng)度值.

4)根據(jù)每個個體的適應(yīng)度值，對個體進(jìn)行快速非支配排序并根據(jù)個體間的支配關(guān)系進(jìn)行分層. 計(jì)算支配關(guān)系算法如算法2所示，根據(jù)個體間的支配關(guān)系，令np表示在種群中支配個體p的所有個體的數(shù)量，Sp表示被個體p支配的所有個體的集合. 根據(jù)個體間支配關(guān)系進(jìn)行分層時首先將np=0的個體加入第一層F1，對Sp集合中包含的所有個體q，將其nq的值減1，然后在剩余個體中取nq為0的個體加入第二層F2，直到所有個體都分層為止(詳見算法3).

5)將進(jìn)行快速非支配排序后得到的非支配解寫入文檔中.

6)從種群中選擇N/2個個體得到FP，選擇操作執(zhí)行過程如圖2所示.

圖1 基于存檔的NSGA-II算法原理圖

圖2 選擇操作執(zhí)行過程

從第一層F1開始選擇個體，若第一層數(shù)目小于N/2則繼續(xù)選擇第二層、第三層，直到個體數(shù)目到達(dá)N/2為止，若當(dāng)前層中的個體數(shù)加上已選擇的個體數(shù)之和大于N/2，則需要對當(dāng)前層次中的個體進(jìn)行擁擠密度排序，優(yōu)先選擇擁擠密度較小的個體，這樣有利于保證種群的多樣性. 擁擠密度即在種群中給定點(diǎn)的周圍個體的密度. 對于包含兩個目標(biāo)的多目標(biāo)優(yōu)化問題，其擁擠密度示意圖如圖3所示. 個體i的擁擠密度通過計(jì)算其與相鄰的個體i-1與個體i+1的距離得到，擁擠距離越大，則擁擠密度越小.

7)交叉. 由于個體采用0，1編碼串的方式表示，每個0或1都對應(yīng)了一個需求的選取情況. 根據(jù)初始時設(shè)置的交叉率，計(jì)算得出需要進(jìn)行交叉的個體數(shù)量，每次交叉從FP中隨機(jī)選擇兩個個體P1、P2，根據(jù)編碼長度，產(chǎn)生兩個隨機(jī)位置作為交叉起點(diǎn)與終點(diǎn)，將起點(diǎn)與終點(diǎn)間的編碼進(jìn)行交換，形成兩個新的個體C1和C2，交叉操作完成后得到種群FQ，交叉操作示意圖如圖4所示.

圖3 包含兩個目標(biāo)的多目標(biāo)優(yōu)化問題擁擠密度示意圖

圖4 對個體進(jìn)行交叉操作示意圖

8)變異. 由于個體采用二進(jìn)制編碼即0，1串來表示需求的選取情況，因此根據(jù)變異率，從種群FQ中隨機(jī)選擇一定數(shù)量的個體，在編碼長度范圍內(nèi)，隨機(jī)選擇一個位置，將此處的編碼取反，即0變?yōu)?，1變?yōu)?，從而得到新的種群FQ.

9)將復(fù)制得到的來自父代的FP與由交叉突變操作新產(chǎn)生的FQ合并形成包含N個個體的子代種群Pt+1，重新執(zhí)行步驟2)至步驟8)，直到迭代次數(shù)超過閾值，迭代終止.

10)對文檔中的個體按照步驟4)進(jìn)行非支配排序與分層，僅保留分層結(jié)果的第一層，即不受任何其他個體支配的個體的集合，這個集合即為通過基于存檔NSGA-II算法得到的最優(yōu)解集.

算法1 基于歸檔的NSGA-II算法主循環(huán)

輸入：種群規(guī)模N、迭代次數(shù)T、代價閾值B、交叉率、變異率、初始種群P0

輸出：需求優(yōu)選的解集

while t<=T do

for 種群Pt中的每一個個體x do

計(jì)算個體的代價cost(x)

if cost(x)>B then

隨機(jī)生成新個體，替換個體x

end

end

計(jì)算種群Pt中每個個體的適應(yīng)度值

fast-non-dominated-sort(Pt) ，將Pt中的非支配解以追加方式寫入文檔中

對種群Pt進(jìn)行選擇操作得到FP，|FP|=N/2

對FP進(jìn)行交叉和變異操作產(chǎn)生新的種群FQ

Let Pt+1= FP∪FQ

Let t= t+1

end

對文檔中的所有個體調(diào)用fast-non-dominated-sort，進(jìn)行非支配排序與分層，僅保留分層結(jié)果的第一層即所有非支配解作為最優(yōu)解集

算法2 計(jì)算支配關(guān)系(dominate)

輸入：決策向量p，q

輸出：p是否支配q

for 對于每個目標(biāo)函數(shù)fi(x) do

if fi(p) < fi(q) then

返回p不支配q

end

end

返回p支配q

算法3 快速非支配排序(fast-non-dominated-sort)

輸入：種群Pt

輸出：得到非支配排序與分層

for種群Pt中的每一個個體p do

Set Sp=?表示個體p所支配的個體集合

Set np=0 表示支配個體p的所有個體的數(shù)目

for種群Pt中的每一個個體q do

if個體p dominate個體q then

Let Sp= Sp∪q

end

else if個體q dominate 個體p then

Let np= np+1

end

end

if np==0 then

Let prank=1

Let F1= F1∪p

end

end

Set i=1

while Fi≠? do

Set Q=?

for Fi中的每一個個體p do

for Sp中的每一個個體q then

Let nq= nq-1

if nq==0 then

Let qrank=i+1

Let Q= Q ∪q

end

end

end

Let i=i+1

Let Fi= Q

end

3 實(shí) 驗(yàn)

3.1 實(shí)驗(yàn)數(shù)據(jù)

為了避免實(shí)驗(yàn)數(shù)據(jù)的主觀性因素，開發(fā)了模擬產(chǎn)生雇主需求數(shù)據(jù)的程序，該程序能夠生成指定組數(shù)的模擬需求數(shù)據(jù)，每組隨機(jī)生成一定數(shù)量的雇主和需求，并為每個需求隨機(jī)分配權(quán)值和代價. 為了保證實(shí)驗(yàn)結(jié)果具有統(tǒng)計(jì)學(xué)上的穩(wěn)定性，本文隨機(jī)產(chǎn)生了50組模擬需求數(shù)據(jù)對算法進(jìn)行測試與評估，每組數(shù)據(jù)隨機(jī)生成5～10個雇主，每個雇主隨機(jī)產(chǎn)生5～50個需求，每個雇主的各需求權(quán)重之和為100，每個需求的代價取值范圍為1～40人/天，控制輸入系統(tǒng)開發(fā)總代價少于隨機(jī)需求總代價以模擬產(chǎn)生雇主沖突. 單個雇主模擬數(shù)據(jù)如表1所示.

表1 單個雇主模擬數(shù)據(jù)樣例

注: 該雇主選擇的需求總數(shù)為17，需求總代價為126，滿意度為86.2. 3.2 需求優(yōu)選結(jié)果評價方法

3.2.1 需求優(yōu)選評價指標(biāo)

為了能夠說明基于文檔NSGA-II算法優(yōu)選的需求能夠平衡雇主沖突，使得雇主總體滿意度較高，且沒有特別不滿意的現(xiàn)象，通過平均滿意度、最小滿意度、滿意度方差3個指標(biāo)來衡量本文提出的優(yōu)選算法的有效性.

3.2.1.1 平均滿意度

統(tǒng)計(jì)平均數(shù)是用于反映現(xiàn)象總體的一般水平，或分布的集中趨勢. 平均滿意度能夠反映出優(yōu)選結(jié)果的一般水平，平均滿意度越大，優(yōu)選效果越優(yōu)異. 平均滿意度的計(jì)算方法為

式中fi表示對于當(dāng)前選擇的需求集第i個雇主的滿意度值.

3.2.1.2 最小滿意度

最小滿意度反映了系統(tǒng)中雇主滿意度最差情況，最小值越小，存在特別不滿意的雇主情況可能性越大. 需求優(yōu)選方法需要考慮全體雇主的滿意度情況，若一個需求優(yōu)選結(jié)果的最小滿意度很小，說明該結(jié)果使得某一個或某一些雇主很不滿意，這種優(yōu)選結(jié)果不能被接受成為最終的需求. 最小滿意度計(jì)算方法為

式中fi表示對于當(dāng)前選擇的需求集第i個雇主的滿意度值.

3.2.1.3 滿意度方差

方差是各個數(shù)據(jù)與其算術(shù)平均數(shù)的離差平方和的平均數(shù)，它能準(zhǔn)確地反映出數(shù)據(jù)的離散程度. 為了能夠反映經(jīng)過模型優(yōu)選系統(tǒng)需求后系統(tǒng)中雇主滿意度處在較為集中的水平，本文將使用數(shù)據(jù)分析結(jié)果中滿意度方差衡量系統(tǒng)的優(yōu)選效果. 滿意度方差計(jì)算方法為

式中：fi表示對于當(dāng)前選擇的需求集第i個雇主的滿意度值，A表示所有M個雇主的平均滿意度.

3.2.2 基線

采用了基于需求實(shí)現(xiàn)難易程度的優(yōu)選方法(簡稱開銷優(yōu)選)、基于需求重要程度的優(yōu)選方法(簡稱權(quán)重優(yōu)選)、基于NSGA-II算法的優(yōu)選方法作為基線方法，與本文提出的基于存檔NSGA-II算法進(jìn)行了對比試驗(yàn)評價.

3.2.2.1 基于需求難易程度的優(yōu)選方法

基于需求難易程度的優(yōu)選方法是指先不考慮系統(tǒng)需求的雇主區(qū)別，將所有雇主提出的需求統(tǒng)一按照需求實(shí)現(xiàn)開銷順序排序，選取從小到大累加開銷和不大于開發(fā)預(yù)算的需求集合，然后求解各個雇主的滿意度，簡稱為開銷優(yōu)選.

3.2.2.2 基于需求重要程度的優(yōu)選方法

基于需求重要程度的優(yōu)選方法是指先不考慮系統(tǒng)需求的雇主區(qū)別，將所有雇主提出的需求統(tǒng)一按照雇主標(biāo)注的需求權(quán)重順序排序，按照權(quán)重從大到小順序選取需求集合直到需求累加時間和大于開發(fā)周期，然后根據(jù)選出的需求集合求解各個雇主的滿意度，簡稱為權(quán)重優(yōu)選.

3.2.2.3 基于NSGA-II算法的優(yōu)選方法

基于NSGA-II算法的優(yōu)選方法是采用傳統(tǒng)NSGA-II算法來解決多雇主多需求問題[14]，參照基于存檔NSGA-II算法實(shí)現(xiàn)了基于NSGA-II算法的需求優(yōu)選方法. 與該算法的對比試驗(yàn)可以說明本文算法對傳統(tǒng)NSGA-II算法改進(jìn)的有效性.

3.3 實(shí)驗(yàn)結(jié)果及分析

3.3.1 平均滿意度實(shí)驗(yàn)結(jié)果

平均滿意度實(shí)驗(yàn)結(jié)果如圖5所示，實(shí)驗(yàn)結(jié)果表明，基于存檔NSGA-II算法的需求優(yōu)選方法在50組隨機(jī)需求數(shù)據(jù)中提出的需求優(yōu)選方案表現(xiàn)優(yōu)異，在絕大多數(shù)數(shù)據(jù)中，所選需求方案的平均滿意度均為最佳，僅在少數(shù)測試集上略差于基線優(yōu)選方法. 因?yàn)榛陔y易程度優(yōu)選方法與基于重要程度優(yōu)選方法都僅考慮了需求實(shí)現(xiàn)的開支或雇主對需求的權(quán)重，而本文提出的方法通過對各個雇主的滿意度進(jìn)行多目標(biāo)優(yōu)化，同時考慮了需求實(shí)現(xiàn)的開支與權(quán)重，從而能夠得到使得雇主更加滿意的結(jié)果.

基于傳統(tǒng)NSGA-II算法的需求優(yōu)選方法在28組需求數(shù)據(jù)上與本文提出方法的結(jié)果相同，在22組需求數(shù)據(jù)上差于本文提出的方法. 這是由于傳統(tǒng)NSGA-II算法沒有在每次迭代過程中保留精英解，在迭代過程中，精英解可能丟失，從而導(dǎo)致最終的優(yōu)化結(jié)果并非最優(yōu). 本文提出的基于存檔NSGA-II算法則通過每次迭代將精英解保留至文檔避免了精英解丟失的問題.

3.3.2 最小滿意度實(shí)驗(yàn)結(jié)果

最小滿意度實(shí)驗(yàn)結(jié)果如圖6所示，實(shí)驗(yàn)結(jié)果表明，在多數(shù)隨機(jī)產(chǎn)生的需求數(shù)據(jù)上，基于存檔NSGA-II算法的需求優(yōu)選方法的最小滿意度均高于基線優(yōu)選方法. 但在部分需求數(shù)據(jù)上，本文提出的需求優(yōu)選方法劣于基線方法. 其中基于NSGA-II算法的需求優(yōu)選方法與本文提出方法表現(xiàn)相近，但在22組數(shù)據(jù)上差于本文提出的方法. 這主要是因?yàn)楸疚奶岢龅幕诖鏅nNSGA-II算法能夠保留每次迭代過程的精英解，克服了傳統(tǒng)NSGA-II算法法精英解丟失的缺點(diǎn).

圖5 平均滿意度實(shí)驗(yàn)結(jié)果

3.3.3 滿意度方差實(shí)驗(yàn)結(jié)果

滿意度方差實(shí)驗(yàn)結(jié)果如圖7所示，實(shí)驗(yàn)結(jié)果表明，在44個組需求數(shù)據(jù)集上，基于存檔NSGA-II算法的需求優(yōu)選方法的結(jié)果滿意度方差小與基于重要程度和基于難易程度兩種優(yōu)選方法，在其余6組需求數(shù)據(jù)集上滿意度方差略大于這兩種基線方法. 在20組需求數(shù)據(jù)集上，本文提出的優(yōu)選方法優(yōu)于基于傳統(tǒng)NSGA-II算法的優(yōu)選方法，在其余組需求數(shù)據(jù)上不差于NSGA-II方法. 這主要是因?yàn)楸疚奶岢龅幕诖鏅nNSGA-II算法的需求優(yōu)選方法以每個雇主的滿意度作為優(yōu)化目標(biāo)，優(yōu)化的結(jié)果使每個雇主的滿意度都盡可能達(dá)到最優(yōu)，從而減少了雇主的滿意度方差；基于存檔NSGA-II算法作為NSGA-II算法的改進(jìn)，在部分需求數(shù)據(jù)上，新方法由于避免了精英解丟失的情況，所以滿意度方差小于傳統(tǒng)方法. 從實(shí)驗(yàn)結(jié)果可以得出結(jié)論，使用基于存檔NSGA-II算法的需求優(yōu)選方法選擇出的需求結(jié)果使得雇主滿意度更加集中.

綜合上述實(shí)驗(yàn)結(jié)果，基于存檔NSGA-II算法的需求優(yōu)選方法在平均滿意度、最小滿意度、滿意度方差這3種評價指標(biāo)上均優(yōu)于開銷優(yōu)選方法和權(quán)重優(yōu)選方法，這說明提出的基于存檔NSGA-II算法的需求優(yōu)選方法能夠在有效提高雇主整體滿意度的同時，使雇主滿意度更加集中.

圖6 最小滿意度結(jié)果

圖7 滿意度方差結(jié)果

3.3.4 與NSGA-II算法的比較結(jié)果

從實(shí)驗(yàn)結(jié)果看，基于存檔的NSGA-II方法在全部的測試數(shù)據(jù)集上的表現(xiàn)均不差于NSGA-II算法，在部分測試數(shù)據(jù)集上的表現(xiàn)優(yōu)于NSGA-II算法. 因?yàn)榛诖鏅n的NSGAⅡ算法與NSGA-II算法的主要不同在于保留每一次迭代的非支配解，優(yōu)于NSGA-II的那部分測試數(shù)據(jù)組即可說明提出的方法能夠保留NSGA-II在迭代過程中丟失的精英解. 圖8給出了在50組測試集上，被 NSGA-II算法流失卻被基于存檔NSGA-II算法獲得的精英解個數(shù). 從圖8可以看出，基于存檔的NSGA-II算法確實(shí)能夠保留NSGA-II在迭代過程中丟失的精英解.

圖8 精英解保留結(jié)果

4 結(jié) 論

通過對軟件工程中存在的多雇主需求優(yōu)選問題進(jìn)行了建模分析，提出了基于存檔NSGA-II算法的需求優(yōu)選方法，實(shí)驗(yàn)結(jié)果表明，本文提出的方法能在滿足雇主資源及需求實(shí)現(xiàn)成本的限制下，得到盡量使所有雇主滿意的需求選擇方案，為軟件工程需求分析提供了客觀、科學(xué)、合理的優(yōu)選方案.

本文所闡述的方法是建立在雇主的需求之間不存在依賴性和相似性的前提下，這與實(shí)際情況相比還很理想化，如何提出一種更普遍并且有效的需求優(yōu)選方法還有待于更深層次的研究.

[1]陳建明. 軟件需求工程及其發(fā)展[J]. 裝甲兵工程學(xué)院學(xué)報,2003, 17(3):66-69.

CHEN Jianming. Review of software requirement engineering[J]. Journal of Armored Force Engineering Institute,2003,17(3):66-69.

[2]王達(dá). 需求工程的探討[J]. 軟件,2011,32(5):67-70.

WANG Da. Discussion of requirements engineering[J]. Software,2011,32(5):67-70.

[3] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.

[4]趙君莉,楊善學(xué),王宇平. 改進(jìn)的非支配排序遺傳算法INSGA-Ⅱ[J].西安科技大學(xué)學(xué)報,2006,26(4):529-531.

ZHAO Junli, YANG Shanxue, WANG Yuping. An improved non-dominated sorting genetic algorithm INSGA-II[J]. Journal of Xi’an University of Science and Technology, 2006,26(4):529-531.

[5] ZHANG Y. Multi-objective search-based requirements selection and optimization, department of computer science[D] London: King's College, 2010.

[6] HARMAN M, MANSOURI S A, ZHANG Y. Search-based software engineering: trends, techniques and applications[J]. ACM Computing Surveys, 2012, 45(1): 11.

[7] HAMAN M, MANSOURI S A, ZHANG Yuanyuan. Search based software engineering: trends, techniques and applications[J]. ACM Computing Surveys, 2012,45(1):17-20.

[8] SRINIVAS N, DEB K. Muiltiobjective optimization using nondominated sorting in genetic algorithms[J]. Evolutionary computation, 1994, 2(3): 221-248.

[9] SRINIVAS N，DEB K. Multi-objective function optimization using nondominated sorting genetic algorithms[J]，Evolutionary Computation，1995,2(3):221-248.

[10]ZHANG Y, HARMAN M, FINKELSTEIN A, et al. Comparing the performance of metaheuristics for the analysis of multi-stakeholder tradeoffs in requirements optimisation[J]. Information and software technology, 2011, 53(7): 761-773.

[11]DURILLO J, ZHANG Y, ALBA E, et al. A study of the multi-objective next release problem[C]//1st International Symposium on Search Based Software Engineering. Windsor: IEEE, 2009: 49-58.

[12]SALIU M, RUHE G. Bi-objective release planning for evolving software systems[C]//Proceedings of the 6thJoint Meeting of the European Software Engineering Conference And the ACM SIGSOFT Symposium on the Foundations Of Software Engineering. Dubrovnik: ACM, 2007: 105-114.

[13]ZHANG Y, HARMAN M, MANSOURI S. The multi-objective next release problem[C]//Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation. ACM, 2007: 1129-1137.

[14]CHARAN KUMARI A, SRINIVAS K, GUPTA MP. Software requirements selection using quantum-inspired elitist multi-objective evolutionary algorithm[C]/Proceedings of the IEEE-International Conference on Advances in Engineering, Science and Management.IEEE,2012):782-787.

[15]CAI X, LI Y, FAN Z, et al. An external archive guided multiobjective evolutionary algorithm based on decomposition for combinatorial optimization[J]. IEEE Transactions on Evolutionary Computation, 2015,19(4):508-532.

[16]PITANGUEIRA A M, TONELLA P, SUSI A, et al. Risk-aware multi-stakeholder next release planning using multi-objective optimization[C]//International Working Conference on Requirements Engineering: Foundation for Software Quality. Springer, 2016: 3-18.

[17]KUMARI A C, SRINIVAS K. Comparing the performance of quantum-inspired evolutionary algorithms for the solution of software requirements selection problem[J]. Information and Software Technology,2016, 76:31-64.

[18]PITANGUEIRA A M, MACIEL R S P, BARROS M. Software requirements selection and prioritization using SBSE approaches: A systematic review and mapping of the literature[J]. Journal of Systems and Software,2014,103:267-280.

[19]DURILLO J J, ZHANG Y, ALBA E, et al. A study of the bi-objective next release problem[J]. Empirical Software Engineering, 2011,16(1):29-60.

(編輯 王小唯 苗秀芝)

Multi-stakeholder requirements optimization based on archived NSGA-II algorithm

TONG Zhixiang， SU Xiaohong， DING Xiao， LI Hongxiang， GUO Qi

(School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China)

Requirement prioritization in complex software system often involves multiple stakeholders and needs to satisfy several different stakeholders’ requirements. In this paper, we define multi-stakeholder tradeoffs in requirements optimization as a multi-objective optimization problem and introduce an archived Non-Dominated Sorted Genetic Algorithm-II (NSGA-II) to the automated analysis of requirements assignments. The results show that the proposed method can generate a set of optimal requirements satisfying multiple stakeholders with the constraints of the resources and the cost. Comparing with the baseline methods, our approach shows better performance on all evaluation metrics, such as average, minimum satisfaction and variance in satisfaction. In summary, the archived NSGA-II algorithm could provide a scientific and reasonable result for the software requirements engineering.

software engineering; requirement analysis; multi-objective optimization; genetic algorithm; NSGA-II

10.11918/j.issn.0367-6234.2016.11.004

2016-01-16

國家自然科學(xué)基金 (61173021, 61672191)

童志祥(1979—)，男，博士研究生; 蘇小紅(1966—)，女，教授，博士生導(dǎo)師

蘇小紅，sxh@hit.edu.cn

TP311.5

A

0367-6234(2016)11-0020-08