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

Research output: Chapter in Book/Report/Conference proceedingConference Proceeding (Non-Journal item)


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.
Original languageEnglish
Title of host publicationGECCO Comp '14
Subtitle of host publicationProceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation
PublisherAssociation for Computing Machinery
Number of pages2
ISBN (Print)978-1-4503-2881-4
Publication statusPublished - 12 Jul 2014
Externally publishedYes
EventGECCO 2014: The Genetic and Evolutionary Computation Conference - Vancouver, Canada
Duration: 12 Jul 201416 Jul 2014


ConferenceGECCO 2014: The Genetic and Evolutionary Computation Conference
Period12 Jul 201416 Jul 2014


  • expected running time
  • helper-objectives
  • multiobjectiviation


Dive into the research topics of 'Onemax helps optimizing XdivK: theoretical runtime analysis for RLS and EA+RL'. Together they form a unique fingerprint.

Cite this