Thumbnail
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

   Open content in new tab
Source: ACM Digital Library