Developing New Concepts to Characterise Empirical Phenomena

Holger H. Hoos and Thomas Stützle

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 domains. 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 and application.

Get full paper as gzipped postscript file (23k), pdf file (43k); get BibTeX entry.