Evaluating Noisy Optimisation Algorithms: First Hitting Time is\n Problematic

A key part of any evolutionary algorithm is fitness evaluation. When fitness\nevaluations are corrupted by noise, as happens in many real-world problems as a\nconsequence of various types of uncertainty, a strategy is needed in order to\ncope with this. Resampling is one of the most common strategies, whereby each\nsolution is evaluated many times in order to reduce the variance of the fitness\nestimates. When evaluating the performance of a noisy optimisation algorithm, a\nkey consideration is the stopping condition for the algorithm. A frequently\nused stopping condition in runtime analysis, known as "First Hitting Time", is\nto stop the algorithm as soon as it encounters the optimal solution. However,\nthis is unrealistic for real-world problems, as if the optimal solution were\nalready known, there would be no need to search for it. This paper argues that\nthe use of First Hitting Time, despite being a commonly used approach, is\nsignificantly flawed and overestimates the quality of many algorithms in\nreal-world cases, where the optimum is not known in advance and has to be\ngenuinely searched for. A better alternative is to measure the quality of the\nsolution an algorithm returns after a fixed evaluation budget, i.e., to focus\non final solution quality. This paper argues that focussing on final solution\nquality is more realistic and demonstrates cases where the results produced by\neach algorithm evaluation method lead to very different conclusions regarding\nthe quality of each noisy optimisation algorithm.\n