Evidence for Invariants in Local Search

Abstract

It is well known that the performance of a stochastic local search procedure depends upon the setting of its noise parameter, and that the optimal setting varies with the problem distribution. It is therefore desirable to develop general priniciples for tuning the procedures. We present two statistical measures of the local search process that allow one to quickly find the optimal noise settings. These properties are independent of the fine details of the local search strategies, and appear to be relatively independent of the structure of the problem domains. We applied these principles to the problem of evaluating new search heuristics, and discovered two promising new strategies. Introduction The performance of a stochastic local search procedure critically depends upon the setting of the "noise" parameter that determines the likelihood of escaping from local minima by making non-optimal moves. In simulated annealing (Kirkpatrick et al. 1983, Dowsland 1993) this is the temperature; ...