کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4960471 1446499 2017 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A new hybridized algorithm based on Population-Based Simulated Annealing with an experimental study of phase transition in 3-SAT
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Procedia Computer Science - Volume 116, 2017, Pages 427-434
نویسندگان
,