UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

On the impact of the performance metric on efficient algorithm configuration

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. Green open access

[thumbnail of Tuning_Paper_AIJ_Version.pdf]
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 κ≤(nln⁡n)/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
Downloads since deposit
21Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item