Onemax helps optimizing XdivK: theoretical runtime analysis for RLS and EA+RL

There exist optimization problems with the target objective, which is to be optimized, and several extra objectives, which can be helpful in the optimization process. The previously proposed EA+RL method is designed to adaptively select objectives during the run of an optimization algorithm in order to reduce the number of evaluations needed to reach an optimum of the target objective.

The case when the extra objective is a fine-grained version of the target one is probably the simplest case when using an extra objective actually helps. We define a coarse-grained version of OneMax called XdivK as follows: XdivK(x)= [OneMax(x)/k] for a parameter k which is a divisor of n- the length of a bit vector. We also define XdivK+OneMax, which is a problem where the target objective is XdivK and a single extra objective is OneMax.

In this paper, the randomized local search (RLS) is used in the EA+RL method as an optimization algorithm. We construct exact expressions for the expected running time of RLS solving the XdivK problem and of the EA+RL method solving the XdivK+OneMax problem. It is shown that the EA+RL method makes optimization faster, and the speedup is exponential in k.