基于代理輔助多目標(biāo)螢火蟲算法的軟件缺陷預(yù)測方法研究*

曹良林，賁可榮,張 獻(xiàn)

(1．海軍工程大學(xué)電子工程學(xué)院，湖北 武漢 430033；2.九江學(xué)院計(jì)算機(jī)與大數(shù)據(jù)科學(xué)學(xué)院，江西 九江 332005)

1 引言

研究表明，軟件缺陷預(yù)測SDP(Software Defect Prediction)能從軟件歷史數(shù)據(jù)中預(yù)判出現(xiàn)有軟件數(shù)據(jù)(正在開發(fā)、已經(jīng)運(yùn)行、版本更新等軟件)可能存在的缺陷，并對軟件有可能存在的缺陷模塊進(jìn)行跟蹤與維護(hù)，合理分配有限的資源，協(xié)助和引導(dǎo)軟件工程師完成軟件開發(fā)與維護(hù)，對保障軟件質(zhì)量有著重要的作用與意義[1]。

雖然軟件缺陷預(yù)測技術(shù)自提出以來經(jīng)歷了多年的技術(shù)突破與發(fā)展，但隨著社會需求的增加、軟件應(yīng)用場景的復(fù)雜化、軟件數(shù)據(jù)的爆炸式增長，軟件缺陷預(yù)測技術(shù)面臨著以下新的挑戰(zhàn)：(1)軟件缺陷數(shù)據(jù)存在異常值、高維度和類不平衡問題，導(dǎo)致預(yù)測模型性能出現(xiàn)很大偏差；(2)在軟件缺陷預(yù)測模型中，往往存在多組利益相抵觸的追求目標(biāo)，如較高的預(yù)測精度與較低的資源開銷、較高的精確率與較高的召回率等，在現(xiàn)有的大量單目標(biāo)預(yù)測技術(shù)中，將存在顧此失彼的問題。

針對上述問題，基于搜索的軟件工程SBSE(Search Based Software Engineering)交叉學(xué)科提出者Harman[2]在2010年首次闡述了軟件預(yù)測性建模與SBSE之間的密切關(guān)系，并提出了基于搜索的預(yù)測性建模SBPM(Search Based Predictive Modeling)的新應(yīng)用。

本文采用搜索技術(shù)構(gòu)建多目標(biāo)優(yōu)化的軟件缺陷預(yù)測模型，能為模型提供多組利益相沖突的目標(biāo)最優(yōu)組合方案，軟件工程師因此能夠在軟件開發(fā)與維護(hù)過程中，根據(jù)實(shí)際需求選擇適合的方案開展缺陷預(yù)測工作。

2 相關(guān)工作

本文從基于搜索技術(shù)構(gòu)建軟件缺陷預(yù)測模型和代理模型在搜索技術(shù)中的應(yīng)用2個方面對相關(guān)的文獻(xiàn)資料進(jìn)行了調(diào)查研究。

2.1 基于搜索的軟件缺陷預(yù)測技術(shù)

軟件缺陷預(yù)測過程主要由4部分組成[3]：數(shù)據(jù)預(yù)處理、軟件度量、模型訓(xùn)練和模型評價。面對軟件缺陷預(yù)測目標(biāo)與其應(yīng)用場景需求構(gòu)建軟件缺陷預(yù)測模型，常常遇到軟件數(shù)據(jù)類不平衡、數(shù)據(jù)高維度和預(yù)測模型性能不穩(wěn)定等問題，為此學(xué)者們展開了大量研究。

關(guān)鍵特征選擇方法是應(yīng)對軟件缺陷預(yù)測中維度災(zāi)難問題最為常見的方法，它主要分為過濾特征選擇FFS(Filter-based Feature Selection)[4]和封裝包特征選擇WFS(Wrapper Feature Selection)[5]。FFS方法使用距離度量、依賴度量和一致性度量等指標(biāo)對數(shù)據(jù)特征進(jìn)行評估和排名，雖然具備低計(jì)算成本和較好的泛化能力，但是FFS通常忽略或不考慮要素之間的相互作用和相互依賴性。這樣，每個特征都將被獨(dú)立評估，而與預(yù)測模型的交互將會被忽略，不利于預(yù)測模型的深入分析。WFS 是在所有特征組合中搜索出預(yù)測模型性能最佳的特征子集。理論上，假設(shè)軟件模塊有K個特征，那么采用WFS方法搜索其特征子集所對應(yīng)的解空間為2K,并且通過任意特征子集所構(gòu)建的SDP模型的性能也是未知的。因此，模型的性能與算法的先進(jìn)性有著強(qiáng)相關(guān)性。傳統(tǒng)的WFS采用最佳第一搜集(Best First Search)和貪婪搜索(Greedy Step-wise Search)求問題最優(yōu)解，該算法容易陷入局部搜索，因此預(yù)測模型容易出現(xiàn)過擬合現(xiàn)象。

