A Modified Simulated Annealing Algorithm and its Application to the Satisfiability Problem

Keywords: Simulated annealing; Satisfiability; Hard problems

Abstract: The simulated annealing algorithm is a non-traditional approach to the approximate solution of hard optimization problems requiring the minimization of an objective (energy) function. The trajectory of states is not monotonic in that the next state could be a higher energy state. In its usual form the algorithm uses a Boltzmann distribution to determine the probability with which such a transition is made. A modified version is discussed here in which the neighborhood of the current state is sampled, and the sample distribution so obtained used instead. The rationale for this is that the local neighborhood of a state may better represent the distribution of energies when changes in the state are localized. This is the case in the satisfiability problem for which heuristics are usually based on flipping a small fraction of the variables. Computational experiments will be discussed.