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

research-article

Reducing the arity in unbiased black-box complexity

Authors:

Benjamin Doerr,

Carola WinzenAuthors Info & Claims

GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation

Pages 1309 - 1316

https://doi.org/10.1145/2330163.2330345

Published: 07 July 2012 Publication History

Abstract

We show that for all 1 < k d log n the k-ary unbiased black-box complexity of the n-dimensional OneMax function class is O(n/k). This indicates that the power of higher arity operators is much stronger than what the previous O(n/log k) bound by Doerr et al. (Faster black-box algorithms through higher arity operators, Proc. of FOGA 2011, pp. 163--172, ACM, 2011) suggests.

The key to this result is an encoding strategy, which might be of independent interest. We show that, using k-ary unbiased variation operators only, we may simulate an unrestricted memory of size O(2^k) bits.

References

[1]

G. Anil and R. P. Wiegand. Black-box search by elimination of fitness functions. In Proc. of the 10th ACM Workshop on Foundations of Genetic Algorithms (FOGA'09), pages 67--78. ACM, 2009.

Digital Library

[2]

V. Chvátal. Mastermind. Combinatorica, 3:325--329, 1983.

[3]

B. Doerr, E. Happ, and C. Klein. Crossover can provably be useful in evolutionary computation. In Proc. of the 10th Annual Genetic and Evolutionary Computation Conference (GECCO'08), pages 539--546. ACM, 2008.

Digital Library

[4]

B. Doerr, D. Johannsen, T. Kötzing, P. K. Lehre, M. Wagner, and C. Winzen. Faster black-box algorithms through higher arity operators. In Proc. of the 11th ACM Workshop on Foundations of Genetic Algorithms (FOGA'11), pages 163--172. ACM, 2011.

Digital Library

[5]

B. Doerr, D. Johannsen, T. Kötzing, F. Neumann, and M. Theile. More effective crossover operators for the all-pairs shortest path problem. In Proc. of the 11th International Conference on Parallel Problem Solving from Nature (PPSN'10), pages 184--193. Springer, 2010.

Digital Library

[6]

B. Doerr, D. Johannsen, and C. Winzen. Drift analysis and linear functions revisited. In Proc. of the 2010 IEEE Congress on Evolutionary Computation (CEC'10), pages 1967--1974. IEEE, 2010.

[7]

B. Doerr, T. Kötzing, J. Lengler, and C. Winzen. Black-box complexities of combinatorial problems. In Proc. of the 13th Annual Genetic and Evolutionary Computation Conference (GECCO'11), pages 981--988. ACM, 2011.

Digital Library

[8]

B. Doerr and M. Theile. Improved analysis methods for crossover-based algorithms. In Proc. of the 11th Annual Genetic and Evolutionary Computation Conference (GECCO'09), pages 247--254. ACM, 2009.

Digital Library

[9]

B. Doerr and C. Winzen. Towards a complexity theory of randomized search heuristics: Ranking-based black-box complexity. In Proc. of the 6th International Computer Science Symposium in Russia (CSR'11), pages 15--28. Springer, 2011.

Digital Library

[10]

B. Doerr and C. Winzen. Breaking the O(n Bog n) barrier of Leading-Ones. In Proc. of Artificial Evolution (EA'11). Springer, 2012. To appear.

Digital Library

[11]

B. Doerr and C. Winzen. Playing mastermind with constant-size memory. In Proc. of the Symposium on Theoretical Aspects of Computer Science (STACS'12), pages 441--452. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2012.

[12]

S. Droste, T. Jansen, and I. Wegener. Upper and lower bounds for randomized search heuristics in black-box optimization. Theory of Computing Systems, 39:525--544, 2006.

Digital Library

[13]

P. Erdos and A. Rényi. On two problems of information theory. Magyar Tud. Akad. Mat. Kutató Int. Közl., 8:229--243, 1963.

[14]

T. Jansen and I. Wegener. The analysis of evolutionary algorithms -- A proof that crossover really can help. Algorithmica, 34:47--66, 2002.

Digital Library

[15]

T. Kötzing, D. Sudholt, and M. Theile. How crossover helps in pseudo-Boolean optimization. In Proc. of the 13th Annual Genetic and Evolutionary Computation Conference (GECCO'11), pages 989--996. ACM, 2011.

Digital Library

[16]

P. K. Lehre and C. Witt. Black-box search by unbiased variation. In Proc. of the 12th Annual Genetic and Evolutionary Computation Conference (GECCO'10), pages 1441--1448. ACM, 2010.

Digital Library

[17]

H. Mühlenbein. How genetic algorithms really work: Mutation and hillclimbing. In Proc. of the 2nd International Conference on Parallel Problem Solving from Nature (PPSN'92), pages 15--26. Elsevier, 1992.

[18]

J. Rowe and M. Vose. Unbiased black box search algorithms. In Proc. of the 13th Annual Genetic and Evolutionary Computation Conference (GECCO'11), pages 2035--2042. ACM, 2011.

Digital Library

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

Reducing the arity in unbiased black-box complexity
1. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Faster black-box algorithms through higher arity operators
FOGA '11: Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms

We extend the work of Lehre and Witt (GECCO 2010) on the unbiased black-box model by considering higher arity variation operators. In particular, we show that already for binary operators the black-box complexity of LeadingOnes drops from Θ(n²) for ...
Too fast unbiased black-box algorithms
GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

Unbiased black-box complexity was recently introduced as a refined complexity model for randomized search heuristics (Lehre and Witt, GECCO 2010). For several problems, this notion avoids the unrealistically low complexity results given by the classical ...
Unbiased black-box complexities of jump functions

We analyze the unbiased black-box complexities of jump functions with small, medium, and large sizes of the fitness plateau surrounding the optimal solution. Among other results, we show that when the jump size is <inline-formula><inline-graphic xlink="...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation

July 2012

1396 pages

ISBN:9781450311779

DOI:10.1145/2330163

Editor:
Terence Soule
University of Idaho, USA
,
General Chair:
Jason H. Moore
Dartmouth College, USA

Copyright © 2012 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 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]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 July 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '12

Sponsor:

SIGEVO

GECCO '12: Genetic and Evolutionary Computation Conference

July 7 - 11, 2012

Pennsylvania, Philadelphia, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
92
Total Downloads

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

Reflects downloads up to 15 Jan 2025

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
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
Doerr BCoello Coello C(2020)A gentle introduction to theory (for non-theoreticians)Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion10.1145/3377929.3389889(373-403)Online publication date: 8-Jul-2020
https://dl.acm.org/doi/10.1145/3377929.3389889
Doerr BAuger AStützle T(2019)Theory for non-theoreticiansProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3319619.3323373(523-549)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3319619.3323373
Doerr BTakadama K(2018)Theory for non-theoreticiansProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3207889(389-414)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3205651.3207889
Bulanova NBuzdalov MTakadama K(2018)Better fixed-arity unbiased black-box algorithmsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3205762(322-323)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3205651.3205762
Doerr BDoerr CArnold D(2014)Black-box complexityProceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation10.1145/2598394.2605352(623-646)Online publication date: 12-Jul-2014
https://dl.acm.org/doi/10.1145/2598394.2605352
Doerr BDoerr CKötzing TArnold D(2014)Unbiased black-box complexities of jump functionsProceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation10.1145/2576768.2598341(769-776)Online publication date: 12-Jul-2014
https://dl.acm.org/doi/10.1145/2576768.2598341
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