On the Impact of the Cutoff Time on the Performance of Algorithm Configurators
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 RLS$_k$ 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 $\kappa$ (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 RLS$_k$ 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 RLS$_k$ for Ridge* for any $\kappa$ while ParamRLS-T requires at least quadratic $\kappa$. For OneMax ParamRLS-F identifies $k=1$ as optimal with linear $\kappa$ while ParamRLS-T requires a $\kappa$ of at least $\Omega(n\log n)$. For smaller $\kappa$ ParamRLS-F identifies that $k>1$ performs better while ParamRLS-T returns $k$ chosen uniformly at random.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Analysis of the Performance of Algorithm Configurators for Search Heuristics with Global Mutation Operators
Recently it has been proved that a simple algorithm configurator called ParamRLS can efficiently identify the optimal neighbourhood size to be used by stochastic local search to optimise two standard benchmark problem cl…
Evolutionary AlgorithmsFast Perturbative Algorithm Configurators
Recent work has shown that the ParamRLS and ParamILS algorithm configurators can tune some simple randomised search heuristics for standard benchmark functions in linear expected time in the size of the parameter space. …
Chameleon 2: An Improved Graph-Based Clustering Algorithm
Traditional clustering algorithms fail to produce human-like results when confronted with data of variable density, complex distributions, or in the presence of noise. We propose an improved graph-based clustering algori…
ClusteringAll Leaks Count, Some Count More: Interpretable Temporal Contamination Detection and Mitigation in LLM Backtesting
Backtesting LLMs on resolved events assumes models reason only from pre-cutoff knowledge, yet pretrained models inevitably leak post-cutoff knowledge. We introduce a claim-level evaluation framework that decomposes predi…
Analyzing the Impact of Undersampling on the Benchmarking and Configuration of Evolutionary Algorithms
The stochastic nature of iterative optimization heuristics leads to inherently noisy performance measurements. Since these measurements are often gathered once and then used repeatedly, the number of collected samples wi…
BenchmarkingEvolutionary Algorithms