Intellectics Group: Technical Report 98-01
Characterizing the Run-time Behavior of Stochastic Local Search
Holger Hoos and Thomas Stützle
Stochastic local search (SLS) algorithms have been successfully
applied to hard combinatorial problems from different domains.
One important feature of SLS algorithms is the fact that
their run-time behavior is characterized by a random variable.
Consequently, the detailed knowledge of the run-time distribution
provides important information for the
analysis of SLS algorithms.
In this paper we investigate the empirical run-time distributions for
several state-of-the-art stochastic local search algorithms for SAT and
Using statistical analysis techniques, we show that on a variety of
problems from both randomized distributions
and encodings of the blocks world planning and graph coloring domains,
the observed run-time behavior can be characterized by
As a first direct consequence of this result, we establish that
these algorithms can be easily parallelized with optimal speedup.