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

research-article

When non-elitism meets time-linkage problems

Authors:

Xin YaoAuthors Info & Claims

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

Pages 741 - 749

https://doi.org/10.1145/3449639.3459347

Published: 26 June 2021 Publication History

Abstract

Many real-world applications have the time-linkage property, and the only theoretical analysis is recently given by Zheng, et al. (TEVC 2021) on their proposed time-linkage OneMax problem, OneMax^(0,1n). However, only two elitist algorithms (1 + 1) EA and (μ + 1) EA are analyzed, and it is unknown whether the non-elitism mechanism could help to escape the local optima existed in OneMax^(0,1n). In general, there are few theoretical results on the benefits of the non-elitism in evolutionary algorithms. In this work, we analyze on the influence of the non-elitism via comparing the performance of the elitist (1 + λ) EA and its non-elitist counterpart (1, λ) EA. We prove that with probability 1 - o(1) (1 + λ) EA will get stuck in the local optima and cannot find the global optimum, but with probability 1, (1, λ) EA can reach the global optimum and its expected runtime is O(n^3+c log n) with [EQUATION] for the constant c ≥ 1. Noting that a smaller offspring size is helpful for escaping from the local optima, we further resort to the compact genetic algorithm where only two individuals are sampled to update the probabilistic model, and prove its expected runtime of O(n³ log n). Our computational experiments also verify the efficiency of the two non-elitist algorithms.

References

[1]

Peter AN Bosman. 2005. Learning, anticipation and time-deception in evolutionary online dynamic optimization. In Genetic and Evolutionary Computation Conference Companion, GECCO 2005 Workshop. ACM, 39--47.

Digital Library

[2]

Tianshi Chen, Ke Tang, Guoliang Chen, and Xin Yao. 2010. Analysis of computational time of simple estimation of distribution algorithms. IEEE Transactions on Evolutionary Computation 14, 1 (2010), 1--22.

Digital Library

[3]

Tianshi Chen, Ke Tang, Guoliang Chen, and Xin Yao. 2012. A large population size can be unhelpful in evolutionary algorithms. Theoretical Computer Science 436 (2012), 54--70.

Digital Library

[4]

Dogan Corus, Pietro S Oliveto, and Donya Yazdani. 2018. Fast artificial immune systems. In International Conference on Parallel Problem Solving from Nature, PPSN 2018. Springer, 67--78.

[5]

Dogan Corus, Pietro S Oliveto, and Donya Yazdani. 2020. When hypermutations and ageing enable artificial immune systems to outperform evolutionary algorithms. Theoretical Computer Science 832 (2020), 166--185.

[6]

Benjamin Doerr. 2019. Analyzing randomized search heuristics via stochastic domination. Theoretical Computer Science 773 (2019), 115--137.

Digital Library

[7]

Benjamin Doerr. 2020. Does comma selection help to cope with local optima?. In Genetic and Evolutionary Computation Conference, GECCO 2020. ACM, 1304--1313.

Digital Library

[8]

Benjamin Doerr. 2020. The runtime of the compact genetic algorithm on jump functions. Algorithmica (2020), 1--49.

[9]

Benjamin Doerr and Martin S Krejca. 2020. The univariate marginal distribution algorithm copes well with deception and epistasis. In European Conference on Evolutionary Computation in Combinatorial Optimisation, EvoCOP 2020. Springer, 51--66.

Digital Library

[10]

Benjamin Doerr and Weijie Zheng. 2020. From understanding genetic drift to a smart-restart parameter-less compact genetic algorithm. In Genetic and Evolutionary Computation Conference, GECCO 2020. ACM, 805--813.

Digital Library

[11]

Benjamin Doerr and Weijie Zheng. 2020. Sharp bounds for genetic drift in estimation of distribution algorithms. IEEE Transactions on Evolutionary Computation 24, 6 (2020), 1140--1149.

Digital Library

[12]

Benjamin Doerr and Weijie Zheng. 2020. Working principles of binary differential evolution. Theoretical Computer Science 801 (2020), 110--142.

[13]

Stefan Droste. 2006. A rigorous analysis of the compact genetic algorithm for linear functions. Natural Computing 5, 3 (2006), 257--283.

Digital Library

