A Reinforced Approach for Enhancing Stochastic Search

摘要

Stochastic search algorithms are often robust, scalable problem solvers. In this paper, we carefully study the Iterative Sampling(IS), Heuristic-Biased Stochastic Sampling(HBSS) and Value-Biased Stochastic Sampling(VBSS) algorithm, and present an approach for enhancing such multi-start algorithms. This paper shows that given some heuristic information about the search start point, these algorithms would achieve a higher level of performance. Historical information can be reused as heuristic information which provides a start node in the search tree. And further, we extend this approach in such a way that a solution is cut off into pieces and the stochastic algorithm produces one piece in every phase of the reinforced approach. Finally, we apply this approach to the HBSS and VBSS, and use them to solve the weighted tardiness scheduling with sequence-dependent setups problem to evaluate this approach. The results of these experiments are positive.