Analysis of the \((1 + 1)\) EA on subclasses of linear functions under uniform and linear constraints

DOI10.1016/j.tcs.2018.04.051zbMath1443.68227OpenAlexW2809877335MaRDI QIDQ2182714

Frank Neumann, J. A. Gregor Lagodzinski, Timo Kötzing, Tobias Friedrich, Martin Schirneck

Publication date: 26 May 2020

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

Full work available at URL: http://hdl.handle.net/2440/124600

zbMATH Keywords

evolutionary algorithmconstraintsknapsackruntime analysis

Mathematics Subject Classification ID

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

Related Items (4)

Do additional target points speed up evolutionary algorithms? ⋮ Time complexity analysis of evolutionary algorithms for 2-hop \((1,2)\)-minimum spanning tree problem ⋮ Improved runtime results for simple randomised search heuristics on linear functions with a uniform constraint ⋮ Running time analysis of the (1+1)-EA for robust linear optimization

Uses Software

• GenProg

Cites Work

• Unnamed Item
• Unnamed Item
• Robustness of populations in stochastic environments
• Concentration of first hitting times under additive drift
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Analyzing evolutionary algorithms. The computer science perspective.
• Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
• Improved time complexity analysis of the simple genetic algorithm
• Runtime analysis of a binary particle swarm optimizer
• On the analysis of the \((1+1)\) evolutionary algorithm
• A study of drift analysis for estimating computation time of evolutionary algorithms
• Multiplicative drift analysis
• Black-box search by unbiased variation
• Upper and lower bounds for randomized search heuristics in black-box optimization
• (1+1) EA on Generalized Dynamic OneMax
• Tight Bounds on the Optimization Time of a Randomized Search Heuristic on Linear Functions
• Simple max-min ant systems and the optimization of linear pseudo-boolean functions
• Optimizing expected path lengths with ant colony optimization using fitness proportional update
• Analysis of the (1+1) EA on Subclasses of Linear Functions under Uniform and Linear Constraints
• Mean Deviation of the Binomial Distribution

This page was built for publication: Analysis of the \((1 + 1)\) EA on subclasses of linear functions under uniform and linear constraints