Paper Info
Title
Onemax helps optimizing XdivK:: theoretical runtime analysis for RLS and EA+RL
Abstract
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.
Year
DOI
Venue
2014
10.1145/2598394.2598442
GECCO (Companion)
Keywords
Field
DocType
expected running time,multiobjectivization,optimization,helper-objectives,learning
Expression (mathematics),Computer science,Artificial intelligence,Optimization algorithm,Divisor,Bit array,Optimization problem,Speedup,Mathematical optimization,Exponential function,Algorithm,Local search (optimization),Machine learning
Conference
Citations 
PageRank 
References 
6
0.49
4
Authors
2
Name
Order
Citations
PageRank
Maxim Buzdalov114125.29
Arina Buzdalova2619.42