NTRS - NASA Technical Reports Server

Back to Results
When Gravity Fails: Local Search TopologyLocal search algorithms for combinatorial search problems frequently encounter a sequence of states in which it is impossible to improve the value of the objective function; moves through these regions, called {\em plateau moves), dominate the time spent in local search. We analyze and characterize {\em plateaus) for three different classes of randomly generated Boolean Satisfiability problems. We identify several interesting features of plateaus that impact the performance of local search algorithms. We show that local minima tend to be small but occasionally may be very large. We also show that local minima can be escaped without unsatisfying a large number of clauses, but that systematically searching for an escape route may be computationally expensive if the local minimum is large. We show that plateaus with exits, called benches, tend to be much larger than minima, and that some benches have very few exit states which local search can use to escape. We show that the solutions (i.e. global minima) of randomly generated problem instances form clusters, which behave similarly to local minima. We revisit several enhancements of local search algorithms and explain their performance in light of our results. Finally we discuss strategies for creating the next generation of local search algorithms.
Document ID
Document Type
Preprint (Draft being sent to journal)
Frank, Jeremy (Caelum Research Corp. Moffett Field, CA United States)
Cheeseman, Peter (Caelum Research Corp. Moffett Field, CA United States)
Stutz, John (NASA Ames Research Center Moffett Field, CA United States)
Lau, Sonie
Date Acquired
August 20, 2013
Publication Date
January 1, 1997
Subject Category
Cybernetics, Artificial Intelligence and Robotics
Funding Number(s)
PROJECT: RTOP 632-30-00
Distribution Limits
Work of the US Gov. Public Use Permitted.