Abstract
Optimisation algorithms play a vital role in solving complex real-world problems by iteratively comparing various solutions to find the optimal or the best solution. However, testing them poses challenges due to their “non-testable” nature, where a reliable test oracle is lacking. Traditional testing techniques may not directly address whether these algorithms yield the best solution. In this context, Metamorphic Testing (MT) emerges as a promising approach. MT leverages Metamorphic Relations (MRs) to indirectly test the System Under Test (SUT) by examining input-output pairs and revealing inconsistencies based on MRs. In this paper, we apply the MT approach to a black-box industrial optimisation algorithm and present our observations and findings. We identify successful aspects, challenges, and opportunities for further research. The findings from our study are expected to shed light on the practical feasibility of MT for testing optimisation algorithms. The paper provides a formal definition of MT, an overview of related work in optimisation algorithms, and a description of the industrial context, methodology, and results.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bartz-Beielstein, T., Chiarandini, M., Paquete, L., Preuss, M.: Experimental Methods for the Analysis of Optimization Algorithms. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-02538-9
Beiranvand, V., Hare, W., Lucet, Y.: Best practices for comparing optimization algorithms. Optim. Eng. 18(4), 815–848 (2017)
Chen, T.Y., Cheung, S.C., Yiu, S.M.: Metamorphic testing: a new approach for generating next test cases. Department of Computer Science, Hong Kong University of Science and Technology, Hong Kong, Technical report (1998)
Duque-Torres, A., Pfahl, D., Klammer, C., Fischer, S.: Bug or not bug? analysing the reasons behind metamorphic relation violations. In: IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER), pp. 905–912 (2023)
Hawkins, D.M., Basak, S.C., Mills, D.: Assessing model fit by cross-validation. J. Chem. Inf. Comput. Sci. 43(2), 579–586 (2003)
Jamil, M., Yang, X.S.: A literature survey of benchmark functions for global optimisation problems. Int. J. Math. Model. Numer. Optim. 4(2), 150–194 (2013)
Peng, Z., Kanewala, U., Niu, N.: Contextual understanding and improvement of metamorphic testing in scientific software development. In: 15th ACM/IEEE International Symposium on Empirical Software Engineering and Measurement (ESEM), pp. 1–6 (2021)
Rounds, J., Kanewala, U.: Systematic testing of genetic algorithms: a metamorphic testing based approach. arXiv preprint arXiv:1808.01033 (2018)
Shahri, M.P., Srinivasan, M., Reynolds, G., Bimczok, D., Kahanda, I., Kanewala, U.: Metamorphic testing for quality assurance of protein function prediction tools. In: IEEE International Conference On Artificial Intelligence Testing (AITest), pp. 140–148. IEEE (2019)
Wiesler, S., Ney, H.: A convergence analysis of log-linear training. In: Advances in Neural Information Processing Systems, vol. 24 (2011)
Yoo, S.: Metamorphic testing of stochastic optimisation. In: Third International Conference on Software Testing, Verification, and Validation Workshops, pp. 192–201 (2010)
Zhang, Y., Gong, D.W., Sun, X.Y., Geng, N.: Adaptive bare-bones particle swarm optimization algorithm and its convergence analysis. Soft. Comput. 18(7), 1337–1352 (2014)
Zhang, Z., Towey, D., Ying, Z., Zhang, Y., Zhou, Z.Q.: MT4NS: metamorphic testing for network scanning. In: 6th IEEE/ACM International Workshop on Metamorphic Testing (MET), MET 2021, pp. 17–23 (2021)
Zhou, Z.Q., Sun, L.: Metamorphic testing of driverless cars. Commun. ACM 62(3), 61–67 (2019). ISSN: 0001–0782
Acknowledgement
The research reported in this paper has been partly funded by BMK, BMAW, and the State of Upper Austria in the frame of the SCCH competence center INTEGRATE [(FFG grant no. 892418)] part of the FFG COMET Competence Centers for Excellent Technologies Programme, as well as by the European Regional Development Fund, and grant PRG1226 of the Estonian Research Council.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Duque-Torres, A., Klammer, C., Fischer, S., Pfahl, D. (2024). Is It the Best Solution? Testing an Optimisation Algorithm with Metamorphic Testing. In: Kadgien, R., Jedlitschka, A., Janes, A., Lenarduzzi, V., Li, X. (eds) Product-Focused Software Process Improvement. PROFES 2023. Lecture Notes in Computer Science, vol 14483. Springer, Cham. https://doi.org/10.1007/978-3-031-49266-2_23
Download citation
DOI: https://doi.org/10.1007/978-3-031-49266-2_23
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-49265-5
Online ISBN: 978-3-031-49266-2
eBook Packages: Computer ScienceComputer Science (R0)