蹇紅梅，成新文，曾燕

（四川理工學(xué)院計算機學(xué)院，四川自貢 643000）

基于自適應(yīng)QPSO算法的軟件測試數(shù)據(jù)自動生成

蹇紅梅，成新文，曾燕

（四川理工學(xué)院計算機學(xué)院，四川自貢 643000）

針對軟件測試數(shù)據(jù)采用遺傳算法和粒子群算法自動生成算法復(fù)雜和容易早熟等問題，提出一種動態(tài)調(diào)整收縮擴張因子的自適應(yīng)量子粒子群算法（AQPSO）。該算法通過引入粒子進化度和聚合度，收縮擴張因子隨粒子進化度因子和聚合度因子變化而變化，從而實現(xiàn)算法的動態(tài)自適應(yīng)性，提高算法收斂速度和求解精度。軟件測試數(shù)據(jù)自動生成實驗驗證了該算法的有效性和可行性。

量子粒子群；軟件測試；測試數(shù)據(jù)生成；收縮擴張因子

0 引言

軟件測試在軟件生命周期中占有十分重要的地位，它是保證軟件質(zhì)量的重要手段，良好的軟件測試數(shù)據(jù)對于程序錯誤的發(fā)現(xiàn)至關(guān)重要。在實際測試過程中，若采用人工方式構(gòu)造測試數(shù)據(jù)，時間花費巨大并且效率低下。自動生成測試數(shù)據(jù)可以有效地降低測試人員的工作強度，提高軟件測試效率，一直被廣泛研究。

近年來，智能優(yōu)化算法開始用于測試數(shù)據(jù)的自動生成。文獻[1]將遺傳算法應(yīng)用于測試數(shù)據(jù)的自動生成；文獻[2]提出了適應(yīng)值函數(shù)構(gòu)造的“分支函數(shù)疊加法”。傅博[3]將模擬退火算法與遺傳算法結(jié)合，取得了一定成果；李軍等[4]提出了自適應(yīng)遺傳算法，通過自適應(yīng)改變交叉率和變異率，提高了算法的覆蓋率；夏蕓等[5]對遺傳算法進行改進，提出了一種基于IGA（免疫遺傳算法）的測試數(shù)據(jù)自動生成方法，有效改善了遺傳算法的未成熟收斂缺陷。由于遺傳算法存在算法復(fù)雜、參數(shù)設(shè)置復(fù)雜的問題，李愛國等[6]提出了一種基于粒子群算法的軟件結(jié)構(gòu)測試數(shù)據(jù)自動生成方法。

但是，粒子群優(yōu)化算法生成測試數(shù)據(jù)存在容易產(chǎn)生早熟收斂而陷入局部最優(yōu)的問題。文獻[7]提供了量子行為粒子群（QPSO）算法，其全局搜索性能遠遠優(yōu)于一般PSO算法。

本文將QPSO算法應(yīng)用于軟件測試數(shù)據(jù)自動生成，在文獻[8]的基礎(chǔ)上提出了基于QPSO的自適應(yīng)算法（AQPSO）。該算法的收縮擴張因子隨粒子進化度和聚合度變化而變化，實現(xiàn)了算法的動態(tài)自適應(yīng)性。

1 粒子群算法

1995 年，美國社會心理學(xué)家Kennedy博士和電氣工程師Eberhart博士提出了粒子群優(yōu)化算法（PSO）[9-10]。粒子群優(yōu)化算法的基本思想是通過群體中個體之間的協(xié)作和信息共享來尋找最優(yōu)解。

如果xi=（xi1，xi2，…，xiD）為D維目標搜索空間中粒子i的當(dāng)前位置；νi=（νi1，νi2，…，νiD）為第i個粒子的當(dāng)前“飛行”速度；pbest=（pi1，pi2，…，piD），i=1，2，…，N為粒子i所經(jīng)歷過的具有最好適應(yīng)值的位置（個體極值），整個粒子群迄今為止搜索到的最優(yōu)位置（全局極值）為gbest=（pg1，pg2，…，pgD）。粒子更新自己的速度和位置的方法如下：

