论文标题
动态加权顶点覆盖问题的随机搜索启发式方法的运行时性能
Runtime Performances of Randomized Search Heuristics for the Dynamic Weighted Vertex Cover Problem
论文作者
论文摘要
随机搜索启发式方法（例如进化算法）经常应用于动态组合优化问题。在本文中，我们介绍了经典加权顶点覆盖问题的动态模型，并分析了经过良好研究的算法随机局部搜索的运行时性能，并且（1+1）EA适应了它，以促进对进化计算的理论理解，以解决动态变化的问题。在我们的研究中，我们使用基于边缘的表示基于线性编程公式的双重形式来解决该问题，并研究适应算法所需的预期运行时，以维持2个适应性的解决方案，当给定的加权图通过边缘编辑或权重的操作修改时。考虑到顶点上的权重相对于图形的大小，阶跃大小适应策略的成熟程度可能是指数性的，有或没有使用1/5-的规则，该规则可用于控制步长大小的增加/降低速率。我们的结果表明，本文中介绍的四种算法中有三种可以重新计算多项式预期运行时研究的动态变化的2个同一解决方案，但是（1+1）EA具有1/5--第5条规则的EA需要伪多项式预期的预期运行时。
Randomized search heuristics such as evolutionary algorithms are frequently applied to dynamic combinatorial optimization problems. Within this paper, we present a dynamic model of the classic Weighted Vertex Cover problem and analyze the runtime performances of the well-studied algorithms Randomized Local Search and (1+1) EA adapted to it, to contribute to the theoretical understanding of evolutionary computing for problems with dynamic changes. In our investigations, we use an edge-based representation based on the dual form of the Linear Programming formulation for the problem and study the expected runtime that the adapted algorithms require to maintain a 2-approximate solution when the given weighted graph is modified by an edge-editing or weight-editing operation. Considering the weights on the vertices may be exponentially large with respect to the size of the graph, the step size adaption strategy is incorporated, with or without the 1/5-th rule that is employed to control the increasing/decreasing rate of the step size. Our results show that three of the four algorithms presented in the paper can recompute 2-approximate solutions for the studied dynamic changes in polynomial expected runtime, but the (1+1) EA with 1/5-th Rule requires pseudo-polynomial expected runtime.
