Next Article in Journal
Special Issue on Process Mining and Emerging Applications
Previous Article in Journal
A Bayesian Nonparametric Learning Approach to Ensemble Models Using the Proper Bayesian Bootstrap
Open AccessArticle

A Dynamic Clause Specific Initial Weight Assignment for Solving Satisfiability Problems Using Local Search

1
Information and Communication Technology, University of Petra, Amman 1196, Jordan
2
The Public Authority for Applied Education and Training, Shuwaikh 70654, Kuwait
3
Department of Computer Information Systems, University of Petra, Amman 1196, Jordan
4
Computer Science, University of Petra, Amman 1196, Jordan
*
Author to whom correspondence should be addressed.
Received: 7 December 2020 / Revised: 24 December 2020 / Accepted: 26 December 2020 / Published: 5 January 2021
(This article belongs to the Section Randomized, Online, and Approximation Algorithms)
For decades, the use of weights has proven its superior ability to improve dynamic local search weighting algorithms’ overall performance. This paper proposes a new mechanism where the initial clause’s weights are dynamically allocated based on the problem’s structure. The new mechanism starts by examining each clause in terms of its size and the extent of its link, and its proximity to other clauses. Based on our examination, we categorized the clauses into four categories: (1) clauses small in size and linked with a small neighborhood, (2) clauses small in size and linked with a large neighborhood, (3) clauses large in size and linked with a small neighborhood, and (4) clauses large in size and linked with a large neighborhood. Then, the initial weights are dynamically allocated according to each clause category. To examine the efficacy of the dynamic initial weight assignment, we conducted an extensive study of our new technique on many problems. The study concluded that the dynamic allocation of initial weights contributes significantly to improving the search process’s performance and quality. To further investigate the new mechanism’s effect, we compared the new mechanism with the state-of-the-art algorithms belonging to the same family in terms of using weights, and it was clear that the new mechanism outperformed the state-of-the-art clause weighting algorithms. We also show that the new mechanism could be generalized with minor changes to be utilized within the general-purpose stochastic local search state-of-the-art weighting algorithms. View Full-Text
Keywords: artificial intelligence; dynamic local search algorithms; optimization; planning artificial intelligence; dynamic local search algorithms; optimization; planning
Show Figures

Figure 1

MDPI and ACS Style

Ishtaiwi, A.; Alshahwan, F.; Jamal, N.; Hadi, W.; AbuArqoub, M. A Dynamic Clause Specific Initial Weight Assignment for Solving Satisfiability Problems Using Local Search. Algorithms 2021, 14, 12. https://0-doi-org.brum.beds.ac.uk/10.3390/a14010012

AMA Style

Ishtaiwi A, Alshahwan F, Jamal N, Hadi W, AbuArqoub M. A Dynamic Clause Specific Initial Weight Assignment for Solving Satisfiability Problems Using Local Search. Algorithms. 2021; 14(1):12. https://0-doi-org.brum.beds.ac.uk/10.3390/a14010012

Chicago/Turabian Style

Ishtaiwi, Abdelraouf; Alshahwan, Feda; Jamal, Naser; Hadi, Wael; AbuArqoub, Muhammad. 2021. "A Dynamic Clause Specific Initial Weight Assignment for Solving Satisfiability Problems Using Local Search" Algorithms 14, no. 1: 12. https://0-doi-org.brum.beds.ac.uk/10.3390/a14010012

Find Other Styles
Note that from the first issue of 2016, MDPI journals use article numbers instead of page numbers. See further details here.

Article Access Map by Country/Region

1
Search more from Scilit
 
Search
Back to TopTop