Enhancing Stochastic Search Performance by Value-Biased Randomization of Heuristics

Abstract

Stochastic search algorithms are often robust, scalable problem solvers. In this paper, we concern ourselves with the class of stochastic search algorithms called stochastic sampling. Randomization in such a search framework can be an efiective means of expanding search around a stochastic neighborhood of a strong domain heuristic. Speciflcally, we show that a value-biased approach can be more efiective than the rank-biased approach of the heuristic-biased stochastic sampling algorithm. We also illustrate the efiectiveness of value-biasing the starting conflgu- rations of a local hill-climber. We use the weighted tardiness scheduling problem to evaluate our approach.