On the Approximation Ability of Evolutionary Optimization with Application to Minimum Set Cover: Extended Abstract

Yu, Yang; Yao, Xin; Zhou, Zhi-Hua

On the Approximation Ability of Evolutionary Optimization with Application to Minimum Set Cover: Extended Abstract

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 3190-3193.

Abstract

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 best-achievable 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.

Yang Yu, Xin Yao, and Zhi-Hua Zhou. 2013. On the Approximation Ability of Evolutionary Optimization with Application to Minimum Set Cover: Extended Abstract. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13. IJCAI, 3190–3193. https://ijcai.org/proceedings/2013/484

@inproceedings{ijcai2013p484,
  title     = {On the Approximation Ability of Evolutionary Optimization with Application to Minimum Set Cover: Extended Abstract},
  author    = {Yu, Yang and Yao, Xin and Zhou, Zhi-Hua},
  booktitle = {Proceedings of the Twenty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-13}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Francesca Rossi},
  pages     = {3190--3193},
  year      = {2013},
  month     = {8},
  url       = {https://ijcai.org/proceedings/2013/484},
}

TY  - CPAPER
TI  - On the Approximation Ability of Evolutionary Optimization with Application to Minimum Set Cover: Extended Abstract
AU  - Yu, Yang
AU  - Yao, Xin
AU  - Zhou, Zhi-Hua
T2  - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2013
SP  - 3190
EP  - 3193
UR  - https://ijcai.org/proceedings/2013/484
ER  -