Abstract
Recently it was shown, using the typical mutation mechanism that is used in evolutionary algorithms, that monotone conjunctions are provably evolvable under a specific set of Bernoulli \((p)^n\) distributions. A natural question is whether this mutation mechanism allows convergence under other distributions as well. Our experiments indicate that the answer to this question is affirmative and, at the very least, this mechanism converges under Bernoulli \((p)^n\) distributions outside of the known proved regime.
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.
A literal is a Boolean variable or its negation.
- 2.
The function c is also called ideal function, as it represents the ideal behavior in a certain environment.
- 3.
Source code available at: https://gitlab.com/marina_pantia/evolvability_code.
References
Diochnos, D.I.: On the evolution of monotone conjunctions: drilling for best approximations. In: Ortner, R., Simon, H.U., Zilles, S. (eds.) ALT 2016. LNCS (LNAI), vol. 9925, pp. 98–112. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-46379-7_7
Diochnos, D.I.: On the evolvability of monotone conjunctions with an evolutionary mutation mechanism. J. Artif. Intell. Res. 70, 891–921 (2021)
Diochnos, D.I., Turán, G.: On evolvability: the swapping algorithm, product distributions, and covariance. In: Watanabe, O., Zeugmann, T. (eds.) SAGA 2009. LNCS, vol. 5792, pp. 74–88. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04944-6_7
Droste, S., Jansen, T., Wegener, I.: On the analysis of the (1+1) evolutionary algorithm. Theor. Comput. Sci. 276(1–2), 51–81 (2002)
Feldman, V.: Evolvability from learning algorithms. In: STOC, pp. 619–628 (2008)
Kalkreuth, R., Droschinsky, A.: On the time complexity of simple cartesian genetic programming. In: IJCCI, pp. 172–179. ScitePress (2019)
Kanade, V.: Evolution with recombination. In: FOCS, pp. 837–846 (2011)
Koza, J.R.: Genetic Programming - On the Programming of Computers by Means of Natural Selection. Complex Adaptive Systems. MIT Press, Cambridge (1993)
Lissovoi, A., Oliveto, P.S.: On the time and space complexity of genetic programming for evolving Boolean conjunctions. J. Artif. Intell. Res. 66, 655–689 (2019)
Mambrini, A., Oliveto, P.S.: On the analysis of simple genetic programming for evolving Boolean functions. In: Heywood, M.I., McDermott, J., Castelli, M., Costa, E., Sim, K. (eds.) EuroGP 2016. LNCS, vol. 9594, pp. 99–114. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-30668-1_7
Pitt, L., Valiant, L.G.: Computational limitations on learning from examples. J. ACM 35(4), 965–984 (1988)
Reyzin, L.: Statistical Queries and Statistical Algorithms: Foundations and Applications. CoRR abs/2004.00557 (2020)
Ros, J.P.: Learning Boolean functions with genetic algorithms: a PAC analysis. In: FOGA, pp. 257–275 (1992)
Snir, S., Yohay, B.: Prokaryotic evolutionary mechanisms accelerate learning. Discrete Appl. Math. 258, 222–234 (2019)
Valiant, L.G.: A theory of the learnable. Commun. ACM 27(11), 1134–1142 (1984)
Valiant, L.G.: Evolvability. J. ACM 56(1), 3:1-3:21 (2009)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Alchirch, PM., Diochnos, D.I., Papakonstantinopoulou, K. (2022). Evolving Monotone Conjunctions in Regimes Beyond Proved Convergence. In: Medvet, E., Pappa, G., Xue, B. (eds) Genetic Programming. EuroGP 2022. Lecture Notes in Computer Science, vol 13223. Springer, Cham. https://doi.org/10.1007/978-3-031-02056-8_15
Download citation
DOI: https://doi.org/10.1007/978-3-031-02056-8_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-02055-1
Online ISBN: 978-3-031-02056-8
eBook Packages: Computer ScienceComputer Science (R0)