Efficient optimisation of noisy fitness functions with population-based evolutionary algorithms

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Authors

Colleges, School and Institutes

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.

Details

Original languageEnglish
Title of host publicationFOGA 2015 - Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII
Publication statusPublished - 17 Jan 2015
Event13th ACM Conference on Foundations of Genetic Algorithms, FOGA 2015 - Aberystwyth, United Kingdom
Duration: 17 Jan 201520 Jan 2015

Conference

Conference13th ACM Conference on Foundations of Genetic Algorithms, FOGA 2015
CountryUnited Kingdom
CityAberystwyth
Period17/01/1520/01/15

Keywords

  • Noisy optimisation, Non-elitism, Runtime Analysis

ASJC Scopus subject areas