Runtime Performances of Randomized Search Heuristics for the Dynamic Weighted Vertex Cover Problem
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationEvolutionary AlgorithmsSimilar Papers 제목 키워드 기반
Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces
Randomized search heuristics have been applied successfully to a plethora of problems. This success is complemented by a large body of theoretical results. Unfortunately, the vast majority of these results regard problem…
Evolutionary AlgorithmsExponential Upper Bounds for the Runtime of Randomized Search Heuristics
We argue that proven exponential upper bounds on runtimes, an established area in classic algorithms, are interesting also in heuristic search and we prove several such results. We show that any of the algorithms randomi…
Heuristic SearchMore Effective Randomized Search Heuristics for Graph Coloring Through Dynamic Optimization
Dynamic optimization problems have gained significant attention in evolutionary computation as evolutionary algorithms (EAs) can easily adapt to changing environments. We show that EAs can solve the graph coloring proble…
Evolutionary AlgorithmsRuntime Analysis of the Compact Genetic Algorithm on the LeadingOnes Benchmark
The compact genetic algorithm (cGA) is one of the simplest estimation-of-distribution algorithms (EDAs). Next to the univariate marginal distribution algorithm (UMDA) -- another simple EDA -- , the cGA has been subject t…
Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem
We contribute to the theoretical understanding of randomized search heuristics for dynamic problems. We consider the classical vertex coloring problem on graphs and investigate the dynamic setting where edges are added t…