Running time analysis of the (1+1)-EA for robust linear optimization

DOI10.1016/J.TCS.2020.07.001zbMATH Open1460.68137arXiv1906.06873OpenAlexW3041825806MaRDI QIDQ2003994FDOQ2003994

Yang Yu, Chao Qian, Chao Bian, Ke Tang

Publication date: 13 October 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: Evolutionary algorithms (EAs) have found many successful real-world applications, where the optimization problems are often subject to a wide range of uncertainties. To understand the practical behaviors of EAs theoretically, there are a series of efforts devoted to analyzing the running time of EAs for optimization under uncertainties. Existing studies mainly focus on noisy and dynamic optimization, while another common type of uncertain optimization, i.e., robust optimization, has been rarely touched. In this paper, we analyze the expected running time of the (1+1)-EA solving robust linear optimization problems (i.e., linear problems under robust scenarios) with a cardinality constraint $k$. Two common robust scenarios, i.e., deletion-robust and worst-case, are considered. Particularly, we derive tight ranges of the robust parameter $d$ or budget $k$ allowing the (1+1)-EA to find an optimal solution in polynomial running time, which disclose the potential of EAs for robust optimization.

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

zbMATH Keywords

computational complexityrobust optimizationevolutionary algorithmsrunning-time analysis

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms (68W40) Evolutionary algorithms, genetic algorithms (computational aspects) (68W50) Integer programming (90C10) Robustness in mathematical programming (90C17)

Cites Work

• An efficient constraint handling method for genetic algorithms
• Greed is Good: Algorithmic Results for Sparse Approximation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Robust optimization - a comprehensive survey
• A simple ant colony optimizer for stochastic shortest path problems
• Multiplicative drift analysis
• Efficient Optimisation of Noisy Fitness Functions with Population-based Evolutionary Algorithms
• Robustness of populations in stochastic environments
• Tight Bounds on the Optimization Time of a Randomized Search Heuristic on Linear Functions
• 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
• Analyzing evolutionary algorithms. The computer science perspective.
• Title not available (Why is that?)
• On the analysis of the \((1+1)\) evolutionary algorithm
• Reoptimization time analysis of evolutionary algorithms on linear functions under dynamic uniform constraints
• Runtime analysis of ant colony optimization on dynamic shortest path problems
• Title not available (Why is that?)
• Robust Monotone Submodular Function Maximization
• Running time analysis of the \((1+1)\)-EA for OneMax and LeadingOnes under bit-wise noise
• (1+1) EA on Generalized Dynamic OneMax
• Run-Time Analysis of Population-Based Evolutionary Algorithm in Noisy Environments
• Analysis of the \((1 + 1)\) EA on subclasses of linear functions under uniform and linear constraints

Cited In (4)

• Fixed Budget Performance of the (1+1) EA on Linear Functions
• Analysing equilibrium states for population diversity
• Analysis of the \((1 + 1)\) EA on subclasses of linear functions under uniform and linear constraints
• Sharp bounds on the runtime of the (1+1) EA via drift analysis and analytic combinatorial tools

   Recommendations

• Robustness analysis via the running time of the interior point methods 👍 👎
• An efficient algorithm for a certain class of robust optimization problems 👍 👎
• Fixed Budget Performance of the (1+1) EA on Linear Functions 👍 👎
• Some extensions of robust linear optimization 👍 👎
• Analysis of the \((1 + 1)\) EA on subclasses of linear functions under uniform and linear constraints 👍 👎
• Robust optimizers for nonlinear programming in approximate dynamic programming 👍 👎
• Analysis of the (1+1) EA on subclasses of linear functions under uniform and linear constraints 👍 👎
• An approximation technique for robust nonlinear optimization 👍 👎
• Run-time transformations of linear multi-objective optimization 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: Running time analysis of the (1+1)-EA for robust linear optimization

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