基于遺傳-蟻群算法的IFPUG的復(fù)雜度權(quán)值修正?

黃治凱 張波雷

（空軍預(yù)警學(xué)院 武漢 430019）

基于遺傳-蟻群算法的IFPUG的復(fù)雜度權(quán)值修正?

黃治凱 張波雷

（空軍預(yù)警學(xué)院 武漢 430019）

論文針對(duì)FPA方法在軟件項(xiàng)目估算過(guò)程中存在的主觀(guān)性和局限性的問(wèn)題，提出了一種基于遺傳-蟻群算法的復(fù)雜度權(quán)值修正方法，該算法不僅繼承了遺傳算法搜索效率高、魯棒性強(qiáng)的特點(diǎn)，同時(shí)也吸納了蟻群算法正反饋性和并行性的優(yōu)點(diǎn)，論文將兩種算法結(jié)合使用，不僅估算精度高，而且運(yùn)行速度快，通過(guò)仿真驗(yàn)證了論文算法的有效性。

功能點(diǎn)分析；遺傳算法；蟻群算法

1 引言

IFPUG［1，4］功能點(diǎn)方法是由國(guó)際功能點(diǎn)用戶(hù)組（International Function Point Users Group）在 Albre?cht提出的功能點(diǎn)方法的基礎(chǔ)上進(jìn)行改進(jìn)和維護(hù)的，同時(shí)也是目前使用最為廣泛的功能點(diǎn)分析方法，已然成為功能點(diǎn)分析方法的代名詞。

FPA是在軟件的基礎(chǔ)上，站在用戶(hù)和功能的角度來(lái)衡量程序的大小，而對(duì)于設(shè)計(jì)語(yǔ)言，無(wú)論是傳統(tǒng)的還是非傳統(tǒng)的，均不在其考慮范圍之內(nèi)，所得結(jié)果可與各類(lèi)開(kāi)發(fā)方法進(jìn)行比較，很多時(shí)候在項(xiàng)目運(yùn)行初期，就可以使用FPA方法對(duì)項(xiàng)目模型進(jìn)行功能點(diǎn)分析估算［2～3］。而這，同時(shí)也是FPA方法的弊端。FPA僅從用戶(hù)和功能的角度看待問(wèn)題［5］，而這種角度將不可避免地造成估算過(guò)程中的主觀(guān)和局限，尤其是在現(xiàn)代軟件開(kāi)發(fā)環(huán)境中［6］。因?yàn)檐浖?nèi)部許多復(fù)雜的處理功能、技術(shù)、質(zhì)量等要求被忽略，而這些同時(shí)也是造成軟件開(kāi)發(fā)中工作量增大的因素，這就不可避免地造成通過(guò)FPA估算結(jié)果無(wú)法真實(shí)反映軟件在開(kāi)發(fā)過(guò)程中的實(shí)際情況。

Burgess等首次將軟件成本估算模型問(wèn)題轉(zhuǎn)化為優(yōu)化問(wèn)題［7～8］，提出并驗(yàn)證了遺傳算法在該領(lǐng)域的可行性和準(zhǔn)確性，自此之后，遺傳算法在軟件開(kāi)發(fā)模型修正領(lǐng)域的應(yīng)用越來(lái)越廣，如 Li［10～12］將遺傳算法用于優(yōu)化類(lèi)比估算等。優(yōu)化算法有很多，各自尤其優(yōu)缺點(diǎn)，如遺傳算法的優(yōu)點(diǎn)是搜索效率高、魯棒性強(qiáng)，具有擴(kuò)展性，易與其它算法相結(jié)合，但其缺點(diǎn)是對(duì)整個(gè)系統(tǒng)的反饋信息利用率低，求精確解的效率不高。蟻群算法的優(yōu)點(diǎn)是使系統(tǒng)具有正反饋性和并行性，但缺點(diǎn)在于求解緩慢，且已陷入局部最優(yōu)。本文的想法是利用充分遺傳和蟻群算法的優(yōu)點(diǎn)，將二者結(jié)合起來(lái)，使整個(gè)算法高效、準(zhǔn)確，最終能夠精確修正IFPUG模型的復(fù)雜度權(quán)值。

2 模型建立

