Golden Ratio Annealing for Satisfiability Problems Using Dynamically Cooling Schemes
Journal
Lecture Notes in Computer Science
Foundations of Intelligent Systems
Date Issued
2008
Author(s)
Frausto-Solís, Juan
Type
Resource Types::text::journal::journal article
Abstract
Abstract Satisfiability (SAT) Problem is an NP-Complete problem which means no deterministic algorithm is able to solve it in a polynomial time. Simulated Annealing (SA) can find very good solutions of SAT instances if its control parameters are correctly tuned. SA can be tuned experimentally or by using a Markov approach; the latter has been shown to be the most efficient one. Moreover Golden Ratio (GR) is an unconventional technique used to solve many problems. In this paper a new algorithm named Golden Ratio for Simulated Annealing (GRSA) is presented; it is tuned for three different cooling schemes. GRSA uses GR to dynamically decrease the SA temperature and a Markov Model to tune its parameters. Two SA tuned versions are compared in this paper: GRSA and a classical SA. Experimentation shows that the former is much more efficient than the latter. © Springer Nature