Information Technology Reference
In-Depth Information
random restart for hard unstructured problems derived from the SATLIB benchmark
suite [24].
Gutierrez and Mali [13] presented a basic local search algorithm for ISAT
integrating the ability of recycling model of the satisfiable set of clauses when adding
new clauses. They presented experimental results on both random and structured
ISAT instances generated using SAT instances from the SATLIB benchmark suite
[24]. However, it is not clear how their algorithm could be compared to state-of-the-
art local search-based algorithms for SAT.
Recently, a local search heuristic method called
Extremal Optimization
(EO) was
proposed for solving hard optimization problems such as the graph partitioning [5],
[7], the graph coloring, the spin glass [6] and the maximum satisfiability [19], [20].
EO is characterized by large fluctuations of the search process and extremal selection
against worst variables in a sub-optimal solution. This make it able to explore effi-
ciently the search space without loosing well-adapted parts of a solution. ISAT can be
perceived as the problem of searching an equilibrium to a dynamic system perturbed
by adding new clauses. By Extremal Optimization process the major parts of the
system can be rearranged so that, a new equilibrium state of optimal adaptation can
be reached. Therefore, it is worthwhile to use this heuristic to design an algorithm for
ISAT.
The remainder of the paper is organized as follows. The next Section presents
Extremal Optimization heuristic. Section 3 describes an implementation of EO to
solve the SAT problem. In Section 4, we present a new EO-based algorithm for
solving ISAT. In Section 5, we report on computational results on ISAT instances
generated from SAT benchmark problems. In Section 6, we conclude and discuss
directions for future work.
2 Extremal Optimization Heuristic
In 1987 Bak, Tang and Wiesenfeld [2] introduced the concept of
Self-Organized
Criticality
(SOC) to describe the scale free behaviour exhibited by natural systems
such as earthquakes, water flows in rivers, mass extinction and evolution to name a
few. These systems are driven by their own dynamics to a SOC state characterized by
power-law distribution of event sizes [1]. SOC is produced by self-organization in a
long transitory period at the border of stability and chaos [1].
The Bak and Sneppen (BS) model of evolution [3] is the prototype of a wide class
of SOC models related to various areas such as real evolution of bacteria populations
[8] and macro-economical processes [23]. In BS model, species have an associated
fitness value between 0 and 1 representing a time scale at which the species will mu-
tate to a different species or become extinct. The species with higher fitness has more
chance of surviving. All species are placed on the vertices of a graph and at each
iteration, a selection process against the species with the poorest degree of adaptation
is applied so that the smallest fitness value is replaced by a new random one which
also impacts the fitness values of its neighbours. A state of optimal adaptation (SOC)
above a certain threshold is attained after a sufficient number of steps. In this state
Search WWH ::
Custom Search