Structural bias in population-based algorithms

Abstract

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

References in corpus (3)

• Fitness Uniform Optimization
• Physical Complexity of Variable Length Symbolic Sequences
• The Eigenvalue Problem for Linear and Affine Iterated Function Systems

Cited by in corpus (9)

• A Prescription of Methodological Guidelines for Comparing Bio-inspired Optimization Algorithms
• Infeasibility and structural bias in Differential Evolution
• Differential evolution outside the box
• The importance of being constrained: dealing with infeasible solutions in Differential Evolution and beyond
• Emergence of Structural Bias in Differential Evolution
• An Efficient Multi-core Implementation of the Jaya Optimisation Algorithm
• Is there Anisotropy in Structural Bias?
• Salp Swarm Optimization: a Critical Review
• A Framework for Knowledge Integrated Evolutionary Algorithms