Evolution under partial information

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

Authors

Colleges, School and Institutes

External organisations

  • University of Nottingham

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.

Details

Original languageEnglish
Title of host publicationGECCO 2014 - Proceedings of the 2014 Genetic and Evolutionary Computation Conference
Publication statusPublished - 2014
Event16th Genetic and Evolutionary Computation Conference, GECCO 2014 - Vancouver, BC, Canada
Duration: 12 Jul 201416 Jul 2014

Conference

Conference16th Genetic and Evolutionary Computation Conference, GECCO 2014
CountryCanada
CityVancouver, BC
Period12/07/1416/07/14

Keywords

  • Non-elitism, Partial evaluation, Runtime analysis