Running time analysis of the (1+1)-EA for OneMax and LeadingOnes under bit-wise noise

DOI10.1007/S00453-018-0488-4zbMATH Open1411.68147arXiv1711.00956OpenAlexW2883770650MaRDI QIDQ1725652FDOQ1725652

Authors: Chao Qian, Chao Bian, Wu Jiang, Ke Tang 

Publication date: 14 February 2019

Published in: Algorithmica (Search for Journal in Brave)

Abstract: In many real-world optimization problems, the objective function evaluation is subject to noise, and we cannot obtain the exact objective value. Evolutionary algorithms (EAs), a type of general-purpose randomized optimization algorithm, have been shown to be able to solve noisy optimization problems well. However, previous theoretical analyses of EAs mainly focused on noise-free optimization, which makes the theoretical understanding largely insufficient for the noisy case. Meanwhile, the few existing theoretical studies under noise often considered the one-bit noise model, which flips a randomly chosen bit of a solution before evaluation; while in many realistic applications, several bits of a solution can be changed simultaneously. In this paper, we study a natural extension of one-bit noise, the bit-wise noise model, which independently flips each bit of a solution with some probability. We analyze the running time of the (1+1)-EA solving OneMax and LeadingOnes under bit-wise noise for the first time, and derive the ranges of the noise level for polynomial and super-polynomial running time bounds. The analysis on LeadingOnes under bit-wise noise can be easily transferred to one-bit noise, and improves the previously known results. Since our analysis discloses that the (1+1)-EA can be efficient only under low noise levels, we also study whether the sampling strategy can bring robustness to noise. We prove that using sampling can significantly increase the largest noise level allowing a polynomial running time, that is, sampling is robust to noise.

Full work available at URL: https://arxiv.org/abs/1711.00956

Recommendations

• Analysing the robustness of evolutionary algorithms to noise: refined runtime bounds and an example where noise is beneficial
• Efficient optimisation of noisy fitness functions with population-based evolutionary algorithms
• Run-time analysis of population-based evolutionary algorithm in noisy environments
• Robustness of populations in stochastic environments
• (1+1) EA on Generalized Dynamic OneMax

zbMATH Keywords

samplingcomputational complexityevolutionary algorithmsrunning time analysisnoisy optimization

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms (68W40)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Adaptive drift analysis
• A simple ant colony optimizer for stochastic shortest path problems
• Multiplicative drift analysis
• The choice of the offspring population size in the \((1,\lambda)\) evolutionary algorithm
• Efficient optimisation of noisy fitness functions with population-based evolutionary algorithms
• Robustness of populations in stochastic environments
• Optimizing expected path lengths with ant colony optimization using fitness proportional update
• Drift analysis and average time complexity of evolutionary algorithms
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Simplified drift analysis for proving lower bounds in evolutionary computation
• Sharpening of the Upper Bound of the Absolute Constant in the Berry–Esseen Inequality
• On the analysis of the \((1+1)\) evolutionary algorithm
• Analysis of runtime of optimization algorithms for noisy functions over discrete codomains
• Title not available (Why is that?)
• Running time analysis of the \((1+1)\)-EA for OneMax and LeadingOnes under bit-wise noise
• Run-time analysis of population-based evolutionary algorithm in noisy environments
• Resampling vs recombination: a statistical run time estimation

Cited In (20)

• Run-time analysis of population-based evolutionary algorithm in noisy environments
• Runtime analysis of \((1+1)\) evolutionary algorithm controlled with Q-learning using greedy exploration strategy on \textsc{OneMax+ZeroMax} problem
• Running time analysis of the (1+1)-EA for robust linear optimization
• Runtime analyses of the population-based univariate estimation of distribution algorithms on LeadingOnes
• Working principles of binary differential evolution
• Fourier analysis meets runtime analysis: precise runtimes on plateaus
• Exponential upper bounds for the runtime of randomized search heuristics
• (1+1) EA on Generalized Dynamic OneMax
• Title not available (Why is that?)
• More precise runtime analyses of non-elitist evolutionary algorithms in uncertain environments
• Sharp bounds on the runtime of the (1+1) EA via drift analysis and analytic combinatorial tools
• Analysis of runtime of optimization algorithms for noisy functions over discrete codomains
• Modeling the dynamics of a changing range genetic algorithm in noisy environments
• Runtime analysis of the \((1+1)\) EA on computing unique input output sequences
• Efficient optimisation of noisy fitness functions with population-based evolutionary algorithms
• Running time analysis of the \((1+1)\)-EA for OneMax and LeadingOnes under bit-wise noise
• The voting algorithm is robust to various noise models
• Self-adaptation Can Improve the Noise-tolerance of Evolutionary Algorithms
• Analysis of noisy evolutionary optimization when sampling fails
• Analysing the robustness of evolutionary algorithms to noise: refined runtime bounds and an example where noise is beneficial

This page was built for publication: Running time analysis of the \((1+1)\)-EA for OneMax and LeadingOnes under bit-wise noise

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1725652)