A Hybrid Artificial Bee Colony and Harmony Search Algorithm to Generate Covering Arrays for Pair-wise Testing

Full Text (PDF, 640KB), PP.59-70

Views: 0 Downloads: 0


Priti Bansal 1,* Sangeeta Sabharwal 1 Nitish Mittal 1

1. Netaji Subhas Institute of Technology, Sector-3, Dwarka, New Delhi-110078, India

* Corresponding author.

DOI: https://doi.org/10.5815/ijisa.2017.08.07

Received: 8 Jan. 2017 / Revised: 15 Feb. 2017 / Accepted: 22 Feb. 2017 / Published: 8 Aug. 2017

Index Terms

Covering array, pair-wise testing, artificial bee colony, harmony search


Combinatorial Interaction Testing (CIT) is a cost effective testing technique that aims to detect interaction faults generated as a result of interaction between components or parameters in a software system. CIT requires the generation of effective test sets that cover all possible t-way (t denotes the strength of testing) interactions between parameters. Covering array (CA) and mixed covering array (MCA) are often used to represent test sets. This paper presents a hybrid algorithm that integrates artificial bee colony algorithm (ABC) and harmony search algorithm (HS) to construct CAs for testing all 2-way interactions (pair-wise testing) in software systems. The performance of the proposed hybrid algorithm ABCHS-CAG is compared and analyzed by performing experiments on a set of benchmark problems on pair-wise testing. The results show that ABCHS-CAG generates smaller CAs than its greedy counterparts whereas its performance is comparable to the existing state-of-the-art meta-heuristic algorithms.

Cite This Paper

Priti Bansal, Sangeeta Sabharwal, Nitish Mittal, "A Hybrid Artificial Bee Colony and Harmony Search Algorithm to Generate Covering Arrays for Pair-wise Testing", International Journal of Intelligent Systems and Applications(IJISA), Vol.9, No.8, pp.59-70, 2017. DOI:10.5815/ijisa.2017.08.07


