On the impact of the cutoff time on the performance of algorithm configurators
George T. Hall, Pietro S. Oliveto, Dirk Sudholt · Proceedings of the Genetic and Evolutionary Computation Conference · 2019
Algorithm configurators are automated methods to optimise the parameters of an algorithm for a class of problems. We evaluate the performance of a simple random local search configurator (ParamRLS) for tuning the neighbourhood size k of the RLSk algorithm. We measure performance as the expected number of configuration evaluations required to identify the optimal value for the parameter. We analyse the impact of the cutoff time κ (the time spent evaluating a configuration for a problem instance) on the expected number of configuration evaluations required to find the optimal parameter value, where we compare configurations using either best found fitness values (ParamRLS-F) or optimisation times (ParamRLS-T). We consider tuning RLSk for a variant of the Ridge function class (Ridge*), where the performance of each parameter value does not change during the run, and for the OneMax function class, where longer runs favour smaller k. We rigorously prove that ParamRLS-F efficiently tunes RLSk for Ridge* for any κ while ParamRLS-T requires at least quadratic κ. For OneMax ParamRLS-F identifies k = 1 as optimal with linear κ while ParamRLS-T requires a κ of at least ω(n log n). For smaller κ ParamRLS-F identifies that k > 1 performs better while ParamRLS-T returns k chosen uniformly at random.