Evaluation of Heuristics Using Data Envelopment Analysis

This paper focuses on identifying relatively efficient configurations of algorithmic operators among a set of configurations in the development of heuristics or meta-heuristics. Each configuration is considered as a decision-making unit with multiple inputs and outputs. Then, data envelopment analysis (DEA) is adopted to evaluate relative and cross-efficiencies of a set of algorithmic configurations. The proposed approach differs from existing methods based on statistical tests in that multiple inputs and outputs are simultaneously considered in an integrated framework for the evaluation of algorithmic efficiency. A case study is presented to demonstrate the application of DEA for determining the efficient configurations of genetic algorithm operators. The evaluation results of two DEA models are also compared. The DEA evaluation results are consistent with those obtained by a commonly used statistical method.