[1]D. M. Cohen, S.R. Dalal, and M. L. Fredman, “The combinatorial design approach to automatic test generation,” IEEE Software, pp. 83–87, 1996.
[2]K. Burr, and W. Young, “Combinatorial test techniques: table-based automation, test generation and code coverage,” International Conference on Software Testing Analysis & Review,San Diego,1998.
[3]R. Kuhn, D. Wallace, and A. Gallo, “Software fault interactions and implications for software testing,” IEEE Transactions of Software Engineering., 30(6), pp. 418–421, 2004.
[4]C. Nie, H. Leung, “A survey of combinatorial testing,” ACM Computing Surveys (CSUR), 43(2), pp. 1-29, 2011
[5]Y. Lei, and K. C. Tai, “ In-parameter-order: a test generation strategy for pairwise testing,” In: 3rd IEEE International Symposium on High-Assurance Systems Engineering, p. 254–261, Washington, DC, 1998.
[6]M. B Cohen, C. J. Colbourn, P. B. Gibbons, and W. B. Mugridge, “Constructing test suites for interaction testing,” ICSE, pp. 38-48, Portland OR, 2003
[7]C. Blum, “Hybrid metaheuristics in combinatorial optimization: A survey,” Applied Soft Computing, 11(6), pp. 4135-4151, 2011.
[8]D. Karaboga,“An idea based on honeybee swarm for numerical optimization,” Technical Report TR06, Erciyes University, Engineering Faculty, Computer Engineering Department, 2005.
[9]Z. W. Geem, J. H. Kim, and G. V. Loganathan, “A new heuristic optimization algorithm: harmony search. Simulation,” pp.60–68, 2001.
[10]A. Hedayat, N. Sloane, and J. Stufken, “Orthogonal Arrays,” Springer New York, 1999.
[11]G. Sherwood , ”TestCover,” http://testcover.com/pub/constex.php.
[12]A. W. Williams, “Determination of test configurations for pair-wise interaction coverage,” 13th International Conference on the Testing of Communicating Systems, Ottawa, Canada, pp. 59-74, 2000.
[13]A. Hartman, and L. P. Raskin,“Problems and algorithms for covering arrays.,”JDM.,284 (1-3), pp. 149-156, 2004.
[14]N. Kobayashi, T. Suchiya, and T. Kikuno, “A new method for constructing pair-wise covering designs for software testing.,” IPL, 81 (2), pp. 85-91, 2002.
[15]Y. Tung, and W. Aldiwan,“Automating test case generation for the new generation mission software system,”IEEE Aerospace Conference, pp. 431-437, 2000.
[16]J. Arshem, “Tvg,”: http://sourceforge.net/projects/tvg.
[17]J. Czerwonka,“ Pairwise testing in real world: practical extension to test case generator,” 24th Pacific Northwest Software Quality Conference, Portland, OR, USA, pp. 419-430, 2006.
[18]B. Jenkins,: http://burtleburtle.net/bob/math/jenny.html. [19]Z.Wang, B. Xu, C. Nie, “Greedy heuristic algorithms to generate variable strength combinatorial test suite,” International Conference on Quality Software. IEEE Computer Society. pp. 155–160, 2008.
[20]Z. Zhang, J. Yan, Y. Zhao, and J. Zhang, “Generating combinatorial test suite using combinatorial optimization,” Journal of Systems and Software, vol. 98, pp. 191–207, 2014.
[21]Y. .Lei, R. Kacker, D. R. Kuhn, V. Okun, and J. Lawrence, “IPOG: A general strategy for t-way software testing,” 14th IEEE International Conference and Work-shops on the Engineering of Computer- Based Systems-ECBS,” Tuscon, AZ,USA, pp. 549-556, 2007.
[22]T. Shiba, T. Tsuchiya, and T. Kikuno, “Using artificial life techniques to generate test cases for combinatorial testing,” 28th Annual International Computer Software and Applications Conference, pp. 72–77, IEEE Computer Society, 2004.
[23]L. Gonzalez-Hernandez, N. Rangel-Valdez, J. Torres-Jimenez, “Construction of mixed covering arrays of strengths 2 through 6 using a tabu search approach,” Discrete Mathematics Algorithms and Applications, 4 (3),2012.
[24]H. Avila-George, J. Torres-Jimenez, V. Hernández, V. L. Gonzalez-Hernandez,“Simulated annealing for constructing mixed covering arrays,” Advances in Intelligent and Soft Computing,vol.151, pp. 657–664, Springer Berlin , Heidelberg, 2012.
[25]B. S. Ahmed, K. Z. Zamli, “The development of a particle swarm based optimization strategy for pairwise testing,” Journal of Artificial Intelligence, 4, pp. 156-165, 2011.
[26]B. J. Garvin, M. B. Cohen, M. B. Dwyer,”Evaluating improvements to a meta-heuristic search for constrained interaction testing,” Empirical Software Engineering, 16(1). pp. 61-102, 2011.
[27]J. D. McCaffrey,“Generation of pairwise test sets using a genetic algorithm,” 33rd Annual IEEE International Computer Software and Applications Conference,” pp. 626–631, Los Alamitos, 2009.
[28]P. Flores, Y. Cheon, “PWiseGen: Generating test cases for pairwise testing using genetic algorithms,”International Conference on Computer Science and Automation Engineering, pp. 747 –752, 2011.
[29]P. Bansal, S. Sabharwal, S. Malik, V. Arora, V. Kumar, “An approach to test set generation for pair-wise testing using genetic algorithms,” In: G. Ruhe and Y. Zhang (Eds.): SSBSE 2103, LNCS 808., pp. 294-299, Springer-Verlag, Berlin Heidelberg, 2013.
[30]B. S. Ahmed, T. S. Abdulsamad, and M. Y. Potrus,“ Achievement of minimized combinatorial test suite for configuration-aware software functional testing using the Cuckoo search algorithm.,”Information and Software Technology, 66, pp. 13–29, 2015.
[31]T. Mahmoud, B. S. Ahmed, “An efficient strategy for covering array construction with fuzzy logic-based adaptive swarm optimization for software testing use,” Experts Systems with Applications, 42, pp. 8753–8765, 2015.
[32]J. Lin, C. Luo, S. Cai, K. Su, D. Hao, and Lu Zhang, “TCA: An efficient two-mode meta-heuristic algorithm for combinatorial test generation,” In 30th International IEEE/ACM Conference on Automated Software Engineering (ASE), pp. 494-505, 2015.
[33]S. Sabharwal, P Bansal, N. Mittal, and S. Malik, “Construction of Mixed Covering Arrays for Pair-wise Testing Using Probabilistic Approach in Genetic Algorithm,” The Arabian Journal for Science and Engineering, Springer, 2016.
[34]S. Sabharwal, P.Bansal and N.Mittal, “Construction of Strength Two Mixed Covering Arrays Using Greedy Mutation in Genetic Algorithm,” International Journal of Information Technology and Computer Science (IJITCS), Vol. 7, No. 10, pp. no..23-34, September 2015, ISSN: 2074-9007 (Print), ISSN: 2074-9015 (Online), DOI: 10.5815/ijitcs
[35]Y. Jia, M. Cohen, and M. Petke, “Learning Combinatorial Interaction Test Generation Strategies using Hyperheuristic Search,” ICSE, pp.540–550, 2015.
[36]P. Bansal, S. Sabharwal, N. Mittal and S. Arora,“ABC-CAG: Covering Array Generator for Pair-wise Testing Using Artificial Bee Colony Algorithm,”e-Informatica Software Engineering Journal, 2016.
[37]J. Stardom, “Metaheuristic and the search for covering and packing arrays,” Master’s Thesis, Simon Fraser University, 2001.
[38]G. Zhu, and S. Kwong, ‘Gbest-guided artificial bee colony algorithm for numerical function optimization,” Applied Mathematics and Computatio,. 217, pp. 3166–3173, 2010.
[39]D. R Kuhn, R. N. Kacker, and Yu Lei, “Practical Combinatorial Testing,” NIST Special Publication, 800-142, 2010.