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

Yang YU, Xin YAO, Zhi-Hua ZHOU

Research output: Book Chapters | Papers in Conference ProceedingsConference (Extended Abstracts)peer-review

7 Citations (Scopus)


Evolutionary algorithms (EAs) are a large family of heuristic optimization algorithms inspired by natural phenomena, and are often used in practice to obtain satisficing instead of optimal solutions. In this work, we investigate a largely underexplored issue: the approximation performance of EAs in terms of how close the obtained solution 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 present general approximation results of SEIP, and specifically on the minimum set cover problem, we find that SEIP achieves the currently bestachievable approximation ratio. Moreover, on an instance class of the k-set cover problem, we disclose how SEIP can overcome the difficulty that limits the greedy algorithm.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Third International Joint Conference on Artificial Intelligence Beijing, China, 3–9 August 2013
EditorsFrancesca ROSSI
Place of PublicationCalifornia
PublisherAAAI press
Number of pages5
ISBN (Print)9781577356332
Publication statusPublished - 2013
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).


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