Developing New Concepts to Characterise Empirical Phenomena
in Proc. of the Workshop on Empirical AI, 16th International Joint Conference on Artificial Intelligence (IJCAI-99).
We advocate a new methodology for empirically analysing the behaviour
of Las Vegas Algorithms, a large class of probabilistic
algorithms comprising prominent methods such as local search algorithms
for SAT and CSPs, like WalkSAT and the Min-Conflicts Heuristic, as well
as more general metaheuristics like Genetic
Algorithms, Simulated Annealing, Iterated Local Search, and
Ant Colony Optimization.
Our method is based on measuring and analysing
run-time distributions (RTDs) for individual problem instances.
We discuss this empirical methodology
and its application to Las Vegas Algorithms for various problem
Our experience so far strongly suggests that
using this approach for studying
the behaviour of Las Vegas Algorithms
can provide a basis for improving the understanding of these algorithms
and thus facilitate further successes in their development
Get full paper as
gzipped postscript file (23k),
pdf file (43k);
get BibTeX entry.