An Approach for the Generation of Multi-Objective Algorithms Applied to the Integration and Test Order Problem
DOI:
https://doi.org/10.5753/jserd.2021.816Keywords:
Multi-Objective Evolutionary Optimization, Grammatical Evolution, Iterated Racing, Software TestingAbstract
Multi-Objective Evolutionary Algorithms (MOEAs) have been successfully applied to solve hard real software engineering problems. However, to choose and design a MOEA is considered a difficult task, since there are several parameters and components to be configured. These aspects directly impact the generated solutions and the performance of MOEAs. In this sense, this paper proposes an approach for the automatic generation of MOEAs applied to the Integration and Test Order (ITO) problem. Such a problem refers to the generation of optimal sequences of units for integration testing. The approach includes a set of parameters and components of different MOEAs, and is implemented with two design algorithms: Grammatical Evolution (GE) and Iterated Racing (irace). Evaluation results are presented, comparing the MOEAs generated by both design algorithms. Furthermore, the generated MOEAs are compared to two well-known MOEAs used in the literature to solve the ITO problem. Results show that the MOEAs generated with GE and irace perform similarly, and both outperform traditional MOEAs. The approach can reduce efforts spent to design and configure MOEAs, and serves as basis for implementing solutions to other software engineering problems.
Downloads
References
Abdurazik, A. and Offutt, J. (2009). Using coupling-based weights for the class integration and test order problem. Computer Journal, 52(5):557–570.
Arcuri, A. and Briand, L. (2014). A hitchhiker’s guide to statistical tests for assessing randomized algorithms in software engineering. Software Testing, Verification and Reliability, 24(3):219–250.
Assunção, W. K. G., Colanzi, T. E., Vergilio, S. R., and Pozo, A. T. R. (2013). Generating integration test orders for aspect oriented software with multi-objective algorithms. Revista de Informática Teórica e Aplicada, 20(2):301–327.
Assunção, W. K. G., Colanzi, T. E., Vergilio, S. R., and Pozo, A. (2014). A multi-objective optimization approach for the integration and test order problem. Information Sciences, 267(0):119–139.
Bansal, P., Sabharwal, S., and Sidhu, P. (2009). An investigation of strategies for finding test order during integration testing of object oriented applications. In Proceedings of the ICM2CS, pages 1–8.
Barros, R. C., Basgalupp, M. P., Cerri, R., da Silva, T. S., and de Carvalho, A. C. (2013). A Grammatical Evolution Approach for Software Effort Estimation. In Genetic and Evolutionary Computation Conference, pages 1413–1420.
Bezerra, L., López-Ibáñez, M., and Stützle, T. (2015). Automatic component-wise design of multiobjective evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 20:1–1.
Bezerra, L. C. T., López-Ibáñez, M., and Stützle, T. (2014). Automatic Design of Evolutionary Algorithms for Multi-Objective Combinatorial Optimization. In Parallel Problem Solving from Nature, volume 8672 of Lecture Notes in Computer Science, pages 508–517. Springer International Publishing.
Briand, L., Labiche, Y., and Wang, Y. (2003). An investigation of graph-based class integration test order strategies. Software Engineering, IEEE Transactions on, 29(7):594–607.
Briand, L. C., Feng, J., and Labiche, Y. (2002a). Using genetic algorithms and coupling measures to devise optimal integration test orders. In International Conference on Software Engineering and Knowledge Engineering, pages 43–50. ACM.
Briand, L. C., Feng, J., and Labiche, Y. (2002b). Using genetic algorithms and coupling measures to devise optimal integration test orders. In Proceedings of the 14th SEKE, pages 43–50. ACM.
Burke, E. K., Hyde, M. R., and Kendall, G. (2012). Grammatical Evolution of Local Search Heuristics. IEEE Transactions on Evolutionary Computation, 16(3):406–417.
Cabral, R. d. V., Pozo, A., and Vergilio, S. R. (2010). A pareto ant colony algorithm applied to the class integration and test order problem. In Petrenko, A., Simão, A., and Maldonado, J. C., editors, Testing Software and Systems, volume 6435 of Lecture Notes in Computer Science, pages 16–29. Springer Berlin Heidelberg.
Coello, C. A. C., Lamont, G. B., and Veldhuizen, D. A. V. (2007). Evolutionary Algorithms for Solving Multi-Objective Problems Second Edition. Springer Science, 2nd edition.
Colanzi, T., Assunção, W., Farah, P., Vergilio, S., and Guizzo, G. (2019). A review of ten years of the symposium on search-based software engineering. In Nejati, S. and Gay, G., editors, Search-Based Software Engineering, pages 42–57, Cham. Springer International Publishing.
Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2):182–197.
Derrac, J., García, S., Molina, D., and Herrera, F. (2011). A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm and Evolutionary Computation, 1(1):3–18.
Dréo, J. (2009). Using Performance Fronts for Parameter Setting of Stochastic Metaheuristics. In Genetic and Evolutionary Computation Conference, pages 2197–2200.
Durillo, J. J. and Nebro, A. J. (2011). jMetal: A Java framework for multi-objective optimization. Advances in Engineering Software, 42(10):760–771.
Eiben, A. and Smit, S. (2011). Parameter tuning for configuring and analyzing evolutionary algorithms. Swarm and Evolutionary Computation, 1(1):19–31.
Eiben, A. and Smit, S. (2012). Evolutionary Algorithm Parameters and Methods to Tune Them. In Autonomous Search, pages 15–36. Springer Berlin Heidelberg.
Eiben, A. E. and Smith, J. E. (2003). Introduction to evolutionary computing. Springer Science & Business Media.
Fonseca, C. M. and Fleming, P. J. (1993). Genetic Algorithms for Multiobjective Optimization: Formulation Discussion and Generalization. In International Conference on Genetic Algorithms, pages 416–423.
Guizzo, G., Fritsche, G. M., Vergilio, S. R., and Pozo, A. T. R. (2015). A Hyper-Heuristic for the Multi-Objective Integration and Test Order Problem. In Genetic and Evolutionary Computation Conference, pages 1343–1350.
Harman, M., Mansouri, S. A., and Zhang, Y. (2012). Search-based Software Engineering: Trends, Techniques and Applications. ACM Computing Surveys, 45(1):1–61.
Hewett, R. and Kijsanayothin, P. (2009). Automated test order generation for software component integration testing. In Proceedings of the 24th ASE, pages 211–220.
Hutter, F., Hoos, H. H., and Stützle, T. (2007). Automatic Algorithm Configuration Based on Local Search. In AAAI Conference on Artificial Intelligence, pages 1152–1157.
Jakubovski Filho, H. L., Lima, J. A. P., and Vergilio, S. R. (2017). Automatic generation of search-based algorithms applied to the feature testing of software product lines. In Proceedings of the 31st Brazilian Symposium on Software Engineering, SBES’17, pages 114–123, New York, NY, USA. ACM.
Jiang, S., Zhang, M., Zhang, Y., Wang, R., Yu, Q., and Keung, J. W. (2019). An integration test order strategy to consider control coupling. IEEE Transactions on Software Engineering, pages 1–1.
Knowles, J. D. and Corne, D. W. (2000). Approximating the Nondominated Front Using the Pareto Archived Evolution Strategy. Evolutionary Computation, 8(2):149–172.
Koza, J. R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press.
López-Ibáñez, M., Dubois-Lacoste, J., Stützle, T., and Birattari, M. (2011). The IRACE package, Iterated Race for Automatic Algorithm Configuration. Technical Report TR/IRIDIA/2011004, IRIDIA, Université Libre de Bruxelles, Belgium.
López-Ibáñez, M. and Stützle, T. (2012). The Automatic Design of Multiobjective Ant Colony Optimization Algorithms. IEEE Transactions on Evolutionary Computation, 16(6):861–875.
Lourenço, N., Pereira, F. B., and Costa, E. (2012). Evolving evolutionary algorithms. In Genetic and Evolutionary Computation Conference, pages 51–58.
Lourenço, N., Pereira, F. B., and Costa, E. (2013). The Importance of the Learning Conditions in Hyperheuristics. In Genetic and Evolutionary Computation Conference, pages 1525–1532.
Lourenço, N., Pereira, F. B., and Costa, E. (2015). The Optimization Ability of Evolved Strategies. In Progress in Artificial Intelligence, volume 9273 of Lecture Notes in Computer Science, pages 226–237. Springer International Publishing.
Mariani, T., Guizzo, G., Vergilio, S., and Pozo, A. (2016). Grammatical evolution for the multi-objective integration and test order problem. In Genetic and Evolutionary Computation Conference, pages 1069–1076.
Marshall, R. J., Johnston, M., and Zhang, M. (2014a). Developing a Hyper-Heuristic Using Grammatical Evolution and the Capacitated Vehicle Routing Problem. In Simulated Evolution and Learning, volume 8886 of Lecture Notes in Computer Science, pages 668–679. Springer International Publishing.
Marshall, R. J., Johnston, M., and Zhang, M. (2014b). Hyperheuristics, Grammatical Evolution and the Capacitated Vehicle Routing Problem. In Genetic and Evolutionary Computation Conference, GECCO Comp ’14, pages 71–72.
Mascia, F., nez, M. L.I., Dubois-Lacoste, J., and Stützle, T. (2014). Grammar-based generation of stochastic local search heuristics through automatic algorithm configuration tools. Computers & Operations Research, 51:190–199.
O’Neill, M. and Nicolau, M. (2017). Distilling the salient features of natural systems: Commentary on “On the mapping of genotype to phenotype in evolutionary algorithms” by Whigham, Dick and Maclaurin. Genetic Programming and Evolvable Machines, 18(3):379–383.
Ré, R., Lemos, O. A. L., and Masiero, P. C. (2007). Minimizing stub creation during integration test of aspect-oriented programs. In Proceedings of the 3rd Workshop on Testing
Aspect-oriented Programs, WTAOP ’07, pages 1–6, New York, NY, USA. ACM.
Ryan, C. (2017). A rebuttal to Whigham, Dick, and Maclaurin by one of the inventors of Grammatical Evolution: Commentary on “On the Mapping of Genotype to Phenotype in Evolutionary Algorithms” by Peter A. Whigham, Grant Dick, and James Maclaurin. Genetic Programming and Evolvable Machines, 18(3):385–389.
Ryan, C., Collins, J. J., and Neill, M. (1998). Grammatical evolution: Evolving programs for an arbitrary language. In Genetic Programming, volume 1391 of Lecture Notes in Computer Science, pages 83–96. Springer Berlin Heidelberg.
Siegel, S. and Castellan, N. J. (1988). Nonparametric Statistics for the Behavioral Sciences. McGrawHill international editions. Statistics series. McGrawHill.
Smit, S. K., Eiben, A. E., and Szlávik, Z. (2010). An MOEA-based Method to Tune EA Parameters on Multiple Objective Functions. In International Joint Conference on Computational Intelligence, pages 261–268.
Talbi, E.G. (2009). Metaheuristics: From Design to Implementation. Wiley Publishing.
Vargha, A. and Delaney, H. D. (2000). A Critique and Improvement of the ”CL” Common Language Effect Size Statistics of McGraw and Wong. Journal of Educational and Behavioral Statistics, 25(2):101–132.
Vergilio, S., Pozo, A., Árias, J., Cabral, R., and Nobre, T. (2012a). Multi-Objective Optimization Algorithms Applied to the Class Integration and Test Order Problem. International Journal on Software Tools for Technology Transfer, 14(4):461–475.
Vergilio, S. R., Pozo, A., Árias, J. a. C. G., da Veiga Cabral, R., and Nobre, T. (2012b). Multi-objective optimization algorithms applied to the class integration and test order problem. International Journal on Software Tools for Technology Transfer, 14(4):461–475.
Wang, Z., Li, B., Wang, L., and Li, Q. (2011). A Brief Survey on Automatic Integration Test Order Generation. In International Conference on Software Engineering and Knowledge Engineering, pages 254–257.
Whigham, P. A., Dick, G., and Maclaurin, J. (2017a). Just because it works: a response to comments on “On the Mapping of Genotype to Phenotype in Evolutionary Algorithms”. Genetic Programming and Evolvable Machines, 18(3):399–405.
Whigham, P. A., Dick, G., and Maclaurin, J. (2017b). On the mapping of genotype to phenotype in evolutionary algorithms. Genetic Programming and Evolvable Machines, 18(3):353–361.
Zitzler, E., Brockhoff, D., and Thiele, L. (2007). The hypervolume indicator revisited: On the design of pareto-compliant indicators via weighted integration. In Obayashi, S., Deb, K., Poloni, C., Hiroyasu, T., and Murata, T., editors, Evolutionary Multi-Criterion Optimization, pages 862–876, Berlin, Heidelberg. Springer Berlin Heidelberg.
Zitzler, E., Laumanns, M., and Thiele, L. (2001). SPEA2: improving the strength Pareto evolutionary algorithm. Technical report, Department of Electrical Engineering, Swiss Federal Institute of Technology.
Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C. M., and da Fonseca, V. G. (2003). Performance assessment of multiobjective optimizers: an analysis and review. IEEE Transactions on Evolutionary Computation, 7(2):117–132.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2021 Thaina Mariani, Giovani Guizzo, Silvia Regina Vergilio, Aurora Pozo
This work is licensed under a Creative Commons Attribution 4.0 International License.
