Abstract
Evolutionary Algorithms (EAs) and other randomized search heuristics are often considered as unbiased algorithms that are invariant with respect to different transformations of the underlying search space. However, if a certain amount of domain knowledge is available the use of biased search operators in EAs becomes viable. We consider a simple (1+1) EA for binary search spaces and analyze an asymmetric mutation operator that can treat zero- and one-bits differently. This operator extends previous work by Jansen and Sudholt (ECJ 18(1), 2010) by allowing the operator asymmetry to vary according to the success rate of the algorithm. Using a self-adjusting scheme that learns an appropriate degree of asymmetry, we show improved runtime results on the class of functions OneMax\(_a\) describing the number of matching bits with a fixed target \(a\in \{0,1\}^n\).
Supported by a grant from the Danish Council for Independent Research (DFF-FNU 8021-00260B).
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
References
Doerr, B.: Probabilistic tools for the analysis of randomized optimization heuristics. In: Doerr and Neumann [6], pp. 1–87
Doerr, B., Doerr, C.: Optimal static and self-adjusting parameter choices for the (1+(\(\lambda \), \(\lambda \))) genetic algorithm. Algorithmica 80(5), 1658–1709 (2018)
Doerr, B., Doerr, C.: Theory of parameter control for discrete black-box optimization: provable performance gains through dynamic parameter choices. In: Doerr and Neumann [6], pp. 271–321
Doerr, B., Doerr, C., Kötzing, T.: Static and self-adjusting mutation strengths for multi-valued decision variables. Algorithmica 80(5), 1732–1768 (2018)
Doerr, B., Gießen, C., Witt, C., Yang, J.: The (1 + \(\lambda \)) evolutionary algorithm with self-adjusting mutation rate. Algorithmica 81(2), 593–631 (2019)
Doerr, B., Neumann, F. (eds.): Theory of Evolutionary Computation - Recent Developments in Discrete Optimization. Springer, Heidelberg (2020). https://doi.org/10.1007/978-3-030-29414-4
Doerr, B., Witt, C., Yang, J.: Runtime analysis for self-adaptive mutation rates. In: Proceedings of GECCO 2018, pp. 1475–1482. ACM Press (2018)
Doerr, C.: Complexity theory for discrete black-box optimization heuristics. In: Doerr and Neumann [6], pp. 133–212
Doerr, C., Wagner, M.: Sensitivity of parameter control mechanisms with respect to their initialization. In: Proceedings of PPSN 2018, pp. 360–372 (2018)
Doerr, C., Ye, F., van Rijn, S., Wang, H., Bäck, T.: Towards a theory-guided benchmarking suite for discrete black-box optimization heuristics: profiling (1+\(\lambda \)) EA variants on OneMax and LeadingOnes. In: Proceedings of GECCO 2018, pp. 951–958. ACM Press (2018)
Fajardo, M.A.H.: An empirical evaluation of success-based parameter control mechanisms for evolutionary algorithms. In: Proceedings of GECCO 2019, pp. 787–795. ACM Press (2019)
Feller, W.: An Introduction to Probability Theory and Its Applications, vol. 1, 3rd edn. Wiley, Hoboken (1968)
Jansen, T.: Analyzing Evolutionary Algorithms - The Computer Science Perspective. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-17339-4
Jansen, T., Sudholt, D.: Analysis of an asymmetric mutation operator. Evol. Comput. 18(1), 1–26 (2010)
Lässig, J., Sudholt, D.: Adaptive population models for offspring populations and parallel evolutionary algorithms. In: 2011 Proceedings of FOGA 2011, Schwarzenberg, Austria, 5–8 January 2011, Proceedings, pp. 181–192. ACM Press (2011)
Lehre, P.K., Witt, C.: Black-box search by unbiased variation. Algorithmica64(4), 623–642 (2012)
Lengler, J.: Drift analysis. In: Doerr and Neumann [6], pp. 89–131
Neumann, A., Alexander, B., Neumann, F.: Evolutionary image transition using random walks. In: Correia, J., Ciesielski, V., Liapis, A. (eds.) EvoMUSART 2017. LNCS, vol. 10198, pp. 230–245. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-55750-2_16
Neumann, F., Wegener, I.: Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theor. Comput. Sci. 378(1), 32–40 (2007)
Neumann, F., Witt, C.: Bioinspired Computation in Combinatorial Optimization - Algorithms and Their Computational Complexity. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-16544-3
Raidl, G.R., Koller, G., Julstrom, B.A.: Biased mutation operators for subgraph-selection problems. IEEE Trans. Evol. Comput. 10(2), 145–156 (2006)
Rajabi, A., Witt, C.: Evolutionary algorithms with self-adjusting asymmetric mutation. CoRR (2020). http://arxiv.org/abs/2006.09126
Rajabi, A., Witt, C.: Self-adjusting evolutionary algorithms for multimodal optimization. In: Proceedings of GECCO 2020 (2020, to appear)
Rodionova, A., Antonov, K., Buzdalova, A., Doerr, C.: Offspring population size matters when comparing evolutionary algorithms with self-adjusting mutation rates. In: Proceedings of GECCO 2019, pp. 855–863. ACM Press (2019)
Sutton, A.M.: Superpolynomial lower bounds for the (1+1) EA on some easy combinatorial problems. Algorithmica 75(3), 507–528 (2016)
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
Rajabi, A., Witt, C. (2020). Evolutionary Algorithms with Self-adjusting Asymmetric Mutation. 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_46
Download citation
DOI: https://doi.org/10.1007/978-3-030-58112-1_46
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)