More Web Proxy on the site http://driver.im/

research-article

Runtime analysis of randomized search heuristics for the dynamic weighted vertex cover problem

Authors:

Jianxin WangAuthors Info & Claims

GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 1515 - 1522

https://doi.org/10.1145/3205455.3205580

Published: 02 July 2018 Publication History

Abstract

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 performances of the two 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 formulation of the problem and study the expected runtimes that the two 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. Our results show that both algorithms can recompute 2-approximate solutions for the studied dynamic changes efficiently

References

[1]

A. Auger and B. Doerr. Theory of Randomized Search Heuristics: Foundations and Recent Developments. World Scientific Publishing Co., Inc., 2011.

Digital Library

[2]

R. Bar-Yehuda and S. Even. A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms, 2(2):198--203, 1981.

[3]

H.-G. Beyer and H.-P. Schwefel. Evolution strategies-a comprehensive introduction. Natural computing, 1(1):3--52, 2002.

Digital Library

[4]

B. Doerr, D. Johannsen, and C. Winzen. Multiplicative drift analysis. Algorithmica, 64(4):673--697, 2012.

Digital Library

[5]

D.-Z. Du, K.-I. Ko, and X. Hu. Design and analysis of approximation algorithms, volume 62. Springer Science & Business Media, 2011.

Digital Library

[6]

T. Friedrich, J. He, N. Hebbinghaus, F. Neumann, and C. Witt. Approximating covering problems by randomized search heuristics using multi-objective models. Evolutionary Computation, 18(4):617--633, 2010.

Digital Library

[7]

T. Friedrich and F. Neumann. What's hot in evolutionary computation. In AAAI, pages 5064--5066, 2017.

[8]

N. Hansen, S. D. Müller, and P. Koumoutsakos. Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (cma-es). Evolutionary computation, 11(1): 1--18, 2003.

Digital Library

[9]

D. S. Hochbaum. Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Applied Mathematics, 6(3):243 -- 254, 1983.

[10]

T. Jansen. Analyzing Evolutionary Algorithms - The Computer Science Perspective. Natural Computing Series. Springer, 2013.

Digital Library

[11]

T.Jansen, P. S. Oliveto, and C. Zarges. Approximating vertex cover using edge-based representations. In Proceedings of the twelfth workshop on Foundations of genetic algorithms XII, pages 87--96. ACM, 2013.

Digital Library

[12]

S. Khot. On the power of unique 2-prover 1-round games. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 767--775. ACM, 2002.

Digital Library

[13]

S. Khot and O. Regev. Vertex cover might be hard to approximate to within 2-ε. Journal of Computer and System Sciences, 74(3):335--349, 2008.

Digital Library

[14]

T. Kötzing, A. Lissovoi, and C. Witt. (1+ 1) ea on generalized dynamic onemax. In Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII, pages 40--51. ACM, 2015.

Digital Library

[15]

S. Kratsch and F. Neumann. Fixed-parameter evolutionary algorithms and the vertex cover problem. Algorithmica, 65(4):754--771, 2013.

Digital Library

[16]

F. Neumann and C. Witt. Bioinspired Computation in Combinatorial Optimization:Algorithms and Their Computational Complexity. Springer-Verlag New York, Inc., New York, NY, USA, 1st edition, 2010.

Digital Library

[17]

F. Neumann and C. Witt. On the runtime of randomized local search and simple evolutionary algorithms for dynamic makespan scheduling. In IJCAI, pages 3742--3748, 2015.

Digital Library

[18]

M. Pourhassan, T. Friedrich, and F. Neumann. On the use of the dual formulation for minimum weighted vertex cover in evolutionary algorithms. In Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, pages 37--44. ACM, 2017.

Digital Library

[19]

M. Pourhassan, W. Gao, and F. Neumann. Maintaining 2-approximations for the dynamic vertex cover problem using evolutionary algorithms. In Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, pages 903--910. ACM, 2015.

Digital Library

[20]

M. Pourhassan, F. Shi, and F. Neumann. Parameterized analysis of multi-objective evolutionary algorithms and the weighted vertex cover problem. In Proceedings of the 14th International Conference on Parallel Problem Solving from Nature (PPSN XIV), pages 729--739. Springer, 2016.

[21]

F. Shi, M. Schirneck, T. Friedrich, T. Kötzing, and F. Neumann. Reoptimization times of evolutionary algorithms on linear functions under dynamic uniform constraints. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 1407--1414. ACM, 2017.

Digital Library

[22]

V. V. Vazirani. Approximation algorithms. Springer Science & Business Media, 2013.

Digital Library

Cited By

Yan XNeumann ANeumann F(2024)Sliding Window Bi-objective Evolutionary Algorithms for Optimizing Chance-Constrained Monotone Submodular FunctionsParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70055-2_2(20-35)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70055-2_2
Shi FNeumann FWang J(2021)Runtime Performances of Randomized Search Heuristics for the Dynamic Weighted Vertex Cover ProblemAlgorithmica10.1007/s00453-019-00662-w83:4(906-939)Online publication date: 1-Apr-2021
https://dl.acm.org/doi/10.1007/s00453-019-00662-w
Bossek JNeumann FPeng PSudholt DCoello Coello C(2020)More effective randomized search heuristics for graph coloring through dynamic optimizationProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3390174(1277-1285)Online publication date: 25-Jun-2020
https://dl.acm.org/doi/10.1145/3377930.3390174
Show More Cited By

Index Terms

Runtime analysis of randomized search heuristics for the dynamic weighted vertex cover problem

Recommendations

Runtime Performances of Randomized Search Heuristics for the Dynamic Weighted Vertex Cover Problem
Abstract
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 ...
The impact of random initialization on the runtime of randomized search heuristics
GECCO '14: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation

It has often been observed that the expected runtime of an evolutionary algorithm with random initialization does not deviate much from the expected runtime when starting in an initial solution of average fitness. Having this information a priori would ...
The Impact of Random Initialization on the Runtime of Randomized Search Heuristics

Analyzing the runtime of a Randomized Search Heuristic (RSH) by theoretical means often turns out to be rather tricky even for simple optimization problems. The main reason lies in the randomized nature of these algorithms. Both the optimization ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference

July 2018

1578 pages

ISBN:9781450356183

DOI:10.1145/3205455

Editor:
Hernan Aguirre
Shinshu University
,
General Chair:
Keiki Takadama
The University of Electro-Communications

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 July 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Australian Research Council
National Natural Science Foundation of China

Conference

GECCO '18

Sponsor:

SIGEVO

GECCO '18: Genetic and Evolutionary Computation Conference

July 15 - 19, 2018

Kyoto, Japan

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
89
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yan XNeumann ANeumann F(2024)Sliding Window Bi-objective Evolutionary Algorithms for Optimizing Chance-Constrained Monotone Submodular FunctionsParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70055-2_2(20-35)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70055-2_2
Shi FNeumann FWang J(2021)Runtime Performances of Randomized Search Heuristics for the Dynamic Weighted Vertex Cover ProblemAlgorithmica10.1007/s00453-019-00662-w83:4(906-939)Online publication date: 1-Apr-2021
https://dl.acm.org/doi/10.1007/s00453-019-00662-w
Bossek JNeumann FPeng PSudholt DCoello Coello C(2020)More effective randomized search heuristics for graph coloring through dynamic optimizationProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3390174(1277-1285)Online publication date: 25-Jun-2020
https://dl.acm.org/doi/10.1145/3377930.3390174
Bossek JNeumann FPeng PSudholt DAuger AStützle T(2019)Runtime analysis of randomized search heuristics for dynamic graph coloringProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321792(1443-1451)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321792
Doerr BDoerr CNeumann FAuger AStützle T(2019)Fast re-optimization via structural diversityProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321731(233-241)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321731
Shi FNeumann FWang JFriedrich TDoerr CArnold D(2019)Runtime analysis of evolutionary algorithms for the depth restricted (1,2)-minimum spanning tree problemProceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3299904.3340314(133-146)Online publication date: 27-Aug-2019
https://dl.acm.org/doi/10.1145/3299904.3340314

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents