research-article

Unknown solution length problems with no asymptotically optimal run time

Authors:

Benjamin Doerr,

Carola Doerr,

Timo KötzingAuthors Info & Claims

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

Pages 1367 - 1374

https://doi.org/10.1145/3071178.3071233

Published: 01 July 2017 Publication History

Get Access

Abstract

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 nor their number is known. In previous work, variants of the (1 + 1) evolutionary algorithm (EA) have been developed that solve, for arbitrary s ∈ ℕ, such OneMax and LeadingOnes instances, simultaneously for all n ∈ ℕ, in expected time O(n(log(n))² log log(n) ... log^(s−1)(n)(log^(s)(n))^1+ε) and O(n² log(n) log log(n) ... log^(s−1)(n)(log^(s)(n))^1+ε), respectively; that is, in almost the same time as if n and the relevant bit positions were known.

In this work, we prove the first, almost matching, lower bounds for this setting. For LeadingOnes, we show that, for every s ∈ ℕ, the (1 + 1) EA with any mutation operator treating zeros and ones equally has an expected run time of ω(n² log(n) log log(n) ... log^(s)(n)) when facing problem size n. Aiming at closing the small remaining gap, we realize that, quite surprisingly, there is no asymptotically best performance. For any algorithm solving, for all n, all instances of size n in expected time at most T(n), there is an algorithm doing the same in time T'(n) with T' = o(T). For OneMax we show results of similar flavor.

References

[1]

M. J. Ash. Neither a worst convergent series nor a best divergent series exists. College Mathematics Journal, 28:296--297, 1997.

Crossref

Google Scholar

[2]

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

Digital Library

Google Scholar

[3]

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

Digital Library

Google Scholar

[4]

B. Doerr, C. Doerr, and T. Kötzing. Solving problems with unknown solution length at (almost) no extra cost. In Proc. of Genetic and Evolutionary Computation Conference (GECCO'15), pages 831--838. ACM, 2015.

Digital Library

Google Scholar

[5]

B. Doerr, T. Jansen, C. Witt, and C. Zarges. A method to derive fixed budget results from expected optimisation times. In Proc. of Genetic and Evolutionary Computation Conference (GECCO'13), pages 1581--1588. ACM, 2013.

Digital Library

Google Scholar

[6]

G. H. Hardy. Orders of infinity. Cambridge University Press, 1910.

Google Scholar

[7]

P. K. Lehre and X. Yao. Runtime analysis of the (1 + 1) EA on computing unique input output sequences. Information Sciences, 259:510--531, 2014. An extended abstract appeared in the Proc. of IEEE Congress on Evolutionary Computation (CEC'07).

Digital Library

Google Scholar

[8]

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

Cited By

View all

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
Lengler JOpris ASudholt D(2024)Analysing Equilibrium States for Population DiversityAlgorithmica10.1007/s00453-024-01226-386:7(2317-2351)Online publication date: 16-Apr-2024
https://dl.acm.org/doi/10.1007/s00453-024-01226-3
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
Show More Cited By

Index Terms

Unknown solution length problems with no asymptotically optimal run time
1. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Discrete optimization
        Optimization with randomized search heuristics
  2. Theory and algorithms for application domains
    1. Theory of randomized search heuristics

Recommendations

Solving Problems with Unknown Solution Length at (Almost) No Extra Cost
GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

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 ...
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 ...
Escaping Local Optima with Diversity Mechanisms and Crossover
GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016
Population diversity is essential for the effective use of any crossover operator. We compare seven commonly used diversity mechanisms and prove rigorous run time bounds for the (μ+1) GA using uniform crossover on the fitness function Jump_k. All ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

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

July 2017

1427 pages

ISBN:9781450349208

DOI:10.1145/3071178

General Chair:
Peter A. N. Bosman
Centrum Wiskunde & Informatica (CWI)

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: 01 July 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

LabEx LMH
Deutsche Forschungsgemeinschaft

Conference

GECCO '17

Sponsor:

SIGEVO

GECCO '17: Genetic and Evolutionary Computation Conference

July 15 - 19, 2017

Berlin, Germany

Acceptance Rates

GECCO '17 Paper Acceptance Rate 178 of 462 submissions, 39%;

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

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
85
Total Downloads

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

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

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
Lengler JOpris ASudholt D(2024)Analysing Equilibrium States for Population DiversityAlgorithmica10.1007/s00453-024-01226-386:7(2317-2351)Online publication date: 16-Apr-2024
https://dl.acm.org/doi/10.1007/s00453-024-01226-3
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
Lengler JOpris ASudholt DSilva SPaquete L(2023)Analysing Equilibrium States for Population DiversityProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590465(1628-1636)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590465
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
Case BLehre P(2020)Self-Adaptation in Nonelitist Evolutionary Algorithms on Discrete Problems With Unknown StructureIEEE Transactions on Evolutionary Computation10.1109/TEVC.2020.298545024:4(650-663)Online publication date: Aug-2020
https://doi.org/10.1109/TEVC.2020.2985450
Einarsson HGauy MLengler JMeier FMujika ASteger AWeissenberger F(2019)The linear hidden subset problem for the (1 + 1) EA with scheduled and adaptive mutation ratesTheoretical Computer Science10.1016/j.tcs.2019.05.021Online publication date: May-2019
https://doi.org/10.1016/j.tcs.2019.05.021
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
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.

Cited By

Index Terms

Recommendations

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

Solving Problems with Unknown Solution Length at Almost No Extra Cost

Escaping Local Optima with Diversity Mechanisms and Crossover