Running time analysis of the (1+1)-EA for robust linear optimization
From MaRDI portal
(Redirected from Publication:2003994)
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 . Two common robust scenarios, i.e., deletion-robust and worst-case, are considered. Particularly, we derive tight ranges of the robust parameter or budget allowing the (1+1)-EA to find an optimal solution in polynomial running time, which disclose the potential of EAs for robust optimization.
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
- scientific article; zbMATH DE number 6843801
Cites work
- scientific article; zbMATH DE number 5968956 (Why is no real title available?)
- scientific article; zbMATH DE number 976350 (Why is no real title available?)
- scientific article; zbMATH DE number 5686753 (Why is no real title available?)
- (1+1) EA on Generalized Dynamic OneMax
- A simple ant colony optimizer for stochastic shortest path problems
- An efficient constraint handling method for genetic algorithms
- Analysis of the \((1 + 1)\) EA on subclasses of linear functions under uniform and linear constraints
- Analyzing evolutionary algorithms. The computer science perspective.
- Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
- Drift analysis and average time complexity of evolutionary algorithms
- Efficient optimisation of noisy fitness functions with population-based evolutionary algorithms
- Greed is Good: Algorithmic Results for Sparse Approximation
- Multiplicative drift analysis
- Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
- On the analysis of the \((1+1)\) evolutionary algorithm
- Optimizing expected path lengths with ant colony optimization using fitness proportional update
- Reoptimization time analysis of evolutionary algorithms on linear functions under dynamic uniform constraints
- Robust monotone submodular function maximization
- Robust optimization - a comprehensive survey
- Robustness of populations in stochastic environments
- Run-time analysis of population-based evolutionary algorithm in noisy environments
- Running time analysis of the \((1+1)\)-EA for OneMax and LeadingOnes under bit-wise noise
- Runtime analysis of ant colony optimization on dynamic shortest path problems
- Tight bounds on the optimization time of a randomized search heuristic on linear functions
Cited in
(4)- Analysing equilibrium states for population diversity
- Fixed Budget Performance of the (1+1) EA on Linear Functions
- 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
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)
