research-article

On the size of weights in randomized search heuristics

Authors:

Joachim Reichel,

Martin SkutellaAuthors Info & Claims

FOGA '09: Proceedings of the tenth ACM SIGEVO workshop on Foundations of genetic algorithms

Pages 21 - 28

https://doi.org/10.1145/1527125.1527130

Published: 09 January 2009 Publication History

Get Access

Abstract

Runtime analyses of randomized search heuristics for combinatorial optimization problems often depend on the size of the largest weight. We consider replacing the given set of weights with smaller weights such that the behavior of the randomized search heuristic does not change. Upper bounds on the size of the new, equivalent weights allow us to obtain upper bounds on the expected runtime of such randomized search heuristics independent of the size of the actual weights. Furthermore we give lower bounds on the largest weights for worst-case instances. Finally we present some experimental results, including examples for worst-case instances.

References

[1]

N. Alon and V. H. Vu. Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hyper-graphs. Journal of Combinatorial Theory, Series A, 79(1):133--160, 1997.

Digital Library

Google Scholar

[2]

T. Friedrich, J. He, N. Hebbinghaus, F. Neumann, and C. Witt. Approximating covering problems by randomized search heuristics using multi-objective models. In Proc. of the 9th Genetic and Evolutionary Computation Conference (GECCO'07), London, pages 797--804, 2007

Digital Library

Google Scholar

[3]

J. Hastad. On the size of weights for threshold gates. SIAM Journal on Discrete Mathematics, 7(3):484--492, 1994.

Digital Library

Google Scholar

[4]

F. Neumann, J. Reichel, and M. Skutella. Computing minimum cuts by randomized search heuristics. In Proc. of the 10th Genetic and Evolutionary Computation Conference(GECCO'08), Atlanta, USA, pages 779--786, 2008.

Digital Library

Google Scholar

[5]

F. Neumann and I. Wegener. Minimum spanning trees made easier via multi-objective optimization. Natural Computing, 5(3):305--319, 2006.

Digital Library

Google Scholar

[6]

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

Digital Library

Google Scholar

[7]

J. Reichel and M. Skutella. Evolutionary algorithms and matroid optimization problems. In Proc. of the 9th Genetic and Evolutionary Computation Conference(GECCO'07), London, pages 947--954, 2007.

Digital Library

Google Scholar

[8]

I. Wegener. Towards a theory of randomized search heuristics. In Proc. of Mathematical Foundations of Com-puter Science (MFCS'03), Bratislava, Slovakia, pages 125--141, 2003.

Crossref

Google Scholar

[9]

I. Wegener. Randomized search heuristics as an alternative to exact optimization. In W. Lenski, editor, Logic versus Approximation, pages 138--149. 2004.

Google Scholar

Cited By

View all

Krejca MWitt CLi XHandl J(2024)A Flexible Evolutionary Algorithm with Dynamic Mutation Rate ArchiveProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654076(1578-1586)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654076
Bossek JSudholt D(2024)Runtime Analysis of Quality Diversity AlgorithmsAlgorithmica10.1007/s00453-024-01254-z86:10(3252-3283)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s00453-024-01254-z
Rajabi AWitt C(2024)Stagnation Detection in Highly Multimodal Fitness LandscapesAlgorithmica10.1007/s00453-024-01249-w86:9(2929-2958)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s00453-024-01249-w
Show More Cited By

Index Terms

On the size of weights in randomized search heuristics
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Fitness levels with tail bounds for the analysis of randomized search heuristics

The fitness-level method, also called the method of f-based partitions, is an intuitive and widely used technique for the running time analysis of randomized search heuristics. It was originally defined to prove upper and lower bounds on the expected ...
Theory of randomized search heuristics in combinatorial optimization
GECCO '11: Proceedings of the 13th annual conference companion on Genetic and evolutionary computation

The rigorous mathematical analysis of randomized search heuristics(RSHs) with respect to their expected runtime is a growing research area where many results have been obtained in recent years. This class of heuristics includes well-known approaches ...
Randomized heuristics for the Capacitated Clustering Problem

In this paper, we investigate the adaptation of the Greedy Randomized Adaptive Search Procedure (GRASP) and Iterated Greedy methodologies to the Capacitated Clustering Problem (CCP). In particular, we focus on the effect of the balance between ...

Comments

Information & Contributors

Information

Published In

FOGA '09: Proceedings of the tenth ACM SIGEVO workshop on Foundations of genetic algorithms

January 2009

204 pages

ISBN:9781605584140

DOI:10.1145/1527125

General Chairs:
Ivan Garibay
University of Central Florida
,
Thomas Jansen
Technische Universität Dortmund
,
R. Paul Wiegand
University of Central Florida
,
Annie S. Wu
University of Central Florida

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 ACM 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 January 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tag

randomized search heuristics

Qualifiers

Research-article

Conference

FOGA '09

Sponsor:

FOGA '09: Foundations of Genetic Algorithms X

January 9 - 11, 2009

Florida, Orlando, USA

Acceptance Rates

FOGA '09 Paper Acceptance Rate 18 of 30 submissions, 60%;

Overall Acceptance Rate 72 of 131 submissions, 55%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
156
Total Downloads

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

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Krejca MWitt CLi XHandl J(2024)A Flexible Evolutionary Algorithm with Dynamic Mutation Rate ArchiveProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654076(1578-1586)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654076
Bossek JSudholt D(2024)Runtime Analysis of Quality Diversity AlgorithmsAlgorithmica10.1007/s00453-024-01254-z86:10(3252-3283)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s00453-024-01254-z
Rajabi AWitt C(2024)Stagnation Detection in Highly Multimodal Fitness LandscapesAlgorithmica10.1007/s00453-024-01249-w86:9(2929-2958)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s00453-024-01249-w
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.003Online publication date: Sep-2021
https://doi.org/10.1016/j.tcs.2021.09.003
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
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
Neumann FPourhassan MWitt CAuger AStützle T(2019)Improved runtime results for simple randomised search heuristics on linear functions with a uniform constraintProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321722(1506-1514)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321722
Neumann FReichel JSkutella M(2018)Computing Minimum Cuts by Randomized Search HeuristicsAlgorithmica10.1007/s00453-009-9370-859:3(323-342)Online publication date: 31-Dec-2018
https://dl.acm.org/doi/10.1007/s00453-009-9370-8
Witt CArnold D(2014)Revised analysis of the (1+1) ea for the minimum spanning tree problemProceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation10.1145/2576768.2598237(509-516)Online publication date: 12-Jul-2014
https://dl.acm.org/doi/10.1145/2576768.2598237
Doerr BLengler JKötzing TWinzen CLanzi P(2011)Black-box complexities of combinatorial problemsProceedings of the 13th annual conference on Genetic and evolutionary computation10.1145/2001576.2001710(981-988)Online publication date: 12-Jul-2011
https://dl.acm.org/doi/10.1145/2001576.2001710
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.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Fitness levels with tail bounds for the analysis of randomized search heuristics

Theory of randomized search heuristics in combinatorial optimization

Randomized heuristics for the Capacitated Clustering Problem

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tag

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations