Using Machine Learning to improve Probabilistic Stochastic Local Search for Satisfiability
by
Toby Latin-Stoermer
Many local search algorithms utilize some mechanism for making non-greedy moves in order to escape from local optima in the hope of finding better overall solutions. In the area of satisfiability testing, the Walksat algorithm makes such random moves with a frequency determined by a "noise" parameter. The optimal noise level varies according to both the individual problem instance and the general class of problem (for example, random k-CNF versus CNF encodings of graph coloring problems). Current practice in using Walksat on an unknown instance to try different runs with different noise levels, in the hope that one of the choices will be close to optimal. A potentially more efficient strategy would be to determine a noise level that would likely be optimal by simply examining the form of the problem instance. In this talk I will discuss our efforts to use machine learning techniques to learn a function that predicts the optimal noise parameter for solving an instance of the basis of its structural properties.
Advised by Henry Kautz
EE1 037
Wednesday
May 5, 2004
4:30 - 5:20 pm