一種改進(jìn)粒子群算法的測試數(shù)據(jù)自動生成方法

安新何明祥

摘要：線性遞減慣性權(quán)重粒子群算法中，搜索后期較小的慣性權(quán)重使粒子具有很強(qiáng)的局部搜索能力。但慣性權(quán)重太小，容易使所有的粒子聚在一起損失多樣性，找到最優(yōu)解的可能性較低，易產(chǎn)生早熟現(xiàn)象。提出了一種利用方差動態(tài)調(diào)整慣性權(quán)重的方法，引入基于適應(yīng)度方差的慣性權(quán)重調(diào)整因子。當(dāng)出現(xiàn)早熟現(xiàn)象時，通過調(diào)整因子適當(dāng)增大慣性權(quán)重的值，以擴(kuò)大搜索范圍，增加找到最優(yōu)解的可能性。當(dāng)未出現(xiàn)早熟現(xiàn)象時，繼續(xù)采用線性遞減慣性權(quán)重策略，加快收斂速度。實驗結(jié)果表明，該算法具有較高的搜索成功率。

關(guān)鍵詞：慣性權(quán)重；早熟收斂；LDWPSO 算法；SPSO算法；搜索成功率

DOIDOI：10.11907/rjdk.161971

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A文章編號文章編號：16727800（2016）009004603

基金項目基金項目：

作者簡介作者簡介：安新（1990-），女，山東泰安人，山東科技大學(xué)計算機(jī)科學(xué)與工程學(xué)院碩士研究生，研究方向為軟件項目管理、軟件測試；何明祥（1969-），男，安徽合肥人，博士，山東科技大學(xué)計算機(jī)科學(xué)與工程學(xué)院副教授、碩士生導(dǎo)師，研究方向為數(shù)據(jù)庫系統(tǒng)、信息處理、人工智能、數(shù)字礦山。本文通訊作者為何明祥。

0引言

軟件測試是發(fā)現(xiàn)軟件缺陷的過程，貫穿于軟件生命周期的各個階段，是保證軟件質(zhì)量的重要手段。軟件測試中大約40%的時間用在測試數(shù)據(jù)設(shè)計階段[1]。隨著軟件復(fù)雜度和軟件規(guī)模的增大，測試開銷和工作量也相應(yīng)增加，傳統(tǒng)的手工生成測試數(shù)據(jù)已不能滿足要求，測試數(shù)據(jù)自動生成對提高測試效率、減少測試開銷具有重要意義。在對測試數(shù)據(jù)自動生成方法的研究中，粒子群算法以其設(shè)置參數(shù)少、簡單易實現(xiàn)、收斂快而受到研究者的青睞。

Shi等[2]提出線性遞減慣性權(quán)重策略，使得搜索初期，粒子具有較好的全局搜索能力，搜索后期具有較好的局部搜索能力。但后期過小的慣性權(quán)重容易使整個粒子群陷入早熟，找到最優(yōu)解的可能性較小；田甜等[3]提出一種非線性動態(tài)調(diào)整慣性權(quán)重策略，解決了線性遞減權(quán)重策略中容易出現(xiàn)的早熟現(xiàn)象。

針對粒子群算法中易出現(xiàn)的早熟問題，本文提出一種基于方差的動態(tài)調(diào)整慣性權(quán)重的粒子群優(yōu)化（FCWPSO）算法。算法思想為：總體上遵循線性遞減慣性權(quán)重策略，當(dāng)出現(xiàn)早熟現(xiàn)象時，通過調(diào)整因子適當(dāng)增大慣性權(quán)重的值，跳出局部極值，擴(kuò)大搜索范圍，增加找到最優(yōu)解的可能性。

1基本粒子群算法

粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法由Eberhart 、Kennedy[3]于1995年提出，基本思想是研究和模擬鳥類的覓食行為。每只鳥相當(dāng)于一個粒子，屬于問題的候選解，飛行空間相當(dāng)于問題的搜索空間，捕食過程相當(dāng)于尋找最優(yōu)解的過程[4]。設(shè)粒子總數(shù)為N，起始狀態(tài)為所有粒子被隨機(jī)分配在D維搜索空間中，每個粒子均有一個D維位置向量Xi=（xi1，xi2，…，xiD）和一個D維速度向量Vi=（vi1，vi2，…，viD），每個粒子通過跟蹤個體極值Pbesti=（pi1，pi2，…，piD）和全局極值Gbest=（g1，g2，…，gD）來更新自身的位置速度。個體極值是該粒子自身搜索到的歷史最優(yōu)值，全局極值是粒子群體搜索到的最優(yōu)值。每個粒子通過不斷更新自身位置和速度找到最優(yōu)解。位置和速度更新見式（1）、式（2）。

Vt+1i=wVti+C1Rand1（）（Pbesti-Xti）+C2Rand2（）（Gbest-Xti）（1）

Xt+1i=Xti+Vt+1i（2）

其中：Vti、Xti分別為第t代中第i個粒子的速度和位置；Vt+1i、Xt+1i分別為第t+1代中第i個粒子的速度和位置；w為慣性權(quán)重，是保持原速度的系數(shù)；C1為粒子追隨自身個體極值的權(quán)重，即粒子對自身的認(rèn)識，一般設(shè)為2；C2為粒子追隨粒子群全局極值的權(quán)重，即粒子對群體的認(rèn)識，一般設(shè)為2；Rand1（）、Rand2（）為0到1之間的隨機(jī)數(shù)；Pbesti為第i個粒子的歷史最優(yōu)值；Gbest為群體的最優(yōu)值。

2基于方差的動態(tài)調(diào)整慣性權(quán)重方案

2.1常用粒子群優(yōu)化算法及存在問題

（1）簡化粒子群優(yōu)化（SPSO）算法。胡旺等[5]指出粒子群的進(jìn)化過程與速度無關(guān)，速度大小可能導(dǎo)致粒子不能沿正確的進(jìn)化方向運動，最終不能有效地找到最優(yōu)解。因此，提出了無速度參數(shù)的簡化粒子群優(yōu)化（Simple Particle Swarm Optimization，SPSO）算法，如式（3）所示，避免了由速度導(dǎo)致的后期收斂慢、精度低的問題，且簡化了粒子進(jìn)化過程。

Xt+1i=wXti+C1Rand1（）（Pbesti-Xti）+C2Rand2（）（Gbest-Xti）（3）

（2）線性遞減慣性權(quán)重粒子群優(yōu)化（LDWPSO）算法。Shi等[2]指出慣性權(quán)重較大，能夠促進(jìn)全局搜索；慣性權(quán)重較小，則促進(jìn)局部搜索。提出了線性遞減慣性權(quán)重的（Linearly Decreasing the inertia weight，LDW）粒子群優(yōu)化算法，如式（4）所示。尋優(yōu)過程中，通過LDW策略，使之從相對較大的值減小為一個較小的值，運行初期，粒子具有較強(qiáng)的全局搜索能力，運行后期，具有較強(qiáng)的局部搜索能力。與固定慣性權(quán)重設(shè)置相比，該算法性能較優(yōu)。

w=wmax-（wmax-wmin）ttmax（4）

其中：wmax為w的最大值；wmin為w的最小值；t為當(dāng)前迭代次數(shù)；tmax為最大迭代次數(shù)。

（3）現(xiàn)有算法存在的問題。早熟收斂或全局收斂時，粒子群都會呈現(xiàn)匯集現(xiàn)象，若此時算法未達(dá)到結(jié)束條件，由于匯集的多樣性喪失，粒子搜索能力下降，導(dǎo)致很難找到最優(yōu)解，搜索成功率較低，這時稱粒子群出現(xiàn)了早熟現(xiàn)象[3，6]。LDWPSO算法后期過小的w使粒子聚集在一起，更易產(chǎn)生早熟現(xiàn)象。

2.2FCWPSO算法

當(dāng)出現(xiàn)早熟現(xiàn)象時，粒子位置相近，因此其適應(yīng)度值也很接近，可采用群體適應(yīng)度方差衡量所有粒子的聚集程度。

