Evolution under partial information

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

Standard

Evolution under partial information. / Dang, Duc Cuong; Lehre, Per Kristian.

GECCO 2014 - Proceedings of the 2014 Genetic and Evolutionary Computation Conference. Association for Computing Machinery , 2014. p. 1359-1366.

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

Harvard

Dang, DC & Lehre, PK 2014, Evolution under partial information. in GECCO 2014 - Proceedings of the 2014 Genetic and Evolutionary Computation Conference. Association for Computing Machinery , pp. 1359-1366, 16th Genetic and Evolutionary Computation Conference, GECCO 2014, Vancouver, BC, Canada, 12/07/14. https://doi.org/10.1145/2576768.2598375

APA

Dang, D. C., & Lehre, P. K. (2014). Evolution under partial information. In GECCO 2014 - Proceedings of the 2014 Genetic and Evolutionary Computation Conference (pp. 1359-1366). Association for Computing Machinery . https://doi.org/10.1145/2576768.2598375

Vancouver

Dang DC, Lehre PK. Evolution under partial information. In GECCO 2014 - Proceedings of the 2014 Genetic and Evolutionary Computation Conference. Association for Computing Machinery . 2014. p. 1359-1366 https://doi.org/10.1145/2576768.2598375

Author

Dang, Duc Cuong ; Lehre, Per Kristian. / Evolution under partial information. GECCO 2014 - Proceedings of the 2014 Genetic and Evolutionary Computation Conference. Association for Computing Machinery , 2014. pp. 1359-1366

Bibtex

@inproceedings{e090fa060df445928750cbe24e816e4d,
title = "Evolution under partial information",
abstract = "Complete and accurate information about the quality of candidate solutions is not always available in real-world optimisation. It is often prohibitively expensive to evaluate candidate solution on more than a few test cases, or the evaluation mechanism itself is unreliable. While evolutionary algorithms are popular methods in optimisation, the theoretical understanding is lacking for the case of partial information. This paper initiates runtime analysis of evolutionary algorithms where only partial information about fitness is available. Two scenarios are investigated. In partial evaluation of solutions, only a small amount of information about the problem is revealed in each fitness evaluation. We formulate a model that makes this scenario concrete for pseudo-Boolean optimisation. In partial evaluation of populations, only a few individuals in the population are evaluated, and the fitness values of the other individuals are missing or incorrect. For both scenarios, we prove that given a set of specific conditions, non-elitist evolutionary algorithms can optimise many functions in expected polynomial time even when vanishingly little information available. The conditions imply a small enough mutation rate and a large enough population size. The latter emphasises the importance of populations in evolution.",
keywords = "Non-elitism, Partial evaluation, Runtime analysis",
author = "Dang, {Duc Cuong} and Lehre, {Per Kristian}",
year = "2014",
doi = "10.1145/2576768.2598375",
language = "English",
isbn = "9781450326629",
pages = "1359--1366",
booktitle = "GECCO 2014 - Proceedings of the 2014 Genetic and Evolutionary Computation Conference",
publisher = "Association for Computing Machinery ",
note = "16th Genetic and Evolutionary Computation Conference, GECCO 2014 ; Conference date: 12-07-2014 Through 16-07-2014",

}

RIS

TY - GEN

T1 - Evolution under partial information

AU - Dang, Duc Cuong

AU - Lehre, Per Kristian

PY - 2014

Y1 - 2014

N2 - Complete and accurate information about the quality of candidate solutions is not always available in real-world optimisation. It is often prohibitively expensive to evaluate candidate solution on more than a few test cases, or the evaluation mechanism itself is unreliable. While evolutionary algorithms are popular methods in optimisation, the theoretical understanding is lacking for the case of partial information. This paper initiates runtime analysis of evolutionary algorithms where only partial information about fitness is available. Two scenarios are investigated. In partial evaluation of solutions, only a small amount of information about the problem is revealed in each fitness evaluation. We formulate a model that makes this scenario concrete for pseudo-Boolean optimisation. In partial evaluation of populations, only a few individuals in the population are evaluated, and the fitness values of the other individuals are missing or incorrect. For both scenarios, we prove that given a set of specific conditions, non-elitist evolutionary algorithms can optimise many functions in expected polynomial time even when vanishingly little information available. The conditions imply a small enough mutation rate and a large enough population size. The latter emphasises the importance of populations in evolution.

AB - Complete and accurate information about the quality of candidate solutions is not always available in real-world optimisation. It is often prohibitively expensive to evaluate candidate solution on more than a few test cases, or the evaluation mechanism itself is unreliable. While evolutionary algorithms are popular methods in optimisation, the theoretical understanding is lacking for the case of partial information. This paper initiates runtime analysis of evolutionary algorithms where only partial information about fitness is available. Two scenarios are investigated. In partial evaluation of solutions, only a small amount of information about the problem is revealed in each fitness evaluation. We formulate a model that makes this scenario concrete for pseudo-Boolean optimisation. In partial evaluation of populations, only a few individuals in the population are evaluated, and the fitness values of the other individuals are missing or incorrect. For both scenarios, we prove that given a set of specific conditions, non-elitist evolutionary algorithms can optimise many functions in expected polynomial time even when vanishingly little information available. The conditions imply a small enough mutation rate and a large enough population size. The latter emphasises the importance of populations in evolution.

KW - Non-elitism

KW - Partial evaluation

KW - Runtime analysis

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

U2 - 10.1145/2576768.2598375

DO - 10.1145/2576768.2598375

M3 - Conference contribution

AN - SCOPUS:84905707091

SN - 9781450326629

SP - 1359

EP - 1366

BT - GECCO 2014 - Proceedings of the 2014 Genetic and Evolutionary Computation Conference

PB - Association for Computing Machinery

T2 - 16th Genetic and Evolutionary Computation Conference, GECCO 2014

Y2 - 12 July 2014 through 16 July 2014

ER -