式中：c1，c2——加速常數(shù)；

w——慣性權(quán)重；

r1，r2——兩兩相互獨立的[0，1]范圍內(nèi)變化的隨機數(shù)。

由于PSO算法簡單容易實現(xiàn)并且沒有太多的參數(shù)調(diào)節(jié)，目前已被廣泛應(yīng)用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、模糊系統(tǒng)控制以及其他遺傳算法的應(yīng)用領(lǐng)域。但是，PSO算法具有搜索空間有限、容易陷入局部最優(yōu)解的缺陷。

2 采用的算法思想和策略

2.1 量子粒子群算法

在量子空間中，粒子的位置和速度不能同時確定，因此粒子的狀態(tài)可以通過波函數(shù)來描述。波函數(shù)模的平方是粒子在空間中某一點出現(xiàn)的概率密度，并通過求解薛定諤方程得到粒子在空間某一點出現(xiàn)的概率密度函數(shù)，隨后通過蒙特卡羅隨機模擬的方式得到量子空間中粒子的位置方程，如下式所示[7]：

式中：p（t）——P（t）與G（t）之間的隨機位置；

P（t）——上一代所有粒子的個體最佳位置；

G（t）——上一代群體的最佳位置；

C（t）——上一代所有粒子個體最佳位置P（t）的平均值；

M——粒子個數(shù)；

α——收縮擴張因子，在算法收斂的過程中線性減??；

it——當(dāng)前迭代次數(shù)；

itmax——設(shè)定的最大迭代次數(shù)；

X（t+1）——粒子的當(dāng)前位置；

φ（t），u（t）——0～1之間的隨機數(shù)，如果u（t）≥0.5時，式（4）則取“-”號，當(dāng)0＜u（t）＜0.5時，式（4）取“+”號。

2.2 自適應(yīng)策略和邊界處理策略

量子粒子群算法的收斂性能與收縮擴張因子α的選擇和控制密切相關(guān)。從式（5）可以看出，在粒子進化過程中，隨著進化代數(shù)的增加收縮擴張系數(shù)α線性減小，這種變化并不能自適應(yīng)避免早熟趨勢。

為此，引入粒子進化度和粒子聚合度兩個粒子群動態(tài)性能指標[11-13]。粒子進化度（degree of evolutionary）描述粒子群的進化速度，表明本次迭代當(dāng)前的全局最優(yōu)值優(yōu)于前一次迭代全局最優(yōu)值的程度；粒子聚合度（degree of aggregation）描述粒子群所有粒子的聚集程度，當(dāng)所有粒子都達到全局最優(yōu)值時，粒子群聚集為一個點。

對于適應(yīng)度函數(shù)最小化優(yōu)化問題，其粒子進化度和粒子聚合度的定義式如下：

式中：f（（xg（t））——第t代粒子群全局最優(yōu)值；

f（xi（t））——粒子i的個體最優(yōu)值；

N——粒子總量。

根據(jù)粒子進化度定義式（7）可知0＜e≤1，e越小粒子進化速度越快，粒子的集中性越小。在程序運行早期，e較小，粒子可以在較大的空間內(nèi)搜索，隨著程序運行e逐漸增大，e較大時可以減少α使得粒子在小范圍內(nèi)搜索，以便更快地找到最優(yōu)值，直到e為1時為止。

根據(jù)粒子聚合度定義式（8）可知0＜β≤1，β越大，則粒子群聚集程度越大，粒子的多樣性越小。程序運行早期β較小時，粒子比較分散，粒子的多樣性大，粒子不易陷入局部最優(yōu)；隨著程序運行β增大，多樣性減少，算法容易陷入局部最優(yōu)值，此時需要增大β從而增大搜索空間，提高粒子群全局尋優(yōu)能力。

根據(jù)上述分析，QPSO算法的收縮擴張因子α應(yīng)隨粒子進化度增大而減小，隨粒子聚合度β增大而增大。因此，基于粒子進化聚合度的收縮擴張因子計算方法如下所示：

式中：e——粒子進化度因子；

β——粒子聚合度因子；

