On the approximation ability of evolutionary optimization with application to minimum set cover

DOI10.1016/J.ARTINT.2012.01.001zbMATH Open1238.68152arXiv1011.4028OpenAlexW2148311277MaRDI QIDQ420829FDOQ420829

Authors: Zhi-Hua Zhou, Xin Yao, Yang Yu 

Publication date: 23 May 2012

Published in: Artificial Intelligence (Search for Journal in Brave)

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 $H_n$-approximation ratio, the asymptotic lower bound, for the unbounded set cover problem. We also find that SEIP efficiently achieves an $(H_k-frack-1/8k^9)$-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.

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

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

zbMATH Keywords

approximation algorithmevolutionary algorithmsapproximation ratio\(k\)-set covertime complexity analysis

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)

Cites Work

• A threshold of ln n for approximating set cover
• A Greedy Heuristic for the Set-Covering Problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximating the Unweighted ${k}$-Set Cover Problem: Greedy Meets Local Search
• Title not available (Why is that?)
• STACS 2005
• Greedy in Approximation Algorithms
• Algorithmic construction of sets for k -restrictions
• Title not available (Why is that?)
• Drift analysis and average time complexity of evolutionary algorithms
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Computing minimum cuts by randomized search heuristics
• The analysis of evolutionary algorithms on sorting and shortest paths problems
• Minimum spanning trees made easier via multi-objective optimization
• Title not available (Why is that?)
• A new approach to estimating the expected first hitting time of evolutionary algorithms
• Speeding up Approximation Algorithms for NP-Hard Spanning Forest Problems by Multi-objective Optimization
• A Tight Analysis of the Greedy Algorithm for Set Cover
• A Better-Than-Greedy Approximation Algorithm for the Minimum Set Cover Problem

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
• 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
• Performance analysis of the \((1+1)\) evolutionary algorithm for the multiprocessor scheduling 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)