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

research-article

Revised analysis of the (1+1) ea for the minimum spanning tree problem

Author:

Carsten WittAuthors Info & Claims

GECCO '14: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation

Pages 509 - 516

https://doi.org/10.1145/2576768.2598237

Published: 12 July 2014 Publication History

Abstract

We revisit the classical analysis of the (1+1) EA for the minimum spanning tree problem in the case that nothing is known about the weights of the underlying graph. Here the original upper bound on the expected running time by Neumann and Wegener [Theor. Comput. Sci. 378(1), 32-40, 2007], which depends on the largest weight of the graph, is of no use. The best upper bound available before in this case is due to Reichel and Skutella [FOGA 2009, 21-28] and is of order O(m³ \log n), where m is the number of edges and n the number of vertices. Using an adaptive drift analysis, we show the improved bound O(m² (sqrt{c(G)} + \log n)), where c(G) is the circumference (length of the longest cycle) of the graph. This is only by an asymptotic factor of at most sqrt{n}/\log n away from the classical lower bound. Furthermore, an alternative fitness function leading to the bound O(m²\log n) is proposed, and limitations of the adaptive drift analysis are pointed out.

References

[1]

Anne Auger and Benjamin Doerr. Theory of Randomized Search Heuristics -- Foundations and Recent Developments. World Scientific Publishing, 2011.

Digital Library

[2]

Surender Baswana, Somenath Biswas, Benjamin Doerr, Tobias Friedrich, Piyush P. Kurur, and Frank Neumann. Computing single source shortest paths using single-objective fitness functions. In Proc.\ of FOGA '09, pages 59--66. ACM Press, 2009.

Digital Library

[3]

Süntje Böttcher, Benjamin Doerr, and Frank Neumann. Optimal fixed and adaptive mutation rates for the LeadingOnes problem. In Proc.\ of PPSN 2010, volume 6238 of Lecture Notes in Computer Science, pages 1--10. Springer, 2010.

Digital Library

[4]

Benjamin Doerr and Leslie Ann Goldberg. Adaptive drift analysis. Algorithmica, 65(1):224--250, 2013.

Digital Library

[5]

Benjamin Doerr, Daniel Johannsen, and Carola Winzen. Multiplicative drift analysis. Algorithmica, 64(4):673--697, 2012.

Digital Library

[6]

Benjamin Doerr and Sebastian Pohl. Run-time analysis of the (1

[7]

1) evolutionary algorithm optimizing linear functions over a finite alphabet. In Proc.\ of GECCO '12, pages 1317--1324. ACM Press, 2012.

Digital Library

[8]

Benjamin Doerr, Dirk Sudholt, and Carsten Witt. When do evolutionary algorithms optimize separable functions in parallel? In Proc.\ of FOGA '13, pages 51--64. ACM Press, 2013.

Digital Library

[9]

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

Digital Library

[10]

Ernst W. Mayr and C. Greg Plaxton. On the spanning trees of weighted graphs. Combinatorica, 12(4):433--447, 1992.

[11]

Frank Neumann and Ingo Wegener. Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theoretical Computer Science, 378(1):32--40, 2007.

Digital Library

[12]

Frank Neumann and Carsten Witt. Bioinspired Computation in Combinatorial Optimization -- Algorithms and Their Computational Complexity. Natural Computing Series. Springer, 2010.

Digital Library

[13]

Joachim Reichel and Martin Skutella. On the size of weights in randomized search heuristics. In Proc.\ of FOGA '09, pages 21--28. ACM Press, 2009.

Digital Library

[14]

Joachim Reichel and Martin Skutella. Evolutionary algorithms and matroid optimization problems. Algorithmica, 57(1):187--206, 2010.

Digital Library

[15]

Ingo Wegener. Simulated annealing beats metropolis in combinatorial optimization. In Proc.\ of ICALP '05, volume 3580 of Lecture Notes in Computer Science, pages 589--601. Springer, 2005.

Digital Library

[16]

Carsten Witt. Tight bounds on the optimization time of a randomized search heuristic on linear functions. Combinatorics, Probability and Computing, 22(2):294--318, 2013.

Cited By

