Intellectics Group: Technical Report 98-01
Evaluating Las Vegas Algorithms: Pitfalls and Remedies
Holger Hoos and Thomas Stützle
Stochastic search algorithms are among the most sucessful approaches
for solving hard combinatorial problems arising in applications from
AI and other domains. A large class of stochastic search approaches
can be cast into the framework of Las Vegas Algorithms (LVAs).
Because the run-time behavior of LVAs is characterized by random
variables, the detailed knowledge of run-time distributions provides
important information for the analysis of these algorithms. In this
paper we propose a novel methodology for evaluating the performance of
LVAs, based on the identification of empirical run-time distributions.
We exemplify our approach by applying it to Stochastic Local Search
(SLS) algorithms for the satisfiability problem (SAT) in propositional
logic. We point out pitfalls arising from the use of improper
empirical methods and discuss the benefits of the proposed methodology
for evaluating and comparing LVAs.