Positional Bias Does Not Influence Cartesian Genetic Programming with Crossover | SpringerLink
Skip to main content
Springer Nature Link
Log in

Positional Bias Does Not Influence Cartesian Genetic Programming with Crossover

  • Conference paper
  • First Online:
Parallel Problem Solving from Nature – PPSN XVIII (PPSN 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 15148))

Included in the following conference series:

  • 311 Accesses

Abstract

The recombination operator plays an important role in many evolutionary algorithms. However, in Cartesian Genetic Programming (CGP), which is part of the aforementioned category, the usefulness of crossover is contested. In this work, we investigate whether CGP’s positional bias actually influences the usefulness of the crossover operator negatively. This bias describes a skewed distribution of CGP’s active and inactive nodes, which might lead to destructive behaviours of standard recombination operators. We try to answer our hypothesis by employing one standard CGP implementation and one without the effects of positional bias. Both versions are combined with one of four standard crossover operators, or with no crossover operator. Additionally, two different selection methods are used to configure a CGP variant. We then analyse their performance and convergence behaviour on eight benchmarks taken from the Boolean and symbolic regression domain. By using Bayesian inference, we are able to rank them, and we found that positional bias does not influence CGP with crossover. Furthermore, we argue that the current research on CGP with standard crossover operators is incomplete, and CGP with recombination might not negatively impact its evolutionary search process. On the contrary, using CGP with crossover improves its performance.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 8007
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 10009
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    The source code can be found at: https://github.com/CuiHen/CGP_with_Crossover_Strategies.

  2. 2.

    We utilized the Python library cmpbayes [24] for all statistical models.

  3. 3.

    For the hyperparameter search, we utilized the Python library Optuna [1].

