基于自適應QPSO算法的軟件測試數據自動生成

蹇紅梅，成新文，曾燕

（四川理工學院計算機學院，四川自貢 643000）

基于自適應QPSO算法的軟件測試數據自動生成

蹇紅梅，成新文，曾燕

（四川理工學院計算機學院，四川自貢 643000）

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

量子粒子群；軟件測試；測試數據生成；收縮擴張因子

0 引言

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

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

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

本文將QPSO算法應用于軟件測試數據自動生成，在文獻[8]的基礎上提出了基于QPSO的自適應算法（AQPSO）。該算法的收縮擴張因子隨粒子進化度和聚合度變化而變化，實現了算法的動態自適應性。

1 粒子群算法

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

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

式中：c1，c2——加速常數；

w——慣性權重；

r1，r2——兩兩相互獨立的[0，1]范圍內變化的隨機數。

由于PSO算法簡單容易實現并且沒有太多的參數調節，目前已被廣泛應用于函數優化、神經網絡訓練、模糊系統控制以及其他遺傳算法的應用領域。但是，PSO算法具有搜索空間有限、容易陷入局部最優解的缺陷。

2 采用的算法思想和策略

2.1 量子粒子群算法

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

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

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

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

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

M——粒子個數；

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

it——當前迭代次數；

itmax——設定的最大迭代次數；

X（t+1）——粒子的當前位置；

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

2.2 自適應策略和邊界處理策略

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

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

對于適應度函數最小化優化問題，其粒子進化度和粒子聚合度的定義式如下：

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

f（xi（t））——粒子i的個體最優值；

N——粒子總量。

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

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

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

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

β——粒子聚合度因子；

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

從而實現了基于粒子進化聚合度的收縮擴張因子動態自適應調整的AQPSO算法。

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

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

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

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

2.3 適應值函數的構造策略

在基于量子粒子群優化算法的測試數據集自動生成算法中，一個粒子代表一個測試數據，一次產生一個測試數據集。適應值函數是QPSO應用于求解問題的優化目標，它的構造直接影響QPSO在具體問題上的運行效率。

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

假定分支謂詞為簡單關系表達式（不等式和等式），則分支謂詞和其對應的等式謂詞描述形式如下：

其中，分支函數F為一個實值函數，分支函數的構造方法如表1所示。

對于分支謂詞通過“And”或“Or”構成的邏輯運算，其分支函數構造形式為Max（F1，F2）。

如果在選定路徑上，有n個分支點，m個輸入參數，則n個分支函數構成的分支函數集為由分支函數疊加構成該路徑的評價函數為

表1 分支函數的構造

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

2.4 基于AQPSO的軟件測試數據自動生成策略

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

（1）分析被測的軟件程序，確定適應值函數，對被測程序進行插樁。

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

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

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

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

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

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

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

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

3 實例驗證

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

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

表2 3種生成直角三角形測試數據算法找到最優解的迭代次數比較

根據表2數據進行分析比較：

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

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

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

4 結束語

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

[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]傅博.基于模擬退火遺傳算法的軟件測試數據自動生成[J].計算機工程與應用，2005（12）：82-84.

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

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

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

[7]Sun J，Feng 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]趙吉，孫俊，須文波.一種求解多峰函數優化問題的量子行為粒子群算法[J].計算機應用，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]朱小六，熊偉麗，徐保國.基于動態慣性因子的PSO算法的研究[J].計算機仿真，2007，24（5）：154-157.

[11]任子暉，王堅.一種動態改變慣性權的自適應粒子群算法[J].計算機科學，2009，36（2）：227-229.

[12]黃澤霞，俞攸紅，黃德才.慣性權自適應調整的量子粒子群優化算法[J].上海交通大學學報，2012（2）：228-232.

[13]陳翔.一種基于粒子群優化的成對組合測試算法框架[J].軟件學報，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-），女，四川南充市人，講師，碩士，研究方向為計算機應用與軟件測試。