基于搜索的軟件工程是傳統(tǒng)軟件工程和智能計(jì)算交叉的新興研究領(lǐng)域，從問題的解空間出發(fā)，采用智能計(jì)算領(lǐng)域的元啟發(fā)式搜索優(yōu)化算法解決軟件工程相關(guān)問題，能夠?qū)崿F(xiàn)自動化和智能化。文獻(xiàn)[6]針對軟件歷史缺陷數(shù)據(jù)類不平衡的問題，采用了多目標(biāo)布谷鳥搜索MOCS(Multi-Objective Cuckoo Search)技術(shù)，同時以高精確率和低誤報率為優(yōu)化目標(biāo),搜索同胞支持向量機(jī)T-SVM(Twins-Support Vector Machine)模型中的最優(yōu)參數(shù)，并用十折交叉驗(yàn)證方法評估了模型性能，最終獲得優(yōu)化后的軟件缺陷預(yù)測模型。文獻(xiàn)[7]針對構(gòu)建軟件預(yù)測模型面對二八規(guī)則的類不平衡問題，對2組多目標(biāo)函數(shù)、3種多目標(biāo)選擇策略分別展開了研究，驗(yàn)證當(dāng)面對數(shù)據(jù)類不平衡問題時，多目標(biāo)演化算法在以哪種評估指標(biāo)作為適應(yīng)度函數(shù)時，軟件缺陷預(yù)測模型表現(xiàn)更好。文獻(xiàn)[8]首次應(yīng)用多目標(biāo)搜索技術(shù)構(gòu)建軟件缺陷預(yù)測模型。該方法搜索更少的特征數(shù)的同時能夠獲得更好的SDP模型性能。實(shí)驗(yàn)結(jié)果表明，該方法應(yīng)對維度災(zāi)難問題取得了很好的效果。

文獻(xiàn)[9]針對數(shù)據(jù)維度爆炸問題，比較分析了現(xiàn)有的采用群智能算法預(yù)測模型的效果，相比遺傳算法GA(Genetic Algorithm)和粒子群優(yōu)化PSO(Particle Swarm Optimization)算法，螢火蟲算法FA(Firefly Algorithm)[10]的效果更好?；谏鲜鲈?，文獻(xiàn)[9]采用FA對軟件數(shù)據(jù)進(jìn)行特征選擇,以改善預(yù)測模型的工作效率。與過去單純以某種評估指標(biāo)作為適應(yīng)度函數(shù)有所不同，文獻(xiàn)[9]在F-Measure評估指標(biāo)基礎(chǔ)上，嵌入了特征選擇數(shù)參數(shù)，使得特征選擇數(shù)最小化的同時預(yù)測模型性能表現(xiàn)最優(yōu)化。但是，文獻(xiàn)[9]的工作仍然存在一定的局限性，雖然能同時優(yōu)化相沖突的多個目標(biāo)，與直接使用多目標(biāo)優(yōu)化算法相比，在最優(yōu)解搜索效率以及搜索的最優(yōu)解方面存在很大的改進(jìn)空間。

文獻(xiàn)[11]首次應(yīng)用多目標(biāo)優(yōu)化技術(shù)構(gòu)建跨項(xiàng)目軟件缺陷預(yù)測模型。文獻(xiàn)[12]針對當(dāng)前跨項(xiàng)目預(yù)測存在的2個焦點(diǎn)問題(即特征維度爆炸和軟件歷史數(shù)據(jù)噪聲)展開研究。為降低訓(xùn)練數(shù)據(jù)集噪聲對預(yù)測模型性能的影響，采用最鄰近過濾方法，并嵌入經(jīng)典的多目標(biāo)非支配排序遺傳算法NSGA-II(Nondominated Sorting Genetic Algorithm-II)優(yōu)化選擇實(shí)例數(shù)據(jù)集作為訓(xùn)練集。同時，為應(yīng)對軟件特征數(shù)據(jù)冗余與大量無關(guān)特征數(shù)據(jù)等問題，文獻(xiàn)[11]提出的模型在保障預(yù)測模型質(zhì)量的前提下，有效地降低了數(shù)據(jù)維度和特征數(shù)，并提高了預(yù)測模型的工作效率。

