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

Duc Cuong Dang; Per Kristian Lehre

doi:10.1145/2725494.2725508

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

Duc Cuong Dang, Per Kristian Lehre

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

27 Citations (Scopus)

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	https://doi.org/10.1145/2725494.2725508
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

Access to Document

10.1145/2725494.2725508Licence: None: All rights reserved

https://dl.acm.org/citation.cfm?doid=2725494.2725508Licence: None: All rights reserved

Cite this

@inproceedings{5726ac1312ac45c0b471aa67707e83a6,

title = "Efficient optimisation of noisy fitness functions with population-based evolutionary algorithms",

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.",

keywords = "Noisy optimisation, Non-elitism, Runtime Analysis",

author = "Dang, {Duc Cuong} and Lehre, {Per Kristian}",

year = "2015",

month = jan,

day = "17",

doi = "10.1145/2725494.2725508",

language = "English",

pages = "62--68",

booktitle = "FOGA 2015 - Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII",

publisher = "Association for Computing Machinery ",

note = "13th ACM Conference on Foundations of Genetic Algorithms, FOGA 2015 ; Conference date: 17-01-2015 Through 20-01-2015",

}

Dang, DC & Lehre, PK 2015, Efficient optimisation of noisy fitness functions with population-based evolutionary algorithms. in FOGA 2015 - Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII. Association for Computing Machinery , pp. 62-68, 13th ACM Conference on Foundations of Genetic Algorithms, FOGA 2015, Aberystwyth, United Kingdom, 17/01/15. https://doi.org/10.1145/2725494.2725508

Efficient optimisation of noisy fitness functions with population-based evolutionary algorithms. / Dang, Duc Cuong; Lehre, Per Kristian.
FOGA 2015 - Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII. Association for Computing Machinery , 2015. p. 62-68.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Dang, Duc Cuong

AU - Lehre, Per Kristian

PY - 2015/1/17

Y1 - 2015/1/17

N2 - 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.

AB - 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.

KW - Noisy optimisation

KW - Non-elitism

KW - Runtime Analysis

UR - http://www.scopus.com/inward/record.url?scp=84960349642&partnerID=8YFLogxK

U2 - 10.1145/2725494.2725508

DO - 10.1145/2725494.2725508

M3 - Conference contribution

AN - SCOPUS:84960349642

SP - 62

EP - 68

BT - FOGA 2015 - Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII

PB - Association for Computing Machinery

T2 - 13th ACM Conference on Foundations of Genetic Algorithms, FOGA 2015

Y2 - 17 January 2015 through 20 January 2015

ER -

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

Abstract

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this