微信服务号

微信订阅号

2025-4-24- 17
Home > Archive>Volume 27, Issue 4, 2016 >855-878. DOI:10.13328/j.cnki.jos.004974
PDF HTML XML Export Cite reminder
Generating Covering Arrays Using Ant Colony Optimization:Exploration and Mining
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61272079, 61321491, 91318301); Research Fund for the Doctoral Program of Higher Education of China (20130091110032)

  • Article
    • | |
  • Metrics
    • |
  • Reference [26]
    • |
  • Related [20]
    • | | |
  • Comments
    Abstract:

    Generation of covering arrays, which has been solved by many mathematical methods and greedy algorithms as well as search based algorithms, is one of significant problems in combinatorial testing. As an effective evolutionary search algorithm for solving combinatorial optimization problems, ant colony optimization has also been used to generate covering arrays. Existing research shows ant colony optimization suitable for generating general covering arrays, variable strength covering arrays and the prioritization of covering arrays. Unfortunately, compared with other methods, ant colony optimization doesn't have significant advantages. To further explore and mine the potential of ant colony optimization in generating covering arrays, this paper focuses on four levels of improvement:1) the integration of ant colony variants; 2) parameter tuning; 3) the adjustment of solution structure and the improvement of evolutionary strategy; 4) using parallel computing to save executing time. The experimental results show that ant colony optimization is much more effective in generating covering arrays after the improvements.

    Reference
    [1] Nie CH. Concepts and Methods of Software Testing. Beijing:Tsinghua University Press, 2013. 1-22(in Chinese).
    [2] Nie CH. Combinatorial Testing. Beijing:Beijing Science Press, 2015. 1-119(in Chinese).
    [3] McCaffrey JD. Generation of pairwise test sets using a genetic algorithm. In:Proc. of the Int'l Conf. on Computer Software and Applications(COMPSAC). 2009. 626-631.[doi:10.1109/COMPSAC.2009.91]
    [4] Nie CH, Leung H. A survey of combinatorial testing. ACM Computing Surveys(CSUR), 2011,43(2):11.[doi:10.1145/1883612. 1883618]
    [5] Yu L, Tai KC. In-Parameter-Order:A test generation strategy for pairwise testing. In:Proc. of the High-Assurance Systems Engineering Symp. 1998. 254-261.[doi:10.1109/HASE.1998.731623]
    [6] Bryce RC, Colbourn CJ. The density algorithm for pairwise interaction testing. SoftwareTesting, Verification and Reliability, 2007,17(3):159-182.[doi:10.1002/stvr.365]
    [7] Dorigo M, Maniezzo V, Colorni A. Ant system:Optimization by a colony of cooperating agents. IEEE Trans. on Systems, Man, and Cybernetics(Part B Cybernetics), 1996,26(1):29-41.[doi:10.1109/3477.484436]
    [8] Dorigo M, Stützle T. Ant Colony Optimization. Cambridge:MIT Press, 2004. 1-151.
    [9] Cohen DM, Dalal SR, Fredman ML, Patton GC. The AETG system:An approach to testing based on combinatorial design. IEEE Trans. on Software Engineering(TSE), 1997,23(7):437-444.[doi:10.1109/32.605761]
    [10] Shiba T, Tsuchiya T, Kikuno T. Using artificial life techniques to generate test cases for combinatorial testing. In:Proc. of the Computer Software and Applications Conf. 2004. 72-77.[doi:10.1109/CMPSAC.2004.1342808]
    [11] Chen X, Gu Q, Li A, Chen DX. Variable strength interaction testing with an ant colony system approach. In:Proc. of the Asia-Pacific Software Engineering Conf.(ASPEC). 2009. 160-167.[doi:10.1109/APSEC.2009.18]
    [12] Chen X, Gu X, Zhang X, Chen DX. Building prioritized pairwise interaction test suites with ant colony optimization. In:Proc. of the Int'l Conf. on Quality Software(QSIC). 2009. 347-352.[doi:10.1109/QSIC.2009.52]
    [13] Nie CH, Wu HY, Liang YL, Leung H, Kuo FC, Li Z. Search based combinatorial testing. In:Proc. of the Asia-Pacific Software Engineering Conf.(ASPEC). 2012. 778-783.[doi:10.1109/APSEC.2012.16]
    [14] Dorigo M, Gambardella LM. Ant colony system:A cooperative learning approach to the traveling salesman problem. IEEE Trans. on Evolutionary Computation, 1997,1(1):1-24.[doi:10.1109/TEVC.1997.585887]
    [15] Dorigo M, Blum C. Ant colony optimization theory:A survey. Theoretical Computer Science, 2005,344(2-3):243-278.[doi:10. 1016/j.tcs.2005.05.020]
    [16] Liang YL, Nie CH. The optimization of configurable genetic algorithm for covering arrays generation. Chinese Journal of Computers, 2012,35(7):1522-1538(in Chinese with English abstract).
    [17] Bryce RC, Colbourn CJ. One-Test-at-a-Time heuristic search for interaction test suites. In:Proc. of the 9th Annual Conf. on Genetic and Evolutionary Computation(GECCO). 2007. 1082-1089.[doi:10.1145/1276958.1277173]
    [18] Nayeri P, Colbourn CJ, Konjevod G. Randomized post-optimization of covering arrays. European Journal of Combinatorics, 2013,34(1):91-103.[doi:10.1016/j.ejc.2012.07.017]
    [19] Torres-Jimenez J, Rodriguez-Tello E. New bounds for binary covering arrays using simulated annealing. Information Sciences, 2012,185(1):137-152.[doi:10.1016/j.ins.2011.09.020]
    [20] Calvagna A, Gargantini A. IPO-s:Incremental generation of combinatorial interaction test data based on symmetries of covering arrays. In:Proc. of the IEEE Int'l Conf. on Software Testing Verification and Validation Workshops. 2009.[doi:10.1109/ICSTW. 2009.7]
    [21] White T. Hadoop:The Definitive Guide. 4th ed., Sebastopol:O'Reilly Media, 2015. 3-97.
    [22] Eckel B. Thinking in Java. 4th ed., Upper Saddle River:Prentice Hall, 2006. 797-822.
    附中文参考文献:
    [1] 聂长海.软件测试的概念与方法.北京:清华大学出版社,2013.1-22.
    [2] 聂长海.组合测试.北京:科学出版社,2015.1-119.
    [16] 梁亚澜,聂长海.覆盖表生成的遗传算法配置参数优化.计算机学报,2012,35(7):1522-1538.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

曾梦凡,陈思洋,张文茜,聂长海.利用蚁群算法生成覆盖表:探索与挖掘.软件学报,2016,27(4):855-878

Copy
Share
Article Metrics
  • Abstract:8117
  • PDF: 7372
  • HTML: 2637
  • Cited by: 0
History
  • Received:August 30,2015
  • Revised:October 15,2015
  • Online: January 14,2016
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2038162Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063