Evaluating Las Vegas Algorithms - Pitfalls and Remedies
arXiv (Cornell University)Published 30 January 2013Open access
Holger H. Hoos, Thomas Stützle
Citations132
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A novel methodology for evaluating the performance of LVAs, based on the identification of empirical run-time distributions is proposed, and is exemplified by applying it to Stochastic Local Search algorithms for the satisfiability problem (SAT) in propositional logic.
Abstract
Stochastic search algorithms are among the most sucessful approaches for solving hard combinatorial problems. A large class of stochastic search approaches can be cast into the framework of Las Vegas Algorithms (LVAs). As 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.
Keywords
Computer Science
A new method for solving hard satisfiability problems
1,183 Citations1992Bart Selman, Hector J. Levesque +1 more
A greedy local search procedure called GSAT is introduced for solving propositional satisfiability problems and its good performance suggests that it may be advantageous to reformulate reasoning tasks that have traditionally been viewed as theorem-proving problems as model-finding tasks.
Parallel ComputingRobust taboo search for the quadratic assignment problem
827 Citations1991Éric D. Taillard
An adaptation of taboo search to the quadratic assignment problem is discussed in this paper, which is efficient and robust, requiring less complexity and fewer parameters than earlier adaptations.
Noise strategies for improving local search
761 Citations1994Bart Selman, Henry Kautz +1 more
It is shown that mixed random walk is the superior strategy for solving MAX-SAT problems, and results demonstrating the effectiveness of local search with walk for solving circuit synthesis and circuit diagnosis problems are presented.
Journal of HeuristicsTesting heuristics: We have it all wrong
426 Citations1995John Hooker
This article argues that a more scientific approach of controlled experimentation, similar to that used in other empirical sciences, avoids or alleviates problems of competitive testing in algorithmic experimentation.
Evidence for invariants in local search
368 Citations1997David McAllester, Bart Selman +1 more
This work presents two statistical measures of the local search process that allow one to quickly find the optimal noise settings, and applies these principles to the problem of evaluating new search heuristics, and discovered two promising new strategies.
Optimal speedup of Las Vegas algorithms
360 Citations2002Michael Luby, Alistair Sinclair +1 more
The authors describe a simple universal strategy S/sup univ/, with the property that, for any algorithm A, T(A,S/Sup univ/)=O (l/sub A/log(l/ sub A/)), which is the best performance that can be achieved, up to a constant factor, by any universal strategy.
Artificial IntelligenceExperimental results on the crossover point in random 3-SAT
292 Citations1996James M. Crawford, Larry D. Auton
This paper reports on the most extensive set of experiments to date on the location and nature of the crossover point in satisfiability problems, finding no evidence of any hard problems in the under-constrained region.
Artificial IntelligenceLocating the phase transition in binary constraint satisfaction problems
219 Citations1996Barbara M. Smith, Martin Dyer
It is shown that the variance of the number of solutions can be used to set bounds on the phase transition and to indicate the accuracy of the prediction.
Operations ResearchNeeded: An Empirical Science of Algorithms
210 Citations1994John Hooker
It is argued that an empirical science of algorithms is a viable alternative to deductive algorithmic science, and some examples of recent work that partially achieves this aim are given.
Journal of Artificial Intelligence ResearchAn Empirical Analysis of Search in GSAT
63 Citations1993Ian P. Gent, Toby Walsh
An extensive study of search in GSAT, an approximation procedure for propositional satisfiability, shows that when applied to randomly generated 3-SAT problems, there is a very simple scaling with problem size for both the mean number of satisfied clauses and the mean branching rate.
Unsatisfied Variables in Local Search
53 Citations1995Ian P. Gent, Toby Walsh
This paper explores the impact of focusing search in local search procedures on the unsatis ed variables that is those variables which appear in clauses which are not yet satis ed for random problems and shows that such a focus reduces the sensitivity to input parameters.
Summarizing CSP hardness with continuous probability distributions
49 Citations1997Daniel Frost, Irina Rish +1 more
Empirical evidence is presented that the distribution of effort required to solve CSPs randomly generated at the 50% satisfiable point, when using a backtracking algorithm, can be approximated by two standard families of continuous probability distribution functions.
Tuning local search for satisfiability testing
44 Citations1996Andrew Parkes, Joachim P. Walser
An efficient probabilistic method for finding the optimal setting for a critical local search parameter, Maxflips, is presented and important details of two differing versions of WSAT are discussed.
AlgorithmicaA method for obtaining randomized algorithms with small tail probabilities
33 Citations1996Hans Wilhelm Alt, Leo J. Guibas +3 more
This work studies strategies for converting randomized algorithms of the Las Vegas type into randomized algorithms with small tail probabilities with large tail probabilities.
National Conference on Artificial IntelligenceExpected gains from parallelizing constraint solving for hard problems
32 Citations1994Tad Hogg, Colin P. Williams
Lecture notes in computer scienceTabu search vs. Random walk
17 Citations1997Olaf Steinmann, Antje Strohmaier +1 more
Experimental evidence is given that Tabu Search can be used to efficiently guide local search procedures like GSAT and WSAT for SAT and the min conflicts heuristic for CSP.
Lecture notes in computer scienceSolving hard combinatorial problems with GSAT — A case study
7 Citations1996Holger H. Hoos
Whether hard combinatorial problems such as the Hamiltonian circuit problem HCP can be practically solved by transformation to the propositional satisfiability problem (SAT) and application of fast universal SAT-algorithms like GSAT to the transformed problem instances is investigated.