On the usefulness of linkage processing for solving MAX-SAT
Presented at the Benelux Conference on Artificial Intelligence (November 2013)
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.
|K.V. Hindriks , M.M. de Weerdt (Mathijs) , B. Riemsdijk , M.E. Warnier (Martijn)|
|Benelux Conference on Artificial Intelligence|
|Organisation||Intelligent and autonomous systems|
Sadowski, K.L, Bosman, P.A.N, & Thierens, D. (2013). On the usefulness of linkage processing for solving MAX-SAT. In K.V Hindriks, M.M de Weerdt, B Riemsdijk, & M.E Warnier (Eds.), Proceedings of BeNeLux Conference on Artificial Intelligence 2013 (pp. 350–351). TU Delft.