caa a22 4500 445804874 CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110301xx s 000 0 eng 10.1007/s00453-009-9352-x doi (NATIONALLICENCE)springer-10.1007/s00453-009-9352-x Precision, Local Search and Unimodal Functions [Elektronische Daten] [Martin Dietzfelbinger, Jonathan Rowe, Ingo Wegener, Philipp Woelfel] We investigate the effects of precision on the efficiency of various local search algorithms on 1-D unimodal functions. We present a (1+1)-EA with adaptive step size which finds the optimum in O(log n) steps, where n is the number of points used. We then consider binary (base-2) and reflected Gray code representations with single bit mutations. The standard binary method does not guarantee locating the optimum, whereas using the reflected Gray code does so in Θ((log n)2) steps. A(1+1)-EA with a fixed mutation probability distribution is then presented which also runs in O((log n)2). Moreover, a recent result shows that this is optimal (up to some constant scaling factor), in that there exist unimodal functions for which a lower bound of Ω((log n)2) holds regardless of the choice of mutation distribution. For continuous multimodal functions, the algorithm also locates the global optimum in O((log n)2). Finally, we show that it is not possible for a black box algorithm to efficiently optimise unimodal functions for two or more dimensions (in terms of the precision used). Springer Science+Business Media, LLC, 2009 Local search nationallicence Precision nationallicence Computational complexity nationallicence Unimodal functions nationallicence Multimodal functions nationallicence Dietzfelbinger Martin Fakultät für Informatik und Automatisierung, Technische Universität Ilmenau, 98684, Ilmenau, Germany aut Rowe Jonathan School of Computer Science, University of Birmingham, B15 2TT, Birmingham, UK aut Wegener Ingo FB Informatik, Technische Universität Dortmund, 44221, Dortmund, Germany aut Woelfel Philipp Department of Computer Science, University of Calgary, T2N 1N4, Calgary, Alberta, Canada aut Algorithmica Springer-Verlag 59/3(2011-03-01), 301-322 0178-4617 59:3<301 2011 59 453 https://doi.org/10.1007/s00453-009-9352-x text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9352-x text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Dietzfelbinger Martin Fakultät für Informatik und Automatisierung, Technische Universität Ilmenau, 98684, Ilmenau, Germany aut NATIONALLICENCE 700 1- Rowe Jonathan School of Computer Science, University of Birmingham, B15 2TT, Birmingham, UK aut NATIONALLICENCE 700 1- Wegener Ingo FB Informatik, Technische Universität Dortmund, 44221, Dortmund, Germany aut NATIONALLICENCE 700 1- Woelfel Philipp Department of Computer Science, University of Calgary, T2N 1N4, Calgary, Alberta, Canada aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 59/3(2011-03-01), 301-322 0178-4617 59:3<301 2011 59 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer