Friedrich Tobias, He Jun, Hebbinghaus Nils, Neumann Frank, Witt Carsten
Max-Planck-Institut für Informatik, Saarbrücken, Germany.
Evol Comput. 2009 Spring;17(1):3-19. doi: 10.1162/evco.2009.17.1.3.
Hybrid methods are very popular for solving problems from combinatorial optimization. In contrast, the theoretical understanding of the interplay of different optimization methods is rare. In this paper, we make a first step into the rigorous analysis of such combinations for combinatorial optimization problems. The subject of our analyses is the vertex cover problem for which several approximation algorithms have been proposed. We point out specific instances where solutions can (or cannot) be improved by the search process of a simple evolutionary algorithm in expected polynomial time.
混合方法在解决组合优化问题方面非常流行。相比之下，对不同优化方法之间相互作用的理论理解却很少见。在本文中，我们朝着对组合优化问题的此类组合进行严格分析迈出了第一步。我们分析的主题是顶点覆盖问题，针对该问题已经提出了几种近似算法。我们指出了在预期多项式时间内，简单进化算法的搜索过程可以（或不能）改进解的特定实例。
