Trial-Based Dominance Enables Non-Parametric Tests to Compare both the Speed and Accuracy of Stochastic Optimizers
This provides a more robust comparison method for researchers and practitioners benchmarking stochastic optimizers, though it is incremental as it extends existing non-parametric tests to handle two-variable outcomes.
The paper tackles the problem of comparing stochastic optimization algorithms when trial outcomes involve both time to reach a target and final fitness value, by introducing a method to impose a linear order on two-variable data so non-parametric tests like Mann-Whitney U can be applied. The result shows that U-scores are more effective than dominance in identifying the better algorithm, as demonstrated in simulations and by determining winners in the CEC 2022 competition.
Non-parametric tests can determine the better of two stochastic optimization algorithms when benchmarking results are ordinal, like the final fitness values of multiple trials. For many benchmarks, however, a trial can also terminate once it reaches a pre-specified target value. When only some trials reach the target value, two variables characterize a trial's outcome: the time it takes to reach the target value (or not) and its final fitness value. This paper describes a simple way to impose linear order on this two-variable trial data set so that traditional non-parametric methods can determine the better algorithm when neither dominates. We illustrate the method with the Mann-Whitney U-test. A simulation demonstrates that U-scores are much more effective than dominance when tasked with identifying the better of two algorithms. We test U-scores by having them determine the winners of the CEC 2022 Special Session and Competition on Real-Parameter Numerical Optimization.