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

基于K-均值聚類(lèi)粒子群優(yōu)化算法的組合測(cè)試數(shù)據(jù)生成摘要:在解決組合測(cè)試中的測(cè)試數(shù)據(jù)集生成問(wèn)題時(shí)，粒子群優(yōu)化算法(pso)在待測(cè)數(shù)據(jù)量增加達(dá)到一定程度以后，出現(xiàn)迭代次數(shù)增加、收斂速度減慢的缺點(diǎn)。針對(duì)該問(wèn)題，提出了一種應(yīng)用于組合測(cè)試數(shù)據(jù)集生成問(wèn)題的基于k.均值聚類(lèi)的粒子群優(yōu)化算法。通過(guò)對(duì)測(cè)試數(shù)據(jù)集合進(jìn)行聚類(lèi)分區(qū)域，增強(qiáng)測(cè)試數(shù)據(jù)集的多態(tài)性，從而對(duì)粒子群優(yōu)化算法進(jìn)行改進(jìn)，增加各個(gè)區(qū)域內(nèi)粒子之間的影響力。典型案例實(shí)驗(yàn)表明該方法在保證覆蓋度的情況下具有一定的優(yōu)勢(shì)和特點(diǎn)。關(guān)鍵詞:組合測(cè)試；粒子群優(yōu)化算法；k.均值聚類(lèi)算法；測(cè)試數(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 引言軟件測(cè)試作為軟件質(zhì)量保證的重要手段，在整個(gè)軟件生命周期中占有重要的地位。而測(cè)試數(shù)據(jù)生成是軟件測(cè)試過(guò)程中的重要環(huán)節(jié)，現(xiàn)代軟件測(cè)試數(shù)據(jù)的數(shù)量龐大，若使用窮盡測(cè)試，則耗費(fèi)大量的時(shí)間且效率低下。目前組合測(cè)試研究的焦點(diǎn)問(wèn)題是生成數(shù)量少質(zhì)量高的測(cè)試數(shù)據(jù)集合問(wèn)題，即根據(jù)具體待測(cè)軟件，用盡量少的測(cè)試數(shù)據(jù)盡可能多地覆蓋軟件系統(tǒng)中的各個(gè)因素以及相應(yīng)組合，以便在對(duì)軟件系統(tǒng)的檢測(cè)時(shí)發(fā)現(xiàn)系統(tǒng)中各個(gè)因素之間的相互作用對(duì)系統(tǒng)所產(chǎn)生的影響。2002年kuhn等1研究了組合測(cè)試的可用性發(fā)現(xiàn)，大約70%的軟件故障是由一個(gè)或兩個(gè)因素的相互作用引發(fā)的，因而研究?jī)蓛山M合覆蓋測(cè)試具有重要的意義。近年來(lái)研究者使用貪心算法、代數(shù)分析法和啟發(fā)式搜索算法解決組合測(cè)試數(shù)據(jù)生成問(wèn)題。 2006年microsoft發(fā)布了工具pict是一種基于one.test.at.a.time策略的，可以有效地按照兩兩組合測(cè)試的原理進(jìn)行測(cè)試數(shù)據(jù)的設(shè)計(jì)；而后由lei等提出了逐因素?cái)U(kuò)展（in.parameter.order）的方式實(shí)現(xiàn)二維組合測(cè)試數(shù)據(jù)的生成，并且基于該方法開(kāi)發(fā)了名為pairtest的二維組合測(cè)試數(shù)據(jù)生成工具2，該方法為以后的研究者進(jìn)行多維的組合測(cè)試數(shù)據(jù)生成提供了新思路。 2009年，mccaffrey將遺傳算法以及蟻群算法應(yīng)用于組合測(cè)試數(shù)據(jù)集生成問(wèn)題3-4，將現(xiàn)代群體智能算法引入，對(duì)測(cè)試數(shù)據(jù)生成的時(shí)間效率和尋優(yōu)能力上有了很大提高。2010年查日軍等5提出組合測(cè)試數(shù)據(jù)生成的交叉熵與粒子群方法，該方法簡(jiǎn)單地使用了傳統(tǒng)粒子群算法取得了一定的效果。近年來(lái)研究者將多種算法與粒子群優(yōu)化算法相結(jié)合，對(duì)粒子群算法進(jìn)行改進(jìn)，例如將粒子群算法與遺傳算法結(jié)合，粒子群算法與模擬退火算法混合等等。這些算法對(duì)于傳統(tǒng)粒子群優(yōu)化算法的各個(gè)方面進(jìn)行改進(jìn)，以滿足應(yīng)用問(wèn)題。本文將k.均值聚類(lèi)算法結(jié)合粒子群優(yōu)化算法(particle swarm optimization, pso)應(yīng)用于兩兩覆蓋的組合測(cè)試數(shù)據(jù)集的生成，實(shí)驗(yàn)表明該方法對(duì)于組合測(cè)試數(shù)據(jù)集生成問(wèn)題的迭代次數(shù)，以及收斂速度上具有優(yōu)勢(shì)和改善。1 組合覆蓋測(cè)試模型假設(shè)影響待測(cè)軟件（software under test, sut）的因素共有n個(gè),形成有限集合f=(f1, f2, fn)，其中因素fi在有限離散集合中包含k個(gè)可選取值，從而形成該因素的取值集合x(chóng)i(1in)，不妨設(shè)xi=xi1,xi2,xik。稱(chēng)一個(gè)n元組test=(x1，x2,xn)(x1x1,x2x1,xnxn)為sut的一條測(cè)試數(shù)據(jù)，相應(yīng)的，稱(chēng)一個(gè)含有多個(gè)這樣的n元組所構(gòu)成的集合為sut的一個(gè)測(cè)試數(shù)據(jù)集。待測(cè)軟件系統(tǒng)sut中任意兩個(gè)因素對(duì)可以用二元關(guān)系矩陣a=(ai,j)kk表示，其中，k表示待測(cè)系統(tǒng)的n個(gè)因素的全部取值總個(gè)數(shù)，即因素集合f的各個(gè)因素取值個(gè)數(shù)相加和，對(duì)各個(gè)取值進(jìn)行編號(hào)為1,2,k，i,j為各個(gè)取值的編號(hào)，ai,j的值表示第i個(gè)離散值和第j個(gè)離散值覆蓋對(duì)是否要覆蓋，ai,j=1表明第i個(gè)離散值和第j個(gè)離散值對(duì)需要覆蓋，ai,j=0表明第i個(gè)值和第j個(gè)值對(duì)不需要覆蓋，不需要覆蓋的原因表示是同一因素內(nèi)部的取值對(duì)，或者是組合對(duì)為已有組合對(duì)的逆轉(zhuǎn)重復(fù)。兩兩覆蓋的組合測(cè)試數(shù)據(jù)集生成問(wèn)題就是找到覆蓋所有因素取值的兩兩組合對(duì)的規(guī)模最小的測(cè)試數(shù)據(jù)集, 在上述模型中找到覆蓋二元關(guān)系矩陣t=(ti,j)pp所有兩兩組合對(duì)的規(guī)模最小的集合,以便在保證錯(cuò)誤檢測(cè)能力的前提下盡可能地降低測(cè)試成本?？梢宰C明, 兩兩覆蓋的組合測(cè)試數(shù)據(jù)集生成問(wèn)題是一個(gè)np.c問(wèn)題6。在實(shí)際的測(cè)試中，人們一般都利用啟發(fā)式算法、貪心算法和一些數(shù)學(xué)代數(shù)等方法近似求解。近幾年，研究者將幾