Hall, George T;
Oliveto, Pietro S;
Sudholt, Dirk;
(2022)
On the impact of the performance metric on efficient algorithm configuration.
Artificial Intelligence
, 303
, Article 103629. 10.1016/j.artint.2021.103629.
Preview |
Text
Tuning_Paper_AIJ_Version.pdf - Accepted Version Download (531kB) | Preview |
Abstract
Algorithm configurators are automated methods to optimise the parameters of an algorithm for a class of problems. We analyse the impact of the cutoff time κ (the time spent evaluating a configuration for a problem instance) on the expected number of configuration comparisons required to find the optimal parameter value for the performance metrics (the measure used to judge the performance of a configuration) that compare configurations using either the best-found fitness values or optimisation times. We first prove that the configurators that use optimisation time as performance metric are not able to tune any unary unbiased algorithm for any function with up to an exponential number of optima using κ≤(nlnn)/2. Afterwards, we show that for simple algorithm configuration scenarios the required cutoff time for the optimisation time metric may be considerably larger while using the best fitness metric allows the tuners to configure the target algorithm in linear time in the number of parameters.
| Type: | Article |
|---|---|
| Title: | On the impact of the performance metric on efficient algorithm configuration |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1016/j.artint.2021.103629 |
| Publisher version: | https://doi.org/10.1016/j.artint.2021.103629 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | Algorithm configurators, parameter tuning, runtime analysis, performance metrics, cutoff time |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences > Faculty of Population Health Sciences > UCL GOS Institute of Child Health UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences > Faculty of Population Health Sciences > UCL GOS Institute of Child Health > Genetics and Genomic Medicine Dept |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10163436 |
Archive Staff Only
 |
View Item |
