基于量子免疫克隆BP算法的軟件缺陷預(yù)測(cè)模型

姜 玥，王 帥，吳克奇，謝 琪，崔夢(mèng)天

(西南民族大學(xué)計(jì)算機(jī)系統(tǒng)國家民委重點(diǎn)實(shí)驗(yàn)室，四川 成都 610041)

軟件在開發(fā)過程中不可避免地會(huì)產(chǎn)生各種缺陷問題.因此，軟件質(zhì)量問題也愈發(fā)重要.如何設(shè)計(jì)出高質(zhì)量、可靠的軟件產(chǎn)品成為當(dāng)下業(yè)界的重要研究問題.軟件缺陷的分布是不均衡的，因此，軟件缺陷預(yù)測(cè)技術(shù)對(duì)于快速開發(fā)軟件和提高軟件系統(tǒng)的質(zhì)量具有重要意義.文獻(xiàn)[1]提出了基于樸素貝葉斯(NB)的軟件缺陷預(yù)測(cè)模型.文獻(xiàn)[2]整合了SVM和粒子群優(yōu)化算法，建立軟件缺陷預(yù)測(cè)模型.文獻(xiàn)[3]利用優(yōu)化的PSO算法調(diào)整BP神經(jīng)網(wǎng)絡(luò).文獻(xiàn)[4]提出了將改進(jìn)的多種群量子遺傳算法用于優(yōu)化BP神經(jīng)網(wǎng)絡(luò)，建立網(wǎng)絡(luò)流量預(yù)測(cè)模型.文獻(xiàn)[5]提出了QPSO-BP的GNSS高程轉(zhuǎn)換方法.文獻(xiàn)[6]提出了基于優(yōu)化問題的量子遺傳算法.文獻(xiàn)[7]采用量子粒子群算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)，應(yīng)用于軟件缺陷預(yù)測(cè).以上各種方法都在對(duì)標(biāo)準(zhǔn)BP神經(jīng)網(wǎng)絡(luò)的優(yōu)化改進(jìn)，避免在實(shí)際應(yīng)用中BP神經(jīng)網(wǎng)絡(luò)算法的不足.為了避免標(biāo)準(zhǔn)BP神經(jīng)網(wǎng)絡(luò)算法在軟件缺陷預(yù)測(cè)中，學(xué)習(xí)能力有限，準(zhǔn)確率和精確率不理想，易陷入局部最優(yōu)，本文提出將量子免疫克隆算法和標(biāo)準(zhǔn)BP神經(jīng)網(wǎng)絡(luò)算法結(jié)合，應(yīng)用于軟件缺陷預(yù)測(cè)中，取得了較好的學(xué)習(xí)效果.

1 免疫算法

免疫算法(Immune Algorithm，IA)的大致算法思路如下[8]:1)分析待求解問題，通過透徹的分析獲得該問題的基本特征信息；2)處理該特征信息，把該特征信息經(jīng)過必需的步驟轉(zhuǎn)化為用來解析回答待求解問題的方案；3)將此方案已確定的規(guī)則轉(zhuǎn)變?yōu)槊庖咚阕舆M(jìn)行操作.其中，人工免疫算法解決問題重點(diǎn)關(guān)注以下三部分:

1)抗原識(shí)別和初抗體的產(chǎn)生.根據(jù)待解決問題的基本特點(diǎn)，設(shè)計(jì)適合的編碼規(guī)則，并按照該編碼規(guī)則生成初抗體種群.

2)抗體評(píng)估.分別采用合適的計(jì)算公式計(jì)算抗體適應(yīng)度和抗體濃度，據(jù)此評(píng)價(jià)抗體的質(zhì)量，從中選出優(yōu)勢(shì)抗體，更新淘汰劣勢(shì)抗體.

3)克隆選擇.采用免疫選擇，克隆變異和種群更新等免疫算子來模仿生物機(jī)體免疫應(yīng)答中的操作，得出基于免疫系統(tǒng)的克隆選擇原理的種群進(jìn)化方法，從而達(dá)到對(duì)目標(biāo)問題的尋優(yōu)搜索.