本文提出一種基于適應(yīng)度方差的動態(tài)調(diào)整慣性權(quán)重的粒子群優(yōu)化（FCWPSO）算法，即在LDWPSO算法的基礎(chǔ)上，引入一個基于適應(yīng)度方差的慣性權(quán)重（FCW）調(diào)整因子，當(dāng)發(fā)生早熟現(xiàn)象時，通過調(diào)整因子適當(dāng)增大慣性權(quán)重w的值，如式（5）、式（6）、式（7）所示。擴(kuò)大搜索范圍，跳出局部極值，增加找到最優(yōu)解的可能性。當(dāng)沒有出現(xiàn)早熟現(xiàn)象時，繼續(xù)沿用LDW方案，加快收斂速度。

w=wmax-（wmax-wmin）ttmax+ε（5）

ε=1-σ2（6）

σ2=1N∑Ni=1Fi-FavgFmax（7）

其中：ε為慣性權(quán)重調(diào)整因子；σ2為粒子群的適應(yīng)度方差；N為粒子總數(shù)；Fi為第i個粒子的適應(yīng)度值；Favg為所有粒子的適應(yīng)度平均值；為了限制方差的大小，F(xiàn)max取值為：Fmax=max（1，max|Fi-Favg|），（i=1，2，…，N），因此，F(xiàn)i-FavgFmax∈（0，1），σ2∈（0，1）。

計算出粒子群的適應(yīng)度方差后，設(shè)定一個閾值。當(dāng)方差小于該閾值且算法還未達(dá)到結(jié)束條件時，說明出現(xiàn)了早熟現(xiàn)象，需要采取FCW方案，增大慣性權(quán)重w的值，擴(kuò)大搜索范圍。

3基于FCWPSO算法的測試數(shù)據(jù)生成

3.1FCWPSO算法流程

FCWPSO算法流程如圖1所示。首先初始化粒子位置、速度，計算其適應(yīng)值，更新個體極值和全局極值。然后判斷是否達(dá)到結(jié)束條件，若是則算法結(jié)束，否則需要繼續(xù)迭代。計算粒子群體的適應(yīng)度方差，若方差小于指定閾值，表示粒子聚集在一起，但此時并未達(dá)到結(jié)束條件，說明粒子群出現(xiàn)了早熟現(xiàn)象，需要使用調(diào)整因子調(diào)整慣性權(quán)重，若方差大于或等于指定閾值，說明未出現(xiàn)早熟現(xiàn)象，繼續(xù)采用線性遞減慣性權(quán)重策略更新慣性權(quán)重。最后更新粒子位置、速度，開始新一輪迭代，直到滿足結(jié)束條件。

3.2適應(yīng)度函數(shù)構(gòu)造

適應(yīng)度函數(shù)用于評價個體位置的優(yōu)劣，本文采用“分支函數(shù)疊加法[7-8]”構(gòu)造適應(yīng)度函數(shù)。程序中的每個分支都可以用分支謂詞來表示，比如判斷語句“if（x>y）{…}”中的分支謂詞就是x>y，可以把分支謂詞抽象成如下形式：

E1 op E2

其中：E1 、E2為算術(shù)表達(dá)式；op為{<，≤，>，≥，=，≠}中的一個，但不包含and、or、布爾運算符。

分支函數(shù)可以將一個分支謂詞轉(zhuǎn)換成一個實值，即分支函數(shù)值，用以衡量邏輯執(zhí)行路徑和實際執(zhí)行路徑的偏差。幾種常見分支謂詞的分支函數(shù)創(chuàng)建方法如表1所示，表中k為大于0的常數(shù)。

分支函數(shù)疊加法基本思想為：首先確定目標(biāo)路徑，然后在路徑中分支節(jié)點前以插樁方式插入分支函數(shù)f，最后將各個分支函數(shù)相加，得到適應(yīng)度函數(shù)。

假設(shè)目標(biāo)路徑中包含m個分支，n個輸入?yún)?shù)（x1 ，x2 ，…xn ），則分支函數(shù)如式（8）所示。f1=f1（x1，x2，…xn）f2=f2（x1，x2，…xn）…fm=fm（x1，x2，…xn）（8）

以上m個分支函數(shù)相加，得到適應(yīng)度函數(shù)F，如式（9）所示。

F=f1+f2+…+fm（9）

4實驗研究

4.1實驗方案及實驗結(jié)果

