### Reactive search, a history-sensitive heuristic for MAX-SATReactive search, a history-sensitive heuristic for MAX-SAT

Access Restriction
Subscribed

 Author Battiti, Roberto ♦ Protasi, Marco Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1997 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Abstract The Reactive Search (RS) method proposes the integration of a simple history-sensitive (machine learning) scheme into local search for the on-line determination of free parameters. In this paper a new RS algorithm is proposed for the approximated solution of the Maximum Satisfiability problem: a component based on local search with temporary prohibitions (Tabu Search) is complemented with a reactive scheme that determines the appropriate value of the prohibition parameter by monitoring the Hamming distance along the search trajectory. The proposed algorithm (H-RTS) can therefore be characterized as a $\textit{dynamic}$ version of Tabu Search.In addition, the $\textit{non-oblivious}$ functions recently introduced in the framework of approximation algorithms are used to discover a better local optimum in the initial part of the searchThe algorithm is developed in two phases. First the bias-diversification properties of individual candidate components are analyzed by extensive empirical evaluation, then a reactive scheme is added to the winning component, based on Tabu Search.The final tests on a benchmark of random MAX-3-SAT and MAX-4-SAT problems demonstrate the superiority of H-RTS with respect to alternative heuristics. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1997-01-01 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 2

#### Open content in new tab

Source: ACM Digital Library