research-article

Solving Problems with Unknown Solution Length at (Almost) No Extra Cost

Authors:

Benjamin Doerr,

Carola Doerr,

Timo KötzingAuthors Info & Claims

GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

Pages 831 - 838

https://doi.org/10.1145/2739480.2754681

Published: 11 July 2015 Publication History

Get Access

Abstract

Most research in the theory of evolutionary computation assumes that the problem at hand has a fixed problem size. This assumption does not always apply to real-world optimization challenges, where the length of an optimal solution may be unknown a priori. Following up on previous work of Cathabard, Lehre, and Yao [FOGA 2011] we analyze variants of the (1+1) evolutionary algorithm for problems with unknown solution length. For their setting, in which the solution length is sampled from a geometric distribution, we provide mutation rates that yield an expected optimization time that is of the same order as that of the (1+1) EA knowing the solution length.

We then show that almost the same run times can be achieved even if no a priori information on the solution length is available.

Finally, we provide mutation rates suitable for settings in which neither the solution length nor the positions of the relevant bits are known. Again we obtain almost optimal run times for the OneMax and LeadingOnes test functions, thus solving an open problem from Cathabard et al.

References

[1]

A. Auger and B. Doerr. Theory of Randomized Search Heuristics. World Scientific, 2011.

Digital Library

Google Scholar

[2]

L. Bianchi, M. Dorigo, L. Gambardella, and W. Gutjahr. A Survey on Metaheuristics for Stochastic Combinatorial optimization. Natural Computing, 8:239--287, 2009.

Digital Library

Google Scholar

[3]

