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

Yang YU, Xin YAO, Zhi-Hua ZHOU

Research output: Journal PublicationsJournal Article (refereed)peer-review

62 Citations (Scopus)

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 Hn-approximation ratio, the asymptotic lower bound, for the unbounded set cover problem. We also find that SEIP efficiently achieves an ( Hk-k-18 k9)- 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. © 2012 Elsevier B.V. All rights reserved.
Original languageEnglish
Pages (from-to)20-33
Number of pages14
JournalArtificial Intelligence
Volume180-181
Early online date10 Jan 2012
DOIs
Publication statusPublished - Apr 2012
Externally publishedYes

Bibliographical note

We thank Dr. Per Kristian Lehre and Dr. Yitong Yin for helpful discussions. This work was partly supported by the National Fundamental Research Program of China (2010CB327903), the National Science Foundation of China (61073097, 61021062), EPSRC (UK) (EP/I010297/1), and an EU FP7-PEOPLE-2009-IRSES project under Nature Inspired Computation and its Applications (NICaiA) (247619).

Keywords

  • Approximation algorithm
  • Approximation ratio
  • Evolutionary algorithms
  • k-Set cover
  • Time complexity analysis

Fingerprint

Dive into the research topics of 'On the approximation ability of evolutionary optimization with application to minimum set cover'. Together they form a unique fingerprint.

Cite this