.png){kind=icon}
Return
An effective heuristic algorithm for the maximum satisfiability problem
.png){kind=icon}
PRE
AI
DOI：10.1007/s10489-006-8514-7.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Stochastic local search algorithms (SLS) have been increasingly applied to approximate solutions of the weighted maximum satisfiability problem (MAXSAT), a model for solutions of major problems in AI and combinatorial optimization. While MAXSAT instances have generally a strong intrinsic dependency between their variables, most of SLS algorithms start the search process with a random initial solution where the value of each variable is generated independently with the same uniform distribution. In this paper, we propose a new SLS algorithm for MAXSAT based on an unconventional distribution known as the Bose-Einstein distribution in quantum physics. It provides a stochastic initialization scheme to an efficient and very simple heuristic inspired by the co-evolution process of natural species and called Extremal Optimization (EO). This heuristic was introduced for finding high quality solutions to hard optimization problems such as colouring and partitioning. We examine the effectiveness of the resulting algorithm by computational experiments on a large set of test instances and compare it with some of the most powerful existing algorithms. Our results are remarkable and show that this approach is appropriate for this class of problems.
Keywords:
problem solving
heuristic search
MAXSAT
Bose-Einstein distribution
extremal optimization
Journal
IF:
3.5
Papers:
7.6K
Citations:
1.7W
Organization
No organization information available
Cited Papers
ShareSaveDeep Brain Stimulation of Medial Dorsal and Ventral Anterior Nucleus of the Thalamus in OCD: A Retrospective Case Series.png)
PLOS ONE
OAAI
PLOS ONEIF0
OAAIShareSaveShareSaveShareSave
View more