How to Estimate the Ability of a Metaheuristic Algorithm to Guide
  Heuristics During Optimization
  Metaheuristics are general methods that guide application of concrete
heuristic(s) to problems that are too hard to solve using exact algorithms.
However, even though a growing body of literature has been devoted to their
statistical evaluation, the approaches proposed so far are able to assess only
coupled effects of metaheuristics and heuristics. They do not reveal us
anything about how efficient the examined metaheuristic is at guiding its
subordinate heuristic(s), nor do they provide us information about how much the
heuristic component of the combined algorithm contributes to the overall
performance. In this paper, we propose a simple yet effective methodology of
doing so by deriving a naive, placebo metaheuristic from the one being studied
and comparing the distributions of chosen performance metrics for the two
methods. We propose three measures of difference between the two distributions.
Those measures, which we call BER values (benefit, equivalence, risk) are based
on a preselected threshold of practical significance which represents the
minimal difference between two performance scores required for them to be
considered practically different. We illustrate usefulness of our methodology
on the example of Simulated Annealing, Boolean Satisfiability Problem, and the
Flip heuristic.