α0——收縮擴張因子初始值，一般取α0=1.0，b=0.5，c=0.1。

從而實現(xiàn)了基于粒子進化聚合度的收縮擴張因子動態(tài)自適應(yīng)調(diào)整的AQPSO算法。

上述AQPSO算法，粒子有時可能會飛出有效的搜索空間，為解決此問題，在實驗中設(shè)計了“隨機回縮法”的邊界處理策略。

“隨機回縮法”的基本思想是：當(dāng)粒子位置大于最大邊界位置時，將其隨機回縮到中心與最大邊界之間；當(dāng)粒子位置小于最小邊界時，將其隨機回縮到中心與最小邊界之間。更新后的粒子新位置計算方法如式（10）：

式中：xmax——粒子的最大邊界位置；

xmin——粒子的最小邊界位置。

2.3 適應(yīng)值函數(shù)的構(gòu)造策略

在基于量子粒子群優(yōu)化算法的測試數(shù)據(jù)集自動生成算法中，一個粒子代表一個測試數(shù)據(jù)，一次產(chǎn)生一個測試數(shù)據(jù)集。適應(yīng)值函數(shù)是QPSO應(yīng)用于求解問題的優(yōu)化目標，它的構(gòu)造直接影響QPSO在具體問題上的運行效率。

可以采用“分支函數(shù)疊加法”來構(gòu)造QPSO的適應(yīng)值函數(shù)[2]。分支函數(shù)是一個分支謂詞到實際值的映射，可以定量描述在測試數(shù)據(jù)的驅(qū)動下，被測單元的實際執(zhí)行路徑對選定路徑的覆蓋程度。在測試程序選定路徑上的各分支點前進行分支函數(shù)的插樁。

假定分支謂詞為簡單關(guān)系表達式（不等式和等式），則分支謂詞和其對應(yīng)的等式謂詞描述形式如下：

其中，分支函數(shù)F為一個實值函數(shù)，分支函數(shù)的構(gòu)造方法如表1所示。

對于分支謂詞通過“And”或“Or”構(gòu)成的邏輯運算，其分支函數(shù)構(gòu)造形式為Max（F1，F(xiàn)2）。

如果在選定路徑上，有n個分支點，m個輸入?yún)?shù)，則n個分支函數(shù)構(gòu)成的分支函數(shù)集為由分支函數(shù)疊加構(gòu)成該路徑的評價函數(shù)為

表1 分支函數(shù)的構(gòu)造

評價函數(shù)的插入位置與分支函數(shù)的插樁位置不同，通常位于程序的結(jié)束位置處。

2.4 基于AQPSO的軟件測試數(shù)據(jù)自動生成策略

基于AQPSO的測試數(shù)據(jù)自動生成方法，將測試數(shù)據(jù)作為粒子群向量X的元素。首先隨機生成測試數(shù)據(jù)，然后用AQPSO算法搜索符合指定路徑的測試數(shù)據(jù)，使得適應(yīng)值函數(shù)的值達到最小。AQPSO算法不僅參數(shù)隨機性強，個數(shù)少，并且能覆蓋所有解空間，保證算法的全局收斂性。該算法生成測試數(shù)據(jù)的具體實現(xiàn)步驟如下：

（1）分析被測的軟件程序，確定適應(yīng)值函數(shù)，對被測程序進行插樁。

（2）設(shè)定粒子數(shù)M，維數(shù)Dimension，最大允許迭代次數(shù)MAXTIER。在問題空間中，初始化粒子群中每一個粒子的當(dāng)前位置Xi（0），并設(shè)置個體的最好位置Pi（0）=Xi（0），設(shè)置迭代次數(shù)計數(shù)器t=0。

（3）根據(jù)式（4）計算粒子群中的平均最好位置。

（4）對于粒子群中的每一個粒子i（1≤i≤M），執(zhí)行（5）～（8）。

