Solver Tuning with Genetic Algorithms

Abstract

Currently the parameters in a constraint solver are often selected by hand by experts in the field; these parameters might include the level of preprocessing to be used, the variable ordering heuristic or the suitable modelling approach. The efficient and automatic mechanism of parameters tuning for a constraint solver is a step towards making constraint programming a more widely accessible technology. Two types of tuning algorithms are discussed in this thesis: single instance tuning algorithms and instance-based tuning algorithms. A standard genetic based algorithm and a sexual genetic based algorithm are proposed and implemented to deal with the single instance tuning. As an instance-based tuning algorithm, the self-learning genetic algorithm, which suggests or predicts a suitable solver configuration for test instances by learning from train instances, is proposed in this thesis. To improve the efficiency of the instance-based tuning in further, a self-learning sexual genetic algorithm, which combines the self-learning mechanism with the sexual genetic algorithm, was discussed. The experiments in the thesis demonstrate how genetic algorithms are implemented and adapted to aid in parameter selection for constraint solvers. Genetic algorithms were implemented as the fundamental algorithm for tuning and the parameter sensitivity of genetic algorithms is also discussed in this thesis.

Date of Award	2015
Original language	English
Awarding Institution	University of Dundee
Supervisor	Karen Petrie (Supervisor)