Enhancing Constraint Solver Efficiency with Self-Learning Genetic Algorithms
Hu Xu, Karen Petrie
Journal of Data Processing, Vol. 15, No. 2, 2025.
DOI: https://doi.org/10.6025/jdp/2025/15/2/51-58
Link: https://www.dline.info/jdp/fulltext/v15n2/jdpv15n2_1.pdf
Abstract:
This paper explores an automated approach to tuning constraint solvers using genetic algorithms (GAs). In
traditional constraint programming, selecting preprocessing parameters is a manual process that requires
expertise, creating a barrier for novices. The authors propose a self-learning genetic algorithm (SLGA) that
leverages knowledge from minor problem instances to guide the search for optimal preprocessing in larger
instances.
SLGA begins by solving small-scale constraint satisfaction problems to identify effective preprocessing strategies.
These strategies then form the starting population for the GA when applied to larger problems, replacing
the standard random initialization. Two strategies are tested: Learning from Best (LFB) and Learning
from Genetic (LFG), with LFB utilising the best-known methods and LFG employing those derived from
previous GA runs.
Experiments on benchmark problems (BIBD, N-Queen, Golomb, and Langford's number) show that SLGA
outperforms standard GAs in both efficiency and solution quality. Particularly, LFG consistently finds better
preprocessing settings, even when exhaustive search is infeasible. The paper concludes that SLGA is a promising
tool for automating configuration in constraint solving, and future work will explore its application to
more complex and large-scale problems.