出于文章研究的廣泛性考慮，本文目標(biāo)方程的建立基于ISBSG Release 9數(shù)據(jù)庫(kù)。那么，根據(jù)ISB?SG數(shù)據(jù)庫(kù)，為了簡(jiǎn)單考慮，本文只考慮質(zhì)量等級(jí)為A、B的數(shù)據(jù)點(diǎn)，對(duì)C、D的數(shù)據(jù)點(diǎn)不予考慮?；诖耍Ａ繇?xiàng)目為1445個(gè)。此外，功能點(diǎn)中有各類(lèi)不同的計(jì)數(shù)方法，而IFPUG方法是最為普遍和被認(rèn)可的，因此本文僅用IFPUG方法計(jì)數(shù)的項(xiàng)目。根據(jù)資源等級(jí)和各等級(jí)在ISBSG數(shù)據(jù)庫(kù)占比的不同（一級(jí)資源等級(jí)為開(kāi)發(fā)級(jí)，二級(jí)資源等級(jí)為開(kāi)發(fā)和支持級(jí)，三級(jí)資源等級(jí)為操作級(jí)，四級(jí)資源等級(jí)為客戶(hù)端級(jí)。），由于一級(jí)資源等級(jí)約占整個(gè)ISBSG數(shù)據(jù)庫(kù)的70%，所以本文僅選擇一級(jí)資源等級(jí)項(xiàng)目。此外，為了普遍起見(jiàn)，本文將項(xiàng)目開(kāi)發(fā)類(lèi)型也作為考慮因素計(jì)入，ISBSG數(shù)據(jù)庫(kù)中包含三類(lèi)開(kāi)發(fā)類(lèi)型，分別為：新開(kāi)發(fā)型（共838個(gè)項(xiàng)目），增強(qiáng)開(kāi)發(fā)型（1132個(gè)項(xiàng)目），重建型（55個(gè)項(xiàng)目）。公共開(kāi)發(fā)和采購(gòu)項(xiàng)目均不屬于以上三種類(lèi)型，而在以上三種類(lèi)型當(dāng)中，新開(kāi)發(fā)項(xiàng)目和重建項(xiàng)目可視為一類(lèi)，規(guī)模計(jì)算如下式：

增強(qiáng)開(kāi)發(fā)型項(xiàng)目的規(guī)模計(jì)算如下式：

在以上論述的基礎(chǔ)上，整個(gè)項(xiàng)目數(shù)據(jù)為409個(gè)。如上所述，該模型中的數(shù)據(jù)點(diǎn)項(xiàng)目質(zhì)量等級(jí)為A、B，計(jì)數(shù)規(guī)模按照IFPUG計(jì)算，工作量為一級(jí)資源等級(jí)，項(xiàng)目為新開(kāi)發(fā)或重建開(kāi)的類(lèi)型。這樣，我們可以得到該模型共包括未調(diào)整的功能點(diǎn)數(shù)目為15個(gè)，GSC標(biāo)準(zhǔn)數(shù)目為14個(gè)，由此將項(xiàng)目數(shù)量減少至184個(gè)。工作量估算公式正是基于以上模型構(gòu)建。

以上數(shù)據(jù)獲得后必然滿(mǎn)足線(xiàn)性回歸分析假設(shè)條件，從而得知軟件規(guī)模與工作量之間必然是正相關(guān)的。由于調(diào)整因子VAF在實(shí)際使用中存在缺陷，本文不考慮規(guī)模調(diào)整因子的影響，僅以UFP作為統(tǒng)計(jì)分析的選擇。那么，我們基于ISBSG Re?lease 9數(shù)據(jù)庫(kù)重新建立方程，由于統(tǒng)計(jì)回歸分析中假設(shè)基礎(chǔ)數(shù)據(jù)服從高斯分布，我們對(duì)等價(jià)方程等式兩邊作對(duì)數(shù)變換，變換后的方程也將服從高斯分布。如下式：

式（3）和式（4）中，α、β、A和B為線(xiàn)性回歸計(jì)算所得到的系數(shù)。

系統(tǒng)模型殘差為高斯分布，相互獨(dú)立且均值為0，同時(shí)也滿(mǎn)足統(tǒng)計(jì)回歸的假設(shè)。

3 算法設(shè)計(jì)

1）建立目標(biāo)函數(shù)

基于上述系統(tǒng)，我們可以將IFPUG功能點(diǎn)各組件的復(fù)雜度權(quán)值修正問(wèn)題轉(zhuǎn)化為優(yōu)化問(wèn)題。即將系統(tǒng)輸入定義為工作量估算精確度的性能指標(biāo)，系統(tǒng)輸出為殘差，從而為系統(tǒng)殘差求解最小值。即：

上式中，f(xn)為系統(tǒng)輸入，選擇平均相對(duì)誤差計(jì)算；xn（n=1，2，…，15）表示的是未調(diào)整功能點(diǎn)的復(fù)雜度。

2）參數(shù)編碼

為減少變量格式，增強(qiáng)系統(tǒng)的局部搜索能力，本文采用實(shí)數(shù)編碼方式，將染色體作為實(shí)參向量，每個(gè)基因?qū)?yīng)一個(gè)代表功能點(diǎn)復(fù)雜度權(quán)值的實(shí)數(shù)。各染色體

3）初始化遺傳群體

根據(jù)各組件不同的復(fù)雜度等級(jí)與功能點(diǎn)數(shù)的對(duì)應(yīng)關(guān)系，如表1所示：

表1 復(fù)雜度等級(jí)與功能點(diǎn)數(shù)對(duì)應(yīng)關(guān)系表

依據(jù)表1，設(shè)置初始種群V0，通過(guò)表1中數(shù)值擾動(dòng)得出向量 R0，R0=（3.0；4.0；6.0；4.0；5.0；7.0；3.0；4.0；6.0；7.0；10.0；15.0；5.0；7.0；10.0）。矩陣V0中的元素θij均由下式得到：

式（7）中，Random是隨機(jī)整數(shù)，取值范圍為1～5；Rj為向量 R0中的元素，j是整數(shù)，取值范圍為1～15，i表示的是種群的大小數(shù)目，取值為整數(shù)，初始值設(shè)置為100。矩陣V0中的每行為遺傳操作個(gè)體。

4）選取適應(yīng)度函數(shù)

為了更加直觀(guān)地了解染色體表示各個(gè)參量的性能，本文首先給出了相對(duì)誤差幅度的概念，并結(jié)合模型結(jié)構(gòu)，給出了相對(duì)誤差幅度的計(jì)算方法，由于相對(duì)誤差幅度無(wú)法衡量各個(gè)染色體的參量性能，在此基礎(chǔ)上，平均誤差幅度能夠客觀(guān)地反映相關(guān)參量情況。所以本文選取平均誤差幅度為整個(gè)模型的適應(yīng)度函數(shù)。

在使用遺傳算法的過(guò)程中，由于遺傳群體在進(jìn)化時(shí)，每代個(gè)體均要計(jì)算適應(yīng)度函數(shù)，因此，我們給出了相對(duì)誤差幅度的概念：

Estimatedi為項(xiàng)目的估計(jì)工作量，而工作量的計(jì)算方法如式（4），Actuali表示各項(xiàng)目的實(shí)際工作量。由此我們可以得到平均誤差幅度的表達(dá)式如下：

平均誤差幅度表示的是個(gè)體對(duì)數(shù)據(jù)庫(kù)中工作量的平均估算經(jīng)度。i表示的是個(gè)體序號(hào)，j指的是項(xiàng)目序列。

5）遺傳選擇

本文使用與概率方法來(lái)進(jìn)行選擇，前提是該概率值與適應(yīng)度值成比例。在遺傳算法的每一代中，每個(gè)個(gè)體被選中的次數(shù)由群體規(guī)模和選擇概率的乘積得出。如下式：

上式中，i表示的是第i個(gè)個(gè)體。

6）遺傳交叉

為避免遺傳算法中后期各基因排列的過(guò)度相似，提高種群的多樣性，并為后續(xù)的蟻群算法結(jié)合做鋪墊，本文采用多點(diǎn)交叉的方法?？紤]篇幅限制，多點(diǎn)交叉的具體方法本文不再贅述。

7）遺傳變異

本文在遺傳算法中設(shè)置變異概率為正負(fù)各0.5，通過(guò)隨機(jī)產(chǎn)生一個(gè)0到1之間的浮點(diǎn)數(shù)，假如該浮點(diǎn)數(shù)小于變異概率值，則進(jìn)行變異操作。本文設(shè)置變異操作如下：隨機(jī)選取向量R0任意元素，假定Kn所帶染色體發(fā)生變異，則將Kn與Kn+1元素進(jìn)行交換，其余不變。如 R0=（3.0；4.0；6.0；4.0；5.0；7.0；3.0；4.0；6.0；7.0；10.0；15.0；5.0；7.0；10.0），K4=4，那么進(jìn)行變異操作后，有：R1=（3.0；4.0；6.0；5.0；4.0；7.0；3.0；4.0；6.0；7.0；10.0；15.0；5.0；7.0；10.0）。

8）開(kāi)始迭代運(yùn)算

通過(guò)以上基本設(shè)置之后，對(duì)整個(gè)遺傳算法開(kāi)始迭代計(jì)算，直至到達(dá)最大迭代次數(shù)，為后續(xù)蟻群算法介入做好數(shù)據(jù)準(zhǔn)備。

9）生成優(yōu)化解

通過(guò)迭代運(yùn)算之后，可以得到若干組優(yōu)化解，這些優(yōu)化解將成為蟻群算法的輸入值。

10）初始化參數(shù)

將步驟9）中得出的優(yōu)化解通過(guò)轉(zhuǎn)換，從而得到蟻群算法的初始信息素分布圖，將螞蟻放到路徑起點(diǎn)上。

11）通過(guò)螞蟻選擇路徑的概率公式計(jì)算出螞蟻選擇節(jié)點(diǎn)的概率值，概率公式為

式（12）中，參數(shù)α和β分別表示信息素和路徑長(zhǎng)度的相對(duì)重要性；ηij根據(jù)問(wèn)題下界定義：

12）當(dāng)螞蟻在某代中遍歷過(guò)所有節(jié)點(diǎn)之后，那么根據(jù)式（14）可以計(jì)算出最優(yōu)螞蟻對(duì)整個(gè)路徑信息素的更改程度。

13）根據(jù)各條路徑上的信息素更新情況，通過(guò)式（15）就可以得知某代中所有路徑的信息素變化情況。

14）根據(jù)以上步驟不斷進(jìn)行遞歸迭代，直到最終的種群路徑基本無(wú)變化即可得到最優(yōu)解。至此，算法結(jié)束。

算法流程圖如圖1所示。

4 仿真驗(yàn)證

為了使算法達(dá)到最優(yōu)效果，本文在進(jìn)行算法仿真前，通過(guò)多次實(shí)驗(yàn)，對(duì)參數(shù)經(jīng)過(guò)不斷修正，最終得出了一組比較準(zhǔn)確可行的參數(shù)設(shè)定。設(shè)定代數(shù)G為500，為了在算法的種群多樣性和算法收斂性之間取得平衡，本文對(duì)遺傳群體設(shè)定的初始規(guī)模為100，代溝g設(shè)定為0.75，交叉概率設(shè)定為0.85，采用多點(diǎn)交叉的方法，變異概率設(shè)定為0.02；蟻群算法中各路徑初始信息素值設(shè)定為500，遺傳算法所得優(yōu)化解轉(zhuǎn)換為蟻群算法初始值是通過(guò)將螞蟻路徑中的若干組優(yōu)化解所占比重與某一常數(shù)相乘得到，仿真環(huán)境中將該常數(shù)設(shè)置為80，ρ=0.8，Q=1000，τmax=250，τmin=100，R=0.35，經(jīng)過(guò)若干次迭代，修正后的UFP復(fù)雜度權(quán)值如表2所示。

表2 修正后的特征點(diǎn)復(fù)雜度權(quán)值對(duì)比

該組權(quán)值是通過(guò)本文算法反復(fù)試驗(yàn)得出的最優(yōu)解，它充分地體現(xiàn)了遺傳算法搜索效率高、魯棒性、擴(kuò)展性強(qiáng)的特點(diǎn)，同時(shí)也涵蓋了蟻群算法正反饋性和并行性的特點(diǎn)，兩種算法較好地結(jié)合，使實(shí)驗(yàn)得出的數(shù)據(jù)相對(duì)誤差較小，使用修正后的復(fù)雜度權(quán)值可以更加科學(xué)合理地估算軟件的規(guī)模。

此外，為更加準(zhǔn)確地估計(jì)算法的精確度，本文在原仿真模型的基礎(chǔ)上，對(duì)遺傳交叉采取10倍數(shù)據(jù)驗(yàn)證。也就是說(shuō)，將原模型中數(shù)據(jù)集隨機(jī)地劃分為10個(gè)等份子集，每等份中包含的項(xiàng)目數(shù)據(jù)統(tǒng)一按60個(gè)計(jì)算。我們使用劃分好的10個(gè)等份子集中的9個(gè)進(jìn)行訓(xùn)練，得出訓(xùn)練數(shù)據(jù)集合VT，然后將VT納入剩下的子集中進(jìn)行集中測(cè)試。這里，我們對(duì)劃分好的10個(gè)子集重復(fù)以上過(guò)程，可以得到對(duì)V0和VT的訓(xùn)練和測(cè)試樣本上的標(biāo)準(zhǔn)偏差和平均偏差，本文以MMRE進(jìn)行表征。表3給出了模型偏差計(jì)算結(jié)果，圖2是通過(guò)表3的數(shù)據(jù)得出的仿真柱狀圖。從圖2和表3可以看出，在解決軟件成本估算問(wèn)題中，采用本文的算法后，相對(duì)誤差有所降低，平均降低約31%。