（5）按照式（14）計算粒子i的當(dāng)前位置Xi（t）的適應(yīng)值，更新粒子的個體最好位置Pi（t），即將Xi（t）適應(yīng)值與前一次迭代Pi（t-1）的適應(yīng)值比較，如果Xi（t）適應(yīng)值優(yōu)于Pi（t-1）的適應(yīng)值，則置Pi（t）=Xi（t），否則，Pi（t）=Pi（t-1）。

（6）對于粒子i，將Pi（t）的適應(yīng)值與全局最好位置G（t-1）的適應(yīng)值進行比較，若優(yōu)于G（t-1）的適應(yīng)值，則置G（t）=Pi（t）；否則Pi（t）=Pi（t-1）。

（7）對粒子的每一維，根據(jù)式（3）計算得到一個隨機點的位置。

（8）按式（9）計算收縮擴張因子，根據(jù)式（6）和式（10）計算和更新粒子位置。

（9）若算法的終止條件不滿足，置t=t+1，返回步驟（2），否則算法結(jié)束。

3 實例驗證

三角形判別問題的程序包含了清晰而又復(fù)雜的邏輯，從而在軟件測試數(shù)據(jù)生成中廣泛使用。為了驗證AQPSO算法自動生成軟件測試數(shù)據(jù)的可行性，采用了與文獻[6]相同的直角三角形判定典型測試實例，并用一組統(tǒng)計數(shù)值來衡量算法的性能。硬件平臺為Lenovo揚天A4600K，Pentium Dual-Core E5800@ 3.2GHz，2G內(nèi)存。算法程序在Matlab R2010b中測試驗證。

表2提供了AQPSO算法、GA算法及PSO算法找到最優(yōu)解的迭代次數(shù)比較數(shù)據(jù)。粒子數(shù)目和種群數(shù)從100到280之間變化，實驗中對每個粒子數(shù)和種群數(shù)各運行10次。表中記錄了10次運行中找到最優(yōu)解迭代次數(shù)的最好、最差及平均值。

表2 3種生成直角三角形測試數(shù)據(jù)算法找到最優(yōu)解的迭代次數(shù)比較

根據(jù)表2數(shù)據(jù)進行分析比較：

（1）分析GA、PSO和該實驗的AQPSO 3種算法找到最優(yōu)解（生成所需的測試數(shù)據(jù)）的迭代次數(shù)。根據(jù)平均值統(tǒng)計情況進行分析，在最好情況下，PSO算法的迭代次數(shù)約是GA算法的1/13，AQPSO算法的迭代次數(shù)約是GA算法的1/32，PSO約是AQPSO的2.4倍；在最壞情況下，PSO算法的迭代次數(shù)約是GA算法的1/12，AQPSO約是GA算法的1/24，PSO算法約是AQPSO算法的2倍；從平均迭代次數(shù)分析，PSO算法的迭代次數(shù)約是GA算法的1/16，AQPSO算法的迭代次數(shù)約是GA算法的1/19，PSO算法的迭代次數(shù)約是AQPSO算法的1.2倍。AQPSO算法的收斂速度均高于PSO算法和GA算法。

（2）分析GA、PSO和該實驗的AQPSO 3種算法找到最優(yōu)解的迭代次數(shù)穩(wěn)定性。GA算法的最好迭代次數(shù)從第3代到240代，相對于迭代平均值48.3變化幅度很大；PSO的最好迭代次數(shù)從第1代到7代，相對于迭代平均值3.6變化幅度下降，最好迭代次數(shù)較穩(wěn)定；AQPSO的最好迭代次數(shù)大多為第1代或第2代，最好迭代次數(shù)最穩(wěn)定。從3種算法最優(yōu)解的平均迭代次數(shù)分析，也可得到同樣的結(jié)果。

總之，采用本文所述方法生成直角三角形測試數(shù)據(jù)的效率和穩(wěn)定性均明顯高于粒子群算法PSO和遺傳算法GA。

4 結(jié)束語

