On the usefulness of linkage processing for solving MAX-SAT

Mixing of partial solutions is a key mechanism used for creating new solutions in many Genetic Algorithms (GAs). However, this mixing can be disruptive and generate improved solutions inefficiently. Exploring a problem’s structure can help in establishing less disruptive operators, leading to more efficient mixing. One way of using a problem’s structure is to consider variable linkage information. This paper focuses on exploring different methods of building family of subsets (FOS) linkage models, which are then used with the Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) to solve MAX-SAT problems. The GOMEA framework provides an efficient mechanism for mixing partial solutions and generating new candidate solutions, given a FOS linkage model. We wish to examine if learning variable linkage information, and representing this linkage within a FOS model can be beneficial in creating highly fit solutions more efficiently.