[14]

Stefan Droste, Thomas Jansen, and Ingo Wegener. 2002. On the analysis of the (1+1) evolutionary algorithm. Theoretical Computer Science 276, 1-2 (2002), 51--81.

Digital Library

[15]

Tobias Friedrich, Timo Kötzing, Martin S Krejca, and Andrew M Sutton. 2017. The compact genetic algorithm is efficient under extreme gaussian noise. IEEE Transactions on Evolutionary Computation 21, 3 (2017), 477--490.

Digital Library

[16]

Josselin Garnier, Leila Kallel, and Marc Schoenauer. 1999. Rigorous hitting times for binary mutations. Evolutionary Computation 7, 2 (1999), 173--203.

Digital Library

[17]

Christian Gießen and Timo Kötzing. 2016. Robustness of populations in stochastic environments. Algorithmica 75, 3 (2016), 462--489.

Digital Library

[18]

Václav Hasenöhrl and Andrew M Sutton. 2018. On the runtime dynamics of the compact genetic algorithm on jump functions. In Genetic and Evolutionary Computation Conference, GECCO 2018. ACM, 967--974.

Digital Library

[19]

Jens Jagerskupper and Tobias Storch. 2007. When the plus strategy outperforms the comma strategyand when not. In IEEE Symposium on Foundations of Computational Intelligence, FOCI 2007. IEEE, 25--32.

[20]

Thomas Jansen and Ingo Wegener. 2007. A comparison of simulated annealing with a simple evolutionary algorithm on pseudo-boolean functions of unitation. Theoretical Computer Science 386, 1-2 (2007), 73--93.

Digital Library

[21]

Martin S Krejca and Carsten Witt. 2020. Theory of estimation-of-distribution algorithms. In Theory of Evolutionary Computation, Benjamin Doerr and Frank Neumann (Eds.). Springer, 405--442.

[22]

Per Kristian Lehre and Phan Trung Hai Nguyen. 2019. On the limitations of the univariate marginal distribution algorithm to deception and where bivariate EDAs might help. In ACM/SIGEVO Conference on Foundations of Genetic Algorithms, FOGA 2019. ACM, 154--168.

Digital Library

[23]

Johannes Lengler, Dirk Sudholt, and Carsten Witt. 2020. The complex parameter landscape of the compact genetic algorithm. Algorithmica (2020), 1--42.

[24]

Andrei Lissovoi, Pietro S Oliveto, and John Alasdair Warwicker. 2019. On the time complexity of algorithm selection hyper-heuristics for multimodal optimisation. In AAAI Conference on Artificial Intelligence, AAAI 2019, Vol. 33. 2322--2329.

Digital Library

[25]

Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller. 1953. Equation of state calculations by fast computing machines. The Journal of Chemical Physics 21 (1953), 1087--1092.

[26]

Trung Thanh Nguyen. 2011. Continuous dynamic optimisation using evolutionary algorithms. Ph.D. Dissertation. University of Birmingham.

[27]

Pietro S Oliveto, Tiago Paixão, Jorge Pérez Heredia, Dirk Sudholt, and Barbora Trubenová. 2018. How to escape local optima in black box optimisation: When non-elitism outperforms elitism. Algorithmica 80, 5 (2018), 1604--1633.

Digital Library

[28]

Tiago Paixão, Jorge Pérez Heredia, Dirk Sudholt, and Barbora Trubenová. 2017. Towards a runtime comparison of natural and artificial evolution. Algorithmica 78, 2 (2017), 681--713.

Digital Library

[29]

Jonathan E Rowe and Dirk Sudholt. 2014. The choice of the offspring population size in the (1, λ) evolutionary algorithm. Theoretical Computer Science 545 (2014), 20--38.

Digital Library

[30]

Dirk Sudholt. 2020. The benefits of population diversity in evolutionary algorithms: a survey of rigorous runtime analyses. Theory of Evolutionary Computation (2020), 359--404.

[31]

Dirk Sudholt and Carsten Witt. 2019. On the choice of the update strength in estimation-of-distribution algorithms and ant colony optimization. Algorithmica 81, 4 (2019), 1450--1489.

Digital Library

[32]

