Is It the Best Solution? Testing an Optimisation Algorithm with Metamorphic Testing

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.