Robust data envelopment analysis approaches for evaluating algorithmic performance

• DEA is adopted to measure the relative efficiency of optimization algorithms.
• Consider not only average but also variation of algorithm’s output values.
• Robust DEA models are developed based on robust counterpart optimization approaches.
• Apply the models to evaluate GA operators for solving the vehicle routing problem.

Recent advances in state-of-the-art meta-heuristics feature the incorporation of probabilistic operators aiming to diversify search directions or to escape from being trapped in local optima. This feature would result in non-deterministic output in solutions that vary from one run to another of a meta-heuristic. Consequently, both the average and variation of outputs over multiple runs have to be considered in evaluating performances of different configurations of a meta-heuristic or distinct meta-heuristics. To this end, this work considers each algorithm as a decision-making unit (DMU) and develops robust data envelopment analysis (DEA) models taking into account not only average but also standard deviation of an algorithm’s output for evaluating relative efficiencies of a set of algorithms. The robust DEA models describe uncertain output using an uncertainty set, and aim to maximize a DMU’s worst-case relative efficiency with respect to that uncertainty set. The proposed models are employed to evaluate a set of distinct configurations of a genetic algorithm and a set of parameter settings of a simulated annealing heuristic. Evaluation results demonstrate that the robust DEA models are able to identify efficient algorithmic configurations. The proposed models contribute not only to the evaluation of meta-heuristics but also to the DEA methodology.