Weijie Zheng, Huanhuan Chen, and Xin Yao. 2021. Analysis of evolutionary algorithms on fitness function with time-linkage property. IEEE Transactions on Evolutionary Computation (2021). In Press.

Digital Library

[33]

Weijie Zheng, Qiaozhi Zhang, Huanhuan Chen, and Xin Yao. 2021. When non-elitism meets time-linkage problems. (2021). arXiv:cs.NE/2104.06831 See https://arxiv.org/abs/2104.06831.

Cited By

Yang TZhou Y(2024)Analysis of Multiobjective Evolutionary Algorithms on Fitness Function With Time-Linkage PropertyIEEE Transactions on Evolutionary Computation10.1109/TEVC.2024.337151928:3(837-843)Online publication date: Jun-2024
https://doi.org/10.1109/TEVC.2024.3371519
Li MZheng WXie WSun AYao X(2024)When Does the Time-Linkage Property Help Optimization by Evolutionary Algorithms?Parallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_18(280-294)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70071-2_18
Gao MLiu XZhan ZZhang J(2023)A Clustering-Based Support Vector Classifier for Dynamic Time-Linkage Optimization2023 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI52147.2023.10371998(953-958)Online publication date: 5-Dec-2023
https://doi.org/10.1109/SSCI52147.2023.10371998
Show More Cited By

Index Terms

When non-elitism meets time-linkage problems
1. Theory of computation
  1. Theory and algorithms for application domains
    1. Theory of randomized search heuristics

Recommendations

Analysis of evolutionary algorithms on fitness function with time-linkage property (hot-off-the-press track at GECCO 2021)
GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference Companion

In real-world applications, many optimization problems have the time-linkage property, that is, the objective function value relies on the current solution as well as the historical solutions. Although the rigorous theoretical analysis on evolutionary ...
When Non-Elitism Outperforms Elitism for Crossing Fitness Valleys
GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

Crossing fitness valleys is one of the major obstacles to function optimization. In this paper we investigate how the structure of the fitness valley, namely its depth d and length l, influence the runtime of different strategies for crossing these ...
Towards a Runtime Comparison of Natural and Artificial Evolution

Evolutionary algorithms (EAs) form a popular optimisation paradigm inspired by natural evolution. In recent years the field of evolutionary computation has developed a rigorous analytical theory to analyse the runtimes of EAs on many illustrative ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

June 2021

1219 pages

ISBN:9781450383509

DOI:10.1145/3449639

Editor:
Francisco Chicano
University of Malaga
,
General Chair:
Krzysztof Krawiec
Poznan University of Technology

Copyright © 2021 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: 26 June 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

GECCO '21

Sponsor:

SIGEVO

GECCO '21: Genetic and Evolutionary Computation Conference

July 10 - 14, 2021

Lille, France

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
68
Total Downloads

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

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yang TZhou Y(2024)Analysis of Multiobjective Evolutionary Algorithms on Fitness Function With Time-Linkage PropertyIEEE Transactions on Evolutionary Computation10.1109/TEVC.2024.337151928:3(837-843)Online publication date: Jun-2024
https://doi.org/10.1109/TEVC.2024.3371519
Li MZheng WXie WSun AYao X(2024)When Does the Time-Linkage Property Help Optimization by Evolutionary Algorithms?Parallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_18(280-294)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70071-2_18
Gao MLiu XZhan ZZhang J(2023)A Clustering-Based Support Vector Classifier for Dynamic Time-Linkage Optimization2023 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI52147.2023.10371998(953-958)Online publication date: 5-Dec-2023
https://doi.org/10.1109/SSCI52147.2023.10371998
Zhang TWang HYuan BJin YYao X(2022)Surrogate-Assisted Evolutionary Q-Learning for Black-Box Dynamic Time-Linkage Optimization ProblemsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.317925627:5(1162-1176)Online publication date: 30-May-2022
https://dl.acm.org/doi/10.1109/TEVC.2022.3179256
Lehre PQin X(2022)More Precise Runtime Analyses of Non-elitist Evolutionary Algorithms in Uncertain EnvironmentsAlgorithmica10.1007/s00453-022-01044-586:2(396-441)Online publication date: 2-Oct-2022
https://dl.acm.org/doi/10.1007/s00453-022-01044-5

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