上述研究表明，優(yōu)化算法已經(jīng)滲透到構(gòu)建軟件缺陷預(yù)測模型的方方面面，例如面對類不平衡問題的數(shù)據(jù)預(yù)處理、特征選擇和模型分類器等，并且顯示出獨(dú)有的多目標(biāo)優(yōu)化能力。

2.2 基于代理模型的智能算法

代理模型是輔助進(jìn)化算法的一種機(jī)制，該機(jī)制采用黑箱設(shè)計(jì)規(guī)則而受到廣泛使用。它通過保存優(yōu)化算法個體的演化過程記錄生成離線數(shù)據(jù)，并通過離線數(shù)據(jù)擬合演化方程式，從而能夠估算輸入的新個體適應(yīng)度值。因此，在實(shí)際演化過程中，部分個體通過代理模型進(jìn)行計(jì)算，可以達(dá)到降低計(jì)算復(fù)雜度的目的。同時，代理模型可以有效地輔助進(jìn)化算法優(yōu)化實(shí)際問題，從而實(shí)現(xiàn)較低的成本。此外，Regis[13]提出代理輔助的進(jìn)化規(guī)劃EP(Evolutionary Programming)算法用于黑箱優(yōu)化，可用于具有許多黑箱不等式約束的高維問題，該算法在性能上比傳統(tǒng)的EP算法更好。

為解決實(shí)際優(yōu)化問題，評估函數(shù)是一個嚴(yán)峻的挑戰(zhàn)，經(jīng)常需要很高的計(jì)算成本。為此，具有輔助代理模型的進(jìn)化算法引起了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注。代理模型不僅增強(qiáng)了進(jìn)化算法，而且還減少了資源消耗。例如，Yu等人[14]引入了代理輔助的PSO優(yōu)化器，其中基于在線數(shù)據(jù)構(gòu)建的徑向基函數(shù)RBF(Radial Basis Function)模型用于選擇最佳解決方案，以減少計(jì)算。Sun等人[15]提出了兩層代理輔助算法，其中采用全局優(yōu)化和一些局部代理輔助模型進(jìn)行適應(yīng)度函數(shù)擬合。該算法可以減少適應(yīng)度函數(shù)評估的次數(shù)，尤其是計(jì)算量大的問題。Vakili等人[16]使用一組可用數(shù)據(jù)和目標(biāo)問題的潛在物理原理構(gòu)造了直接問題的近似函數(shù)，實(shí)現(xiàn)成本低。Pan等人[17]提出利用神經(jīng)網(wǎng)絡(luò)來預(yù)測主導(dǎo)關(guān)系，分開逼近候選解的目標(biāo)值和參考解決方案。此外，Wang等人[18]提出一種新穎的離線數(shù)據(jù)驅(qū)動進(jìn)化算法，將bootstrap采樣技術(shù)用于提取訓(xùn)練數(shù)據(jù)集，這些數(shù)據(jù)集構(gòu)建一個RBF替代模型庫，通過RBF模型計(jì)算適應(yīng)度值，最終降低了計(jì)算復(fù)雜度。

基于上述文獻(xiàn)的調(diào)查研究及團(tuán)隊(duì)前期研究工作的積累[19 - 22]，本文首次將嵌入代理模型的多目標(biāo)優(yōu)化算法引入軟件缺陷預(yù)測。

3 嵌入代理模型的多目標(biāo)螢火蟲算法構(gòu)建軟件缺陷預(yù)測模型

針對降低軟件歷史數(shù)據(jù)的維度和提高穩(wěn)定的預(yù)測性能目標(biāo)，同時最大程度降低模型計(jì)算復(fù)雜度，本文采用嵌入代理模型的多目標(biāo)螢火蟲算法SMO-MSFFA(Surrogate-assisted Multi-Objective Multiple Strategies FireFly Algorithm)構(gòu)建軟件缺陷預(yù)測模型，如圖1所示。

Figure 1 Framework of software defect prediction based on SMO-MSFFA algorithm圖1 基于SMO-MSFFA算法的軟件缺陷預(yù)測框架

該模型主要由4個模塊構(gòu)成：(1)經(jīng)過數(shù)據(jù)預(yù)處理技術(shù)的數(shù)據(jù)庫；(2)嵌入代理模型的多目標(biāo)螢火蟲算法優(yōu)化模塊；(3)機(jī)器學(xué)習(xí)算法分類器；(4)ROC曲線下面積AUC(Area Under an ROC Curve)評價模塊。

3.1 數(shù)據(jù)預(yù)處理

