  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.

Neural and Evolutionary Computing