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

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

Standard

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 proceedingConference contribution

Harvard

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

APA

Dang, D. C., & Lehre, P. K. (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 (pp. 62-68). Association for Computing Machinery . https://doi.org/10.1145/2725494.2725508

Vancouver

Dang DC, Lehre PK. 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 . 2015. p. 62-68 https://doi.org/10.1145/2725494.2725508

Author

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

Bibtex

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

}

RIS

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 -