研究者普遍使用的公開評測數(shù)據(jù)集有PROMISE Repository[23]、NASA MDP(Metrics Data Program of the National Aeronautics and Space Administration)[24]、AEEEM(Apache Lucene, Eclipse JDT Core, Eclipse PDE UI, Equinox framework, Mylyn)[25]和Relink[26]等。這些數(shù)據(jù)集應(yīng)用各種粒度的度量方法收集數(shù)據(jù)準(zhǔn)確的特征信息。源數(shù)據(jù)集需通過各種數(shù)據(jù)預(yù)處理技術(shù)進(jìn)行降噪、歸一化后，才能作為模型的數(shù)據(jù)輸入源。

本文首先調(diào)用isnan函數(shù)保留數(shù)值型數(shù)據(jù)，去除非數(shù)值型數(shù)據(jù)；接著調(diào)用mapminmax對數(shù)據(jù)進(jìn)行歸一化，將矩陣數(shù)據(jù)集每行數(shù)據(jù)值映射在[0,1]。

3.2 基于代理模型的多目標(biāo)算法

在本文提出的基于SMO-MSFFA軟件缺陷預(yù)測方法中，最關(guān)鍵的步驟是采用代理模型的多目標(biāo)算法進(jìn)行特征選擇，盡量降低冗余或無關(guān)特征對軟件缺陷預(yù)測模型的負(fù)面影響。SMO-MSFFA算法框架如圖2所示。

Figure 2 Framework of the SMO-MSFFA algorithm圖2 SMO-MSFFA算法框架

采用MSFFA(FireFly Algorithm with Multiple Strategies)算法[27]對相應(yīng)的數(shù)據(jù)集進(jìn)行特征子集的搜索，搜索過程中保存所有特征子集及其所對應(yīng)的個體適應(yīng)度值(即模型性能評估的返回值)，并生成離線數(shù)據(jù)?；陔x線數(shù)據(jù)，采用代理模型近似擬合評價函數(shù)方程式。新個體的適應(yīng)度值可通過該方程式直接進(jìn)行估算，從而輔助FA進(jìn)行特征選擇。在優(yōu)化過程中，部分個體評價函數(shù)通過代理模型進(jìn)行離線計(jì)算，剩余個體評價函數(shù)通過多目標(biāo)優(yōu)化算法在線計(jì)算。以FA為例，在數(shù)據(jù)集KC1上采用SVM訓(xùn)練預(yù)測模型，構(gòu)建代理模型的具體步驟如下所示：(1)在數(shù)據(jù)集KC1上，采用FA搜索特征子集并通過SVM訓(xùn)練SDP模型，以SDP模型的性能評估值作為特征子集對應(yīng)的適應(yīng)度值，保存演化過程中一定數(shù)量的個體及適應(yīng)度值并生成離線數(shù)據(jù)集；(2)調(diào)用RBF模型依據(jù)離線數(shù)據(jù)集擬合FA演化方程式，并保存方程式所有參數(shù)值；(3)調(diào)用演化參數(shù)計(jì)算新個體的適應(yīng)度值。

為了從完整的特征集中獲取合理的特征子集，在FA的特征選擇過程中，維數(shù)的大小與給定數(shù)據(jù)集中的屬性數(shù)相同。所有維度變量值都限制在[0，1]內(nèi)，如果隨機(jī)值小于替代概率，并且當(dāng)變量值接近1時，則在分類中選擇其對應(yīng)的特征作為候選值，如式(1)所示。如果通過代理模型進(jìn)行計(jì)算，則不會對變量值進(jìn)行任何處理。

(1)

其中，fij表示第i個軟件模塊中第j個特征是否被選擇，當(dāng)隨機(jī)數(shù)Xij大于或等于0.5時，該特征被標(biāo)記為選中，否則標(biāo)記為不選中。

如式(2)所示的特征選擇比率feature作為多目標(biāo)螢火蟲算法MOFA(Multi-objective Firefly Algorithm)的目標(biāo)之一進(jìn)行優(yōu)化搜索，代理模型作為輔助進(jìn)行離線計(jì)算，構(gòu)建的模型達(dá)到了最小化特征數(shù)、降低計(jì)算復(fù)雜度的效果。

(2)

其中，F(xiàn)S表示被選中的特征數(shù)量，AT表示總特征數(shù)量。

采用AUC機(jī)制對SDP模型性能進(jìn)行評價并將其返回值作為個體適應(yīng)度值，是本文方法的另一個優(yōu)化目標(biāo)。在實(shí)際軟件數(shù)據(jù)集中，常常存在類不平衡問題，采用AUC作為模型性能的評價指標(biāo)能夠較好地規(guī)避數(shù)據(jù)類不平衡問題對模型造成的影響。AUC值越大，說明模型性能越好，其計(jì)算方式如式(3)所示：

