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\nParamRLS can efficiently identify the optimal neighbourhood size to be used by\nstochastic local search to optimise two standard benchmark problem classes. In\nthis paper we analyse the performance of algorithm configurators for tuning the\nmore sophisticated global mutation operator used in standard evolutionary\nalgorithms, which flips each of the $n$ bits independently with probability\n$\\chi/n$ and the best value for $\\chi$ has to be identified. We compare the\nperformance of configurators when the best-found fitness values within the\ncutoff time $\\kappa$ are used to compare configurations against the actual\noptimisation time for two standard benchmark problem classes, Ridge and\nLeadingOnes. We rigorously prove that all algorithm configurators that use\noptimisation time as performance metric require cutoff times that are at least\nas large as the expected optimisation time to identify the optimal\nconfiguration. Matters are considerably different if the fitness metric is\nused. To show this we prove that the simple ParamRLS-F configurator can\nidentify the optimal mutation rates even when using cutoff times that are\nconsiderably smaller than the expected optimisation time of the best parameter\nvalue for both problem classes.\n