The ACM Journal of Experimental Algorithmics

The Reactive Search (RS) method proposes the integration of a simple history-based feedback 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 is complemented with a reactive scheme that determines ("learns") the appropriate value of the prohibition parameter by monitoring the Hamming distance along the search trajectory (algorithm H-RTS). In addition, the 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 search. The 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-3Sat and Max-4Sat problems demonstrate the superiority of H-RTS with respect to alternative heuristics.

• Keywords:
• CR Categories:
• Sources:
  
  • The LaTeX version of the article; this is a Unix tar file that contains the LaTeX source, several EPS figures, and several bibliographies; note that you must be a subscriber (institutional or individual) to access this file.
  • The Postscript version or PDF version of the article;
    note that you must be a subscriber (institutional or individual) to access these files.
  • The HTML version of the article;
    note that you must be a subscriber (institutional or individual) to access this file.
  • The software suite accompanying the article; this is a small Unix tar file.
  • The bibliography given in the article.

Last updated and validated May 19, 1997, by editor@jea.acm.org