圖2 偏差計(jì)算情況

5 結(jié)語(yǔ)

本文針對(duì)FPA方法在軟件項(xiàng)目估算過(guò)程中存在的主觀(guān)和局限的問(wèn)題，提出了一種基于遺傳-蟻群算法的復(fù)雜度權(quán)值修正方法，該算法不僅繼承了遺傳算法搜索效率高、魯棒性強(qiáng)的特點(diǎn)，同時(shí)也吸納了蟻群算法正反饋性和并行性的優(yōu)點(diǎn)，本文將兩種算法結(jié)合使用，不僅估算精度高，且運(yùn)行速度快，通過(guò)仿真驗(yàn)證了本文算法的有效性。

［1］Hericko M，Rozman I，Zivkovic A.A formal repre-senta?tion of functional size measurement methods［J］.Journal of Systems and Software，2006，79（9）：1341-1358.

［2］Habra N，Abran A，Lopez M，et al.A framework for the design and verification of software measurement methods［J］.Journal of Systems and Software，2008，81（5）：633-648.

［3］Abran A，Silva I，Primera L.Fields Studies Using Func?tional Size Measurement in Building Estimation Models for Software Maintenance［J］.Journal of Software Mainte?nance and Evolution：Research and Practice，2002，14（1）：31-64.

［4］IFPUG.Function Point Counting Practices Manual，Re?lease 4.1［Z］.International Function Point Users Group，1999：165-274.

［5］Kishore S，Naik R.軟件需求與估算［M］.北京：機(jī)械工業(yè)出版社，2004：319-523.

［6］Keung J.Software development cost estimation using anal?ogy：a review［J］.IEEE Software，2001：327-336.

［7］Aljahdali S，Sheta A F.Software effort estimation by tun?ing COCOMO model parameters using differential evolu?tion［J］.IEEE Software，2002：323-333.

［8］Seo Y S，Yoon K A，Bae D H.Improving the accuracy of software effort estimation based on multiple least square re?gression models by estimation error-based data partition?ing［C］//16th Asia-Pacific Software Engineering Confer?ence，2009：3-10.

［9］McConnell S.軟件估算：“黑匣子”揭秘［M］.宋銳等 譯.北京：電子工業(yè)出版社，2007：82-239.

［10］Lind K，Heldal R.On the relationship between function?al size and software code size［C］//Proceedings of the 2010 ICSE Workshop on Emerging Trends in Software Metrics.New York：ACM，2010：34-82.

［11］Yahya M A，Ahmad R，Lee S.Impact of CMMI based software process maturity on COCOMO II's effort estima?tion［J］.The International Arab Journal of Information Technology，2010，7（2）：129-137.

［12］G.Y.Kulikov，M.V.Kulikova.Accurate numerical im?plementation of the continuous-discrete extended Kal?man filter［J］.IEEE Transactions on Automatic Con?trol，2014，59（1）：273-279.

Complexity Weight Correction Based on Genetic-ant colony Algorithm of IFPUG

HUANG ZhikaiZHANG Bolei
（Air Force Warning institution，Wuhan 430019）

The paper aims at the problem of subjectivities and limitations of FPA in software project estimation，proposes a complex weight correction algorithm based on genetic-ant colony algorithm.The algorithm not only inherits the characteristic of high searching efficiency and strong robustness，but also admits the advantages of positive feedback and parallelism.The paper combines the two algorithms.the algorithm has high estimation accuracy and runs fast.The effectiveness of the algorithm is proved through sim?ulation.

function point analysis（FPA），genetic algorithm，ant colony algorithm

TP311.52

10.3969/j.issn.1672-9730.2017.11.011

Class Number TP311.52

2017年5月5日，

2017年6月26日

黃治凱，男，碩士研究生，研究方向：裝備管理。張波雷，男，研究方向：雷達(dá)信號(hào)與信息處理。