caa a22 4500 445804823 CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110301xx s 000 0 eng 10.1007/s00453-010-9396-y doi (NATIONALLICENCE)springer-10.1007/s00453-010-9396-y Jägersküpper Jens Institute of Aerodynamics and Flow Technology, Center for Computer Applications in Aerospace Science and Engineering (C²A²S²E), German Aerospace Center (DLR), Braunschweig, Germany aut Combining Markov-Chain Analysis and Drift Analysis [Elektronische Daten] The (1+1)Evolutionary Algorithm on Linear Functions Reloaded [Jens Jägersküpper] In their seminal article Droste, Jansen, and Wegener (Theor. Comput. Sci. 276:51-82, 2002) consider a basic direct-search heuristic with a global search operator, namely the so-called (1+1) Evolutionary Algorithm ((1+1) EA). They present the first theoretical analysis of the (1+1) EA's expected runtime for the class of linear functions over the search space {0,1}n. In a rather long and involved proof they show that, for any linear function, the expected runtime is O(nlog n), i.e., that there are two constants c and n′ such that, for n≥n′, the expected number of iterations until a global optimum is generated is bounded above by c⋅nlog 2 n. However, neither c nor n′ are specified—they would be pretty large. Here we reconsider this optimization scenario to demonstrate the potential of an analytical method that makes use of the distribution of the evolving candidate solution over the search space {0,1}n. Actually, an invariance property of this distribution is proved, which is then used to obtain a significantly improved bound on the drift, namely the expected change of a potential function, here the number of bits set correctly. Finally, this better estimate of the drift enables an upper bound on the expected number of iterations of 3.8nlog 2 n+7.6log 2 n for n≥2. Springer Science+Business Media, LLC, 2010 Heuristic optimization nationallicence Direct search nationallicence Evolutionary algorithms nationallicence Genetic algorithms nationallicence Randomized algorithms nationallicence Drift analysis nationallicence Markov-Chain analysis nationallicence Algorithmica Springer-Verlag 59/3(2011-03-01), 409-424 0178-4617 59:3<409 2011 59 453 https://doi.org/10.1007/s00453-010-9396-y text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9396-y text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Jägersküpper Jens Institute of Aerodynamics and Flow Technology, Center for Computer Applications in Aerospace Science and Engineering (C²A²S²E), German Aerospace Center (DLR), Braunschweig, Germany aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 59/3(2011-03-01), 409-424 0178-4617 59:3<409 2011 59 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer