Solver Tuning with Genetic Algorithms

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.

Name dc:type.qualificationname

Doctor of Philosophy

Level dc:type.qualificationlevel

Doctoral Thesis

Grantor dc:publisher.institution

University of Dundee

Year dc:date.issued

2015

Author dc:creator

• Xu, Hu

Advisor dc:contributor.advisor

• Petrie, Karen

Language dc:language

eng

Identifier

oai:discovery.dundee.ac.uk:studenttheses/eee8f5d9-ede2-4b87-af77-8142b2d0209c

OAI identifier oai:identifier

oai:discovery.dundee.ac.uk:studenttheses/eee8f5d9-ede2-4b87-af77-8142b2d0209c