Simulated Annealing for SAT Problems Using Dynamic Markov Chains with Linear Regression Equilibrium
Journal
2008 Seventh Mexican International Conference on Artificial Intelligence
Date Issued
2008
Author(s)
Frausto-Solís, Juan
Type
text::conference output::conference proceedings::conference paper
Abstract
Since the appearance of Simulated Annealing (SA) algorithm it has shown to be an efficient method to solve combinatorial optimization problems. This algorithm is based on two cycles: the external or temperature cycle and the internal or Metropolis Cycle. In this paper a new SA method named LRSA is presented. LRSA dynamically finds the equilibrium in the Metropolis cycle by using Linear Regression. Experimentation shows that the proposed method is more efficient than the classical one, since it obtains the same quality in the final solution with less processing time.