Item

Abstract

At last year’s GECCO a novel perspective for theoretical performance analysis of evolutionary algorithms and other randomised search heuristics was introduced that concen- trates on the expected function value after a pre-defined number of steps, called budget. This is significantly differ- ent from the common perspective where the expected op- timisation time is analysed. While there is a huge body of work and a large collection of tools for the analysis of the ex- pected optimisation time the new fixed budget perspective introduces new analytical challenges. Here it is shown how results on the expected optimisation time that are strength- ened by deviation bounds can be systematically turned into fixed budget results. We demonstrate our approach by con- sidering the (1+1) EA on LeadingOnes and significantly improving previous results. We prove that deviating from the expected time by an additive term of ω n 3 / 2 happens only with probability o (1). This is turned into tight bounds on the function value using the inverse function. We use three, increasingly strong or general approaches to proving the deviation bounds, namely via Chebyshev’s inequality, via Chernoff bounds for geometric random variables, and via variable drift analysis.