Abstract
In 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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
It is called ‘probability vector’ in the original publications [11]; a terminology which we find somewhat misleading in case of a continuous search space and a Gaussian generating distribution.
- 2.
This list clearly does not exhaust all possibilities.
- 3.
To avoid complicating Table 1 further, results for cGA that requires no SDIS are shown as dismiss – it is the closest to how cGA deals with infeasible solutions.
- 4.
This is easily explained if saturation is used but is not trivial if toroidal is used.
- 5.
The quantiles are chosen ad hoc, based on the distribution of statistical measure over all combinations of algorithms and SDISs.
References
Bäck, T.: Evolutionary Algorithms in Theory and Practice. Oxford University Press, New York (1996)
Campelo, F., Aranha, C.: EC bestiary: a bestiary of evolutionary, swarm and other metaphor-based algorithms, June 2018. https://doi.org/10.5281/zenodo.1293352
Caraffini, F.: The stochastic optimisation software (SOS) platform, June 2019. https://doi.org/10.5281/zenodo.3237023
Caraffini, F., Iacca, G.: The SOS platform: designing, tuning and statistically benchmarking optimisation algorithms. Mathematics 8(5), 785 (2020). https://doi.org/10.3390/math8050785
Caraffini, F., Kononova, A.V.: Structural bias in differential evolution: a preliminary study. In: 14th International Workshop on Global Optimization, LeGO 2018, vol. 2070, p. 020005. AIP, Leiden (2018)
Caraffini, F., Kononova, A.V.: Structural Bias in Optimisation Algorithms: Extended Results (2020). https://doi.org/10.17632/zdh2phb3b4.2. Mendeley Data
Caraffini, F., Kononova, A.V., Corne, D.W.: Infeasibility and structural bias in differential evolution. Inf. Sci. 496, 161–179 (2019). https://doi.org/10.1016/j.ins.2019.05.019
Das, S., Biswas, A., Dasgupta, S., Abraham, A.: Bacterial foraging optimization algorithm: theoretical foundations, analysis, and applications. In: Abraham, A., Hassanien, A.E., Siarry, P., Engelbrecht, A. (eds.) Foundations of Computational Intelligence. SCI, vol. 203, pp. 23–55. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01085-9_2
De Jong, K.A.: An analysis of the behavior of a class of genetic adaptive systems. Ph.D. thesis, University of Michigan, USA (1975)
Hauschild, M., Pelikan, M.: An introduction and survey of estimation of distribution algorithms. Swarm Evol. Comput. 1(3), 111–128 (2011). https://doi.org/10.1016/j.swevo.2011.08.003
Iacca, G., Caraffini, F.: Compact optimization algorithms with re-sampled inheritance. In: Kaufmann, P., Castillo, P.A. (eds.) EvoApplications 2019. LNCS, vol. 11454, pp. 523–534. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-16692-2_35
Inselberg, A.: The plane with parallel coordinates. Vis. Comput. 1(2), 69–91 (1985). https://doi.org/10.1007/BF01898350
Justel, A., Peña, D., Zamar, R.: A multivariate Kolmogorov-Smirnov test of goodness of fit. Stat. Probab. Lett. 35(3), 251–259 (1997)
Kononova, A.V., Caraffini, F., Wang, H., Bäck, T.: Can single solution optimisation methods be structurally biased? MDPI Preprints (2020). https://doi.org/10.20944/preprints202002.0277.v1
Kononova, A.V., Corne, D.W., Wilde, P.D., Shneer, V., Caraffini, F.: Structural bias in population-based algorithms. Inf. Sci. 298, 468–490 (2015). https://doi.org/10.1016/j.ins.2014.11.035
Kost, J.T., McDermott, M.P.: Combining dependent p-values. Stat. Probab. Lett. 60(2), 183–190 (2002)
L’Ecuyer, P., Simard, R.: TestU01: a C library for empirical testing of random number generators. ACM Trans. Math. Softw. 33(4) (2007). https://doi.org/10.1145/1268776.1268777
Mühlenbein, H., Paaß, G.: From recombination of genes to the estimation of distributions I. Binary parameters. In: Voigt, H.-M., Ebeling, W., Rechenberg, I., Schwefel, H.-P. (eds.) PPSN 1996. LNCS, vol. 1141, pp. 178–187. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-61723-X_982
Pelikan, M., Goldberg, D., Lobo, F.: A survey of optimization by building and using probabilistic models. In: Proceedings of the 2000 American Control Conference, vol. 5, pp. 3289–3293 (2000)
Piotrowski, A.P., Napiorkowski, J.J.: Searching for structural bias in particle swarm optimization and differential evolution algorithms. Swarm Intell. 10(4), 307–353 (2016). https://doi.org/10.1007/s11721-016-0129-y
Price, K.V., Storn, R., Lampinen, J.: Differential Evolution: A Practical Approach to Global Optimization. Springer, Heidelberg (2005). https://doi.org/10.1007/3-540-31306-0
Razali, N.M., Wah, Y.B.: Power comparisons of Shapiro-Wilk, Kolmogorov-Smirnov, Lilliefors and Anderson-Darling tests. J. Stat. Model. Anal. 2(1), 21–33 (2011)
Wolpert, D., Macready, W.: No free lunch theorems for optimization. IEEE Trans. Evol. Comput. 1, 67–82 (1997). https://doi.org/10.1109/4235.585893
Acknowledgments
The work of Hao Wang was supported by the Paris Ile-de-France Region.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Kononova, A.V., Caraffini, F., Wang, H., Bäck, T. (2020). Can Compact Optimisation Algorithms Be Structurally Biased?. In: Bäck, T., et al. Parallel Problem Solving from Nature – PPSN XVI. PPSN 2020. Lecture Notes in Computer Science(), vol 12269. Springer, Cham. https://doi.org/10.1007/978-3-030-58112-1_16
Download citation
DOI: https://doi.org/10.1007/978-3-030-58112-1_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-58111-4
Online ISBN: 978-3-030-58112-1
eBook Packages: Computer ScienceComputer Science (R0)