基于改进粒子群算法的组合测试用例生成方法
Combinatorial Test Case Generation Method Based on Improved Particle Swarm Optimization Algorithm
DOI: 10.12677/SEA.2020.92018, PDF,  被引量   
作者: 张 娜, 董亮亮, 包晓安：浙江理工大学信息学院，浙江 杭州；金瑜婷*, 涂小妹：浙江理工大学信息学院，浙江 杭州；浙江广厦建设职业技术学院，浙江 东阳
关键词: 组合测试；粒子群算法；布谷鸟搜索；IPO策略；Combination Testing； Particle Swarm Optimization； Cuckoo Search； IPO Strategy
摘要: 组合测试难以对所有可能取值的组合进行全面覆盖，针对如何生成最小测试用例集的问题，提出了一种基于约束处理和评估指标的类IPO策略和CS-SPSO算法相结合的测试用例集生成方法。首先，考虑测试用例的特性对粒子进行编码，将得到的初始种群划分为若干子种群。其次，利用简化粒子群算法搜索各子种群中的最优测试用例并在种群间进行随机交流。接着，利用布谷鸟搜索的全局搜索能力来寻找适应度更好的测试用例，引入动态步长加速算法收敛。最后，与改进的类IPO策略相结合生成组合测试用例集。实验结果表明，与基本的PSO、CS算法以及基本的IPO策略相比，本文提出的算法在用例规模和执行时间上具有一定的优势。
Abstract: The combined test is difficult to achieve fully coverage about the all possibilities. In order to gen-erate the least number of test cases, a method of test case set generation based on the combination of IPO strategy and CS-SPSO algorithm is proposed. Firstly, considering the characteristics of test cases to code particle, the initial population was divided into several subpopulations. Secondly, the simplified particle swarm optimization algorithm was used to search the optimal test cases in each subpopulation and communicated randomly among the populations. Then, the global search ability of cuckoo search was used to find the test case with better adaptability, and the dynamic step size was introduced to accelerate the convergence of the algorithm. Finally, combined it with the improved IPO strategy to generate combinational test cases. The experimental results show that, compared with the basic PSO, CS algorithm and the basic IPO Strategy, the proposed algorithm has certain advantages in case size and execution time.
文章引用：张娜, 金瑜婷, 涂小妹, 董亮亮, 包晓安. 基于改进粒子群算法的组合测试用例生成方法[J]. 软件工程与应用, 2020, 9(2): 148-158. https://doi.org/10.12677/SEA.2020.92018

参考文献

[1] 申情, 蒋云良, 沈张果, 等. 基于组合混沌遗传算法的最小测试用例集生成[J]. 电信科学, 2016, 32(6): 93-102.
[2] 宋晓秋, 梁凡. 两两组合测试用例生成的遍历搜索算法[J]. 计算机工程与设计, 2019, 40(2): 433-437.
[3] Lei, Y., Kacker, R., Kuhn, D.R., et al. (2008) IPOG/IPOG-D: Efficient Test Generation for Multi-Way Combinatorial Testing. Software Testing, Verification and Reliability, 18, 24. [Google Scholar] [CrossRef] 
[4] 艾华, 宋晓秋, 安恒. 简单循环约减三三组合测试用例生成方法[J]. 计算机工程与设计, 2018, 39(12): 3728-3733.
[5] Nie, C.H. and Leung, H. (2011) A Survey of Combinatorial Testing. ACM Computing Surveys, 43, 1-29. [Google Scholar] [CrossRef] 
[6] Sabharwal, S., Bansal, P., Mittal, N., et al. (2016) Construction of Mixed Covering Arrays for Pair-Wise Testing Using Probabilistic Approach in Genetic Algorithm. Arabian Journal for Science and Engineering, 41, 2821-2835. [Google Scholar] [CrossRef] 
[7] 戚荣志, 王志坚, 黄宜华, 等. 基于Spark的并行化组合测试用例集生成方法[J]. 计算机学报, 2018, 41(6): 1064-1079.
[8] 曾梦凡, 陈思洋, 张文茜, 等. 利用蚁群算法生成覆盖表: 探索与挖掘[J]. 软件学报, 2016, 27(4): 855-878.
[9] 王小银, 王曙燕, 孙家泽. 基于蚁群算法的三三组合测试用例集的生成[J]. 计算机应用研究, 2015, 32(11): 3328-3331.
[10] Chandra, P., Subhash, T., Vrushali, K., et al. (2018) A Critical Review on Automated Test Case Generation for Conducting Combinatorial Testing Using Particle Swarm Optimization. In-ternational Journal of Engineering & Technology, 38, 22-28. [Google Scholar] [CrossRef] 
[11] 包晓安, 鲍超, 金瑜婷, 等. 基于动态调整简化粒子群优化的组合测试用例生成方法[J]. 计算机科学, 2018, 45(11): 199-203.
[12] Kennedy, J. (2011) Particle Swarm Optimization. Proceedings of 1995 IEEE International Conference of Neural Networks, 4, 1942-1948.
[13] 陈翔, 顾庆, 王子元, 等. 一种基于粒子群优化的成对组合测试算法框架[J]. 软件学报, 2011, 22(12): 2879-2893.
[14] 包晓安, 杨亚娟, 张娜, 等. 基于自适应粒子群优化的组合测试用例生成方法[J]. 计算机科学, 2017, 44(6): 177-181.
[15] Mahmoud, T. and Ahmed, B.S. (2015) An Efficient Strategy for Covering Array Construction with Fuzzy Logic-Based Adaptive Swarm Optimization for Software Testing Use. Expert Systems with Applications, 42, 8753-8765. [Google Scholar] [CrossRef] 
[16] 胡旺, 李志蜀. 一种更简化而高效的粒子群优化算法[J]. 软件学报, 2007, 18(4): 861-868.
[17] Yang, X.S. and Deb, S. (2010) Cuckoo Search via Levy Flights. Mathematics, 22, 210-214.
[18] Yang, X.S. and Deb, S. (2013) Multiobjective Cuckoo Search for Design Optimization. Computers & Operations Research, 40, 1616-1624. [Google Scholar] [CrossRef] 
[19] Yang, X.S. and Deb, S. (2010) Engineering Optimization by Cuckoo Search. International Journal of Mathematical Modelling and Numerical Optimisation, 1, 330-343. [Google Scholar] [CrossRef] 
[20] Tai, K.C. and Lei, Y. (2002) A Test Generation Strategy for Pairwise Testing. IEEE Transactions on Software Engineering, 28, 109-111. [Google Scholar] [CrossRef] 
[21] 张煜培, 赵知劲, 郑仕链. 利用多目标PSO优化的累积时延和信道容量联合优化的频谱切换算法[J]. 电信科学, 2018, 34(7): 62-71.
[22] Ahmed, B.S., Abdulsamad, T.S. and Potrus, M.Y. (2015) Achievement of Minimized Combinatorial Test Suite for Configuration-Aware Software Functional Testing Using the Cuckoo Search algorithm. Information and Software Technology, 66, 13-29. [Google Scholar] [CrossRef] 

为你推荐