以直角三角形判定程序為例，以覆蓋所有分支的路徑作為目標(biāo)路徑，分別采用FCWPSO算法、LDWPSO算法和SPSO算法生成測試數(shù)據(jù)，所生成的測試數(shù)據(jù)為0-100的3個整數(shù)，作為三角形的三條邊，統(tǒng)計每種算法的搜索成功率。

測試方法：記錄粒子數(shù)分別為100、120、140、160、180、200時，3種算法生成的測試數(shù)據(jù)情況，即是否能夠生成構(gòu)成直角三角形的測試數(shù)據(jù)，每組試驗進(jìn)行60次，記錄3種算法在60次實驗中的搜索成功率。

實驗參數(shù)設(shè)置為：C1=C2=2，最大迭代次數(shù)為500次，SPSO算法中，w=0.7；LDWPSO算法中，w從0.7到0.4線性遞減；FCWPSO算法中，總體上采用w從0.7到0.4線性遞減策略，當(dāng)方差<0.1時使用慣性權(quán)重調(diào)整因子ε適度增大w值，擴(kuò)大粒子的搜索范圍，消除早熟。實驗結(jié)果如表2所示。

4.2實驗結(jié)果分析

根據(jù)表2的統(tǒng)計結(jié)果，分析3種算法性能，如圖2所示?？梢钥闯觯現(xiàn)CWPSO算法具有較高的搜索成功率，約為90%，說明其很好地解決了早熟問題，增加了找到最優(yōu)解的可能性。LDWPSO算法和SPSO算法的搜索成功率較低，約為50%，原因是其無法擺脫早熟現(xiàn)象所致，找到最優(yōu)解的可能性較小。本文FCWPSO算法較其它兩種算法具有較高的效率。

5結(jié)語

針對LDWPSO算法搜索后期易產(chǎn)生早熟的問題，本文引入一個基于適應(yīng)度方差的慣性權(quán)重調(diào)整因子，出現(xiàn)早熟現(xiàn)象時，通過調(diào)整因子適當(dāng)增大慣性權(quán)重，擴(kuò)大搜索范圍，有效解決了早熟問題。未出現(xiàn)早熟現(xiàn)象時，繼續(xù)沿用線性遞減慣性權(quán)重策略，縮小搜索范圍，加快收斂速度。在生成直角三角形測試數(shù)據(jù)中，相比LDWPSO算法和SPSO算法，該算法搜索成功率較高，證明了該算法能有效解決早熟問題，跳出局部極值，增加找到最優(yōu)解的可能性。

參考文獻(xiàn)參考文獻(xiàn)：

[1]聶鵬，耿技，秦志光.軟件測試用例自動生成算法綜述[J]. 計算機(jī)應(yīng)用研究，2012，29（2）：401405.

[2]YUHUI SHI， RUSSELL C EBERHART. Empirical study of particle swarm optimization. Proceedings of the 1999 Congress on Evolutionary Computation[C].Washington，1999（3）：19451950.

[3]田甜，毛明志. 基于DWSPSO的軟件測試數(shù)據(jù)自動生成[J]. 計算機(jī)工程與設(shè)計，2011，32（6）：21342137.

[4]邵楠，周雁舟，惠文濤，等. 基于自適應(yīng)變異粒子群優(yōu)化算法的測試數(shù)據(jù)生成[J]. 計算機(jī)應(yīng)用研究，2015，32（3）：786789.

[5]胡旺，李志蜀. 一種更簡化而高效的粒子群優(yōu)化算法[J].軟件學(xué)報，2007，18（4）：861868.

[6]董躍華，戴玉倩. 一種改進(jìn)PSO的軟件測試數(shù)據(jù)自動生成算法[J].小型微型計算機(jī)系統(tǒng)，2015，36（9）：20152020.

[7]陳琳玲. 基于簡化粒子群算法的測試數(shù)據(jù)自動生成方法研究[D].重慶：西南大學(xué)，2010.

[8]董躍華，戴玉倩. 混合粒子群算法的軟件測試數(shù)據(jù)自動生成[J].計算機(jī)應(yīng)用，2015，35（2）：545549.

責(zé)任編輯（責(zé)任編輯：杜能鋼）