Improved Mixed Neighborhood Tabu Search by Random Selection for Combinatorial Interaction Testing

  • Imad Hadi Hasan Department of Software and Informatics Engineering, College of Engineering , Salahaddin University-Erbil, Kurdistan Region, Iraq.
  • Moayad Potrus Department of Software and Informatics Engineering, College of Engineering , Salahaddin University-Erbil, Kurdistan Region, Iraq.
Keywords: Combinatorial Interaction Testing, Covering Array, Combinatorial Optimization, Software Testing


Combinatorial interaction testing (CIT) is a technique used to find minimal test suite among configuration options of a System Under Test (SUT) that uses a Covering Array (CA) as a combinatorial structure. CIT is very effective for reducing the costs of the testing process that uses a sampling technique instead of exhaustive testing. This paper proposes the modification of Mixed Neighborhood Tabu Search (RMiTS) algorithm using the random selection strategy. The base MiTS algorithm is originally used for generating t-way Mixed Covering Array (MCA). The modification improves the algorithm performance (running time) to cover all possible input configuration combinations to produce the optimal or near-optimal test suites. The modified algorithm is evaluated through a comparison against the base MiTS algorithm to confirm the performance improvements. Also, it is compared to a state-of-the-art algorithm known as Advanced Combinatorial Test Tool (ACTS) to confirm its efficiency. The experimental results confirm the effectiveness of the modifications that improved the performance for all applied benchmarks, and also it shows that RMiTS is more efficient than ACTS.


