Runtime Performances of Randomized Search Heuristics for the Dynamic Weighted Vertex Cover Problem
Runtime Performances of Randomized Search Heuristics for the Dynamic Weighted Vertex Cover Problem
复制标题
动态加权顶点覆盖问题的随机搜索启发式运行时性能
DOI：
10.1007/s00453-019-00662-w
复制
发表时间：
2020-01
期刊：
影响因子：
--
通讯作者：
Jianxin Wang
中科院分区：
文献类型：
--
作者：
Feng Shi;Frank Neumann;Jianxin Wang
随机搜索算法，如进化算法，经常应用于动态组合优化问题。在本文中，我们提出了一个动态模型的经典加权顶点覆盖问题，并分析了运行时性能的研究很好的算法随机局部搜索和（1 + 1）EA适应它，有助于理论理解进化计算的动态变化的问题。在我们的调查中，我们使用基于边的表示的对偶形式的线性规划制定的问题和研究预期的运行时间，适应算法需要保持2-近似的解决方案时，给定的加权图修改边编辑或权重编辑操作。考虑到顶点上的权值相对于图的大小可能是指数级的，引入了步长自适应策略，使用或不使用1/5规则来控制步长的增加/减少速率。结果表明，本文提出的四种算法中有三种算法可以对多项式期望运行时间的动态变化重新计算2-近似解，但1/5规则的（1 + 1）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.
登录
查看更多内容
DOI：
10.1007/978-0-387-30162-4_28
发表时间：
2021-08
期刊：
Proceedings of the 1997 International Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN'97)
影响因子：
--
作者：
通讯作者：
--
DOI：
10.1145/2464576.2466738
发表时间：
2010-11
期刊：
Proceedings of the 15th annual conference companion on Genetic and evolutionary computation
影响因子：
--
作者：
F. Neumann;C. Witt
通讯作者：
F. Neumann;C. Witt
DOI：
--
发表时间：
2015-04
期刊：
--
影响因子：
--
作者：
F. Neumann;C. Witt
通讯作者：
F. Neumann;C. Witt
影响因子：
1.1
作者：
Stefan Kratsch;F. Neumann
通讯作者：
Stefan Kratsch;F. Neumann
DOI：
10.1609/aaai.v31i1.10639
发表时间：
2017-02
期刊：
--
影响因子：
--
作者：
T. Friedrich;F. Neumann
通讯作者：
T. Friedrich;F. Neumann