Skip to main content

Structural bias in population-based algorithms

Kononova, Anna V., Corne, David W., De Wilde, Philippe, Shneer, Vsevolod, Caraffini, Fabio (2015) Structural bias in population-based algorithms. Information Sciences, 298 . pp. 468-490. ISSN 0020-0255. E-ISSN 1872-6291. (doi:10.1016/j.ins.2014.11.035)

Abstract

Challenging optimisation problems are abundant in all areas of science and industry. Since the 1950s, scientists have responded to this by developing ever-diversifying families of 'black box' optimisation algorithms. The latter are designed to be able to address any optimisation problem, requiring only that the quality of any candidate solution can be calculated via a 'fitness function' specific to the problem. For such algorithms to be successful, at least three properties are required: (i) an effective informed sampling strategy, that guides the generation of new candidates on the basis of the fitnesses and locations of previously visited candidates; (ii) mechanisms to ensure efficiency, so that (for example) the same candidates are not repeatedly visited; and (iii) the absence of structural bias, which, if present, would predispose the algorithm towards limiting its search to specific regions of the solution space. The first two of these properties have been extensively investigated, however the third is little understood and rarely explored. In this article we provide theoretical and empirical analyses that contribute to the understanding of structural bias. In particular, we state and prove a theorem concerning the dynamics of population variance in the case of real-valued search spaces and a 'flat' fitness landscape. This reveals how structural bias can arise and manifest as non-uniform clustering of the population over time. Critically, theory predicts that structural bias is exacerbated with (independently) increasing population size, and increasing problem difficulty. These predictions, supported by our empirical analyses, reveal two previously unrecognised aspects of structural bias that would seem vital for algorithm designers and practitioners. Respectively, (i) increasing the population size, though ostensibly promoting diversity, will magnify any inherent structural bias, and (ii) the effects of structural bias are more apparent when faced with (many classes of) 'difficult' problems. Our theoretical result also contributes to the 'exploitation/exploration' conundrum in optimisation algorithm design, by suggesting that two commonly used approaches to enhancing exploration - increasing the population size, and increasing the disruptiveness of search operators - have quite distinct implications in terms of structural bias.

Item Type: Article
DOI/Identification number: 10.1016/j.ins.2014.11.035
Additional information: cited By 4
Uncontrolled keywords: Algorithms; Computation theory; Design; Evolutionary algorithms; Optimization; Population statistics, Algorithmic design; Non-uniform clustering; Optimisation problems; Optimisations; Population variances; Population-based algorithm; Sampling strategies; Structural bias, Shape optimization
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 75 Electronic computers. Computer science
Divisions: Faculties > Sciences > School of Computing > Computational Intelligence Group
Depositing User: Philippe De Wilde
Date Deposited: 24 Oct 2016 10:53 UTC
Last Modified: 31 Jan 2020 11:09 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/58007 (The current URI for this page, for reference purposes)
De Wilde, Philippe: https://orcid.org/0000-0002-4332-1715
  • Depositors only (login required):

Downloads

Downloads per month over past year