A new hybridized algorithm based on Population-Based Simulated Annealing with an experimental study of phase transition in 3-SAT

This paper is about experiments for satisfiability problem using a new algorithm (GR-MM-PBSA) that improves the algorithm Population-Based Simulated Annealing (PBSA). GR-MM-PBSA runs in a parallel way Simulated Annealing (SA) and Threshold Annealing (TA) algorithms with a Golden Ratio space search strategy and Markovian Model to select initial and final temperature. In this paper we execute differents hybridized Simulated Annealing (or Threshold Accepting) algorithms and compares the efficiency of these, using a metric based on transition phase effect. Simulated Annealing Algorithms (SAA) theoretically can reach the optimum if the control parameters and cooling scheme are chosen correctly. All algorithms are compared with a metric based on transition phase obtained for 3-SAT instances. This paper shows the results of SAA hybridizations are more efficient than the original algorithm, without increasing their computational complexity. We also show the experimental data about runs with 820 3-SAT instances with ratio clauses-variables between 2.0 to 6.0.