Amplification of Search Performance through Randomization of Heuristics

Vincent Cicirello and Stephen Smith
Conference Paper, Principles and Practice of Constraint Programming: 8th International Conference, Proceedings, Vol. LNCS 2470 of Lecture Notes in Computer Science, pp. 124-138, September, 2002

View Publication

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.


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.

author = {Vincent Cicirello and Stephen Smith},
title = {Amplification of Search Performance through Randomization of Heuristics},
booktitle = {Principles and Practice of Constraint Programming: 8th International Conference, Proceedings},
year = {2002},
month = {September},
editor = {P. Van Hentenryck},
volume = {LNCS 2470 of Lecture Notes in Computer Science},
pages = {124-138},
publisher = {Springer-Verlag},
} 2017-09-13T10:45:00-04:00