On the Approximation Ability of Evolutionary Optimization with Application to Minimum Set Cover: Extended Abstract?
Abstract
Evolutionary algorithms (EAs) are a large family of heuristic optimization algorithms inspired by natural phenomena, and are often used in practice to obtain satis?cing 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 singleor multi-objective EA. We present general approximation results of SEIP, and speci?cally on the minimum set cover problem, we ?nd 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 dif?culty that limits the greedy algorithm.