2 量子免疫算法

量子免疫算法(Quantum Immune Algorithm，QIA)是將量子計(jì)算理論與一般的人工免疫算法相結(jié)合而提出的一種新型概率進(jìn)化算法[9].該算法將量子計(jì)算的高效并行性引入傳統(tǒng)免疫算法中，使其抗體種群多樣性得到保障的同時(shí)，提高收斂速度，得到全局最優(yōu)解；采用量子比特的概率幅對(duì)抗體進(jìn)行量子編碼，使抗體處于疊加狀態(tài).同時(shí)，將抗體通過量子旋轉(zhuǎn)門和量子非門進(jìn)行克隆變異操作，使抗體種群得到優(yōu)化.

混沌現(xiàn)象是自然界中廣泛存在的一種非線性現(xiàn)象，其具有隨機(jī)性的同時(shí)又兼具內(nèi)在規(guī)律.計(jì)算量子旋轉(zhuǎn)門旋轉(zhuǎn)角大小時(shí)，利用混沌系統(tǒng)原理，本文創(chuàng)新性地引入混沌優(yōu)化系統(tǒng)中廣泛應(yīng)用的Logistic映射:

其中，μ是混沌吸引子，取值范圍為[0，4]，當(dāng)μ＝4時(shí)，系統(tǒng)進(jìn)入混沌狀體，產(chǎn)生混沌變量△n，其值在[0，1]區(qū)間內(nèi)，△0取值范圍在(0，1)的任意數(shù)值.

由此定義旋轉(zhuǎn)角大小為:

其中，θ0調(diào)節(jié)因子，由查詢表獲得；△由式(1)得到；t為當(dāng)前進(jìn)化代數(shù)，T為總進(jìn)化代數(shù).在克隆更新時(shí)，抗體的適應(yīng)度與最優(yōu)抗體適應(yīng)度差別越大，則旋轉(zhuǎn)門的角度越大，其大小會(huì)隨著搜索的進(jìn)行而縮小.

3 軟件缺陷預(yù)測(cè)模型的建立

3.1 量子免疫克隆算法

量子免疫克隆算法(Quantum Immune Clonal Algorithm，QIC)中，設(shè)量子抗體種群Q(t)＝{q1t，q2t，...，qnt}，n為抗體種群大小，t為算法進(jìn)化次數(shù)，qit為第i個(gè)量子編碼抗體，m為量子抗體比特的長(zhǎng)度[12].

QIC的算法步驟如下，流程圖如圖1所示.

圖1 量子免疫克隆算法流程圖Fig.1 Flow chart of quantum immune clonal algorithm

1)初始化量子抗體種群，將n個(gè)抗體的2*m*n個(gè)概率幅均初始化為1/Sqrt(2)，即每個(gè)抗體均以概率1/Sqrt(2m)處于所有可能狀態(tài)的疊加態(tài)中，生成并初始化第一代量子種群Q(t)，其中Sqrt為開根號(hào)函數(shù).

2)對(duì)第一代抗體逐一測(cè)量，得到對(duì)應(yīng)的確定解.觀察Q(t)的狀態(tài)生成二進(jìn)制解集P(t)＝{p1t，p2t，...pmt}，其中每個(gè)解pjt均(j＝1，2，...，m)為二進(jìn)制串，長(zhǎng)度位m，其值由量子比特幅度｜αit｜2或｜βit｜2(i＝1，2，...，m)計(jì)算所得，二進(jìn)制的構(gòu)成是產(chǎn)生隨機(jī)數(shù)R[1，0]，若R＞｜αit｜2，取1；，否則取0；

3)計(jì)算解P(t)的適應(yīng)度，獲得當(dāng)前最優(yōu)解.

4)根據(jù)適應(yīng)度值，對(duì)優(yōu)勢(shì)抗體進(jìn)行量子克隆選擇.

