+91 8617752708

Current Journal of Applied Science and Technology, ISSN: 2457-1024; 2231-0843 (old),Vol.: 25, Issue.: 2


Reducing the Cost of Exploring Neighborhood Areas in Dynamic Local Search for SAT


Abdelraouf Ishtaiwi1*, Ghassan Issa1 and Wael Hadi1

1Faculty of IT, School of CS, University of Petra, Amman, Jordan.

Article Information
(1) Wei Wu, Professor, Department of Applied Mathematics, Dalian University of Technology, China.
(1) Sanjib Kumar Datta, University of Kalyani, India.
(2) Utku Kose, Suleyman Demirel University, Turkey.
(3) K. Ashwini, Visvesvaraya Technological University, India.
(4) Sofiya Ostrovska, Atilim University, Turkey.
Complete Peer review History: http://www.sciencedomain.org/review-history/22549


Stochastic Local Search (SLS) algorithms are of great importance to many fields of Computer Sciences and Artificial Intelligence. This is due to their efficient performance when applied for solving randomly generated satisfiability problems (SAT). Our focus in the current work is on one of the SLS dynamic weighting approaches known as multi-level weight distribution (mulLWD). We experimentally investigated the performance and the weight behaviors of mulLWD. Based on our experiments, we observed that the 2nd level weights movements could lead to poor performance of mulLWD, especially when applied for solving large and harder SAT problems. Therefore, we developed a new heuristic that could reduce the cost of the 2nd level neighborhood exploitation known as partial multi-level weight distribution mulLWD+. Experimental results indicate that mulLWD+ heuristic has significantly better performance than mulLWD in a wide range of SAT problems.

Keywords :

Artificial intelligence; Boolean satisfiability; search algorithms.

Full Article - PDF    Page 1-9

DOI : 10.9734/CJAST/2017/38361

Review History    Comments

Our Contacts

Guest House Road, Street no - 1/6,
Hooghly, West Bengal,

+91 8617752708


Third Floor, 207 Regent Street
London, W1B 3HH,

+44 20-3031-1429