(3)

其中，positiveclass表示正樣本集合，MM表示正樣本數(shù)，NN表示負(fù)樣本數(shù)，Si表示正樣本預(yù)測值的排序，取值在[1,MM]，rankSi表示排序值為Si的樣本總數(shù)。

采用MSFFA算法作為搜索策略，以feature和fAUC為優(yōu)化目標(biāo)進(jìn)行多目標(biāo)搜索。MSFFA算法規(guī)則如下所示：

(1)隨機(jī)選擇K只螢火蟲組成一個小組，學(xué)習(xí)完后適應(yīng)度值最好的螢火蟲進(jìn)入下一組學(xué)習(xí)，直到最后一個小組完成學(xué)習(xí)。

(2)任意2只相互吸引的螢火蟲，適應(yīng)度值好的螢火蟲進(jìn)入自由模式(如式(4)所示)；若處于自由模式螢火蟲適應(yīng)度值偏差，則進(jìn)入基本模式(如式(5)所示)；若處于自由模式的螢火蟲適應(yīng)度值偏好，保持自由模式。保持自由模式次數(shù)通過參數(shù)times控制，一旦超過設(shè)置的最大次數(shù)，則選擇歷史過程中最差的適應(yīng)度值更新，并切換為基本模式。

Xid(t+1)=

(4)

Xid(t+1)=

(5)

式(4)中，Xrandom指種群中隨機(jī)選擇的個體位置信息，times指當(dāng)前個體處于自由模式學(xué)習(xí)的連續(xù)次數(shù)，v指調(diào)控參數(shù)；式(5)中，Xid表示個體在解空間中第d個維度的位置信息，rij表示螢火蟲i和j的歐氏距離，β0表示r=0時的吸引率，α表示步長因子，ε表示在[0,1]取值的隨機(jī)數(shù)，t表示迭代輪次。

螢火蟲算法[10]是群智能算法的一種，主要依據(jù)設(shè)定的目標(biāo)函數(shù)計(jì)算個體的適應(yīng)度值，個體在解空間中的位置將指代個體的適應(yīng)度值，個體通過位置的移動搜索新的目標(biāo)函數(shù)值。在MSFFA中,原始螢火蟲算法個體位置依據(jù)式(5)更新并定義為基本模式；個體位置更新的新計(jì)算方式如式(4)所示，并定義為自由模式。

3.3 機(jī)器學(xué)習(xí)分類器

在相關(guān)工作介紹中已經(jīng)表明采用機(jī)器學(xué)習(xí)方法構(gòu)建軟件缺陷預(yù)測模型分類器是主流技術(shù)之一,其中KNN(K-Nearest Neighbor)、RF(Random Forest)和SVM(Support Vector Machine)分別在查全率、查準(zhǔn)率和準(zhǔn)確值評價指標(biāo)上表現(xiàn)最為穩(wěn)定[28]。為充分驗(yàn)證本文所提方法的獨(dú)立性與有效性，分別采用這3種技術(shù)構(gòu)建模型分類器。

(1)KNN分類器，給定一個軟件缺陷預(yù)測訓(xùn)練數(shù)據(jù)集,對新輸入的實(shí)例,采用歐幾里得距離對量化后的特征數(shù)據(jù)進(jìn)行考量，在訓(xùn)練數(shù)據(jù)集中找到與該實(shí)例最近鄰的K個實(shí)例,這K個實(shí)例的多數(shù)屬于有缺陷或無缺陷類,就把該輸入實(shí)例分類到對應(yīng)的類中。

(2)RF分類器，給定一個軟件缺陷預(yù)測訓(xùn)練數(shù)據(jù)集,隨機(jī)選擇樣本和特征集，通過迭代找到最小誤差率模型的特征排序后，對新的數(shù)據(jù)按照模型特征排序進(jìn)行分類。

(3)SVM分類器，給定一個軟件缺陷預(yù)測訓(xùn)練數(shù)據(jù)集，找到一個超平面，使得附近的不同類別且被正確分類的數(shù)據(jù)點(diǎn)離該超平面都比較遠(yuǎn)，對新的數(shù)據(jù)按照此平面函數(shù)進(jìn)行分類。

這3種分類器在面對數(shù)據(jù)類不平衡及數(shù)據(jù)維度災(zāi)難時，分類性能往往表現(xiàn)不夠理想。為提高此類分類器性能，本文采用多目標(biāo)群智能算法搜索最優(yōu)的特征子集，模型評價指標(biāo)AUC和選擇的特征維度最小化為本文構(gòu)建SDP模型的目標(biāo)。同時，考慮群智能算法高昂的計(jì)算成本，本文嵌入代理模型以降低分類器的重復(fù)使用率，提高SDP工作效率。

