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
- A Better-Than-Greedy Approximation Algorithm for the Minimum Set Cover Problem
- A Greedy Heuristic for the Set-Covering Problem
- A new approach to estimating the expected first hitting time of evolutionary algorithms
- A threshold of ln n for approximating set cover
- A Tight Analysis of the Greedy Algorithm for 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
- 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?)
- Minimum spanning trees made easier via multi-objective optimization
- Speeding up Approximation Algorithms for NP-Hard Spanning Forest Problems by Multi-objective Optimization
- STACS 2005
- The analysis of evolutionary algorithms on sorting and shortest paths problems
Cited in
(13)- Optimization methods for regularization-based ill-posed problems: a survey and a multi-objective framework
- Time complexity analysis of evolutionary algorithms for 2-hop \((1,2)\)-minimum spanning tree problem
- Performance analysis of randomised search heuristics operating with a fixed budget
- Optimizing group learning: an evolutionary computing approach
- Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms
- A simulated evolution-based solution of the cover problem
- On the analysis of the \((1+1)\) evolutionary algorithm for the maximum leaf spanning tree problem
- An analysis on recombination in multi-objective evolutionary optimization
- Performance analysis of the \((1+1)\) evolutionary algorithm for the multiprocessor scheduling problem
- On the Use of the Dual Formulation for Minimum Weighted Vertex Cover in Evolutionary Algorithms
- Lower bounds for comparison based evolution strategies using VC-dimension and sign patterns
- Solving overlapping coalition structure generation in task-based settings
- Runtime performance of evolutionary algorithms for the chance-constrained makespan scheduling problem
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)