References

  1. Akiba, T., Sano, S., Yanase, T., Ohta, T., Koyama, M.: Optuna: a next-generation hyperparameter optimization framework. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2019)

    Google Scholar 

  2. Cai, X., Smith, S.L., Tyrrell, A.M.: Positional independence and recombination in cartesian genetic programming. In: Collet, P., Tomassini, M., Ebner, M., Gustafson, S., Ekárt, A. (eds.) Genetic Programming, pp. 351–360. Springer, Heidelberg (2006). https://doi.org/10.1007/11729976_32

  3. Calvo, B., Ceberio, J., Lozano, J.A.: Bayesian inference for algorithm ranking analysis. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO 2018), pp. 324–325. Association for Computing Machinery, New York (2018). https://doi.org/10.1145/3205651.3205658

  4. Clegg, J., Walker, J.A., Miller, J.F.: A new crossover technique for cartesian genetic programming. In: Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation (GECCO 2007), pp. 1580–1587. Association for Computing Machinery, New York (2007). https://doi.org/10.1145/1276958.1277276

  5. Cui, H., Margraf, A., Hähner, J.: Equidistant reorder operator for cartesian genetic programming. In: van Stein, N., Marcelloni, F., Lam, H.K., Cottrell, M., Filipe, J. (eds.) Proceedings of the 15th International Joint Conference on Computational Intelligence - ECTA, 13–15 November 2023, Rome, pp. 64 – 74 (2023). https://doi.org/10.5220/0012174100003595

  6. Cui, H., Margraf, A., Heider, M., Hähner, J.: Towards understanding crossover for cartesian genetic programming. In: van Stein, N., Marcelloni, F., Lam, H.K., Cottrell, M., Filipe, J. (eds.) Proceedings of the 15th International Joint Conference on Computational Intelligence - ECTA, 13–15 November 2023, Rome, pp. 308 – 314 (2023). https://doi.org/10.5220/0012231400003595

  7. Goldman, B.W., Punch, W.F.: Analysis of cartesian genetic programming’s evolutionary mechanisms. IEEE Trans. Evolution. Comput. 19(3), 359–373 (2015). https://doi.org/10.1109/TEVC.2014.2324539

  8. Goldman, B.W., Punch, W.F.: Length bias and search limitations in cartesian genetic programming. In: Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation (GECCO 2013), pp. 933–940. Association for Computing Machinery, New York (2013). https://doi.org/10.1145/2463372.2463482

  9. Goldman, B.W., Punch, W.F.: Reducing wasted evaluations in cartesian genetic programming. In: Krawiec, K., Moraglio, A., Hu, T., Etaner-Uyar, A.Ş., Hu, B. (eds.) Genetic Programming, pp. 61–72. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-37207-0_6

  10. Husa, J., Kalkreuth, R.: A comparative study on crossover in cartesian genetic programming. In: Castelli, M., Sekanina, L., Zhang, M., Cagnoni, S., García-Sánchez, P. (eds.) Genetic Programming, pp. 203–219. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-77553-1_13

  11. Kalkreuth, R.: A comprehensive study on subgraph crossover in cartesian genetic programming. In: Proceedings of the 12th International Joint Conference on Computational Intelligence (IJCCI 2020) - ECTA, pp. 59–70. INSTICC, SciTePress (2020). https://doi.org/10.5220/0010110700590070

  12. Kalkreuth, R.: Towards discrete phenotypic recombination in cartesian genetic programming. In: Rudolph, G., Kononova, A.V., Aguirre, H., Kerschke, P., Ochoa, G., Tušar, T. (eds.) Parallel Problem Solving from Nature – PPSN XVII, pp. 63–77. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-14721-0_5

  13. Kalkreuth, R., Rudolph, G., Droschinsky, A.: A new subgraph crossover for cartesian genetic programming. In: McDermott, J., Castelli, M., Sekanina, L., Haasdijk, E., García-Sánchez, P. (eds.) Genetic Programming, pp. 294–310. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-55696-3_19

  14. Kaufmann, P., Kalkreuth, R.: An empirical study on the parametrization of cartesian genetic programming. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO 2017), pp. 231–232. Association for Computing Machinery, New York (2017). https://doi.org/10.1145/3067695.3075980

  15. Kaufmann, P., Platzner, M.: Advanced techniques for the creation and propagation of modules in cartesian genetic programming. In: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation (GECCO 2008), pp. 1219–1226. Association for Computing Machinery, New York (2008). https://doi.org/10.1145/1389095.1389334

  16. Kruschke, J.K.: Bayesian estimation supersedes the t test. J. Exp. Psychol. Gen. 142(2), 573–603 (2013). https://doi.org/10.1037/a0029146

    Article  Google Scholar 

  17. Langdon, W.B., Poli, R., McPhee, N.F., Koza, J.R.: Genetic Programming: An Introduction and Tutorial, with a Survey of Techniques and Applications, pp. 927–1028. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78293-3_22

  18. Miller, J., Smith, S.: Redundancy and computational efficiency in cartesian genetic programming. IEEE Trans. Evol. Comput. 10(2), 167–174 (2006). https://doi.org/10.1109/TEVC.2006.871253

    Article  Google Scholar 

  19. Miller, J., Thomson, P., Fogarty, T.: Designing electronic circuits using evolutionary algorithms. arithmetic circuits: a case study. In: Genetic Algorithms and Evolution Strategies in Engineering and Computer Science (1999)

    Google Scholar 

  20. Miller, J.F.: Cartesian Genetic Programming. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-17310-3_2

  21. Miller, J.F.: An empirical study of the efficiency of learning Boolean functions using a cartesian genetic programming approach. In: Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation (GECCO 1999), vol. 2, pp. 1135–1142. Morgan Kaufmann Publishers Inc., San Francisco (1999)

    Google Scholar 

  22. Miller, J.F.: Cartesian genetic programming: its status and future. Genet. Program Evolvable Mach. 21(1), 129–168 (2020)

    Article  Google Scholar 

  23. Payne, A.J., Stepney, S.: Representation and structural biases in CGP. In: 2009 IEEE Congress on Evolutionary Computation, pp. 1064–1071 (2009). https://doi.org/10.1109/CEC.2009.4983064

  24. Pätzel, D.: cmpbayes. https://github.com/dpaetzel/cmpbayes

  25. Slaný, K., Sekanina, L.: Fitness landscape analysis and image filter evolution using functional-level cgp. In: Ebner, M., O’Neill, M., Ekárt, A., Vanneschi, L., Esparcia-Alcázar, A.I. (eds.) Genetic Programming, pp. 311–320. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-71605-1_29

  26. Spears, W.M., Anand, V.: A study of crossover operators in genetic programming. In: Ras, Z.W., Zemankova, M. (eds.) Methodologies for Intelligent Systems, pp. 409–418. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-54563-8_104

  27. Stegherr., H., Heider., M., Hähner., J.: Assisting convergence behaviour characterisation with unsupervised clustering. In: Proceedings of the 15th International Joint Conference on Computational Intelligence - ECTA, pp. 108–118. INSTICC, SciTePress (2023). https://doi.org/10.5220/0012202100003595

  28. Torabi, A., Sharifi, A., Teshnehlab, M.: Using Cartesian genetic programming approach with new crossover technique to design convolutional neural networks. Neural Process. Lett. 55(5), 5451–5471 (2023). https://doi.org/10.1007/s11063-022-11093-0

  29. Turner, A.J., Miller, J.F.: Neutral genetic drift: an investigation using cartesian genetic programming. Genet. Program. Evol. Mach. 16(4), 531–558 (2015). https://doi.org/10.1007/s10710-015-9244-6

  30. Vasicek, Z.: Bridging the gap between evolvable hardware and industry using Cartesian genetic programming. In: Stepney, S., Adamatzky, A. (eds.) Inspired by Nature. ECC, vol. 28, pp. 39–55. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-67997-6_2

  31. White, D.R., et al.: Better GP benchmarks: community survey results and proposals. Genet. Program. Evol. Mach. 14(1), 3–29 (2013)

    Google Scholar 

  32. White, D.R., Poulding, S.: A rigorous evaluation of crossover and mutation in genetic programming. In: Vanneschi, L., Gustafson, S., Moraglio, A., De Falco, I., Ebner, M. (eds.) EuroGP 2009. LNCS, vol. 5481, pp. 220–231. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01181-8_19

  33. Wilson, D.G., Miller, J.F., Cussat-Blanc, S., Luga, H.: Positional cartesian genetic programming (2018)

    Google Scholar 