3.4 SMO-MSFFA算法構(gòu)建SDP模型

利用SMO-MSFFA算法構(gòu)建SDP模型包括以下步驟：

(1)數(shù)據(jù)預(yù)處理模塊：輸入原始數(shù)據(jù)集，并進(jìn)行降噪和歸一處理，生成新的數(shù)據(jù)集。

(2)模型分類器模塊：導(dǎo)入新的數(shù)據(jù)集，采用十折交叉驗(yàn)證訓(xùn)練模型。

(3)代理模型模塊：調(diào)入模型分類器，基于MSFFA算法搜索最優(yōu)AUC值及對應(yīng)的特征比率，保存所有個體搜索記錄并生成離線數(shù)據(jù)。根據(jù)離線數(shù)據(jù)擬合演化方程；

(4)軟件缺陷預(yù)測主模塊：

Step1導(dǎo)入數(shù)據(jù)集并調(diào)入數(shù)據(jù)預(yù)處理模塊生成新數(shù)據(jù)集。

Step2初始化種群。

Step3設(shè)定多目標(biāo)函數(shù)：

minF(x)={feature,1-fAUC}

Step4設(shè)定迭代終止條件并開始演化。

Step5部分個體輸入代理模型模塊離線搜索特征選擇比例feature和SDP模型性能評價返回值fAUC。

Step6:剩余個體調(diào)入模型分類器模塊。并采用MSFFA算法在線搜索feature和fAUC。

Step7判斷是否達(dá)到迭代終止條件,未達(dá)到終止條件跳轉(zhuǎn)至Step 5。

Step8輸出feature和fAUC。

Step9結(jié)束。