5)量子非門對(duì)抗體進(jìn)行變異操作.

6)將抗體群通過量子旋轉(zhuǎn)門進(jìn)行更新進(jìn)化操作.將二進(jìn)制解集P(t)與當(dāng)前最優(yōu)解抗體進(jìn)行比較，并使用量子旋轉(zhuǎn)門R更新抗體群Q(t).

7)轉(zhuǎn)(2)，并且選擇P(t)中的當(dāng)前最優(yōu)解，如果該抗體解比當(dāng)下最優(yōu)解更優(yōu)，則更新記憶庫，將其加入到記憶庫中，來代替記憶庫中原來的抗體，t＝t＋1，當(dāng)滿足條件或達(dá)到最大進(jìn)化代數(shù)時(shí)，算法結(jié)束.

3.2 軟件缺陷預(yù)測(cè)模型

本文采用量子免疫克隆BP神經(jīng)網(wǎng)絡(luò)算法(Quantum Immune Clonal Algorithm Based on BP，QICBP)[10]，建立軟件缺陷預(yù)測(cè)模型(SDPM-QICBP).該模型主要包括三部分:①對(duì)待預(yù)測(cè)的數(shù)據(jù)集進(jìn)行預(yù)處理，使用歸一法進(jìn)行處理，提升算法效率；②執(zhí)行量子免疫克隆算法，在全局范圍內(nèi)搜索，獲取最優(yōu)值并使用該值對(duì)BP神經(jīng)網(wǎng)絡(luò)的權(quán)值和閾值進(jìn)行優(yōu)化；③將處理后的數(shù)據(jù)集分為學(xué)習(xí)樣本與測(cè)試樣本，利用所提出的軟件缺陷預(yù)測(cè)模型進(jìn)行訓(xùn)練和測(cè)試.QICBP算法步驟如下，SDPM-QICBP的流程圖如圖2所示.

圖2 SDPM-QICBP模型流程圖Fig.2 Flow chart of SDPM-QICBP model

1)構(gòu)建BP神經(jīng)網(wǎng)絡(luò)，規(guī)定輸入輸出.對(duì)MDP數(shù)據(jù)集進(jìn)行預(yù)處理，獲得學(xué)習(xí)樣本與測(cè)試樣本.

2)隨機(jī)產(chǎn)生初始種群Q(t)，對(duì)BP神經(jīng)網(wǎng)絡(luò)的權(quán)值和閾值編碼.

3)根據(jù)數(shù)據(jù)集確定適應(yīng)度函數(shù)，計(jì)算適應(yīng)度值，評(píng)估輸出值.

4)將BP神經(jīng)網(wǎng)絡(luò)的輸出進(jìn)行解空間變換，得到初始種群的全局最優(yōu)解.

5)將種群中的抗體的概率幅通過量子旋轉(zhuǎn)門進(jìn)行遺傳操作(克隆選擇和變異)，實(shí)現(xiàn)種群更新.

6)若誤差或者進(jìn)化次數(shù)滿足進(jìn)化要求，則轉(zhuǎn)7)，否則轉(zhuǎn)3).

7)解碼QIC算法搜索的最優(yōu)解，用于BP神經(jīng)網(wǎng)絡(luò)初始權(quán)向量.

8)訓(xùn)練BP神經(jīng)網(wǎng)絡(luò)，直至滿足需要.

算法1(QICBP):基于量子免疫克隆BP算法(Quantum Immune Clonal Algorithm Based on BP，QICBP)輸入:樣本數(shù)據(jù)集輸出:分類集步驟:1.Normalize(Input_train)； //歸一化輸入數(shù)據(jù)2.Normalize(Output_train)； //歸一化輸出數(shù)據(jù)3.CreatBP； //構(gòu)建神經(jīng)網(wǎng)絡(luò)4.t＝0；5.Initialzie； //初始化種群6.ChromeCode； //種群編碼7.Compute_Fitness； //抗體適應(yīng)度評(píng)估8.KeepBestIndividual； //保留最優(yōu)抗體9.While(MinErr＜ε｜｜t＜T) //種群更新10.{t＝t＋1；11.ChromeCode 12.Compute_Fitness；13.Update； //通過量子門更新種群14.KeepBestIndividual；15.}16.x＝Zbest；17.TrainBP； //訓(xùn)練BP神經(jīng)網(wǎng)絡(luò)

