2018/12/03 by Dirk Sudholt, Sudholt, Dirk
Computer Science · #Advanced Multi-Objective Optimization Algorithms #Data Structures and Algorithms (cs.DS) #Evolutionary Algorithms and Applications #FOS: Computer and information sciences #Metaheuristic Optimization Algorithms Research #Neural and Evolutionary Computing (cs.NE)
paper · pdf · doi:10.48550/arxiv.1812.00966
openalex publication_date 2018/12/03 · openalex created_date 2022/08/01 · openalex updated_date 2026/07/28
We analyse the performance of well-known evolutionary algorithms (1+1)EA and\n(1+\λ)EA in the prior noise model, where in each fitness evaluation the\nsearch point is altered before evaluation with probability p. We present\nrefined results for the expected optimisation time of the (1+1)EA and the\n(1+\λ)EA on the function LeadingOnes, where bits have to be optimised in\nsequence. Previous work showed that the (1+1)EA on LeadingOnes runs in\npolynomial expected time if p = O((\log n)/n2) and needs superpolynomial\nexpected time if p = \ω((\log n)/n), leaving a huge gap for which no\nresults were known. We close this gap by showing that the expected optimisation\ntime is \Θ(n2) \⋅ \exp(\Θ(\min pn2, n )) for all p \≤ 1/2,\nallowing for the first time to locate the threshold between polynomial and\nsuperpolynomial expected times at p = \Θ((\log n)/n2). Hence the (1+1)EA\non LeadingOnes is much more sensitive to noise than previously thought. We also\nshow that offspring populations of size \λ \≥ 3.42\log n can\neffectively deal with much higher noise than known before.\n Finally, we present an example of a rugged landscape where prior noise can\nhelp to escape from local optima by blurring the landscape and allowing a hill\nclimber to see the underlying gradient. We prove that in this particular\nsetting noise can have a highly beneficial effect on performance.\n