本文針對FA與MSFFA算法的時間復(fù)雜度進(jìn)行了對比分析。假設(shè)一個含N個個體的螢火蟲群體，F(xiàn)A的個體更新計(jì)算時間為T1，個體適應(yīng)度值計(jì)算時間為T2，最大迭代次數(shù)為M，那么FA的計(jì)算時間為O(M*N*N*(T1+T2)，其時間復(fù)雜度可表示為O(N2)。MSFFA個體更新計(jì)算時間為T3，個體適應(yīng)度值計(jì)算時間為T2，最大迭代次數(shù)為M，那么MSFFA的計(jì)算時間為O(M*(N/K)*(N/K)*K*(T3+T2)),其時間復(fù)雜度可表示為O(N2/K)。很明顯，MSFFA的時間復(fù)雜度優(yōu)于FA的，其大小取決于參數(shù)K的值(分組的數(shù)量)。

4 實(shí)驗(yàn)驗(yàn)證

本節(jié)對提出的SMO-MSFFA算法構(gòu)建軟件缺陷預(yù)測模型的有效性開展實(shí)證研究。通過和較優(yōu)的MOFA和NSGA-II的比較，面對歷史數(shù)據(jù)的類不平衡及較高特征維度問題時，驗(yàn)證本文方法在模型性能、特征選擇和計(jì)算復(fù)雜度方面的優(yōu)劣性。

4.1 實(shí)驗(yàn)過程

本文以NASA[23]中數(shù)據(jù)集PC1、MC1和KC1作為數(shù)據(jù)源輸入，具體信息如表1所示。

Table 1 Details of PC1,MC1 and KC1 in NASA dataset

表1中的數(shù)據(jù)集缺陷分布特征滿足八二原則，即類不平衡問題突出，并且數(shù)據(jù)特征維度比較大，數(shù)據(jù)規(guī)模分布在不同層級，契合以改善類不平衡問題及降低數(shù)據(jù)特征維度為目標(biāo)構(gòu)建軟件缺陷預(yù)測的研究工作。

為充分驗(yàn)證本文算法構(gòu)建的模型性能表現(xiàn)，分別與純機(jī)器學(xué)習(xí)方法、FA[29]、MOFA[30]和NSGA-II[31]算法構(gòu)建的軟件缺陷預(yù)測模型進(jìn)行比較。同時，考慮到分類器給模型帶來的不確定性影響，都分別采用了RF、SVM和KNN作為模型分類器。

群智能算法個體數(shù)越大、迭代次數(shù)越多，搜索最優(yōu)方案越好，但是計(jì)算復(fù)雜度也越高。為驗(yàn)證本文方法的性能，所有比較算法參數(shù)設(shè)定等同，所有群智能算法個體數(shù)均設(shè)置為20，迭代總數(shù)(The Maximum number of iterations)設(shè)置為10。此外，其他參數(shù)和算法結(jié)構(gòu)的設(shè)計(jì)與原始設(shè)計(jì)相同。所有實(shí)驗(yàn)均在具有3.60 GHz四核處理器和8 GB RAM的Windows 10計(jì)算機(jī)上完成，所有算法均在Matlab R2016b中實(shí)現(xiàn)。

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

本文分3組實(shí)驗(yàn)在不同的數(shù)據(jù)集上驗(yàn)證了SMO-MSFFA算法的有效性。

第1組實(shí)驗(yàn)：完成了機(jī)器學(xué)習(xí)方法、FA、MO-FA、NSGA-II、MO-MSFFA、SMO-MSFFA優(yōu)化算法在數(shù)據(jù)集PC1上構(gòu)建的軟件缺陷預(yù)測模型的性能驗(yàn)證工作，模型的AUC值、特征選擇比率和計(jì)算耗時如表2所示。

Table 2 Results of software defect prediction on PC1 dataset

在表2中，面對類不平衡且特征維度較大的數(shù)據(jù)集時，單純采用機(jī)器學(xué)習(xí)構(gòu)建的預(yù)測模型性能接近隨機(jī)預(yù)測(AUC值為0.5表明隨機(jī)猜測)。當(dāng)采用單目標(biāo)FA構(gòu)建模型時，預(yù)測模型性能得到了很大的提升(AUC值分別為0.98,0.82和1)，但是特征維度選擇比率改善并不理想且計(jì)算耗時相對較長。MO-FA在實(shí)現(xiàn)數(shù)據(jù)特征維度減少的同時(特征選擇比率分別為0.2,0.27和0.27)仍然能保持預(yù)測模型較好的性能(AUC值分別為0.83,0.74和0.94)，但是較明顯的缺點(diǎn)是計(jì)算耗時在增加。采用經(jīng)典的多目標(biāo)優(yōu)化算法NSGA-II構(gòu)建的預(yù)測模型計(jì)算耗時得到很大的改善。以RF和SVM為例，特征選擇比率為0.36時模型AUC值能達(dá)到0.9，當(dāng)特征選擇比率為0.2時模型AUC值降低至0.58。當(dāng)采用改進(jìn)的多目標(biāo)螢火蟲算法MO-MSFFA構(gòu)建預(yù)測模型時，模型性能的提升和特征維度的減少都獲得了較好的表現(xiàn)，同時計(jì)算耗時相對FA、MO-FA有了明顯的改善，但是和NSGA-II相比有一定的差距。本文提出的代理模型多目標(biāo)螢火蟲算法SMO-MSFFA構(gòu)建的模型在性能上得到進(jìn)一步提升，和同類多目標(biāo)優(yōu)化算法相比，所有分類器均獲得最佳AUC值，在KNN分類器上獲得了特征選擇最佳比率0.25，在SVM和KNN分類器上獲得了最短的計(jì)算耗時(分別為44 s和13 s)。各算法的AUC值和特征選擇比率比較圖如圖3和圖4所示。

Figure 3 AUC values of SDP models based on PC1 dataset圖3 PC1數(shù)據(jù)集上的SDP模型AUC值

Figure 4 Feature selection ratio of SDP models on PC1 dataset圖4 PC1數(shù)據(jù)集上的SDP模型特征選擇比率

通過第1組實(shí)驗(yàn)發(fā)現(xiàn)，應(yīng)用優(yōu)化算法優(yōu)化軟件缺陷預(yù)測是一種行之有效的方法，但是計(jì)算耗時增長非常明顯，相對而言NSGA-II和本文算法綜合表現(xiàn)較好。為了進(jìn)一步驗(yàn)證SMO-MSFFA的性能，繼續(xù)選擇NSGA-II進(jìn)行比較，分別在中等規(guī)模數(shù)據(jù)集KC1及大規(guī)模數(shù)據(jù)集MC1上開展軟件缺陷預(yù)測實(shí)驗(yàn)。

第2組實(shí)驗(yàn)：完成了機(jī)器學(xué)習(xí)方法、NSGA-II、SMO-MSFFA優(yōu)化算法在數(shù)據(jù)集KC1上構(gòu)建的軟件缺陷預(yù)測模型的性能驗(yàn)證工作，模型的AUC值、特征選擇比率和計(jì)算耗時如表3所示。

Table 3 Results of software defect prediction on KC1 dataset

表3結(jié)果表明，與NSGA-II算法相比，雖然兩者的AUC均值比較接近(相差0.01)，但本文算法在各種分類器上的性能更穩(wěn)定(均為0.86)。另外，特征選擇比率均得到了較大程度的改善，在3種分類器模型中分別降低了0.33,0.19和0.04。尤其是3種分類器的計(jì)算耗時分別縮短了425 s、158 s和14 s。由此可見，當(dāng)數(shù)據(jù)規(guī)模增大一倍時，本文算法在各方面的性能優(yōu)勢很明顯。

第3組實(shí)驗(yàn)：完成了機(jī)器學(xué)習(xí)方法、NSGA-II、SMO-MSFFA優(yōu)化算法在數(shù)據(jù)集MC1上構(gòu)建的軟件缺陷預(yù)測模型的性能驗(yàn)證工作，模型的AUC值、特征選擇比率和計(jì)算耗時如表4所示。

Table 4 Results of software defect prediction on MC1 dataset

表4結(jié)果表明，伴隨著模塊規(guī)模的急劇增大，在缺陷模塊占比更低的數(shù)據(jù)集MC1上，SMO-MSFFA算法在RF分類器上AUC值及特征比率表現(xiàn)不如NSGA-II算法，但在SVM及KNN分類器上仍然保持著高性能、較低的特征選擇比率及低耗時的優(yōu)勢。綜合3種分類器的平均性能表現(xiàn)，本文提出的算法全面超過了NSGA-II,AUC值超出0.09，特征選擇比率低0.05，計(jì)算耗時節(jié)省431 s。由此可見，面對超大數(shù)據(jù)集時，本文提出的算法性能優(yōu)勢更加明顯。

NSGA-II與本文提出的算法對比結(jié)果如圖5～圖7所示。

Figure 5 AUC values of SDP models on MC1 dataset圖5 MC1數(shù)據(jù)集上的SDP模型AUC值

Figure 6 Feature selection ratio of SDP models on MC1 dataset圖6 MC1數(shù)據(jù)集上的SDP模型的特征選擇比率

Figure 7 Computational cost of SDP models on MC1 dataset圖7 MC1數(shù)據(jù)集上的SDP模型時間耗費(fèi)

圖5～圖7表明，NSGA-II算法在RF分類器上的AUC值和特征選擇比率優(yōu)于本文算法的，在SVM和KNN分類器上所有性能都不如本文算法。

3組實(shí)驗(yàn)結(jié)果表明，在不同的分類器上構(gòu)建的多目標(biāo)軟件缺陷預(yù)測模型在AUC性能、特征選擇比率和計(jì)算耗時上各有利弊。與NSGA-II算法相比，本文算法AUC均值分別提升0.17,-0.01和0.09，平均特征選擇比率降低0.08，0.17和0.05，平均耗時縮短了-131 s,199 s和431 s?；诓煌瑪?shù)據(jù)集和不同的分類器，本文提出的SMO-MSFFA能有效地同時解決類不平衡問題和數(shù)據(jù)特征維度問題所帶來的負(fù)面影響。隨著數(shù)據(jù)集規(guī)模變大，SMO-MSFFA的性能穩(wěn)定性及低耗時的優(yōu)勢越來越明顯。以KC1與MC1為例，數(shù)據(jù)模塊數(shù)由2 107增長至9 466時，NSGA-II平均性能下降了0.1，而SMO-MSFFA只下降了0.004。NSGA-II計(jì)算耗時增加了850 s，而SMO-MSFFA的計(jì)算耗時只增加了618 s。

5 結(jié)束語

當(dāng)歷史數(shù)據(jù)表現(xiàn)出類不平衡和特征維度問題時，采用多目標(biāo)進(jìn)化算法能明顯提升軟件缺陷預(yù)測性能，較明顯的缺點(diǎn)是增加了計(jì)算復(fù)雜度。本文首次提出結(jié)合代理模型的多目標(biāo)螢火蟲算法構(gòu)建軟件缺陷預(yù)測模型。與現(xiàn)有應(yīng)用在軟件缺陷預(yù)測的進(jìn)化算法相比，本文算法具有更加穩(wěn)定的模型性能，更低的特征選擇比率和計(jì)算耗時。特別地，隨著數(shù)據(jù)規(guī)模的增大，較短的計(jì)算耗時優(yōu)勢也越來越明顯。因此，本文提出SMO-MSFFA是一種較理想的軟件缺陷預(yù)測算法，可以改善數(shù)據(jù)類不平衡、維度爆炸和較高的計(jì)算復(fù)雜度所帶來的問題。開展基于代理模型其它高效搜索技術(shù)在跨項(xiàng)目和即時軟件缺陷預(yù)測應(yīng)用場景的研究將是后續(xù)的工作。