算法1中，input_train、output_train是訓(xùn)練輸入、輸出原始數(shù)據(jù)，ε為誤差閾值，T為總進(jìn)化代數(shù)，Zbest為最優(yōu)參數(shù).

命題1算法1的時(shí)間復(fù)雜度為O(N2＋MN2)，其中N為種群大小，三層神經(jīng)元數(shù)量分別為N1，N2和N3，樣本數(shù)為M.

證明:尋找最優(yōu)抗體的過程是雙重循環(huán)，兩層循環(huán)分別掃描N次.因此，量子克隆尋優(yōu)的時(shí)間復(fù)雜度為O(N2).

對(duì)三層BP神經(jīng)網(wǎng)絡(luò)，設(shè)每層神經(jīng)元數(shù)量分別為N1，N2和N3，則M個(gè)樣本的前饋計(jì)算時(shí)間復(fù)雜度是O(M*(N1*N2＋N2*N3))＝O(MN2).

綜上，算法1的時(shí)間復(fù)雜度為O(N2＋MN2).

4 實(shí)驗(yàn)與性能分析

為了驗(yàn)證和比較算法的性能和有效性，將SDPMQICBP模型和傳統(tǒng)方法的實(shí)際運(yùn)行效果進(jìn)行了實(shí)驗(yàn)和討論，采用了Windows10操作系統(tǒng)，Visual Studio2019.

實(shí)驗(yàn)采用NASA提供的MDP軟件缺陷基礎(chǔ)數(shù)據(jù)集[11]，其含有13個(gè)子數(shù)據(jù)集，每一個(gè)都來源于實(shí)際開發(fā)項(xiàng)目，大部分采用C/C＋＋語言編寫.MDP數(shù)據(jù)集擁有良好的真實(shí)性，可以清晰地描述軟件系統(tǒng)內(nèi)部的軟件缺陷信息，且已有多個(gè)機(jī)構(gòu)對(duì)其進(jìn)行了軟件缺陷分析和預(yù)測(cè)等相關(guān)信息.數(shù)據(jù)集的每條記錄作為一個(gè)樣本.數(shù)據(jù)集部分信息如表1所示.由表1知，KC4數(shù)據(jù)集記錄過少，因此，實(shí)驗(yàn)選擇其他12個(gè)子數(shù)據(jù)集.學(xué)習(xí)樣本集和測(cè)試樣本集記錄數(shù)為1∶1，學(xué)習(xí)樣本隨機(jī)選擇[12].

表1 實(shí)驗(yàn)數(shù)據(jù)集Table 1 Experimental dataset

4.1 評(píng)估指標(biāo)

本實(shí)驗(yàn)的性能評(píng)估采用準(zhǔn)確率和精確率，以上指標(biāo)是從混淆矩陣中推導(dǎo)出來的[13-15]，混淆矩陣如表2所示.

表2 混淆矩陣Table 2 Confusion matrix

為了方便描述，定義了以下指標(biāo).

定義1設(shè)TP，F(xiàn)P，F(xiàn)N和TN分別為表4所示.

①(準(zhǔn)確率)設(shè)Acc為準(zhǔn)確率，則

②(精確率)設(shè)Pre為精確率，則

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

對(duì)數(shù)據(jù)集采用歸一化方法進(jìn)行處理，將標(biāo)準(zhǔn)BP神經(jīng)網(wǎng)絡(luò)算法，樸素貝葉斯(Navie Bayes，NB)和QICBP算法建立的軟件缺陷預(yù)測(cè)模型進(jìn)行對(duì)比，分類預(yù)測(cè)結(jié)果如表3所示，標(biāo)準(zhǔn)BP神經(jīng)網(wǎng)絡(luò)算法和QICBP算法迭代次數(shù)如表4所示.

表3 算法預(yù)測(cè)結(jié)果Table 3 The prediction results among BP，NB and QICBP

表4 算法迭代次數(shù)Table 4 The number of iteration between BP and QICBP

由表3知，SDPM-QICBP模型預(yù)測(cè)的準(zhǔn)確性達(dá)到75%以上，其中PC2的預(yù)測(cè)正確率達(dá)到95%，表明SDPM-QICBP模型具有較好的學(xué)習(xí)效果.以子數(shù)據(jù)集CM1為例，QICBP預(yù)測(cè)的準(zhǔn)確率達(dá)到80%且精確度達(dá)到88%，而采用標(biāo)準(zhǔn)BP算法與NB算法后的分類準(zhǔn)確率僅為74%和75%.QICBP算法的性能優(yōu)于標(biāo)準(zhǔn)BP算法與NB算法，即QICBP算法對(duì)軟件缺陷的預(yù)測(cè)能力比標(biāo)準(zhǔn)BP算法與NB算法更強(qiáng)，說明QICBP算法有效.在觀察分析其他子數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果，也可得到同樣的結(jié)論.

實(shí)驗(yàn)結(jié)果的精確率對(duì)比說明QICBP算法的最優(yōu)解具有全局最優(yōu)性，這是其他兩個(gè)傳統(tǒng)算法所不具備的.本文算法在大部分?jǐn)?shù)據(jù)集下，其準(zhǔn)確率和精確度均優(yōu)于其他兩個(gè)傳統(tǒng)算法.

由表1知，子數(shù)據(jù)集MC2共352條記錄，相對(duì)較少，但實(shí)驗(yàn)準(zhǔn)確率也達(dá)到83%，這表明在樣本數(shù)量較少的情況下，QICBP算法依然具有強(qiáng)的穩(wěn)健性，獲得較優(yōu)的預(yù)測(cè)性能.

但是，子數(shù)據(jù)集KC1、PC1等極少數(shù)幾個(gè)的實(shí)驗(yàn)結(jié)果中，QICBP算法的準(zhǔn)確率和精確度并未同時(shí)提高，這是由于該預(yù)測(cè)模型在學(xué)習(xí)和預(yù)處理過程中樣本中正誤模塊數(shù)量的差異造成.

由表4知，QICBP算法和標(biāo)準(zhǔn)BP算法相比，迭代次數(shù)降低11%以上，表明OICBP算法在先對(duì)進(jìn)入BP神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)精選后，會(huì)明顯縮短迭代次數(shù)，找到最優(yōu)解，說明該算法能有效地改善標(biāo)準(zhǔn)BP神經(jīng)網(wǎng)絡(luò)算法用于軟件缺陷預(yù)測(cè).

5 結(jié)論

傳統(tǒng)算法在軟件缺陷預(yù)測(cè)上存在著學(xué)習(xí)能力不足，不能很好地保留優(yōu)勢(shì)抗體，性能指標(biāo)易陷入局部最優(yōu).本文將QIC算法引入到BP神經(jīng)網(wǎng)絡(luò)算法中，發(fā)揮免疫的抗體優(yōu)勢(shì)，利用QIC算法對(duì)進(jìn)入BP神經(jīng)網(wǎng)絡(luò)的參數(shù)精選，設(shè)計(jì)了QICBP算法；將該算法應(yīng)用到軟件缺陷預(yù)測(cè)中，設(shè)計(jì)了SDPM-QICBP模型，取得到較好的結(jié)果.

下一步的工作，將在本文的基礎(chǔ)上，將基因表達(dá)式編程算法引入到BP神經(jīng)網(wǎng)絡(luò)算法中[16]，擴(kuò)大數(shù)據(jù)集范圍，使之在軟件缺陷預(yù)測(cè)上取得更好的性能.