Ahmed, B. S. (2016) ‘Test case minimization approach using fault detection and combinatorial optimization techniques for configuration-aware structural testing’, Engineering Science and Technology, an International Journal. Elsevier, 19(2), pp. 737–753. doi: 10.1016/j.jestch.2015.11.006.
Ahmed, B. S. et al. (2017) ‘Handling constraints in combinatorial interaction testing in the presence of multi objective particle swarm and multithreading’, Information and Software Technology. Elsevier, 86, pp. 20–36. doi: 10.1016/J.INFSOF.2017.02.004.
Ahmed, B. S. and Zamli, K. Z. (2011) ‘A variable strength interaction test suites generation strategy using Particle Swarm Optimization’, Journal of Systems and Software, 84(12), pp. 2171–2185. doi: 10.1016/j.jss.2011.06.004.
Ahmed, B. S., Zamli, K. Z. and Lim, C. P. (2012) ‘Constructing a t-way interaction test suite using the particle swarm optimization approach’, International Journal of Innovative Computing, Information and Control. ICIC International, 8(1), pp. 431–452.
Avila-George, H. et al. (2012) ‘Simulated Annealing for Constructing Mixed Covering Arrays’, in. Springer, Berlin, Heidelberg, pp. 657–664. doi: 10.1007/978-3-642-28765-7_79.
Bryce, R. C., Colbourn, C. J. and Cohen, M. B. (2005) ‘A framework of greedy methods for constructing interaction test suites’, in Proceedings of the 27th international conference on Software engineering - ICSE ’05. New York, New York, USA: ACM Press, p. 146. doi: 10.1145/1062455.1062495.
Cohen, D. M. et al. (1997) ‘The AETG system: an approach to testing based on combinatorial design’, IEEE Transactions on Software Engineering, 23(7), pp. 437–444. doi: 10.1109/32.605761.
Cohen, M. B., Gibbons, P. B., Mugridge, W. B., Colbourn, C. J., et al. (2003) ‘A variable strength interaction testing of components’, in 27th Annual International Computer Software and Applications Conference. COMPAC 2003. IEEE Comput. Soc, pp. 413–418. doi: 10.1109/CMPSAC.2003.1245373.
Cohen, M. B., Gibbons, P. B., Mugridge, W. B. and Colbourn, C. J. (2003) ‘Constructing test suites for interaction testing’, in 25th International Conference on Software Engineering, 2003. Proceedings. IEEE, pp. 38–48. doi: 10.1109/ICSE.2003.1201186.
Cohen, M. B., Colbourn, C. J. and Ling, A. C. H. (2003) ‘Augmenting simulated annealing to build interaction test suites’, in Proceedings - International Symposium on Software Reliability Engineering, ISSRE. IEEE, pp. 394–405. doi: 10.1109/ISSRE.2003.1251061.
Cohen, M. B., Dwyer, M. B. and Shi, J. (2007) ‘Interaction testing of highly-configurable systems in the presence of constraints’, in Proceedings of the 2007 international symposium on Software testing and analysis - ISSTA ’07. New York, New York, USA: ACM Press, p. 129. doi: 10.1145/1273463.1273482.
Ghazi, S. A. and Ahmed, M. A. (2003) ‘Pair-wise test coverage using genetic algorithms’, in 2003 Congress on Evolutionary Computation, CEC 2003 - Proceedings. IEEE, pp. 1420–1424. doi: 10.1109/CEC.2003.1299837.
Glover, F. (1986) ‘Future paths for integer programming and links to artificial intelligence’, Computers and Operations Research. Pergamon, 13(5), pp. 533–549. doi: 10.1016/0305-0548(86)90048-1.
Glover, F. (1998) ‘Tabu Search: A Tutorial’, Interfaces, 20(4), pp. 74–94. doi: 10.1287/inte.20.4.74.
Glover, F. and Laguna, M. (1999) TABU search. Kluwer Academic Publishers.
Gonzalez-Hernandez, L. (2015) ‘New bounds for mixed covering arrays in t-way testing with uniform strength’, Information and Software Technology. Elsevier, 59, pp. 17–32. doi: 10.1016/j.infsof.2014.10.009.
Gonzalez-Hernandez, L. and Torres-Jimenez, J. (2010) ‘MiTS: A new approach of tabu search for constructing mixed covering arrays’, in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer, Berlin, Heidelberg, pp. 382–393. doi: 10.1007/978-3-642-16773-7_33.
Kalaee, A. and Rafe, V. (2016) ‘An Optimal Solution for Test Case Generation Using ROBDD Graph and PSO Algorithm’, Quality and Reliability Engineering International. John Wiley & Sons, Ltd, 32(7), pp. 2263–2279. doi: 10.1002/qre.1934.
Kuhn, D. R., Kacker, R. N. and Lei, Y. (Associate professor of computer science) (2013) Introduction to combinatorial testing. CRC Press. Available at: (Accessed: 19 January 2019).
Lei, Y. et al. (2007) ‘IPOG: A general strategy for T-way software testing’, in Proceedings of the International Symposium and Workshop on Engineering of Computer Based Systems. IEEE, pp. 549–556. doi: 10.1109/ECBS.2007.47.
Lei, Y. and Tai, K. C. (1998) ‘In-parameter-order: A test generation strategy for pairwise testing’, in Proceedings - 3rd IEEE International High-Assurance Systems Engineering Symposium, HASE 1998. IEEE Comput. Soc, pp. 254–261. doi: 10.1109/HASE.1998.731623.
Lin, J. et al. (2016) ‘TCA: An efficient two-mode meta-heuristic algorithm for combinatorial test generation’, in Proceedings - 2015 30th IEEE/ACM International Conference on Automated Software Engineering, ASE 2015. IEEE, pp. 494–505. doi: 10.1109/ASE.2015.61.
McCaffrey, J. D. (2009) ‘Generation of Pairwise Test Sets Using a Genetic Algorithm’, in 2009 33rd Annual IEEE International Computer Software and Applications Conference. IEEE, pp. 626–631. doi: 10.1109/COMPSAC.2009.91.
Nie, C. and Leung, H. (2011) ‘A survey of combinatorial testing’, ACM Computing Surveys. ACM, 43(2), pp. 1–29. doi: 10.1145/1883612.1883618.
Ploskas, N. et al. (2016) ‘Introduction to GPU programming in MATLAB’, GPU Programming in MATLAB. Morgan Kaufmann, pp. 71–107. doi: 10.1016/B978-0-12-805132-0.00004-7.
Schmidt, B. et al. (2018) ‘Compute Unified Device Architecture’, Parallel Programming. Morgan Kaufmann, pp. 225–285. doi: 10.1016/B978-0-12-849890-3.00007-1.
Yu, L. et al. (2013) ‘ACTS: A combinatorial test generation tool’, in Proceedings - IEEE 6th International Conference on Software Testing, Verification and Validation, ICST 2013. IEEE, pp. 370–375. doi: 10.1109/ICST.2013.52.
How to Cite
Hasan, I. and Potrus, M. (2020) “Improved Mixed Neighborhood Tabu Search by Random Selection for Combinatorial Interaction Testing”, Zanco Journal of Pure and Applied Sciences, 32(5), pp. 1-19. doi: 10.21271/ZJPAS.32.5.1.
Mathematics ,Physics and Engineering Researches