Fixed-Parameter Evolutionary Algorithms and the Vertex Cover Problem
Fixed-Parameter Evolutionary Algorithms and the Vertex Cover Problem
复制标题
DOI：
10.1007/s00453-012-9660-4
复制
发表时间：
2009-07
期刊：
影响因子：
1.1
通讯作者：
Stefan Kratsch;F. Neumann
中科院分区：
文献类型：
--
作者：
Stefan Kratsch;F. Neumann
在本文中，我们考虑多目标进化算法的顶点覆盖问题的参数化复杂性的背景下。我们将我们的算法的运行时间与输入大小和最小解的成本相关联，并指出进化算法的搜索过程创建了类似于核化效果的部分解（即从参数化复杂性中进行特殊类型的预处理）。在此基础上，我们表明，进化算法有效地解决顶点覆盖问题，如果一个最小顶点覆盖的大小不是太大，即预期的运行时间是有界的O（f（OPT）nc），其中是一个常数和fa函数，只依赖于OPT.This表明，进化算法是随机固定参数的易于处理的顶点覆盖问题的算法。
In this paper, we consider multi-objective evolutionary algorithms for theVertex Coverproblem in the context of parameterized complexity. We relate the runtime of our algorithms to the input size and the cost of a minimum solution and point out that the search process of evolutionary algorithms creates partial solutions that are similar to the effect of a kernelization (i.e. a special type of preprocessing from parameterized complexity). Based on this, we show that evolutionary algorithms solve the vertex cover problem efficiently if the size of a minimum vertex cover is not too large, i.e. the expected runtime is bounded byO(f(OPT)nc), wherecis a constant andfa function that only depends on OPT. This shows that evolutionary algorithms are randomized fixed-parameter tractable algorithms for the vertex cover problem.