Doerr BLi XHandl J(2024)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648402(800-829)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648402
Doerr BSilva SPaquete L(2023)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3595042(946-975)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3595042
Doerr BWagner M(2022)A gentle introduction to theory (for non-theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3533628(890-921)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3533628
Show More Cited By

Index Terms

Revised analysis of the (1+1) ea for the minimum spanning tree problem
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

A Tight Runtime Analysis for the $(μ + λ)$ EA
Abstract
Despite significant progress in the theory of evolutionary algorithms, the theoretical understanding of evolutionary algorithms which use non-trivial populations remains challenging and only few rigorous results exist. Already for the most basic ... $\frac{}{} \frac{}{} \frac{^{}^{}}{^{}}$ $^{}$ $\frac{}{}$ $\frac{}{}$
Approximation guarantees of evolutionary optimization on the minimum crossing spanning tree problem

The minimum crossing spanning tree (MCST) problem is to find a spanning tree in a given graph G and a family of subsets of vertices S such that the maximum number of edges crossing any set in S reaches minimum value. Evolutionary algorithms (EAs) have ...
A Tight Runtime Analysis of the (1+(λ, λ)) Genetic Algorithm on OneMax
GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

Understanding how crossover works is still one of the big challenges in evolutionary computation research, and making our understanding precise and proven by mathematical means might be an even bigger one. As one of few examples where crossover provably ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '14: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation

July 2014

1478 pages

ISBN:9781450326629

DOI:10.1145/2576768

Editor-in-chief:
Christian Igel
Ruhr University of Bochum, University of Copenhagen
,
General Chair:
Dirk V. Arnold
Dalhousie University

Copyright © 2014 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: 12 July 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '14

Sponsor:

SIGEVO

GECCO '14: Genetic and Evolutionary Computation Conference

July 12 - 16, 2014

BC, Vancouver, Canada

Acceptance Rates

GECCO '14 Paper Acceptance Rate 180 of 544 submissions, 33%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
185
Total Downloads

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

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Doerr BLi XHandl J(2024)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648402(800-829)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648402
Doerr BSilva SPaquete L(2023)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3595042(946-975)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3595042
Doerr BWagner M(2022)A gentle introduction to theory (for non-theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3533628(890-921)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3533628
Shi FYan XNeumann F(2022)Runtime Analysis of Simple Evolutionary Algorithms for the Chance-Constrained Makespan Scheduling ProblemParallel Problem Solving from Nature – PPSN XVII10.1007/978-3-031-14721-0_37(526-541)Online publication date: 15-Aug-2022
https://doi.org/10.1007/978-3-031-14721-0_37
Shnytkin MAntipov DKrawiec K(2021)The lower bounds on the runtime of the (1 + (λ, λ)) GA on the minimum spanning tree problemProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3449726.3463220(1986-1989)Online publication date: 7-Jul-2021
https://dl.acm.org/doi/10.1145/3449726.3463220
Doerr BKrawiec K(2021)A gentle introduction to theory (for non-theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3449726.3461406(369-398)Online publication date: 7-Jul-2021
https://dl.acm.org/doi/10.1145/3449726.3461406
Shi FNeumann FWang J(2021)Time complexity analysis of evolutionary algorithms for 2-hop (1,2)-minimum spanning tree problemTheoretical Computer Science10.1016/j.tcs.2021.09.003893(159-175)Online publication date: Nov-2021
https://doi.org/10.1016/j.tcs.2021.09.003
Rajabi AWitt C(2021)Stagnation Detection with Randomized Local SearchEvolutionary Computation in Combinatorial Optimization10.1007/978-3-030-72904-2_10(152-168)Online publication date: 27-Mar-2021
https://doi.org/10.1007/978-3-030-72904-2_10
Roostapour VBossek JNeumann FCoello Coello C(2020)Runtime analysis of evolutionary algorithms with biased mutation for the multi-objective minimum spanning tree problemProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3390168(551-559)Online publication date: 25-Jun-2020
https://dl.acm.org/doi/10.1145/3377930.3390168
Neumann FPourhassan MWitt C(2020)Improved Runtime Results for Simple Randomised Search Heuristics on Linear Functions with a Uniform ConstraintAlgorithmica10.1007/s00453-020-00779-3Online publication date: 4-Nov-2020
https://doi.org/10.1007/s00453-020-00779-3
Show More Cited By

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