周啟超
(渤海大學(xué) 信息科學(xué)與技術(shù)學(xué)院,遼寧 錦州 121013)
BP算法改進(jìn)及在軟件成本估算中的應(yīng)用
周啟超
(渤海大學(xué) 信息科學(xué)與技術(shù)學(xué)院,遼寧 錦州 121013)
軟件成本估算在軟件開發(fā)過程中扮演著重要角色,它是控制軟件進(jìn)度、降低軟件風(fēng)險(xiǎn)和保證軟件質(zhì)量的有效措施。軟件成本估算是復(fù)雜的工作,受眾多因素影響且具有不確定性。針對(duì)軟件成本難以估算的現(xiàn)狀,文中基于BP算法展開研究。首先,研究BP算法原理和數(shù)學(xué)表示;然后,在分析BP算法存在問題的基礎(chǔ)上,將自適應(yīng)學(xué)習(xí)率、附加動(dòng)量項(xiàng)法與退火模擬算法、遺傳算法等方法相結(jié)合對(duì)其進(jìn)行改進(jìn);最后,構(gòu)建軟件成本估算指標(biāo)體系,并將改進(jìn)的BP算法應(yīng)用于軟件成本估算。結(jié)果表明,算法具有估算結(jié)果精確、節(jié)省人力物力、減少資金浪費(fèi)等優(yōu)點(diǎn),對(duì)加快軟件開發(fā)進(jìn)度、提高軟件質(zhì)量具用重要作用。
BP算法;改進(jìn);成本估算;應(yīng)用
軟件系統(tǒng)規(guī)模不斷增大且越來越復(fù)雜化,隨之帶來了軟件項(xiàng)目延期和預(yù)算超支等問題,準(zhǔn)確估算軟件成本是控制項(xiàng)目進(jìn)度、減少項(xiàng)目成本的重要手段。軟件成本估算主要指軟件開發(fā)過程中所花費(fèi)的工作量及相應(yīng)的代價(jià)[1],影響軟件成本的因素不僅多且異常復(fù)雜,而且隨著項(xiàng)目的不斷開發(fā),影響因素也在不斷變化,存在復(fù)雜的非線性關(guān)系,要準(zhǔn)確高效地進(jìn)行軟件成本估算是非常困難的。因?yàn)锽P神經(jīng)網(wǎng)絡(luò)具有較強(qiáng)的非線性映射能力,能以任意精度逼近非線性函數(shù),其高度的自我學(xué)習(xí)能力和自適應(yīng)能力,能夠快速地學(xué)習(xí)和提取知識(shí),將其應(yīng)用于軟件成本估算中,不必費(fèi)力去尋找和發(fā)現(xiàn)成本驅(qū)動(dòng)因素與軟件成本之間的關(guān)系[2-3]。
BP神經(jīng)網(wǎng)絡(luò)在前饋神經(jīng)網(wǎng)絡(luò)中應(yīng)用最廣泛,是一種3層或者3層以上的神經(jīng)網(wǎng)絡(luò),包括一個(gè)輸入層,一個(gè)或多個(gè)隱含層,一個(gè)輸出層,相鄰兩層之間的所有神經(jīng)元互相連接,而處于同一層的神經(jīng)元不能相互連接[4]。采用的BP算法具有計(jì)算量小、并行性強(qiáng)、可操作性強(qiáng)等優(yōu)點(diǎn)。隨著BP算法的不斷應(yīng)用,一些不足逐漸被發(fā)現(xiàn)。因此,文中研究BP算法的原理、存在的問題及改進(jìn)方法,并應(yīng)用到復(fù)雜的軟件成本估算中。
1.1 原 理
BP算法也稱誤差反向傳播算法,實(shí)質(zhì)是一邊傳播一邊不斷調(diào)整權(quán)值的過程,使實(shí)際輸出與期望輸出的誤差達(dá)到最小。主要思想是輸入信號(hào)從輸入層經(jīng)過隱含層處理,到達(dá)輸出層,輸出端產(chǎn)生輸出信號(hào),在信號(hào)向前傳遞過程中網(wǎng)絡(luò)的權(quán)值是固定不變的,每一層神經(jīng)元的狀態(tài)只影響下一層神經(jīng)元的狀態(tài)[5],這是工作信號(hào)的正向傳播。當(dāng)實(shí)際輸出沒有達(dá)到期望輸出,將誤差信號(hào)由輸出端開始逐層向前傳播,按照原來神經(jīng)元連接的路線返回,這是信號(hào)的反向傳播。在反向傳播過程中,網(wǎng)絡(luò)的實(shí)際輸出與期望輸出之間的差值即為誤差信號(hào),將誤差分?jǐn)偨o各層所有的單元,根據(jù)誤差反饋修改各層權(quán)值,經(jīng)過多次的迭代,使實(shí)際輸出越來越逼近期望值或達(dá)到預(yù)先設(shè)定的學(xué)習(xí)次數(shù),停止訓(xùn)練。
1.2 BP算法數(shù)學(xué)表達(dá)式
三層BP神經(jīng)網(wǎng)絡(luò)是BP神經(jīng)網(wǎng)絡(luò)中最典型的,所以介紹如下[6]:如輸入層、隱含層和輸出層的節(jié)點(diǎn)個(gè)數(shù)分別是m,n,s,輸入樣本總數(shù)P。把閾值寫入連接權(quán)中,即把閾值看成節(jié)點(diǎn)的一個(gè)輸入的權(quán)值,則各節(jié)點(diǎn)的輸出可以表示為向量的形式vjixpi,隱含層、輸出層節(jié)點(diǎn)的輸出分別為:
(1)
(2)
其中,xpi表示第p個(gè)樣本的第i個(gè)輸入值;vji表示輸入層第i個(gè)節(jié)點(diǎn)到隱含層第j個(gè)節(jié)點(diǎn)的權(quán)值;wkj表示隱含層第j個(gè)節(jié)點(diǎn)到輸出層第k個(gè)節(jié)點(diǎn)的權(quán)值。
在式(1)、(2)中激勵(lì)函數(shù)選取Sigmoid函數(shù):
(3)
f(x)具有連續(xù)可導(dǎo)的特點(diǎn),且有:
(4)
全局誤差函數(shù)為:
(5)
其中,Ep是第p個(gè)樣本的誤差;tpk是第p個(gè)樣本第k個(gè)節(jié)點(diǎn)的期望輸出。
(6)
在反向傳播中,采用梯度下降方法,其各層調(diào)整公式如下所示。其中η是學(xué)習(xí)率,一般取值(0,1)。
輸出層各神經(jīng)元權(quán)值調(diào)整公式為:
(7)
其中:
δpk=(tpk-opk)opk(1-opk)
(8)
隱層各神經(jīng)元權(quán)值調(diào)整公式為:
(9)
其中:
(10)
根據(jù)以上公式進(jìn)行網(wǎng)絡(luò)訓(xùn)練,BP算法的實(shí)現(xiàn)步驟[7-8]如圖1所示。
圖1 BP算法流程圖
2.1 BP算法存在的問題
BP算法因?yàn)楣潭ǖ膶W(xué)習(xí)率,需要長(zhǎng)時(shí)間的調(diào)整和多次的迭代,因此訓(xùn)練次數(shù)多,收斂速度慢,訓(xùn)練時(shí)間較長(zhǎng),對(duì)于一些復(fù)雜問題,所需的訓(xùn)練時(shí)間會(huì)更長(zhǎng),這是由于學(xué)習(xí)率太小所致,如果加快收斂速度,則容易產(chǎn)生振蕩;由于網(wǎng)絡(luò)誤差曲面是非常繁雜的高維的凹凸不平的曲面,BP算法收斂到某個(gè)值時(shí)不能保證誤差是全局最小值,也可能是局部極小值,不同的起始點(diǎn)可能導(dǎo)致不同的極小值,而無法得到全局最優(yōu)解[9]。由于在一些平坦地區(qū)內(nèi)誤差的改變很小幾乎為零,造成網(wǎng)絡(luò)不能得到訓(xùn)練,收斂速度就會(huì)變慢,難以達(dá)到給定的誤差。還有網(wǎng)絡(luò)結(jié)構(gòu)的選擇,包括輸入層和輸出層節(jié)點(diǎn)數(shù)、網(wǎng)絡(luò)隱層數(shù)、隱層神經(jīng)元數(shù),只能根據(jù)經(jīng)驗(yàn)或者通過反復(fù)實(shí)驗(yàn)去確定。網(wǎng)絡(luò)的學(xué)習(xí)和記憶具有不穩(wěn)定性,容易造成過擬合現(xiàn)象導(dǎo)致泛化能力差等缺點(diǎn)。
2.2 改進(jìn)BP算法的方法
目前隨著對(duì)BP算法的大量研究,已經(jīng)得出了很多改進(jìn)的方法,在前人基礎(chǔ)上進(jìn)行再改進(jìn),將幾種改進(jìn)后與其他智能算法相結(jié)合,如下所示。
自適應(yīng)調(diào)節(jié)學(xué)習(xí)率的方法是為了減少訓(xùn)練時(shí)間,實(shí)現(xiàn)快速有效的學(xué)習(xí)收斂的過程?;舅枷耄焊鶕?jù)誤差增量的大小來調(diào)節(jié)學(xué)習(xí)率的大小,當(dāng)誤差減小,增大學(xué)習(xí)率;當(dāng)誤差增大,減小學(xué)習(xí)率[10]。對(duì)此進(jìn)行改進(jìn),修正公式為:
(11)
其中,η(t+1)、η(t)分別表示學(xué)習(xí)率迭代到第t、t+1次時(shí)的值;ΔE=Et+1-Et;0<α1<α2<1為常量。
此公式不僅考慮了誤差增量,還考慮了相對(duì)誤差Et+1/Et,根據(jù)它適當(dāng)減小學(xué)習(xí)率的調(diào)整幅度,進(jìn)而有更合理的學(xué)習(xí)率進(jìn)行訓(xùn)練,避免出現(xiàn)振蕩。優(yōu)點(diǎn)是算法穩(wěn)定性得到保證,又使算法收斂速度加快。
附加動(dòng)量項(xiàng)法,BP算法中η的選取很重要,η值大網(wǎng)絡(luò)收斂速度快,但過大會(huì)引起不穩(wěn)定;若η值小雖避免了不穩(wěn)定,收斂速度變慢,加入動(dòng)量項(xiàng)來改變?chǔ)菑亩岣呔W(wǎng)絡(luò)性能。動(dòng)量項(xiàng)能記憶上一時(shí)刻的權(quán)值修改方向[11],使權(quán)值調(diào)節(jié)向著誤差曲面底部的平均方向變化,不僅可以微調(diào)權(quán)值的修正量,也避免陷入局部極小值,加速了網(wǎng)絡(luò)的收斂,避免了網(wǎng)絡(luò)的來回振蕩,起到了緩沖平滑的作用。其中動(dòng)量項(xiàng)βΔw(t)=β[w(t)-w(t-1)],β為動(dòng)量因子,0<β<1,一般取0.3~0.6。
(12)
模擬退火算法是通過模擬金屬熱加工中溫度與能量的關(guān)系,溫度高原子的能量高,隨著溫度降低,能量越來越小而達(dá)到最低點(diǎn)確定關(guān)系。概率為P(E)∞exp(-E/kT),定義人工溫度T,需要加入一個(gè)干擾Δw,則ΔE=E(w+Δw)-E(w),ΔE<0,干擾接受,ΔE>0,則依據(jù)概率公式判斷是否接受,干擾接受w=w+Δw,否則不變。
文中將自適應(yīng)學(xué)習(xí)率法和附加動(dòng)量項(xiàng)法與模擬退火算法、遺傳算法相結(jié)合?;舅枷胧牵涸贐P算法進(jìn)行樣本數(shù)據(jù)訓(xùn)練時(shí),首先利用遺傳算法產(chǎn)生初始種群,確定網(wǎng)絡(luò)的權(quán)值,根據(jù)式(1)、(2)計(jì)算節(jié)點(diǎn)的輸出,式(5)計(jì)算全局誤差,得到測(cè)試誤差;然后判斷訓(xùn)練是否達(dá)到平衡狀態(tài),是則調(diào)用自適應(yīng)學(xué)習(xí)率調(diào)整算法和附加動(dòng)量項(xiàng)法,根據(jù)權(quán)值修正公式(7)、(9),式(11)和式(12)的調(diào)整學(xué)習(xí)率和附加動(dòng)量項(xiàng),來進(jìn)行權(quán)值調(diào)整。若Et+1
將以上改進(jìn)BP算法和智能算法相結(jié)合的方法,應(yīng)用到軟件項(xiàng)目的成本估算中,以提高軟件成本估算的效率和準(zhǔn)確性。
3.1 構(gòu)建指標(biāo)體系
軟件成本估算通常是通過估算工作量來進(jìn)行,綜合得到,一級(jí)指標(biāo)是產(chǎn)品元素、計(jì)算機(jī)元素、人員因素、項(xiàng)目因素;相對(duì)應(yīng)的16個(gè)二級(jí)指標(biāo)[13-15]如圖2所示。
圖2 軟件成本估算指標(biāo)體系
實(shí)現(xiàn)步驟如下:
(1)對(duì)輸入訓(xùn)練樣本進(jìn)行歸一化,公式如下:
(13)
(2)定義網(wǎng)絡(luò)輸入和期望輸出。
(3)設(shè)BP神經(jīng)網(wǎng)絡(luò)中輸入層節(jié)點(diǎn)數(shù)為17個(gè),前16個(gè)為成本驅(qū)動(dòng)因子,第17個(gè)節(jié)點(diǎn)取KDSI代碼千行數(shù),只需要一個(gè)輸出節(jié)點(diǎn),根據(jù)前人的研究理論,隱層節(jié)點(diǎn)為2×17+1=35個(gè)。建立相應(yīng)BP網(wǎng)絡(luò),根據(jù)改進(jìn)算法進(jìn)行。
3.2 仿真結(jié)果比較
用MATLAB仿真改進(jìn)前后的算法比較輸出結(jié)果?;贑OCOMO數(shù)據(jù)庫(kù)[16]的80個(gè)項(xiàng)目的訓(xùn)練樣本得到的結(jié)果如圖3和圖4所示。
結(jié)果表明在使用同一組數(shù)據(jù)時(shí),改進(jìn)后的訓(xùn)練步數(shù)減少很多,大約是改進(jìn)前的一半,且隨著訓(xùn)練步數(shù)增加,誤差更趨于穩(wěn)定收斂,沒有很多跳躍的點(diǎn),減少陷入局部極小值的問題,大大減少了估算時(shí)間。同樣在比較實(shí)際輸出與期望輸出結(jié)果,改進(jìn)前雖然基本上和實(shí)際輸出大體一致,但存在很多相差很大的部分,而改進(jìn)后的基本與實(shí)際輸出一致。準(zhǔn)確率也相應(yīng)提高,誤差率也達(dá)到了實(shí)際應(yīng)用的要求。
圖3 改進(jìn)前訓(xùn)練誤差
圖4 改進(jìn)后訓(xùn)練誤差
因此,結(jié)果更加表明有效的改進(jìn)更適用于實(shí)際估算,它不僅兼具了標(biāo)準(zhǔn)BP算法的優(yōu)點(diǎn),還帶有自適應(yīng)學(xué)習(xí)率、附加動(dòng)量項(xiàng),模擬退火算法和遺傳算法的優(yōu)點(diǎn)。使軟件成本估算時(shí)間短且相對(duì)簡(jiǎn)單,并且?guī)в袦?zhǔn)確性[17-18]。
隨著對(duì)BP神經(jīng)網(wǎng)絡(luò)理論不斷深入的研究,以及網(wǎng)絡(luò)計(jì)算能力不斷的提高,BP算法更適應(yīng)于很多復(fù)雜難以解決的問題,對(duì)其不斷改進(jìn)將會(huì)使應(yīng)用范圍不斷擴(kuò)大。為了改善BP神經(jīng)網(wǎng)絡(luò)的各種不足,前人已經(jīng)在各個(gè)方面采用不同的方法,有了大量的研究及改進(jìn)。
文中已有研究成果的基礎(chǔ)上,將其改進(jìn)并和遺傳算法、模擬退火算法等智能算法相結(jié)合,算法各自發(fā)揮自己獨(dú)特的優(yōu)勢(shì),具有全局優(yōu)化搜索性質(zhì)、容易得到全局最優(yōu)解等特點(diǎn),又根據(jù)影響軟件成本估算的因素眾多且不具有確定性等特點(diǎn),將算法應(yīng)用到軟件成本估
算中。結(jié)果表明不僅減少了估算的時(shí)間,估算的精確度也得到了很大提高。
[1] 任永昌.軟件項(xiàng)目管理[M].北京:清華大學(xué)出版社,2012.
[2] 張 紅.基于神經(jīng)網(wǎng)絡(luò)的軟件項(xiàng)目工作量估算系統(tǒng)實(shí)現(xiàn)[J].寧波職業(yè)技術(shù)學(xué)院學(xué)報(bào),2014,18(4):87-90.
[3] Mittas N,Andreas S.Integrating non-parametric models with linear components for producing software cost estimations[J].Journal of Systems and Software,2015,99(1):120-134.
[4] 王盛源,王 穎,劉連光,等.基于誤差反向傳播ANN的電網(wǎng)磁暴災(zāi)害風(fēng)險(xiǎn)評(píng)估方法[J].計(jì)算機(jī)與數(shù)字工程,2014,42(12):2223-2226.
[5] 孟 棟,樊重俊,王家楨.混沌遺傳算法對(duì)BP神經(jīng)網(wǎng)絡(luò)的改進(jìn)研究[J].數(shù)學(xué)理論與應(yīng)用,2014,34(1):102-110.
[6] 蔣 亮.BP神經(jīng)網(wǎng)絡(luò)的優(yōu)化研究[D].南昌:南昌大學(xué),2014.
[7] 王晶晶,王 劍.一種BP神經(jīng)網(wǎng)絡(luò)改進(jìn)算法研究[J].軟件導(dǎo)刊,2015,14(3):52-53.
[8] 李曉華,周加波,周 韋.基于誤差反向傳播神經(jīng)網(wǎng)絡(luò)的江蘇省用電量預(yù)測(cè)研究[J].科技與企業(yè),2014,23(20):197-198.
[9] 白牧可,唐 巍,張 璐,等.基于BP神經(jīng)網(wǎng)絡(luò)群的中壓配電網(wǎng)電壓降落估算[J].電力系統(tǒng)保護(hù)與控制,2014,42(2):132-138.
[10] 蘇麗冰.BP神經(jīng)網(wǎng)絡(luò)的改進(jìn)綜述[J].信息與電腦:理論版,2013,7(6):110-111.
[11] 江 麗.基于粒子群與模擬退火算法的BP網(wǎng)絡(luò)學(xué)習(xí)方法研究[D].合肥:安徽大學(xué),2013.
[12] 孫海濤,李仲秋.模擬退火算法改進(jìn)BP算法的區(qū)域物流中心選址[J].計(jì)算機(jī)技術(shù)與發(fā)展,2014,24(9):222-225.
[13] Boehm B W.Software cost estimation with COCOMO II[M].[s.l.]:Prentice Hall PTR,2009.
[14] Seo Yeong-Seok,Jeffery R.Software effort estimation based on multiple regressions with adaptive recursive data partitioning[J].Information and Software Technology,2013,55(10):1710-1725.
[15] Nassif A B,Ho D.Towards an early software estimation using log-linear regression and a multilayer perceptron model[J].Journal of Systems and Software,2013,86(1):144-160.
[16] 焦玉婷.軟件成本估算模型的研究[D].北京:北京工業(yè)大學(xué),2013.
[17] 段美美,于本海,朱 萌.基于CBR的軟件項(xiàng)目成本估算方法[J].計(jì)算機(jī)工程與設(shè)計(jì),2014,35(11):3837-3844.
[18] 郝勝蘭.基于模糊神經(jīng)網(wǎng)絡(luò)的房產(chǎn)軟件項(xiàng)目成本估算研究[D].大連:大連海事大學(xué),2012.
Improvement of BP Algorithms and Its Application in Software Cost Estimation
ZHOU Qi-chao
(College of Information Science and Technology,Bohai University,Jinzhou 121013,China)
Software cost estimation plays an important role in the software development process,which is an effective measure to control software progress and reduce software risk and ensure software quality.Software cost estimation is a complicated task,affected by many factors and uncertainties.According to the current situation of software costs are difficult to estimate,a study based on BP algorithm is carried out.Firstly,BP algorithm principle and mathematical representation is researched.Then,based on the analysis of existing problems on BP algorithm,the adaptive learning rate,the additional momentum method and simulated annealing,and genetic algorithm are combined to improve it.Finally,the software cost estimation index system is established and the improved BP algorithm is used in software cost estimation.The results show that the improved BP algorithm has the advantages of accurate estimated result,saving manpower and material resources,reducing waste of money,to accelerate software development progress and improve software quality with an important role.
BP algorithm;improvement;cost estimation;application
2015-04-02
2015-07-08
時(shí)間:2016-01-04
2014年遼寧省教育科學(xué)研究項(xiàng)目(L2014248)
周啟超(1990-),女,碩士,研究方向?yàn)槿斯ぶ悄堋?/p>
http://www.cnki.net/kcms/detail/61.1450.TP.20160104.1453.006.html
TP39
A
1673-629X(2016)02-0195-04
10.3969/j.issn.1673-629X.2016.02.043