Download references

Acknowledgements

The authors would like to thank the German Federal Ministry of Education and Research (BMBF) for supporting the project SaMoA within VIP+ (grant number 03VP09291).

Author information

Authors and Affiliations

  1. University of Augsburg, 86159, Augsburg, Germany

    Henning Cui, Michael Heider & Jörg Hähner

Authors
  1. Henning Cui
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Michael Heider
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jörg Hähner
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Henning Cui .

Editor information

Editors and Affiliations

  1. University of Applied Sciences Upper Austria, Wels, Austria

    Michael Affenzeller

  2. University of Applied Sciences Upper Austria, Hagenberg, Austria

    Stephan M. Winkler

  3. Leiden University, Leiden, The Netherlands

    Anna V. Kononova

  4. University of Paderborn, Paderborn, Germany

    Heike Trautmann

  5. Jožef Stefan Institute, Ljubljana, Slovenia

    Tea Tušar

  6. University of Coimbra, Coimbra, Portugal

    Penousal Machado

  7. Leiden University, LEIDEN, The Netherlands

    Thomas Bäck

Ethics declarations

Disclosure of Interests

The authors have no competing interests to declare that are relevant to the content of this article.

Rights and permissions

Reprints and permissions

Copyright information

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Cui, H., Heider, M., Hähner, J. (2024). Positional Bias Does Not Influence Cartesian Genetic Programming with Crossover. In: Affenzeller, M., et al. Parallel Problem Solving from Nature – PPSN XVIII. PPSN 2024. Lecture Notes in Computer Science, vol 15148. Springer, Cham. https://doi.org/10.1007/978-3-031-70055-2_10

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-70055-2_10

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-70054-5

  • Online ISBN: 978-3-031-70055-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation