Projects per year
Abstract
Real-world optimisation problems often involve dynamics, where objective functions may change over time. Previous studies have shown that evolutionary algorithms (EAs) can solve dynamic optimisation problems. Additionally, the use of diversity mechanisms, populations, and parallelisation can enhance the performance of EAs in dynamic environments if appropriate parameter settings are utilised. Self-adaptation, which encodes parameters in genotypes of individuals and allows them to evolve together with solutions, can help configure parameters of EAs. This parameter control mechanism has been proved to effectively handle a static problem with unknown structure. However, the benefit of self-adaptation on dynamic optimisation problems remains unknown. We consider a tracking dynamic optima problem, the so-called Dynamic Substring Matching (DSM) problem, which requires algorithms to successively track a sequence of structure-changing optima. Our analyses show that mutation-based EAs with a fixed mutation rate have a negligible chance of tracking these dynamic optima, while the self-adaptive EA tracks them with an overwhelmingly high probability. Furthermore, we provide a level-based theorem with tail bounds, which bounds the chance of the algorithm finding the current optima within a given evaluation budget. Overall, self-adaptation is promising for tracking dynamic optima.
Original language | English |
---|---|
Title of host publication | GECCO ’23 |
Subtitle of host publication | Proceedings of the Genetic and Evolutionary Computation Conference |
Publisher | Association for Computing Machinery (ACM) |
Pages | 1619–1627 |
Number of pages | 7 |
ISBN (Electronic) | 9798400701191 |
DOIs | |
Publication status | Published - 12 Jul 2023 |
Event | GECCO '23: Genetic and Evolutionary Computation Conference - Lisbon, Portugal Duration: 15 Jul 2023 → 19 Jul 2023 https://dl.acm.org/conference/gecco |
Publication series
Name | GECCO: Genetic and Evolutionary Computation Conference |
---|
Conference
Conference | GECCO '23: Genetic and Evolutionary Computation Conference |
---|---|
Abbreviated title | GECCO '23 |
Country/Territory | Portugal |
City | Lisbon |
Period | 15/07/23 → 19/07/23 |
Internet address |
Bibliographical note
Acknowledgments:Thanks to Alistair Benford for proof assistance, and to all the reviewers for their valuable feedback. Lehre was supported by a Turing AI Fellowship (EPSRC grant ref EP/V025562/1).
Keywords
- Evolutionary algorithms
- self-adaptation
- dynamic optimisation
Fingerprint
Dive into the research topics of 'Self-adaptation Can Help Evolutionary Algorithms Track Dynamic Optima'. Together they form a unique fingerprint.Projects
- 1 Active
-
Turing AI Fellowship: Rigorous time-complexity analysis of co-evolutionary algorithms
Engineering & Physical Science Research Council
1/01/21 → 31/12/25
Project: Research Councils