Principles and Practice of Constraint Programming: 8th International Conference, Proceedings, Springer-Verlag, Vol. LNCS 2470 of Lecture Notes in Computer Science, September, 2002, pp. 124-138.
Amplification of Search Performance through Randomization of Heuristics
Vincent Cicirello and Stephen F. Smith
The Robotics Institute
Carnegie Mellon University
Pittsburgh, PA 15213, USA
Abstract
Randomization as a means for improving search performance in combinatorial domains has received increasing interest in recent years. In optimization contexts, it can provide a means for overcoming the deficiencies of available search heuristics and broadening search in productive directions. In this paper, we consider the issue of amplifying the performance of a search heuristic through randomization. We introduce a general framework for embedding a base heuristic within an iterative sampling process and searching a stochastic neighborhood of the heuristic's prescribed trajectory. In contrast to previous approaches, which have used rank-ordering as a basis for randomization, our approach instead relies on assigned heuristic value. Use of heuristic value is important because it makes it possible to vary the level of stochasticity in relation to the discriminatory power of the heuristic in different decision contexts, and hence concentrate search around those decisions where the heuristic is least informative. To evaluate the efficacy of the approach, we apply it to a complex, weighted-tardiness scheduling problem. Taking a state-of-the-art heuristic for this scheduling problem as a starting point, we demonstrate an ability to consistently and significantly improve on the deterministic heuristic solution across a broad range of problem instances. Our approach is also shown to consistently outperform a previously developed, rank-ordering based approach to randomizing the same heuristic in terms of percentage of improvement obtained.
Copyright 2002, Cicirello and Smith.
All rights reserved.
Full paper in pdf Format