Robust data envelopment analysis approaches for evaluating algorithmic performance

Chung-Cheng Lu*

*Corresponding author for this work

Research output: Contribution to journalArticle

21 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)78-89
Number of pages12
JournalComputers and Industrial Engineering
Volume81
DOIs
StatePublished - 1 Jan 2015

Keywords

  • Data envelopment analysis
  • Meta-heuristics
  • Robust counterpart optimization
  • Uncertainty modeling

Fingerprint Dive into the research topics of 'Robust data envelopment analysis approaches for evaluating algorithmic performance'. Together they form a unique fingerprint.

  • Cite this