Golden Parameter Search:
|
Automated algorithm configuration improves algorithm performance, often by several orders of magnitude, by finding high quality parameter settings. Formally, automated algorithm configuration can be defined as an optimization problem with algorithm A with parameters p that we want to optimize with respect to metric m (here this is running time) on a set I of problem instances.
Previous methods assume algorithm configuration landscapes are complex. These methods are typically heavily based on powerful meta-heuristics that were originally designed for complex and challenging search landscapes. However, we recently showed that many prominent algorithm configuration landscapes are in fact highly structured and much simpler than expected [Pushak & Hoos, 2018].
Golden Parameter Search (GPS) is the first of a new generation of automated algorithm configuration procedures that exploit landscape structure. GPS assumes that all numerical parameters are globally uni-modal and that most parameters do not interact strongly. These assumptions, combined with several key ingredients from other automated algorithm configuration procedures (e.g., racing procedures, intensification mechanisms and an improved version of adaptive capping), allow GPS to quickly and efficiently explore an algorithm's parameter configuration space.
GPS is a highly parallelized method, capable of efficiently scaling from using as few as 2 CPU cores, up to a theoretically unlimitted number. GPS employs multiple granularities of parellelism: it performs a semi-independent search process for each parameter, and it further parallelizes the individual target algorithm runs required to evaluate multiple parameter configurations on multiple problem instances. The more parameters your algorithm has and the longer it takes to perform target algorithm runs — i.e. the harder your problem is to solve — the more GPS will be able to effectively make use of a large number of parallel resources.
GPS often finds equal or better configurations using smaller configuration budgets than several other long-standing, state-of-the-art algorithm configuration procedures [Pushak & Hoos, 2020].
GPS is available as an open source tool that you can use to optimize the performance of your own algorithms in your own work. You can find the latest version of GPS here.