Learning the Large-Scale Structure of the MAX-SAT Landscape Using Populations

A new algorithm for solving maximum satisfiability (MAX-SAT) problems is introduced which clusters good solutions, and restarts the search from the closest feasible solution to the centroid of each cluster. This is shown to be highly efficient for finding good solutions of large MAX-SAT problems. We argue that this success is due to the population learning the large-scale structure of the fitness landscape. Systematic studies of the landscape are presented to support this hypothesis. In addition, a number of other strategies are tested to rule out other possible explanations of the success. Preliminary results are shown, indicating that extensions of the proposed algorithm can give similar improvements on other hard optimization problems.