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