On the approximation ability of evolutionary optimization with application to minimum set cover
From MaRDI portal
Abstract: Evolutionary algorithms (EAs) are heuristic algorithms inspired by natural evolution. They are often used to obtain satisficing solutions in practice. In this paper, we investigate a largely underexplored issue: the approximation performance of EAs in terms of how close the solution obtained is to an optimal solution. We study an EA framework named simple EA with isolated population (SEIP) that can be implemented as a single- or multi-objective EA. We analyze the approximation performance of SEIP using the partial ratio, which characterizes the approximation ratio that can be guaranteed. Specifically, we analyze SEIP using a set cover problem that is NP-hard. We find that in a simple configuration, SEIP efficiently achieves an -approximation ratio, the asymptotic lower bound, for the unbounded set cover problem. We also find that SEIP efficiently achieves an -approximation ratio, the currently best-achievable result, for the k-set cover problem. Moreover, for an instance class of the k-set cover problem, we disclose how SEIP, using either one-bit or bit-wise mutation, can overcome the difficulty that limits the greedy algorithm.
Recommendations
- Performance analysis of the \((1+1)\) evolutionary algorithm for the multiprocessor scheduling problem
- Runtime analysis of evolutionary algorithms for the depth restricted \((1,2)\)-minimum spanning tree problem
- Analysis of a simple evolutionary algorithm for the multiobjective shortest path problem
- A comparative performance analysis of evolutionary algorithms on k-median and facility location problems
- Evolutionary computation in combinatorial optimization
Cites work
- scientific article; zbMATH DE number 976350 (Why is no real title available?)
- scientific article; zbMATH DE number 1962832 (Why is no real title available?)
- scientific article; zbMATH DE number 1559541 (Why is no real title available?)
- scientific article; zbMATH DE number 1559563 (Why is no real title available?)
- scientific article; zbMATH DE number 5686753 (Why is no real title available?)
- A Better-Than-Greedy Approximation Algorithm for the Minimum Set Cover Problem
- A Greedy Heuristic for the Set-Covering Problem
- A Tight Analysis of the Greedy Algorithm for Set Cover
- A new approach to estimating the expected first hitting time of evolutionary algorithms
- A threshold of ln n for approximating set cover
- Algorithmic construction of sets for k -restrictions
- Approximating the Unweighted ${k}$-Set Cover Problem: Greedy Meets Local Search
- Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
- Computing minimum cuts by randomized search heuristics
- Drift analysis and average time complexity of evolutionary algorithms
- Greedy in Approximation Algorithms
- Minimum spanning trees made easier via multi-objective optimization
- STACS 2005
- Speeding up Approximation Algorithms for NP-Hard Spanning Forest Problems by Multi-objective Optimization
- The analysis of evolutionary algorithms on sorting and shortest paths problems
Cited in
(11)- Lower bounds for comparison based evolution strategies using VC-dimension and sign patterns
- On the Use of the Dual Formulation for Minimum Weighted Vertex Cover in Evolutionary Algorithms
- A simulated evolution-based solution of the cover problem
- Optimizing group learning: an evolutionary computing approach
- An analysis on recombination in multi-objective evolutionary optimization
- Performance analysis of the \((1+1)\) evolutionary algorithm for the multiprocessor scheduling problem
- Time complexity analysis of evolutionary algorithms for 2-hop \((1,2)\)-minimum spanning tree problem
- On the analysis of the \((1+1)\) evolutionary algorithm for the maximum leaf spanning tree problem
- Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms
- Performance analysis of randomised search heuristics operating with a fixed budget
- Optimization methods for regularization-based ill-posed problems: a survey and a multi-objective framework
This page was built for publication: On the approximation ability of evolutionary optimization with application to minimum set cover
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q420829)
