A statistical methodology for analysing heuristic algorithms

Abstract

Heuristic experimentation commonly entails running an algorithm on the instances of some standard benchmark problem set and measuring its performance solution quality, run time or both. These performance results are then compared with the results other heuristic algorithms obtained on this benchmark problem set. It is a type of evaluation that ensues a competition with state-of-the-art methods in the literature. This approach, however, does not seek to explain why one method performs better than another one. Even though some competition between researchers might spur innovation, it has been noted that true innovation builds on the understanding of how a heuristic algorithm behaves, and not on proof of competitiveness. A competitive focus works when considering a speci c setting [4], but when the objective is to learn how the diff erent heuristic elements contribute to performance and make statements beyond a specifi c problem setting, a statistical evaluation methodology has to be applied. We propose such a statistical methodology with the principal aim of gaining a thorough understanding of the relationship between algorithm performance, algorithmic properties, and problem instance characteristics.