Research Article Open Access

Using Background Knowledge and Random Sampling in Genetic Programming: A Case Study in Learning Boolean Parity Functions

Lappoon R. Tang 1
  • 1 Department of Engineering, Roborn Technology Limited 8/F, Core F, Cyberport 3, 100. Cyberport Road, Hong Kong

Abstract

The Boolean even-N-parity function returns T (i.e., true) if an even number of its Boolean arguments for N arguments are T and otherwise returns NIL (i.e., false). Learning Boolean even-N-parity functions has been recognized as a difficult problem for evolutionary computation (such as genetic programming) especially when N is large (e.g., 20+). A number of approaches have been proposed for solving the benchmark problem of even-N-parity. Most approaches focus on improving the representation of individuals and/or improving the effectiveness of crossover. So far, no approach has attempted to use high-arity background knowledge/functions for automating problem decomposition in the course of evolution. Our current approach combines the use of high-arity background functions, automatically defined functions, and random sampling of fitness cases to (1) Automate problem decomposition for high-arity even-N-parity problems and (2) Promote diversity in the retainment of genetic materials across generations by using random samples of fitness cases in fitness evaluation. Experimental evaluation shows that such an approach can dramatically reduce the total number of individuals needed to be processed by genetic programming. Therefore, such an approach to genetic programming can significantly improve computational efficiency.

Journal of Computer Science
Volume 19 No. 7, 2023, 900-908

DOI: https://doi.org/10.3844/jcssp.2023.900.908

Submitted On: 8 February 2023 Published On: 10 July 2023

How to Cite: Tang , L. R. (2023). Using Background Knowledge and Random Sampling in Genetic Programming: A Case Study in Learning Boolean Parity Functions. Journal of Computer Science, 19(7), 900-908. https://doi.org/10.3844/jcssp.2023.900.908

  • 902 Views
  • 537 Downloads
  • 0 Citations

Download

Keywords

  • Genetic Programming
  • Symbolic Regression
  • Even-N-Parity Boolean Functions
  • Random Sampling
  • Background Functions