论文标题
进化仍然好：对一般覆盖问题进化算法的理论分析
Evolution is Still Good: Theoretical Analysis of Evolutionary Algorithms on General Cover Problems
论文作者
论文摘要
近年来，有关进化算法的理论研究已经大力发展。许多这样的算法在运行时间和近似比都具有理论保证。一些近似机制似乎固有地嵌入了许多进化算法中。在本文中，我们通过提出通用简单多目标进化算法（GSEMO）的统一分析框架来确定这种关系，并将其应用于最小重量的一般覆盖问题。对于广泛的问题（包括次数的最小覆盖问题，其中的最小覆盖函数是实现的，以及潜在函数无屈服的最小连接的主导设置问题），GSEMO在预期的多项式时间内渐近地收益均匀地近似近似值。
Theoretical studies on evolutionary algorithms have developed vigorously in recent years. Many such algorithms have theoretical guarantees in both running time and approximation ratio. Some approximation mechanism seems to be inherently embedded in many evolutionary algorithms. In this paper, we identify such a relation by proposing a unified analysis framework for a generalized simple multi-objective evolutionary algorithm (GSEMO), and apply it on a minimum weight general cover problem. For a wide range of problems (including the the minimum submodular cover problem in which the submodular function is real-valued, and the minimum connected dominating set problem for which the potential function is non-submodular), GSEMO yields asymptotically tight approximation ratios in expected polynomial time.
