International Journal of Information Technology and Computer Science (IJITCS)
IJITCS Vol. 7, No. 10, 8 Sep. 2015
Cover page and Table of Contents: PDF (size: 551KB)
Construction of Strength Two Mixed Covering Arrays Using Greedy Mutation in Genetic Algorithm
Full Text (PDF, 551KB), PP.23-34
Views: 0 Downloads: 0
Author(s)
Index Terms
Pair-wise testing, mixed covering arrays, genetic algorithm, mutation, greedy approach
Abstract
Metaheuristic methods are capable of solving a wide range of combinatorial problems competently. Genetic algorithm (GA) is a metaheuristic search based optimization algorithm that can be used to generate optimal Covering Arrays (CAs) and Mixed Covering Arrays (MCAs) for pair-wise testing. Our focus in the work presented in this paper is on the strategies of performing mutation in GA to enhance the overall performance of GA in terms of solution quality and computational time (number of generations). This is achieved by applying a greedy approach to perform mutation at a position that minimizes the loss of existing distinct pairs in the parent CA/MCA and ensures that the generated offspring is of good quality. Experiments are conducted on several benchmark problems to evaluate the performance of the proposed greedy based GA with respect to the existing state-of-the-art algorithms. Our evaluation shows that the proposed algorithm outperforms its GA counterpart by generating better quality MCA in lesser number of generations. Also the proposed approach yields better/comparable results compared to the existing state-of-the-art algorithms for generating CAs and MCAs.
Cite This Paper
Sangeeta Sabharwal, Priti Bansal, Nitish 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.23-34, 2015. DOI:10.5815/ijitcs.2015.10.04
Reference
[1]D. M. Cohen, S. R. Dalal, M. L. Fredman and G. C. Patton, “The AETG system: an approach to testing based on combinatorial design”, IEEE Transactions on Software Engineering, 1997, 23(7):437–443.
[2]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, HASE 98, pp. 254–261, 1998, Washington, DC.
[3]D. M. Cohen, S. R. Dalal, A. Kajla and G. C., “The automatic efficient test generator”, In Proceedings of the IEEE International Symposium on Software Reliability Engineering, pp. 303–309, 1994.
[4]D. M. Cohen, S. R. Dalal, M. L. Fredman and G. C. Patton, “The combinatorial design approach to automatic test generation”, IEEE Software, pp. 83–87, 1996.
[5]K. Burr and W. Young, “Combinatorial test techniques: table-based automation, test generation and code coverage”, In Proceedings of the International Conference on Software Testing Analysis & Review, San Diego, 1998.
[6]S. R. Dalal, A. J. N. Karunanithi, J. M. L. Leaton, G. C. P. Patton and B. M. Horowitz, “Model-based testing in practice”, In Proceedings of the International Conference on Software Engineering, (ICSE ’99), pp. 285-94, New York, 1999.
[7]R. Kuhn, D. Wallace and A. Gallo, “Software fault interactions and implications for software testing”, IEEE Transactions of Software Engineering, 30(6):418–421, 2004.
[8]G. Seroussi and N. Bshouty, “Vector sets for exhaustive testing of logical circuits”, IEEE Trans. Information Theory, 34:513-522, 1988.
[9]B. J. Garvin, M. B. Cohen and M. B. Dwyer, “Evaluating improvements to a meta-heuristic search for constrained interaction testing”, Empirical Software Engineering. 16:61–102, 2011.
[10]P. Bansal, N. Mittal, A. Sabharwal and S. Koul, “Integrating greedy based approach with genetic algorithm to generate mixed covering arrays for pair-wise testing”, In Proceedings of the Seventh International Conference on Contemporary Computing, IEEE Computer Society, Noida, India, 2014.
[11]P. Flores and Y. Cheon, “PWiseGen: Generating test cases for pairwise testing using genetic algorithms”, In IEEE International Conference on Computer Science and Automation Engineering (CSAE), vol. 2, pp. 747 –752, 2011.
[12]P. Flores, PWiseGen, 2010. https://code.google.com/p/pwisegen/.
[13]X. Yuan, M.B. Cohen and A. Memon, “Covering array sampling of input event sequences for automated GUI testing”, In Proceedings of the 22nd International Conference on Automated Software Engineering, pp. 405-408, 2007.
[14]W. Wang, S. Sampath, Y. Lei and R. Kacker, “An interaction–based test sequence generation approach for testing web applications”, In Proceedings of 11th International IEEE HASE symposium, pp. 209-218, 2008."
[15]C. D. Nguyen, A. Marchetto and P. Tonella, “Combining model-based and combinatorial testing for effective test case generation”, In Proceedings of International Symposium on Software Testing and Analysis, ISSTA, pp. 100-110, 2012.
[16]X. Qu, M.B. Cohen and K. M. Woolf, “Combinatorial Interaction Regression Testing: a Study of Test Case Generation and Prioritization”, In Proceedings of the IEEE International Conference on Software Maintenance, pp. 255-264, 2007.
[17]M. B. Cohen, M. B. Dwyer and J. F. Shi, “Constructing Interaction Test Suites for Highly-Configurable Systems in the Presence of Constraints: A Greedy Approach”, IEEE Transaction on Software Engineering, 34(5), pp. 633-650, 2008.
[18]A. Hedayat, N. Sloane and J. Stufken, “Orthogonal Arrays”, Springer New York. 1999.
[19]R. Mandl, “Orthogonal latin squares: an application of experiment design to compiler testing”, Communications of the ACM, 28(10): pp. 1054-1058, 1985.
[20]C. Nie and H.Leung, “A survey of combinatorial testing”, ACM Computing Surveys (CSUR)”, v.43 n.2, pp.1-29, 2011.
[21]N. Sloane. “Covering arrays and intersecting codes”, Journal of Combinatorial Designs, 1(1):51–63, 1993.
[22]M. B. Cohen, C.J. Colbourn, P.B. Gibbons and W. B. Mugridge, “Constructing test suites for interaction testing”, In Proceedings of the International Conference on Software Engineering, (ICSE 2003), pp. 38-48, Portland OR, 2003.
[23]D. E. Goldberg, “Genetic algorithms in search, optimization, and machine learning”, Reading, MA: Addison-Wesley, 1989.
[24]S. Marsili-Libelli and P. Alba, “Adaptive mutation in genetic algorithms”, Soft Computing. 4, 76–80, 2000.
[25]K. A. Bush, “Orthogonal arrays of index unity”, In Annals of Mathematical Statistics 23.3, pp. 426-434, 1952.
[26]A. Hartman, “Software and hardware testing using combinatorial covering suites”, In Graph Theory, Combinatorics and Algorithms, Operations Research/Computer Science Interfaces Series, Springer US, vol.34, pp. 237-266, 2005.
[27]A. W. Williams, “Determination of test configurations for pair-wise interaction coverage”, In Proceedings of 13th International Conference on the Testing of Communicating Systems, Ottawa, Canada, pp. 59-74, 2000.
[28]Y. Lei, R. Kacker, D. R. Kuhn, V. Okun and J. Lawrence, “IPOG: a general strategy for t-way software testing”, In Proceedings of the 14th Annual IEEE International Conference and Work-shops on the Engineering of Computer- Based Systems-ECBS, Tuscon, AZ,USA, IEEE Computer Society, pp. 549-556, 2007.
[29][M. Grindal, J. Offutt and J. Mellin, “Conflict management when using combination strategies for software testing”, In Proceedings of 18th Australian Software Engineering Conference, Melbourne, Australia, 2007.
[30]Y. Tung and W. Aldiwan, “Automating test case generation for the new generation mission software system”, In Proceedings of the IEEE Aerospace Conference, pp. 431-437, 2000.
[31]E. Lehmann and J. Wegener, “Test case design by means of the CTE XL”, In 8th European International Conference on Software Testing, Analysis & Review (EuroSTAR 2000), Copenhagen, Denmark, pp. 1-10, 2000.
[32]B.Jenkins, Jenny download web page, Bob Jenkin’s website, 2005 http://burtleburtle.net/bob/math/jenny.html.
[33]J. Czerwonka, “Pairwise testing in real world: practical extension to test case generator”, In 24th pacific Northwest Software Quality Conference, IEEE Computer Society, Portland, OR, USA, pp. 419-430, 2006.
[34]R. C. Bryce and C. J. Colbourn, “The density algorithm for pairwise interaction testing”. Software Testing”, Verification and Reliability 17, 3, pp. 159-182, 2007.
[35]R. C. Bryce and C. J. Colbourn, “A density–based greedy algorithm for higher strength covering arrays”, Software Testing, Verification and Reliability 17, 3, pp. 1-17, 2008.
[36]M.I. Younis, K. Z. Zamli, M. F. J. Klaib, Z. H. C. Soh, S. A. C. Abdullah and N. A.M. Isa, “Assessing IRPS as an efficient pairwise test data generation strategy”, In International Journal of Advanced Intelligence Paradigms 2.1, pp. 90-104, 2010.
[37]K. C. Tai and Y. Lei, “A test generation strategy for pairwise testing”, IEEE Transaction Software Engineering 28, 1, pp. 109-111, 2002.
[38]Y. Lei, R. Kacker, D. R. Kuhn, V. Okun and J. Lawrence, “IPOG/IPOG-D: efficient test generation for multi-way combinatorial testing”, Software Testing, Verification and Reliability 18, 3, pp. 125-148, 2008.
[39]A. Calvagna and A. Gargantini, “IPO-s: incremental generation of combinatorial interaction test data based on symmetries of covering arrays”, In IEEE International Conference on Software Testing, Verification, and Validation Workshops, IEEE Computer Society, Denver, CO, USA, pp. 10–18, 2009.
[40]M.B. Cohen and C.J. Colbourn, J. S. Collofello, P.B. Gibbons and W. B. Mugridge, “Variable strength interaction testing of components”, In Proceedings of the International Computer Software and Applications Conference, (COMPSAC 2003), Dallas TX, 2003.
[41]M. B. Cohen, C. J. Colbourn and A. C.H. Ling, “Augmenting simulated annealing to build interaction test suites”, In Proceedings of the 14th International Symposium on Software Reliability Engineering, IEEE Computer Society, pp. 394-405, 2003.
[42]M. B. Cohen, C. J. Colbourn and A. C.H. Ling, “Constructing strength three covering arrays with augmented annealing”, In Discrete Mathematics 308.13, pp. 2709-2722, 2008.
[43]H. Avila-George, J. Torres-Jimenez, V. Hernández and L. Gonzalez-Hernandez, “Simulated annealing for constructing mixed covering arrays”, In Proceedings of the 9th International Symposium on Distributed Computing and Arti?cial Intelligence - DCAI, ser. Advances in Intelligent and Soft Computing, vol. 151, pp. 657–664, Springer Berlin, Heidelberg, 2012.
[44]H.Avila-George, J. Torres-Jimenez, L.Gonzalez-Hernandez and V. Hernández, “Metaheuristic approach for constructing functional test-suites”, In Software, IET, Volume: 7, Issue: 2, pp. 104-117, 2013.
[45]K. J. Nurmela, “Upper bounds for covering arrays by tabu search”, In Discrete Applied Mathematics 138 (1-2 2004), pp. 143-152, 2004.
[46]R. A. Walker II and C. J. Colbourn, “Tabu Search for covering arrays using permutation vectors”, In Journal of Statistical Planning and Inference 139.1(2009), pp. 69-80.
[47]L. Gonzalez-Hernandez, N. Rangel-Valdez and J. Torres-Jimenez, “Construction of mixed covering arrays of variable strength using a tabu search approach”, In: Wu, W., Daescu, O. (eds.) COCOA 2010, Part I. LNCS, vol. 6508, pp. 51–64, Springer, Heidelberg, 2010.
[48]T. Shiba, T. Tsuchiya and T. Kikuno, “ Using artificial life techniques to generate test cases for combinatorial testing”, In Proceedings of the 28th Annual International Computer Software and Applications Conference, pp. 72–77. IEEE Computer Society, 2004..
[49]X. Chen, Q. Gu, J. Qi and D. Chen, “Applying particle swarm optimization to pairwise testing”, In Proceedings of the 34th Annual IEEE Computer Software and Application Conference, Seoul, Korea, 2010.
[50]B. S. Ahmed and K. Z. Zamli, “PSTG: a t-way strategy adopting particle swarm optimization”, In 4th Asia International Conference on Mathematical/ Analytical Modelling and Computer Simulation, IEEE Computer Society, Kota Kinabalu, Borneo, Malaysia, pp. 1-5, 2010.
[51]B. S. Ahmed and K. Z. Zamli, “T –way test data generation strategy based on particle swarm optimization”, In 2nd International Conference on Computer Research and Development, IEEE Computer Society, Kuala Lumpur, Malaysia, pp. 93-97, 2010.
[52]B. S. Ahmed and K. Z. Zamli, “The development of a particle swarm based optimization strategy for pairwise testing”, In Journal of Artificial Intelligence, 4: pp. 156-165, 2011.
[53]B. S. Ahmed and K. Z. Zamli, “A variable strength interaction test suites generation strategy using Particle Swarm Optimization”, Journal of Systems and Software, December, 84(12): 2171-2185, 2011.
[54]B. S. Ahmed, K. Z. Zamli and C. P. Lim, “Application of particle swarm optimization to uniform and variable strength covering array construction”, Applied Soft Computing, 12, 1330–1347, 2012..
[55]S. Jia-Ze and W. Shu-Yan, “Generation of pairwise test sets using novel DPSO algorithm”, Green Communications and Networks, LNEE, vol.113, pp. 479-487, Springer, Heidelberg, 2012.
[56]S. A. Ghazi and M. A. Ahmed, “Pair-wise test coverage using genetic algorithms”, In the 2003 Congress on Evolutionary Computation, vol. 2, pp. 1420-1423, IEEE Computer Society, Australia, 2003.
[57]J. D. McCaffrey, “Generation of pairwise test sets using a genetic algorithm”, In Proceedings of 33rd Annual IEEE International Computer Software and Applications Conference, pp. 626–631, IEEE Press, Los Alamitos, 2009.
[58]J. D.McCaffrey, “An empirical study of pairwise test set generation using a genetic algorithm”, In ITNG 2010: 6th International Conference on Information Technology: New Generations, pp. 992-997, IEEE Computer Society, Las Vegas, 2010.
[59]L. Yalan, C. Nie, J. M. Kauffman, G. M. Kapfhammer and H. Leung, “Empirically identifying the best genetic algorithm for covering array generation”, In Proceedings of the Third International Symposium on Search Based Software Engineering, Fast Abstract Track, Szeged, Hungary, 2011.
[60]P. Bansal, S. Sabharwal, S. Malik, V. Arora and 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 8084, pp. 294-299, Springer-Verlag, Berlin Heidelberg, 2013.
[61]J. Stardom, “Metaheuristic and the search for covering and packing arrays”, Master’s Thesis, Simon Fraser University, 2001.
[62]B. Garvin, M. Cohen and M. Dwyer, “An improved meta-heuristic search for constrained interaction testing”, In International Symposium on Search Based Software Engineering (SSBSE), pages 13-22, 2009.
[63]B. Hnich, S. Prestwich, E. Selensky and B. M. Smith, “Constraint models for the covering test problem”, Constraints, v. 11 n.2-3, pp. 199–219, 2006.
[64]J. Yan and J. Zhang, “Backtracking algorithms and search heuristics to generate test suites for combinatorial testing”, In Proceedings of the 30th Annual International Conference on Computer Software and Applications (COMPSAC’06), pp. 385-394, 2006.
[65]M. Banbara, H. Matsunaka, N. Tamura K. Inoue, “Generating combinatorial test cases by efficient SAT encodings suitable for CDCL SAT solvers”, Springer Berlin Heidelberg, 2010.
[66]A. Calvagna and A. Gargantini, “Combining satisfiability solving and heuristics to constrained combinatorial interaction testing”, In 3rd international conference on tests and proofs, Springer, pp 27–42, 2009.
[67]A. Calvagna and A. Gargantini, “A logic-based approach to combinatorial testing with constraints”, In B. Beckert and R. H?hnle, editors, Tests and Proofs, Second International Conference, TAP 2008, Prato, Italy, April 9-11, 2008. Proceedings, volume 4966 of Lecture Notes in Computer Science, pages 66_83. Springer, 2008.
[68]A. Calvagna and A. Gargantini, “A formal logic approach to constrained combinatorial testing”, Journal of Automated Reasoning pp.1-28, 2010.
[69]P. J. Schroeder and P. Bolaki and V. Gopu, “Comparing the fault detection effectiveness of n-way and random test suites”, In Proceedings of the International Symposium on Empirical Software Engineering (ISESE), IEEE Computer Society, pp. 49-59, 2004.
[70]http://www.pairwise.org
[71]J. D. Schaffer et. al., “A study of control parameters affecting online performance of genetic algorithms for function optimization”, In Proceeding of the Third International Conference on Genetic Algorithms. pp. 51-60, 1989.
[72]T. B?ck, “Optimal mutation rates in genetic search”, In Proceedings of the Fifth International Conference on Genetic Algorithms. pp. 2-8, 1993.
[73]ACTS download page, National Institute of Standards and Technology, Information Technology Laboratory.
[74]http://sourceforge.net/projects/allpairs/.