(1) Department of Computer Science, Drexel University, 3141 Chestnut Street, Philadelphia, PA, 19104;(2) The Robotics Insitute, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA, 15213
Abstract:
This paper investigates the utility of introducing randomization as a means of boosting the performance of search heuristics. We introduce a particular approach to randomization, called Value-biased stochastic sampling (VBSS), which emphasizes the use of heuristic value in determining stochastic bias. We offer an empirical study of the performance of value-biased and rank-biased approaches to randomizing search heuristics. We also consider the use of these stochastic sampling techniques in conjunction with local hill-climbing. Finally, we contrast the performance of stochastic sampling search with more systematic search procedures as a means of amplifying the performance of search heuristics.