On the Sufficiency of SAT Features for Genetic Algorithm Parameter Selection

Authors:
Open Access
Publisher website
Google Scholar
Abstract
Numerous studies have proposed a wide range of features for Boolean SAT (satisfiability) problems, primarily aimed at predicting solver runtime or guiding algorithm selection. In this study, we investigate whether SAT instance features can be leveraged to predict suitable Island Genetic Algorithm (IGA) parameter settings for a given SAT instance. Our results indicate that even a single SAT feature is sufficient to guide the selection of IGA parameter settings with reasonable performance. We analyze this phenomenon by training an ensemble of machine learning models on progressively smaller subsets of features and evaluating how performance degrades as features are removed. In particular, models trained on a single feature typically retain at least 90% of the performance achieved by models trained on the full feature set. Moreover, several parameters can be accurately predicted using only basic SAT statistics, such as the number of clauses and variables. Additionally, it can be observed from the results that certain features have strong generalization ability and can serve as proxies for a set of other features when predicting IGA parameter settings. Overall, our findings demonstrate that a small set of simple SAT features yields a practical and transferable signal for instance-specific IGA parameter selection.
Funding Information
  • Polish Ministry of Education and Science
  • AGH University of Krakow — Excellence Initiative – Research University
  • National Science Centre Poland (UMO-2021/01/2/ST6/00004)
  • National Science Centre Poland (ARTIQ/0004/2021)

This publication has 27 references indexed in Scilit: