Abstract
Population-based EAs can optimise pseudo-Boolean functions in expected polynomial time, even when only partial information about the problem is available. In this paper, we show that the approach used to analyse optimisation with partial information extends naturally to optimisation under noise. We consider pseudo-Boolean problems with an additive noise term. Very general conditions on the noise term is derived, under which the EA optimises the noisy function in expected polynomial time. In the case of the OneMax and LeadingOnes problems, effcient optimisation is even possible when the variance of the noise distribution grows quickly with the problem size.
Original language | English |
---|---|
Title of host publication | FOGA 2015 - Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII |
Publisher | Association for Computing Machinery |
Pages | 62-68 |
Number of pages | 7 |
ISBN (Electronic) | 9781450334341 |
DOIs | |
Publication status | Published - 17 Jan 2015 |
Event | 13th ACM Conference on Foundations of Genetic Algorithms, FOGA 2015 - Aberystwyth, United Kingdom Duration: 17 Jan 2015 → 20 Jan 2015 |
Conference
Conference | 13th ACM Conference on Foundations of Genetic Algorithms, FOGA 2015 |
---|---|
Country/Territory | United Kingdom |
City | Aberystwyth |
Period | 17/01/15 → 20/01/15 |
Keywords
- Noisy optimisation
- Non-elitism
- Runtime Analysis
ASJC Scopus subject areas
- Computational Theory and Mathematics