Provably Optimal Self-adjusting Step Sizes for Multi-valued Decision Variables

被引:10
作者
Doerr, Benjamin [1 ]
Doerr, Carola [2 ,3 ]
Koetzing, Timo [4 ]
机构
[1] Ecole Polytech, Palaiseau, France
[2] UPMC Univ Paris 06, CNRS, LIP6, Paris, France
[3] UPMC Univ Paris 06, Sorbonne Univ, Paris, France
[4] Hasso Plattner Inst, Potsdam, Germany
来源
PARALLEL PROBLEM SOLVING FROM NATURE - PPSN XIV | 2016年 / 9921卷
关键词
Run time analysis; Adaptive parameter choices; Mutation; Theory; SEARCH; OPTIMIZATION; ALGORITHMS; BOUNDS;
D O I
10.1007/978-3-319-45823-6_73
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
We regard the problem of maximizing a OneMax-like function defined over an alphabet of size gamma. In previous work [GECCO 2016] we have investigated how three different mutation operators influence the performance of Randomized Local Search (RLS) and the (1+ 1) Evolutionary Algorithm. This work revealed that among these natural mutation operators none is superior to the other two for any choice of gamma. We have also given in [ GECCO 2016] some indication that the best achievable run time for large gamma is theta(n log r(log n + logr)), regardless of how the mutation operator is chosen, as long as it is a static choice (i.e., the distribution used for variation of the current individual does not change over time). Here in this work we show that we can achieve a better performance if we allow for adaptive mutation operators. More precisely, we analyze the performance of RLS using a self-adjusting mutation strength. In this algorithm the size of the steps taken in each iteration depends on the success of previous iterations. That is, the mutation strength is increased after a successful iteration and it is decreased otherwise. We show that this idea yields an expected optimization time of theta( n( log n + logr)), which is optimal among all comparison-based search heuristics. This is the first time that self-adjusting parameter choices are shown to outperform static choices on a discrete multi-valued optimization problem.
引用
收藏
页码:782 / 791
页数:10
相关论文
共 19 条
[1]  
Auger A., 2013, CORR
[2]  
Auger A., 2011, Theory of randomized search heuristics: Foundations and recent developments
[3]  
Böttcher S, 2010, LECT NOTES COMPUT SC, V6238, P1, DOI 10.1007/978-3-642-15844-5_1
[4]   Tight Bounds for Blind Search on the Integers and the Reals [J].
Dietzfelbinger, Martin ;
Rowe, Jonathan E. ;
Wegener, Ingo ;
Woelfel, Philipp .
COMBINATORICS PROBABILITY & COMPUTING, 2010, 19 (5-6) :711-728
[5]  
Doerr B., 2016, P ACM GEN E IN PRESS
[6]   Optimal Parameter Choices Through Self-Adjustment: Applying the 1/5-th Rule in Discrete Settings [J].
Doerr, Benjamin ;
Doerr, Carola .
GECCO'15: PROCEEDINGS OF THE 2015 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, 2015, :1335-1342
[7]   From black-box complexity to designing new genetic algorithms [J].
Doerr, Benjamin ;
Doerr, Carola ;
Ebel, Franziska .
THEORETICAL COMPUTER SCIENCE, 2015, 567 :87-104
[8]   Adaptive Drift Analysis [J].
Doerr, Benjamin ;
Goldberg, Leslie Ann .
ALGORITHMICA, 2013, 65 (01) :224-250
[9]   Multiplicative Drift Analysis [J].
Doerr, Benjamin ;
Johannsen, Daniel ;
Winzen, Carola .
ALGORITHMICA, 2012, 64 (04) :673-697
[10]   Upper and lower bounds for randomized search heuristics in black-box optimization [J].
Droste, Stefan ;
Jansen, Thomas ;
Wegener, Ingo .
THEORY OF COMPUTING SYSTEMS, 2006, 39 (04) :525-544