Heuristic evaluation - Complex systems and AI

Contents

Methods for evaluating heuristics

The problem of evaluating heuristics is crucial. Indeed, heuristics offer no guarantee of optimality: they can find the optimum for certain data, or be very far from it.

Relative performance

Suppose that we are studying a combinatorial problem for which we already have an exact (optimal) reference method. For a heuristic H and a datum d, we note H(d) the cost of the heuristic solution and OPT(d) the optimal cost. We call relative performance of H on d the quotient: R_H (d) = H (d) / OPT (d).

For a problem of minimization, R_h (d) ≥ 1. We can also speak of distance to the optimum as a percentage with the formula: 100 * (R_H (d) - 1). Relative performance is an evaluation of heuristics which can be bounded a priori (with the tests) or unpredictable a posteriori (after the tests).

A priori assessment

We call the worst case performance ratio P_H of a heuristic H its worst relative performance on the set of possible data: P_H = max {R_H (d), for any valid d}.

This is a performance guarantee obtained by theoretical analysis of H. For this we limit R_H (d) for any data d, then we construct a data showing that this worst case can actually be reached. This result is very difficult to obtain, and is often not possible to calculate, in particular for all heuristics which do not include mathematical choice characters.

Take an example of a minimization heuristic with P_H = 1.5. This means that whatever the input data, the heuristic will never give a result more than 50% above the overall optimum. "Never" since this has been proven mathematically.

A posteriori evaluation: lower bounds

When the evaluation of heuristics before execution is impossible, it is still possible to evaluate the results after execution of the heuristic H. We have seen the relative performance, but this method only applies if it is possible to know the global optimum.

We can however obtain an evaluation if we have a default evaluation B (d) for the optimum OPT (d) with: R_H (d) = H (d) / OPT (d) ≤ H (d) / B (d). In particular, if H (d) = B (d), then we have reached the global optimum. It is always possible to find a bound to the global optimum by a naive or greedy method.

Statistical evaluation

A priori and a posteriori evaluations of heuristics still pose a problem: when are there very large problems? The simplest heuristic evaluation consists in comparing solutions with those given in benchmarks or widely used methods. The value of the solution, over a large set of tests, compared to known methods, gives a good approximation of the efficiency of the heuristic.