針對遺傳算法生成軟件測試數(shù)據(jù)存在參數(shù)多、算法復(fù)雜以及標準粒子群算法容易早熟而陷入局部最優(yōu)問題，引入自適應(yīng)量子粒子群優(yōu)化算法（AQPSO）。該算法改變了標準量子粒子群算法收縮擴張因子線性變化難以自適應(yīng)避免早熟趨勢的缺點。通過粒子進化度和聚合度自適應(yīng)動態(tài)調(diào)整收縮擴張因子，從而實現(xiàn)了算法的動態(tài)自適應(yīng)性，提高了算法的收斂速度和求解穩(wěn)定性。軟件測試數(shù)據(jù)自動生成實驗驗證了算法的有效性和可行性，擴展了量子粒子群算法應(yīng)用范圍。

[1]Hermadi I，Ahmed M A.Genetic algorithm based test data generator[C]∥Evolutionary Computation，2003.

[2]Korel B.Automated software test data generation.Software Engineering[J].IEEE Transactions，1990，16（8）：870-879.

[3]傅博.基于模擬退火遺傳算法的軟件測試數(shù)據(jù)自動生成[J].計算機工程與應(yīng)用，2005（12）：82-84.

[4]李軍，李艷輝，彭存銀.基于自適應(yīng)遺傳算法的路徑測試數(shù)據(jù)生成[J].計算機工程，2009，35（2）：203-205.

[5]夏蕓，劉鋒.基于免疫遺傳算法的軟件測試數(shù)據(jù)自動生成[J].計算機應(yīng)用，2008（3）：723-725.

[6]李愛國，張艷麗.基于PSO的軟件結(jié)構(gòu)測試數(shù)據(jù)自動生成方法[J].計算機工程，2008（6）：93-94，97.

[7]Sun J，F(xiàn)eng B，Xu W B.Particle swarm op tim ization with particles having quantum behavior[C]∥Proceedings of Congress on Evolutionary Computation，2004：325-331.

[8]趙吉，孫俊，須文波.一種求解多峰函數(shù)優(yōu)化問題的量子行為粒子群算法[J].計算機應(yīng)用，2006，26（12）：2956-2960.

[9]Kennedy J，Eberhart R.Particle swarm optimization[C]∥Proc of IEEE International Conference on Neural Networks.Perth：IEEE Press，1995：1942-1948.

[10]朱小六，熊偉麗，徐保國.基于動態(tài)慣性因子的PSO算法的研究[J].計算機仿真，2007，24（5）：154-157.

[11]任子暉，王堅.一種動態(tài)改變慣性權(quán)的自適應(yīng)粒子群算法[J].計算機科學(xué)，2009，36（2）：227-229.

[12]黃澤霞，俞攸紅，黃德才.慣性權(quán)自適應(yīng)調(diào)整的量子粒子群優(yōu)化算法[J].上海交通大學(xué)學(xué)報，2012（2）：228-232.

[13]陳翔.一種基于粒子群優(yōu)化的成對組合測試算法框架[J].軟件學(xué)報，2011（12）：2879-2893.

Automatic generation of software test data based on adaptive QPSO algorithm

JIAN Hong-mei，CHENG Xin-wen，ZENG Yan
（School of Computer Science，Sichuan University of Science&Engineering，Zigong 643000，China）

For the complexity and prematurity of the automatic software test data generation algorithm based on the genetic algorithm and the standard particle swarm optimization algorithm，an adaptive quantum-behaved particle swarm optimization（AQPSO）algorithm is presented to dynamically adjust the contraction expansion factro to overcome these shortcomings.By introducing the evolution degree and polymerization degree of the particle into this method，the contraction expansion factor keeps changing as the evolution dgree and polymerization dgree factors are changing，orderly the dynamical and adaptive algorithm is realize，which improves the convergence speed and precision the traditional algorithm.The experiment on automatic generation of software test data verified the validity and feasibility of the algorithm.

QPSO；software testing；test data generation；contraction expansion factor

TP206+.1；TP301.6；TP311.52；TP311.55

A

1674-5124（2013）03-0100-04

2012-11-07；

：2013-01-08

四川省教育廳科研基金項目（10ZC084）人工智能四川省重點實驗室科研基金（2008RK010）

蹇紅梅（1980-），女，四川南充市人，講師，碩士，研究方向為計算機應(yīng)用與軟件測試。