S. Böttcher, B. Doerr, and F. Neumann. Optimal fixed and adaptive mutation rates for the LeadingOnes problem. In Proc. of the 11th International Conference on Parallel Problem Solving from Nature (PPSN'10), pages 1--10. Springer, 2010.

Digital Library

Google Scholar

[4]

S. Cathabard, P. K. Lehre, and X. Yao. Non-uniform mutation rates for problems with unknown solution lengths. In Proc. of the 11th ACM Workshop on Foundations of Genetic Algorithms (FOGA'11), pages 173--180. ACM, 2011.

Digital Library

Google Scholar

[5]

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

Digital Library

Google Scholar

[6]

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

Digital Library

Google Scholar

[7]

Y. Jin and J. Branke. Evolutionary Optimization in Uncertain Environments--A Survey. IEEE Transactions on Evolutionary Computation, 9:303--317, 2005.

Digital Library

Google Scholar

[8]

V. Ladret. Asymptotic hitting time for a simple evolutionary model of protein folding. Journal of Applied Probability, 42:39--51, 2005.

Crossref

Google Scholar

[9]

F. Neumann and C. Witt. Bioinspired Computation in Combinatorial Optimization -- Algorithms and Their Computational Complexity. Springer, 2010.

Digital Library

Google Scholar

[10]

D. Sudholt. A new method for lower bounds on the running time of evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 17:418--435, 2013.

Digital Library

Google Scholar

[11]

C. Witt. Tight bounds on the optimization time of a randomized search heuristic on linear functions. Combinatorics, Probability & Computing, 22:294--318, 2013.

Crossref

Google Scholar

Cited By

View all

Gadea Harder JKötzing TLi XRadhakrishnan ARuff JLi XHandl J(2024)Run Time Bounds for Integer-Valued OneMax FunctionsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654091(1569-1577)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654091
Reinitz JVakulenko SGrigoriev DWeber A(2019)Adaptation, fitness landscape learning and fast evolutionF1000Research10.12688/f1000research.18575.28(358)Online publication date: 13-Sep-2019
https://doi.org/10.12688/f1000research.18575.2
Reinitz JVakulenko SGrigoriev DWeber A(2019)Adaptation, fitness landscape learning and fast evolutionF1000Research10.12688/f1000research.18575.18(358)Online publication date: 1-Apr-2019
https://doi.org/10.12688/f1000research.18575.1
Show More Cited By

Index Terms

Solving Problems with Unknown Solution Length at (Almost) No Extra Cost
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Unknown solution length problems with no asymptotically optimal run time
GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference

We revisit the problem of optimizing a fitness function of unknown dimension; that is, we face a function defined over bit-strings of large length N, but only n ≪ N of them have an influence on the fitness. Neither the position of these relevant bits ...
Solving Problems with Unknown Solution Length at Almost No Extra Cost

Following up on previous work of Cathabard et al. (in: Proceedings of foundations of genetic algorithms (FOGA'11), ACM, 2011) we analyze variants of the (1 + 1) evolutionary algorithm (EA) for problems with unknown solution length. For their setting, in ...
Unbiased black-box complexities of jump functions: how to cross large plateaus
GECCO '14: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation

We analyze the unbiased black-box complexity of jump functions with large jump sizes. Among other results, we show that when the jump size is (1/2 - epsilon)n, that is, only a small constant fraction of the fitness values is visible, then the unbiased ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

July 2015

1496 pages

ISBN:9781450334723

DOI:10.1145/2739480

Editor:
Sara Silva
Universidade de Lisboa, Portugal
,
General Chair:
Anna I. Esparcia-Alcázar
Universitat Politècnica de València, Spain

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 July 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Fondation Mathmatique Jacques Hadamard

Conference

GECCO '15

Sponsor:

SIGEVO

GECCO '15: Genetic and Evolutionary Computation Conference

July 11 - 15, 2015

Madrid, Spain

Acceptance Rates

GECCO '15 Paper Acceptance Rate 182 of 505 submissions, 36%;

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

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
89
Total Downloads

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

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gadea Harder JKötzing TLi XRadhakrishnan ARuff JLi XHandl J(2024)Run Time Bounds for Integer-Valued OneMax FunctionsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654091(1569-1577)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654091
Reinitz JVakulenko SGrigoriev DWeber A(2019)Adaptation, fitness landscape learning and fast evolutionF1000Research10.12688/f1000research.18575.28(358)Online publication date: 13-Sep-2019
https://doi.org/10.12688/f1000research.18575.2
Reinitz JVakulenko SGrigoriev DWeber A(2019)Adaptation, fitness landscape learning and fast evolutionF1000Research10.12688/f1000research.18575.18(358)Online publication date: 1-Apr-2019
https://doi.org/10.12688/f1000research.18575.1
Doerr BGieβen CWitt CYang J(2019)The ($$1+\lambda $$1+ý) Evolutionary Algorithm with Self-Adjusting Mutation RateAlgorithmica10.1007/s00453-018-0502-x81:2(593-631)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s00453-018-0502-x
Doerr BDoerr CKötzing T(2019)Solving Problems with Unknown Solution Length at Almost No Extra CostAlgorithmica10.1007/s00453-018-0477-781:2(703-748)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s00453-018-0477-7
Einarsson HLengler JGauy MMeier FMujika ASteger AWeissenberger FTakadama K(2018)The linear hidden subset problem for the (1 + 1) EA with scheduled and adaptive mutation ratesProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205519(1491-1498)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205519
Doerr BDoerr CKötzing TBosman P(2017)Unknown solution length problems with no asymptotically optimal run timeProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071233(1367-1374)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3071233
Dang DLehre P(2016)Self-adaptation of Mutation Rates in Non-elitist PopulationsParallel Problem Solving from Nature – PPSN XIV10.1007/978-3-319-45823-6_75(803-813)Online publication date: 31-Aug-2016
https://doi.org/10.1007/978-3-319-45823-6_75

View Options

Login options

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

Cited By

Index Terms

Recommendations

Unknown solution length problems with no asymptotically optimal run time

Solving Problems with Unknown Solution Length at Almost No Extra Cost

Unbiased black-box complexities of jump functions: how to cross large plateaus