A hybrid simulated annealing and threshold accepting for satisfiability problems using dynamically cooling schemes
Journal
CIMMACS'07: Proceedings of the 6th WSEAS international conference on Computational intelligence, man-machine systems and cybernetics
Date Issued
2007
Author(s)
Frausto-Solís, Juan
Type
Resource Types::text::conference output::conference proceedings::conference paper
Abstract
For Satisfiability (SAT) Problem there is not a deterministic algorithm able to solve it in a polynomial time. Simulated Annealing (SA) and similar algorithms like Threshold Accepting (TA) are able to find very good solutions of SAT instances only if their control parameters are correctly tuned. Classical TA usually uses the same Markov chain length for each temperature cycle but they spend a lot of time. In this paper a method based on the neighborhood structure to get the Markov chain length in a dynamical way for each temperature cycle is proposed. Three cooling schemes are also presented in the paper. The experimentation presented in the paper shows that the proposed method is more efficient than the classical one.
How to cite
Martínez Ríos, F. & Frausto-Solís, J. (2007). A hybrid simulated annealing and threshold accepting for satisfiability problems using dynamically cooling schemes, 6th WSEAS Int. Conference on Computational Intelligence, Man-Machine Systems and Cybernetics, Tenerife, Spain, December 14-16, 2007.