Paper Info
Title
MAX-SAT Problem using Hybrid Harmony Search Algorithm.
Abstract
Maximum Satisfiability problem is an optimization variant of the Satisfiability problem (SAT) denoted as MAX-SAT. The aim of this problem is to find Boolean variable assignment that maximizes the number of satisfied clauses in the Boolean formula. In case the number of variables per clause is equal or greater than three, then this problem is considered NP-complete. Hence, many researchers have developed techniques to deal with MAX-SAT. In this paper, we investigate the impact of different hybrid versions of binary harmony search (HS) algorithm on solving MAX 3-SAT problem. Therefore, we propose two novel hybrid binary HS algorithms. The first hybridizes Flip heuristic with HS, and the second uses Tabu search combined with Flip heuristic. Furthermore, a distinguished feature of our proposed approaches is using an objective function that is updated dynamically based on the stepwise adaptation of weights (SAW) mechanism to evaluate the MAX-SAT solution using the proposed hybrid versions. The performance of the proposed approaches is evaluated over standard MAX-SAT benchmarks, and the results are compared with six evolutionary algorithms and three stochastic local search algorithms. The obtained results are competitive and show that the proposed novel approaches are effective.
Year
DOI
Venue
2018
10.1515/jisys-2016-0129
JOURNAL OF INTELLIGENT SYSTEMS
Keywords
Field
DocType
Maximum satisfiability problem,harmony search,local search,optimization,3SAT problem,evolutionary algorithms,MAX-SAT problem,metaheuristic
Maximum satisfiability problem,Heuristic,Search algorithm,Computer science,Boolean satisfiability problem,Algorithm,Harmony search,Local search (optimization),Best-first search,Tabu search
Journal
Volume
Issue
ISSN
27
4
0334-1860
Citations 
PageRank 
References 
0
0.34
15
Authors
4
Name
Order
Citations
PageRank
Iyad Abu Doush117823.76
Amal Lutfi Quran200.34
Mohammed Azmi Al-Betar362043.69
mohammed a awadallah427322.16