Measuring the Quality of Heuristics

The fact that we do not examine all possible row-orderings when calculating our heuristic suggests that we may be getting costs far away from the realistic optimal costs. For some reason (which I do not entirely understand, but do appreciate), the heuristic based on a simple and fast bipartite matching yields results pretty close to the true cost.

Looking at the values of the actual cost, the heuristic, and the sum of these, as we progress down the branches to a final solution, will show how well the heuristic matches the expectations. (Ideally the $g(s)+h(s)$ function would be a horizontal line). Such a sampling of the heuristic and cost values, is found in figure 3.3. This plot is taken from the best solution to the system describing the chemical reactions used in the aerial pollution model.

Figure 3.3: $h(s), g(s)$ and $h(s)+g(s)$ down the search tree. Depth 0 is the beginning (top) of the search tree, and depth 1 is the end (where final solutions are)

As can be seen in the figure, the heuristic somewhat overshoots the actual cost. This is compensated for, by multiplying the heuristic with some ``acceptance'' factor. Per default, the optimizer uses an acceptance factor of $0.68$. This value was found to work well in a wide range of systems. Experimenting with this value will sometimes yield better results, but often at the expense of a severely increased execution time of the optimizer (of course due to the much larger number of accepted branches in the search).

<