Browsing by Author "Kononova, Anna V."
Now showing 1 - 10 of 10
Results Per Page
Sort Options
Item Embargo Analysis of structural bias in Differential Evolution configurations(Springer, 2022-01-01) Vermetten, Diederick; van Stein, Bas; Kononova, Anna V.; Caraffini, FabioDifferential Evolution is a popular optimisation method with a small number of parameters. However, different hyper-parameters and Differential Evolution variants such as different mutation operators and the F and Cr parameter may introduce structural bias. Structural bias is a form of bias where artefacts in the algorithm lead to a preference to particular regions in the search space regardless of the objective function. Many algorithm configurations suffer from structural bias but it is very hard to automatically detect it and even harder to detect what kind of structural bias is involved and what component might be the cause of it. A comprehensive study of the occurrence and type of structural bias in Differential Evolution configurations has not yet been carried out till now. In this chapter we systematically evaluate 10980 Differential Evolution configurations on structural bias with the open source BIAS toolbox. Using this toolbox we identify which configurations cause bias and what type of bias it is. In addition, we analyse the results to make clear recommendations on which components and parameters can be used in Differential Evolution to ensure unbiased behaviour within reasonable computational budget.Item Open Access BIAS: A Toolbox for Benchmarking Structural Bias in the Continuous Domain(IEEE, 2022-07-13) Vermetten, Diederick; van Stein, Bas; Caraffini, Fabio; Minku, Leandro L.; Kononova, Anna V.Benchmarking heuristic algorithms is vital to understand under which conditions and on what kind of problems certain algorithms perform well. Most benchmarks are performance-based, to test algorithm performance under a wide set of conditions. There are also resource- and behaviour-based benchmarks to test the resource consumption and the behaviour of algorithms. In this article, we propose a novel behaviour-based benchmark toolbox: BIAS (Bias in Algorithms, Structural). This toolbox can detect structural bias per dimension and across dimension based on 39 statistical tests. Moreover, it predicts the type of structural bias using a Random Forest model. BIAS can be used to better understand and improve existing algorithms (removing bias) as well as to test novel algorithms for structural bias in an early phase of development. Experiments with a large set of generated structural bias scenarios show that BIAS was successful in identifying bias. In addition we also provide the results of BIAS on 432 existing state-of-the-art optimisation algorithms showing that different kinds of structural bias are present in these algorithms, mostly towards the centre of the objective space or showing discretization behaviour. The proposed toolbox is made available open-source and recommendations are provided for the sample size and hyper-parameters to be used when applying the toolbox on other algorithms.Item Open Access Can compact optimisation algorithms be structurally biased?(Springer, 2020-08-31) Kononova, Anna V.; Caraffini, Fabio; Wang, Hao; Bäck, ThomasIn the field of stochastic optimisation, the so-called structural bias constitutes an undesired behaviour of an algorithm that is unable to explore the search space to a uniform extent. In this paper, we investigate whether algorithms from a subclass of estimation of distribution algorithms, the compact algorithms, exhibit structural bias. Our approach, justified in our earlier publications, is based on conducting experiments on a test function whose values are uniformly distributed in its domain. For the experiment, 81 combinations of compact algorithms and strategies of dealing with infeasible solutions have been selected as test cases. We have applied two approaches for determining the presence and severity of structural bias, namely an (existing) visual and an (updated) statistical (Anderson-Darling) test. Our results suggest that compact algorithms are more immune to structural bias than their counterparts maintaining explicit populations. Both tests indicate that strong structural bias is found only in the cBFO algorithm, regardless of the choice of strategy of dealing with infeasible solutions, and cPSO with mirror strategy. For other test cases, statistical and visual tests disagree on some cases classified as having mild or strong structural bias: the former one tends to make harsher decisions, thus needing further investigation.Item Open Access Can Single Solution Optimisation Methods Be Structurally Biased?(MDPI, 2020-02-19) Kononova, Anna V.; Caraffini, Fabio; Wang, Hao; Back, ThomasThis paper investigates whether optimisation methods with the population made up of one solution can suffer from structural bias just like their multisolution variants. Following recent results highlighting the importance of choice of strategy for handling solutions generated outside the domain, a selection of single solution methods are considered in conjunction with several such strategies. Obtained results are tested for the presence of structural bias by means of a traditional approach from literature and a newly proposed here statistical approach. These two tests are demonstrated to be not fully consistent. All tested methods are found to be structurally biased with at least one of the tested strategies. Confirming results for multisolution methods, it is such strategy that is shown to control the emergence of structural bias in single solution methods. Some of the tested methods exhibit a kind of structural bias that has not been observed before.Item Open Access Differential evolution outside the box(Elsevier, 2021-09-30) Kononova, Anna V.; Caraffini, Fabio; Bäck, ThomasThis paper investigates how often the popular configurations of Differential Evolution generate solutions outside the feasible domain. Following previous publications in the field, we argue that what the algorithm does with such solutions and how often this has to happen is important for the overall performance of the algorithm and interpretation of results. Based on observations therein, we conclude that significantly more solutions than what is usually assumed by practitioners need to undergo some sort of 'correction' to conform with the definition of the problem's search domain. A wide range of popular Differential Evolution configurations is considered in this study. Conclusions are made regarding the effect the Differential Evolution components and parameter settings have on the distribution of proportions of infeasible solutions generated in a series of independent runs. Results shown in this study suggest strong dependencies between proportions of generated infeasible solutions and every aspect mentioned above. Further investigation of the distribution of proportions of generated infeasible solutions is required.Item Open Access Emergence of Structural Bias in Differential Evolution(ACM, 2021-07) van Stein, Bas; Caraffini, Fabio; Kononova, Anna V.Heuristic optimisation algorithms are in high demand due to the overwhelming amount of complex optimisation problems that need to be solved. The complexity of these problems is well beyond the boundaries of applicability of exact optimisation algorithms and therefore require modern heuristics to find feasible solutions quickly. These heuristics and their effects are almost always evaluated and explained by particular problem instances. In previous works, it has been shown that many such algorithms show structural bias, by either being attracted to a certain region of the search space or by consistently avoiding regions of the search space, on. special test function designed to ensure uniform 'exploration' of the domain. In this paper, we analyse the emergence of such structural bias for Differential Evolution (DE) configurations and, specifically, the effect of different mutation, crossover and correction strategies. We also analyse the emergence of the structural bias during the run-time of each algorithm. We conclude with recommendations of which configurations should be avoided in order to run DE unbiased.Item Open Access Infeasibility and structural bias in Differential Evolution(Elsevier, 2019-05-11) Caraffini, Fabio; Kononova, Anna V.; Corne, DavidStructural bias is a recently identified property of optimisation algorithms, causing them to favour certain regions of the search space over others, independently of the objective function. Since structural bias can adversely affect the progress of optimisation, a better understanding of it is needed in order to inform the theory and practice of algorithm design. For example, it is generally accepted that larger populations are favoured when solution quality is paramount and time constraints are permissive. However, common variants of both Genetic Algorithms and Particle Swarm Optimisation have been found to exhibit structural bias that increases with population size. Herein we investigate structural bias in popular variants of Differential Evolution (DE), and attempt to identify which algorithm features trigger its emergence. In particular, we focus on the (often overlooked) constraint handling mechanism. Our results suggest that DE is generally robust to structural bias. Only one of the variants studied – DE/current-to-best/1/bin – shows clear signs of bias, however this is mitigated by a judicious choice of constraint handling technique. These findings contribute towards explaining the widespread success of DE in algorithm comparison studies; its robustness to structural bias represents the absence of a factor that may confound other algorithms.Item Open Access Is there Anisotropy in Structural Bias?(ACM, 2021-07) Vermetten, Diederick; Kononova, Anna V.; Caraffini, Fabio; Wang, Hao; Back, ThomasStructural Bias (SB) is an important type of algorithmic deficiency within iterative optimisation heuristics. However, methods for detecting structural bias have not yet fully matured, and recent studies have uncovered many interesting questions. One of these is the question of how structural bias can be related to anisotropy. Intuitively, an algorithm that is not isotropic would be considered structurally biased. However, there have been cases where algorithms appear to only show SB in some dimensions. As such, we investigate whether these algorithms actually exhibit anisotropy, and how this impacts the detection of SB. We find that anisotropy is very rare, and even in cases where it is present, there are clear tests for SB which do not rely on any assumptions of isotropy, so we can safely expand the suite of SB tests to encompass these kinds of deficiencies not found by the original tests. We propose several additional testing procedures for SB detection and aim to motivate further research into the creation of a robust portfolio of tests. This is crucial since no single test will be able to work effectively with all types of SB we identify.Item Metadata only Proceedings of the 12th EMO: International Conference on Evolutionary Multi-Criterion Optimization(Springer Cham, 2023-03) Emmerich, Michael; Deutz, André; Wang, Hao; Kononova, Anna V.; Naujoks, Boris; Li, Ke; Miettinen, Kaisa; Yevseyeva, IrynaItem Embargo Using Structural Bias to Analyse the Behaviour of Modular CMA-ES(ACM, 2022-07-17) Vermetten, Diederick; Caraffini, Fabio; van Stein, Bas; Kononova, Anna V.The Covariance Matrix Adaptation Evolution Strategy (CMA-ES) is a commonly used iterative optimisation heuristic for optimising black-box functions. CMA-ES comes in many flavours with different configuration settings. In this work, we investigate whether CMAES suffers from structural bias and which modules and parameters affect the strength and type of structural bias. Structural bias occurs when an algorithm or a component of the algorithm biases the search towards a specific direction in the search space irrespective of the objective function. In addition to this investigation, we propose a method to assess the relationship between structural bias and the performance of configurations with different types of bias on the BBOB suite of benchmark functions. Surprisingly for such a popular algorithm, 90.3% of the 1 620 CMA-ES configurations were found to have Structural Bias. Some interesting patterns between module settings and bias types are presented and further insights are discussed.