Reducing the cost of partition crossover on large MAXSAT problems
Preston Dunton, Darrell Whitley · Proceedings of the Genetic and Evolutionary Computation Conference · 2022
Combining Iterated Local Search with Partition Crossover (PX) has the potential to be a powerful hybrid search strategy for MAX-kSAT problems. The disadvantage of standard Partition Crossover is that it touches every variable and every clause. This paper borrows strategies from WalkSAT to improve Partition Crossover such that it only touches a fraction of clauses by focusing on unsatisfied clauses. On average, it is possible to speed up Partition Crossover by one or two orders of magnitude. The PX-preprocessor also simplifies the interface between Partition Crossover and local search. Partition Crossover is compared with and without the PX-preprocessor on 478 SAT instances from the 2014 SAT competition; PX is particularly effective on application problems and larger problem instances.