EVOLVED PREAMBLES FOR MAX-SAT HEURISTICS

Luís O. Rigo Jr., Valmir C. Barbosa

2011

Abstract

MAX-SAT heuristics normally operate from random initial truth assignments to the variables. We consider the use of what we call preambles, which are sequences of variables with corresponding single-variable assignment actions intended to be used to determine a more suitable initial truth assignment for a given problem instance and a given heuristic. For a number of well established MAX-SAT heuristics and benchmark instances, we demonstrate that preambles can be evolved by a genetic algorithm such that the heuristics are outperformed in a significant fraction of the cases. The heuristics we consider include the well-known novelty, walksat-tabu, and adaptnovelty+. Our benchmark instances are those of the 2004 SAT competition and those of the 2008 MAX-SAT evaluation.

Paper Citation

in Harvard Style

O. Rigo Jr. L. and C. Barbosa V. (2011). EVOLVED PREAMBLES FOR MAX-SAT HEURISTICS . In Proceedings of the International Conference on Evolutionary Computation Theory and Applications - Volume 1: ECTA, (IJCCI 2011) ISBN 978-989-8425-83-6, pages 23-31. DOI: 10.5220/0003660400230031

in Bibtex Style

@conference{ecta11,
author={Luís O. Rigo Jr. and Valmir C. Barbosa},
title={EVOLVED PREAMBLES FOR MAX-SAT HEURISTICS},
booktitle={Proceedings of the International Conference on Evolutionary Computation Theory and Applications - Volume 1: ECTA, (IJCCI 2011)},
year={2011},
pages={23-31},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0003660400230031},
isbn={978-989-8425-83-6},
}

in EndNote Style

TY - CONF
JO - Proceedings of the International Conference on Evolutionary Computation Theory and Applications - Volume 1: ECTA, (IJCCI 2011)
TI - EVOLVED PREAMBLES FOR MAX-SAT HEURISTICS
SN - 978-989-8425-83-6
AU - O. Rigo Jr. L.
AU - C. Barbosa V.
PY - 2011
SP - 23
EP - 31
DO - 10.5220/0003660400230031