基于K-均值聚類粒子群優(yōu)化算法的組合測試數(shù)據(jù)生成.doc

基于K-均值聚類粒子群優(yōu)化算法的組合測試數(shù)據(jù)生成摘要:在解決組合測試中的測試數(shù)據(jù)集生成問題時，粒子群優(yōu)化算法(pso)在待測數(shù)據(jù)量增加達到一定程度以后，出現(xiàn)迭代次數(shù)增加、收斂速度減慢的缺點。針對該問題，提出了一種應(yīng)用于組合測試數(shù)據(jù)集生成問題的基于k.均值聚類的粒子群優(yōu)化算法。通過對測試數(shù)據(jù)集合進行聚類分區(qū)域，增強測試數(shù)據(jù)集的多態(tài)性，從而對粒子群優(yōu)化算法進行改進，增加各個區(qū)域內(nèi)粒子之間的影響力。典型案例實驗表明該方法在保證覆蓋度的情況下具有一定的優(yōu)勢和特點。關(guān)鍵詞:組合測試；粒子群優(yōu)化算法；k.均值聚類算法；測試數(shù)據(jù) test data generation based on k.means clustering and particle swarm optimizationpan shuo*, wang shu.yan, sun jia.zeschool of computer science and technology，xian university of posts and telecommunications，xian shaanxi 710061, chinaabstract:to solve the problem of the test data set generation in combinatorial testing, if the software under test has a great many factors and values, the traditional particle swarm optimization(pso)will have large iteration times and slow convergence velocity. a test data set generation method based on k.means clustering algorithm and pso has been proposed. the polymorphism of the test data set has been enhanced, though the clustering and partition the test data set. and it makes pso has been improved. the compact between the particles in each area has been promoted. the several typical cases show that this method has some merits with ensuring the coverage.to solve the problem of the test data set generation in combinatorial test, if the software under test has a great many factors and values, the traditional particle swarm optimization (pso)will have large iteration times and slow convergence velocity. a test data set generation method based on k.means clustering algorithm and pso has been proposed. the polymorphism of the test data set has been enhanced, though clustering and partitioning the test data set. and it makes pso has been improved. the compact between the particles in each area has been promoted. several typical cases show that this method has some merits while ensuring the coverage.key words:combinatorial test; particle swarm optimization (pso) algorithm; k.means clustering algorithm; test data0 引言軟件測試作為軟件質(zhì)量保證的重要手段，在整個軟件生命周期中占有重要的地位。而測試數(shù)據(jù)生成是軟件測試過程中的重要環(huán)節(jié)，現(xiàn)代軟件測試數(shù)據(jù)的數(shù)量龐大，若使用窮盡測試，則耗費大量的時間且效率低下。目前組合測試研究的焦點問題是生成數(shù)量少質(zhì)量高的測試數(shù)據(jù)集合問題，即根據(jù)具體待測軟件，用盡量少的測試數(shù)據(jù)盡可能多地覆蓋軟件系統(tǒng)中的各個因素以及相應(yīng)組合，以便在對軟件系統(tǒng)的檢測時發(fā)現(xiàn)系統(tǒng)中各個因素之間的相互作用對系統(tǒng)所產(chǎn)生的影響。2002年kuhn等1研究了組合測試的可用性發(fā)現(xiàn)，大約70%的軟件故障是由一個或兩個因素的相互作用引發(fā)的，因而研究兩兩組合覆蓋測試具有重要的意義。近年來研究者使用貪心算法、代數(shù)分析法和啟發(fā)式搜索算法解決組合測試數(shù)據(jù)生成問題。 2006年microsoft發(fā)布了工具pict是一種基于one.test.at.a.time策略的，可以有效地按照兩兩組合測試的原理進行測試數(shù)據(jù)的設(shè)計；而后由lei等提出了逐因素擴展（in.parameter.order）的方式實現(xiàn)二維組合測試數(shù)據(jù)的生成，并且基于該方法開發(fā)了名為pairtest的二維組合測試數(shù)據(jù)生成工具2，該方法為以后的研究者進行多維的組合測試數(shù)據(jù)生成提供了新思路。 2009年，mccaffrey將遺傳算法以及蟻群算法應(yīng)用于組合測試數(shù)據(jù)集生成問題3-4，將現(xiàn)代群體智能算法引入，對測試數(shù)據(jù)生成的時間效率和尋優(yōu)能力上有了很大提高。2010年查日軍等5提出組合測試數(shù)據(jù)生成的交叉熵與粒子群方法，該方法簡單地使用了傳統(tǒng)粒子群算法取得了一定的效果。近年來研究者將多種算法與粒子群優(yōu)化算法相結(jié)合，對粒子群算法進行改進，例如將粒子群算法與遺傳算法結(jié)合，粒子群算法與模擬退火算法混合等等。這些算法對于傳統(tǒng)粒子群優(yōu)化算法的各個方面進行改進，以滿足應(yīng)用問題。本文將k.均值聚類算法結(jié)合粒子群優(yōu)化算法(particle swarm optimization, pso)應(yīng)用于兩兩覆蓋的組合測試數(shù)據(jù)集的生成，實驗表明該方法對于組合測試數(shù)據(jù)集生成問題的迭代次數(shù)，以及收斂速度上具有優(yōu)勢和改善。1 組合覆蓋測試模型假設(shè)影響待測軟件（software under test, sut）的因素共有n個,形成有限集合f=(f1, f2, fn)，其中因素fi在有限離散集合中包含k個可選取值，從而形成該因素的取值集合xi(1in)，不妨設(shè)xi=xi1,xi2,xik。稱一個n元組test=(x1，x2,xn)(x1x1,x2x1,xnxn)為sut的一條測試數(shù)據(jù)，相應(yīng)的，稱一個含有多個這樣的n元組所構(gòu)成的集合為sut的一個測試數(shù)據(jù)集。待測軟件系統(tǒng)sut中任意兩個因素對可以用二元關(guān)系矩陣a=(ai,j)kk表示，其中，k表示待測系統(tǒng)的n個因素的全部取值總個數(shù)，即因素集合f的各個因素取值個數(shù)相加和，對各個取值進行編號為1,2,k，i,j為各個取值的編號，ai,j的值表示第i個離散值和第j個離散值覆蓋對是否要覆蓋，ai,j=1表明第i個離散值和第j個離散值對需要覆蓋，ai,j=0表明第i個值和第j個值對不需要覆蓋，不需要覆蓋的原因表示是同一因素內(nèi)部的取值對，或者是組合對為已有組合對的逆轉(zhuǎn)重復。兩兩覆蓋的組合測試數(shù)據(jù)集生成問題就是找到覆蓋所有因素取值的兩兩組合對的規(guī)模最小的測試數(shù)據(jù)集, 在上述模型中找到覆蓋二元關(guān)系矩陣t=(ti,j)pp所有兩兩組合對的規(guī)模最小的集合,以便在保證錯誤檢測能力的前提下盡可能地降低測試成本?？梢宰C明, 兩兩覆蓋的組合測試數(shù)據(jù)集生成問題是一個np.c問題6。在實際的測試中，人們一般都利用啟發(fā)式算法、貪心算法和一些數(shù)學代數(shù)等方法近似求解。近幾年，研究者將幾