Solving the maximum satisfiability problem using an evolutionary local search algorithm
Joint Authors
Batouche, Muhammad
Menai, Muhammad al-Bachir
Source
The International Arab Journal of Information Technology
Issue
Vol. 2, Issue 2 (30 Apr. 2005), pp.154-161, 8 p.
Publisher
Publication Date
2005-04-30
Country of Publication
Jordan
No. of Pages
8
Main Subjects
Information Technology and Computer Science
Topics
Abstract EN
The MAXimum propositional SATisfiability problem (MAXSAT) is a well known NP-hard optimization problem with many theoretical and practical applications in artificial intelligence and mathematical logic.
Heuristic local search algorithms are widely recognized as the most effective approaches used to solve them.
However, their performance depends both on their complexity and their tuning parameters which are controlled experimentally and remain a difficult task.
Extremal Optimization (EO) is one of the simplest heuristic methods with only one free parameter, which has proved competitive with the more elaborate general-purpose method on graph partitioning and coloring.
It is inspired by the dynamics of physical systems with emergent complexity and their ability to self-organize to reach an optimal adaptation state.
In this paper, we propose an extremal optimization procedure for MAXSAT and consider its effectiveness by computational experiments on a benchmark of random instances.
Comparative tests showed that this procedure improves significantly previous results obtained on the same benchmark with other modern local search methods like WSAT, simulated annealing and Tabu Search (TS).
American Psychological Association (APA)
Menai, Muhammad al-Bachir& Batouche, Muhammad. 2005. Solving the maximum satisfiability problem using an evolutionary local search algorithm. The International Arab Journal of Information Technology،Vol. 2, no. 2, pp.154-161.
https://search.emarefa.net/detail/BIM-12152
Modern Language Association (MLA)
Menai, Muhammad al-Bachir& Batouche, Muhammad. Solving the maximum satisfiability problem using an evolutionary local search algorithm. The International Arab Journal of Information Technology Vol. 2, no. 2 (Apr. 2005), pp.154-161.
https://search.emarefa.net/detail/BIM-12152
American Medical Association (AMA)
Menai, Muhammad al-Bachir& Batouche, Muhammad. Solving the maximum satisfiability problem using an evolutionary local search algorithm. The International Arab Journal of Information Technology. 2005. Vol. 2, no. 2, pp.154-161.
https://search.emarefa.net/detail/BIM-12152
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references : p. 160-161
Record ID
BIM-12152