  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.
