多雇主軟件需求優(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)選問(wèn)題，使得所有雇主同時(shí)達(dá)到最優(yōu)滿意度，提出基于存檔的NSGA-II算法，通過(guò)將多雇主需求優(yōu)選問(wèn)題定義為多目標(biāo)優(yōu)化問(wèn)題，自動(dòng)而有效地求解滿足數(shù)量較多的雇主需求優(yōu)化目標(biāo)的解集. 實(shí)驗(yàn)結(jié)果表明：本文提出的需求優(yōu)選方法，能夠在資源和成本的限制下，求解一個(gè)令盡可能多雇主滿意的需求集，在雇主平均滿意度、最小滿意度、滿意度方差等評(píng)價(jià)指標(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ù)雜，每一個(gè)軟件系統(tǒng)往往會(huì)涉及多個(gè)雇主甚至大量的雇主，每個(gè)雇主對(duì)于系統(tǒng)的功能特征、性能特征、UI特征、業(yè)務(wù)流程都有自己的理解，往往會(huì)產(chǎn)生大量的軟件需求，但是由于受到開發(fā)成本和開發(fā)時(shí)間的限制，每一個(gè)軟件系統(tǒng)都無(wú)法同時(shí)滿足所有雇主的需求[1]. 雇主往往會(huì)由于現(xiàn)實(shí)生活中的工作職能不同，對(duì)需求集合的優(yōu)化選擇具有不同的期望，對(duì)需求的優(yōu)先實(shí)現(xiàn)順序持有不同的意見(jiàn)，這些意見(jiàn)甚至可能是彼此沖突的[2]. 如何從龐大的需求集合中優(yōu)選出一個(gè)子集，既要盡可能高地保證不同雇主的滿意度，又要確保有足夠的資源來(lái)實(shí)現(xiàn)選定的需求，成為需求工程中一個(gè)具有挑戰(zhàn)性的問(wèn)題.

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

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

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

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

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

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

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

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

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

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

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

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

令S={S1,S2,…,SM}表示包含M個(gè)雇主的集合，R={R1,R2,…,Rn}表示包含n個(gè)需求的集合，C={cost1,cost2,…,costn}表示實(shí)現(xiàn)每個(gè)需求所需要的代價(jià)，costi為實(shí)現(xiàn)Ri所需要的代價(jià). 雇主Si對(duì)需求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}表示雇主對(duì)于集合R中需求的選取情況，xi=1表示需求Ri被選取，xi=0表示需求Ri未被選取.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

while t<=T do

for 種群Pt中的每一個(gè)個(gè)體x do

計(jì)算個(gè)體的代價(jià)cost(x)

if cost(x)>B then

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

end

end

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

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

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

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

Let Pt+1= FP∪FQ

Let t= t+1

end

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

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

輸入：決策向量p，q

輸出：p是否支配q

for 對(duì)于每個(gè)目標(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中的每一個(gè)個(gè)體p do

Set Sp=?表示個(gè)體p所支配的個(gè)體集合

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

for種群Pt中的每一個(gè)個(gè)體q do

if個(gè)體p dominate個(gè)體q then

Let Sp= Sp∪q

end

else if個(gè)體q dominate 個(gè)體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中的每一個(gè)個(gè)體p do

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

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

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

3.2.1 需求優(yōu)選評(píng)價(jià)指標(biāo)

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

3.2.1.1 平均滿意度

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

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

3.2.1.2 最小滿意度

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

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

3.2.1.3 滿意度方差

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

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

3.2.2 基線

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

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

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

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

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

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

基于NSGA-II算法的優(yōu)選方法是采用傳統(tǒng)NSGA-II算法來(lái)解決多雇主多需求問(wèn)題[14]，參照基于存檔NSGA-II算法實(shí)現(xiàn)了基于NSGA-II算法的需求優(yōu)選方法. 與該算法的對(duì)比試驗(yàn)可以說(shuō)明本文算法對(duì)傳統(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ù)測(cè)試集上略差于基線優(yōu)選方法. 因?yàn)榛陔y易程度優(yōu)選方法與基于重要程度優(yōu)選方法都僅考慮了需求實(shí)現(xiàn)的開支或雇主對(duì)需求的權(quán)重，而本文提出的方法通過(guò)對(duì)各個(gè)雇主的滿意度進(jìn)行多目標(biāo)優(yōu)化，同時(shí)考慮了需求實(shí)現(xiàn)的開支與權(quán)重，從而能夠得到使得雇主更加滿意的結(jié)果.

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

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算法能夠保留每次迭代過(guò)程的精英解，克服了傳統(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個(gè)組需求數(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)選方法以每個(gè)雇主的滿意度作為優(yōu)化目標(biāo)，優(yōu)化的結(jié)果使每個(gè)雇主的滿意度都盡可能達(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種評(píng)價(jià)指標(biāo)上均優(yōu)于開銷優(yōu)選方法和權(quán)重優(yōu)選方法，這說(shuō)明提出的基于存檔NSGA-II算法的需求優(yōu)選方法能夠在有效提高雇主整體滿意度的同時(shí)，使雇主滿意度更加集中.

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

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

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

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

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

4 結(jié) 論

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

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

[1]陳建明. 軟件需求工程及其發(fā)展[J]. 裝甲兵工程學(xué)院學(xué)報(bào),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é)報(bào),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

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

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

蘇小紅，sxh@hit.edu.cn

TP311.5

A

0367-6234(2016)11-0020-08