Abstract
Geometric Semantic Genetic Programming (GSGP) proposed an important enhancement to GP-based learning, incorporating search operators that operate directly on the semantics of the parents with bounded effects on the semantics of the offspring. This approach posed any symbolic regression fitness landscape as a unimodal function, allowing for more directed search. Moreover, it became evident that the search could be implemented in a much more efficient manner, that does not require the execution, evaluation or manipulation of variable length syntactic models. Hence, efficient implementations of this algorithm have been developed using both CPU and GPU processing. However, current implementations are still ill-suited for real-time learning, or learning on devices with limited resources, scenarios that are becoming more prevalent with the continued development of the Internet-of-Things and the increased need for efficient and distributed learning on the Edge. This paper presents GSGP-Hardware, a fully pipelined and parallel design of GSGP developed fully using VHDL, for implementation on FPGA devices. Using Vivado AMD-Xilinx for synthesis and simulation, GSGP-Hardware achieves an approximate improvement in efficiency, in terms of run time and Gpops/s, of three and four orders of magnitude, respectively, compared with the state-of-the-art GPU implementation. This is a performance increase that has not been achieved by other FPGA-based implementations of genetic programming. This is possible due to the manner in which GSGP evolves a model, and competitive accuracy is achieved by incorporating simple but powerful enhancements to the original GSGP algorithm. GSGP-Hardware allows for instantaneous symbolic regression, opening up new application domains for this powerful variant of genetic programming.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Availability of data
Data generated during the current study are available from the corresponding author on reasonable request.
Notes
GSGP-Hardware with a configuration 32 individuals, 12 features, 2 generations, and 2 data.
References
S.P.H. Alinodehi, S. Moshfe, M.S. Zaeimian, A. Khoei, K. Hadidi, High-speed general purpose genetic algorithm processor. IEEE Trans. Cybern. 46(7), 1551–1565 (2016)
A. Amaricai, O. Boncalo, Srt radix-2 dividers with (5, 4) redundant representation of partial remainder, in 2013 NORCHIP (IEEE, 2013)
C. AMD, Vivado design suite, user guide logic simulation (2018). https://docs.amd.com/v/u/2018.3-English/ug900-vivado-logic-simulation
C. AMD, Quality and reliability vivado (2023). https://www.xilinx.com/support/quality.html
C. AMD, Reliability vivado (2023). https://www.xilinx.com/support/quality/reliability.html
C. AMD, Virtex Ultrascale + FPGA (2023). https://www.xilinx.com/content/dam/xilinx/publications/product-briefs/virtex-ultrascale-plus-vu19p-product-brief.pdff
C. AMD, Virtex ultrascale+ FPGA data sheet (2023). https://www.xilinx.com/content/dam/xilinx/support/documents/data_sheets/ds923-virtex-ultrascale-plus.pdf
C. AMD, Vivado design suite (2023). www.amd.com
C. AMD, Xilinx system generator for dsp (2023)
I. Arnaldo, K. Krawiec, U.M. O’Reilly, Multiple regression genetic programming, in GECCO ’14 (Association for Computing Machinery, New York, 2014), pp. 879–886
A. Asad, R. Kaur, F. Mohammadi, A survey on memory subsystems for deep neural network accelerators. Future Internet 14(5), 146 (2022)
F. Baeta, J. Correia, T. Martins, P. Machado, Tensorgp-genetic programming engine in tensorflow, in Applications of Evolutionary Computation-24th International Conference, EvoApplications 2021 (Springer, 2021)
S. Bharany, S. Sharma, O.I. Khalaf, G.M. Abdulsahib, A.S.A. Humaimeedy, T.H.H. Aldhyani, M. Maashi, H. Alkahtani, A systematic survey on energy-efficient techniques in sustainable cloud computing. Sustainability 14(10), 6256 (2022)
M. Bhardwaj, Aradhana, A. Kumar, P. Kumar, V. Nath, Digital implementation of sigmoid function in artificial neural network using VHDL, in Nanoelectronics, Circuits and Communication Systems (Springer, Singapore, 2020), pp. 45–53
J. Brookhouse, F.E. Otero, M. Kampouridis, Working with opencl to speed up a genetic programming financial forecasting algorithm: initial results, in Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation, GECCO Comp ’14 (Association for Computing Machinery, New York, 2014), pp. 1117–1124
S.Z.V. Brown, Fundamentals of Digital Logic (McGraw-Hill, New York, 2009)
B. Burlacu, G. Kronberger, M. Kommenda, Operon c++: An efficient genetic programming framework for symbolic regression, in Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion, GECCO ’20 (Association for Computing Machinery, New York, 2020), pp. 1562–1570
G. Cappuccino Pa, G.C. Corsonello, High performance vlsi modules for division and square roots. Microprocess. Microsyst. 22(5), 239–246 (1998)
M. Castelli, L. Manzoni, Gsgp-c++ 2.0: a geometric semantic genetic programming framework. SoftwareX 10, 100313 (2019)
M. Castelli, S. Silva, L. Vanneschi, A c++ framework for geometric semantic genetic programming. Genet. Prog. Evolv. Mach. 16(1), 73–81 (2015)
M. Castelli, L. Trujillo, L. Vanneschi, A. Popovič, Prediction of energy performance of residential buildings: a genetic programming approach. Energy Build. 102, 67–74 (2015)
M. Castelli, L. Trujillo, L. Vanneschi, S. Silva, E. Z-Flores, P. Legrand, Geometric semantic genetic programming with local search, in Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, GECCO ’15 (2015), pp. 999–1006
D.M. Chitty, Faster GPU-based genetic programming using a two-dimensional stack. Soft. Comput. 21(14), 3859–3878 (2016)
M. Clive Max, in FPGA Architectures (Newnes, Burlington, 2008), pp. 13–48
C. Crary, W. Piard, G. Stitt, C. Bean, B. Hicks, Using FPGA devices to accelerate tree-based genetic programming: A preliminary exploration with recent technologies, in Lecture Notes in Computer Science (Springer, Switzerland, 2023), pp. 182–197
F.M. De Rainville, F.A. Fortin, M.A. Gardner, M. Parizeau, C. Gagné, Deap: a python framework for evolutionary algorithms, in Proceedings of the 14th Annual Conference Companion on Genetic and Evolutionary Computation, GECCO ’12 (Association for Computing Machinery, New York, 2012), pp. 85–92
J.C. Dibene, Y. Maldonado, L. Trujillo, E. Dunn, Prepare for ludicrous speed: marker-based instantaneous binocular rolling shutter localization. IEEE Trans. Visual Comput. Graph. 28(5), 2201–2211 (2022)
C. Digilent, Artix-7 fpga (2023)
P. Fernando, S. Katkoori, D. Keymeulen, R. Zebulum, A. Stoica, Customizable FPGA IP core implementation of a general-purpose genetic algorithm engine. IEEE Trans. Evol. Comput. 14(1), 133–149 (2010)
J. Fowers, G. Brown, P. Cooke, G. Stitt, A performance and energy comparison of FPGAs, gpus, and multicores for sliding-window applications, in Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA ’12 (ACM, 2012)
A.I. Funie, P. Grigoras, P. Burovskiy, W. Luk, M. Salmon, Run-time reconfigurable acceleration for genetic programming fitness evaluation in trading strategies. J. Signal Process. Syst. 90(1), 39–52 (2017)
I. Gonçalves, S. Silva, C.M. Fonseca, On the generalization ability of geometric semantic genetic programming, in Genetic Programming. ed. by P. Machado, M.I. Heywood, J. McDermott, M. Castelli, P. García-Sánchez, P. Burelli, S. Risi, K. Sim (Springer, Cham, 2015), pp.41–52
C. Goribar, Y. Maldonado, L. Trujillo, Automatic random tree generator on FPGA, in NEO 2015. Studies in Computational Intelligence. ed. by O. Schütze, L. Trujillo, P. Legrand, Y. Maldonado (Springer, New York, 2016), pp.89–104
L. Guo, A.I. Funie, D.B. Thomas, H. Fu, W. Luk, Parallel genetic algorithms on multiple FPGAs 43(4), 86–93 (2016)
L. Guo, D.B. Thomas, W. Luk, Automated framework for general-purpose genetic algorithms in FPGAs, in Applications of Evolutionary Computation (Springer, Berlin, Heidelberg, 2014), pp. 714–725
A. Guyot, L. Montalvo, A. Houelle, H. Mehrez, N. Vaucher, Comparison of the layout synthesis of radix-2 and pseudo-radix-4 dividers, in Proceedings of the 8th International Conference on VLSI Design, ICVD-95 (IEEE Comput. Soc. Press, 1995)
D.L.N. Hettiarachchi, V.S.P. Davuluru, E.J. Balster, Integer vs. floating-point processing on modern FPGA technology, in 2020 10th Annual Computing and Communication Workshop and Conference (CCWC) (IEEE, 2020)
T.K. Ho, The random subspace method for constructing decision forests. IEEE Trans. Pattern Anal. Mach. Intell. 20(8), 832–844 (1998)
J. Hopf, A parameterizable handelc divider generator for FPGAs with embedded hardware multipliers, in IEEE International Conference on Field-Programmable Technology (IEEE, New York), pp. 355–358
R. Hrbacek, M. Sikulova, Coevolutionary cartesian genetic programming in FPGA, in Advances in Artificial Life, ECAL 2013 (MIT Press, 2013)
L.Y. Hu, Y. Dongming, H. Hefei, A wrapper of pci express with fifo interfaces based on FPGA. arvix 1(5), 1–5 (2013)
H. Hua, Y. Li, T. Wang, N. Dong, W. Li, J. Cao, Edge computing with artificial intelligence: a machine learning perspective. ACM Comput. Surv. (2023). https://doi.org/10.1145/3555802
E.A. Huerta, A. Khan, E. Davis, C. Bushell, W.D. Gropp, D.S. Katz, V. Kindratenko, S. Koric, W.T.C. Kramer, B. McGinty, K. McHenry, A. Saxton, Convergence of artificial intelligence and high performance computing on NSF-supported cyberinfrastructure. J. Big Data 7, 1 (2020)
G. Ibarra-Vazquez, G. Olague, M. Chan-Ley, C. Puente, C. Soubervielle-Montalvo, Brain programming is immune to adversarial attacks: towards accurate and robust image classification using symbolic learning. Swarm Evol. Comput. 71, 101059 (2022)
C. Intel, FPGA optimization guide for intel (2023). www.intel.com
J.R. Koza, Human-competitive results produced by genetic programming. Genet. Prog. Evol. Mach. 11(3–4), 251–284 (2010)
W. La Cava, P. Orzechowski, B. Burlacu, F. de Franca, M. Virgolin, Y. Jin, M. Kommenda, J. Moore, Contemporary symbolic regression methods and their relative performance, in Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks, ed. by J. Vanschoren, S. Yeung (eds) , vol. 1 (Curran, 2021)
W.B. Langdon, A many threaded CUDA interpreter for genetic programming, in Lecture Notes in Computer Science (Springer, Berlin, Heidelberg, 2010), pp. 146–158
W.B. Langdon, Failed disruption propagation in integer genetic programming, in Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO ’22 (Association for Computing Machinery, New York, 2022), pp. 574–577
W.B. Langdon, Jaws 30. Genet. Program. Evolv. Mach. (2023). https://doi.org/10.1007/s10710-023-09467-x
M. Letras, A. Morales-Reyes, R. Cumplido, A scalable and customizable processor array for implementing cellular genetic algorithms. Neurocomputing 175, 899–910 (2016)
G. Louppe, P. Geurts, Ensembles on random patches, in Machine Learning and Knowledge Discovery in Databases (Springer, Berlin, Heidelberg, 2012), pp. 346–361
Y. Lu, Industry 4.0: a survey on technologies, applications and open research issues. J. Ind. Inform. Integr. 6, 1–10 (2017)
P. Martin, A hardware implementation of a genetic programming system using FPGAs and handel-c. Genet. Prog. Evolv. Mach. 2(4), 317–343 (2001)
D.W. Matula, M.T. Panu, J.Y. Zhang, Multiplicative division employing independent factors. IEEE Trans. Comput. 64(7), 2012–2019 (2015)
Y. Martínez, E. Naredo, L. Trujillo, P. Legrand, U. López, A comparison of fitness-case sampling methods for genetic programming. J. Exp. Theor. Artif. Intell. 29(6), 1203–1224 (2017)
M. McCann, N. Pippenger, Srt division algorithms as dynamical systems. SIAM J. Comput. 6(34), 1279–1301 (2005)
L. Montalvo, A. Guyot, Svoboda-tung division with no compensation, in Proceedings of the 8th International Conference on VLSI Design (IEEE, New York, 1995), pp. 381–385
A. Moraglio, K. Krawiec, C.G. Johnson, Geometric semantic genetic programming, in Proceedings of the 12th International Conference on Parallel Problem Solving from Nature-Volume Part I, PPSN’12 (2012), pp. 21–31
G. Olague, L. Trujillo, Evolutionary-computer-assisted design of image operators that detect interest points using genetic programming. Image Vis. Comput. 29(7), 484–498 (2011)
I. Ortigosa, R. Lopez, J. G, A neural networks approach to residuary resistance of sailing yachts prediction, in Proceedings of the International Conference on Marine Engineering MARINE (2007), p. 250
U.S. Patankar, A. Koel, Review of basic classes of dividers based on division algorithm. IEEE Access 9, 23035–23069 (2021)
M. Qasaimeh, K. Denolf, J. Lo, K. Vissers, J. Zambreno, P.H. Jones, Comparing energy efficiency of CPU, GPU and FPGA implementations for vision kernels, in 2019 IEEE International Conference on Embedded Software and Systems (ICESS) (IEEE, 2019)
J.R. Quinlan, Combining instance-based and model-based learning, in Machine Learning, Proceedings of the Tenth International Conference (University of Massachusetts, Amherst, 1993), pp. 236–243
E. Real, A. Aggarwal, Y. Huang, Q.V. Le, Regularized evolution for image classifier architecture search. Proc. AAAI Conf. Artif. Intell. 33(01), 4780–4789 (2019)
E. Real, C. Liang, D. So, Q. Le, AutoML-zero: Evolving machine learning algorithms from scratch, in Proceedings of the 37th International Conference on Machine Learning, Proceedings of Machine Learning Research, vol. 119, ed. by H.D. III, A. Singh (PMLR, 2020), pp. 8007–8019
E. Real, S. Moore, A. Selle, S. Saxena, Y.L. Suematsu, J. Tan, Q.V. Le, A. Kurakin, Large-scale evolution of image classifiers, in Proceedings of the 34th International Conference on Machine Learning, Proceedings of Machine Learning Research, vol. 70, ed. by D. Precup, Y.W. Teh (PMLR, 2017), pp. 2902–2911
J.E. Robertson, A new class of digital division methods. IRE Trans. Electron. Comput. EC–7(3), 218–222 (1958)
D. Robilliard, V. Marion-Poty, C. Fonlupt, Genetic programming on graphics processing units. Genet. Prog. Evolv. Mach. 10(4), 447–471 (2009)
C. Rudin, Do simpler models exist and how can we find them?, in Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD ’19 (Association for Computing Machinery, New York, 2019), pp. 1–2
C. Rudin, Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nat. Mach. Intell. 1(5), 206–215 (2019)
A. Rushton, Vhdl for logic synthesis, in VHDL for Logic Synthesis (Wiley, 2011), pp. 1–496
O. Said, A bandwidth control scheme for reducing the negative impact of bottlenecks in IoT environments: simulation and performance evaluation. Internet Things 21, 100682 (2023)
K.O.M. Salih, T.A. Rashid, D. Radovanovic, N. Bacanin, A comprehensive survey on the internet of things with the industrial marketplace. Sensors 22(3), 730 (2022)
I.H. Sarker, Deep learning: a comprehensive overview on techniques, taxonomy, applications and research directions. SN Comput. Sci. 2(6) (2021)
H. Schmit, S. Cadambi, M. Moe, Pipeline reconfigurable FPGAs. J. VLSI Signal Process. Syst. 24, 129–146 (2000)
B. Shackleford, G. Snider, R.J. Carter, E. Okushi, M. Yasuda, K. Seo, H. Yasuura, A high-performance, pipelined, FPGA-based genetic algorithm machine. Genet. Prog. Evolv. Mach. 2(1), 33–60 (2001)
R.P.S. Sidhu, A. Mei, V.K. Prasanna, Genetic programming using self-reconfigurable FPGAs, in Field Programmable Logic and Applications (Springer, Berlin, Heidelberg, 1999), pp. 301–312
M. Sipper, W. Fu, K. Ahuja, J.H. Moore, Investigating the parameter space of evolutionary algorithms. BioData Min. 11(1) (2018)
K. Sörensen, M. Sevaux, F. Glover, A history of metaheuristics, in Handbook of Heuristics (Springer, 2018), pp. 1–18
N. Soronkin, Implementation of high-speed fixed-point dividers on FPGA. J. Comput. Sci. Technol. 6(1), 8–11 (2006)
K. Staats, E. Pantridge, M. Cavaglia, I. Milovanov, A. Aniyan, Tensorflow enabled genetic programming, in Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO ’17 (Association for Computing Machinery, New York, 2017), pp. 1872–1879
E. Strubell, A. Ganesh, A. McCallum, Energy and policy considerations for modern deep learning research. Proc. AAAI Conf. Artif. Intell. 34(09), 13693–13696 (2020)
M. Suganuma, M. Kobayashi, S. Shirakawa, T. Nagao, Evolution of deep convolutional neural networks using cartesian genetic programming. Evol. Comput. 28(1), 141–163 (2020)
G. Sutter, J.P. Deschamps, High speed fixed point dividers for FPGAs, in 2009 International Conference on Field Programmable Logic and Applications (IEEE, 2009)
K. Tocher, Techniques of multiplication and division for automatic binary computers. Q. J. Mech. Appl. Math. 11(3), 364–384 (1998)
J. Togelius, G.N. Yannakakis, Choose your weapon: Survival strategies for depressed ai academics (2023)
L. Trujillo, E. Álvarez González, E. Galván, J.J. Tapia, A. Ponsich, On the analysis of hyper-parameter space for a genetic programming system with iterated f-race. Soft. Comput. 24(19), 14757–14770 (2020)
L. Trujillo, J.M. Muñoz Contreras, D.E. Hernandez, M. Castelli, J.J. Tapia, Gsgp-cuda—a cuda framework for geometric semantic genetic programming. SoftwareX 18, (2022)
A. Tsanas, A. Xifara, Accurate quantitative estimation of energy performance of residential buildings using statistical machine learning tools. Energy Build. 49, 560–567 (2012)
L. Vanneschi, M. Castelli, S. Silva, A survey of semantic methods in genetic programming. Genet. Prog. Evolv. Mach. 15(2), 195–214 (2014)
L. Vanneschi, S. Silva, M. Castelli, L. Manzoni, Geometric Semantic Genetic Programming for Real Life Applications (Springer, New York, 2014), pp. 191–209
Z. Vasicek, L. Sekanina, Hardware accelerators for cartesian genetic programming, in Lecture Notes in Computer Science (Springer, Berlin, Heidelberg, 2008), pp. 230–241
Z. Vašíček, L. Sekanina, Hardware accelerator of cartesian genetic programming with multiple fitness units. Comput. Inform. 29(6+), 1359–1371 (2012)
H. Wang, Z. Qu, Q. Zhou, H. Zhang, B. Luo, W. Xu, S. Guo, R. Li, A comprehensive survey on training acceleration for large machine learning models in IoT. IEEE Internet Things J. 9(2), 939–963 (2022)
J. Wang, C. Wang, Q. Lin, C. Luo, C. Wu, J. Li, Adversarial attacks and defenses in deep learning for image recognition: a survey. Neurocomputing 514, 162–181 (2022)
X. Xu, Z. Yu, FPGA-Based PCI Data Acquisition Synchronization Card of Railway Clearance Detection System (Springer, Berlin, Heidelberg, 2011), pp.15–23
Y. Yang, L. Wu, G. Yin, L. Li, H. Zhao, A survey on security and privacy issues in internet-of-things. IEEE Internet Things J. 4(5), 1250–1258 (2017)
I. Yeh, Modeling of strength of high-performance concrete using artificial neural networks. Cement Concr. Res. 28(12), 1797–1808 (1998)
Acknowledgements
Special thanks are give to Juan Flores-R engineering student, Carlos Goribar and Jose Manuel Muñoz Contreras, PhD students that also supported this research.
Funding
This work was supported by TecNM (Mexico) projects 16788.23-P, 17615.23-P, 19400.24-P and 19455.24-P, CONAHCYT (Mexico) project CF-2023-I-724, and Red-CI Baja projects Detección de daño en palas de aerogeneradores con técnicas de clasificación de series de tiempo and Clasificación de patrones de deambuilaje en personas afectadas con demencia utilizando aprendizaje automático from the Secretaria de Economía e Innovación and Amazon Web Services. The second, third and fourth author were supported by CONAHCYT scholarships 993254, 1014860, and 692786, respectively.
Author information
Authors and Affiliations
Contributions
Conceptualization: LT, YM; Methodology: RS, YM; Formal analysis and investigation: YM; Validation: JAQ, RV, YM and LT; Writing—original draft preparation: LT, YM; Writing—review and editing: LT; Funding acquisition: LT, YM; Resources: LT, YM; Supervision: LT, YM.
Corresponding author
Ethics declarations
Conflict of interest
The authors have no conflicts of interest to declare that are relevant to the content of this article. Leonardo Trujillo is an Associate Editors of Genetic Programming and Evolvable Machines.
Ethics approval
This work did not require approval by an institutional or independent ethics committee.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Maldonado, Y., Salas, R., Quevedo, J.A. et al. GSGP-hardware: instantaneous symbolic regression with an FPGA implementation of geometric semantic genetic programming. Genet Program Evolvable Mach 25, 18 (2024). https://doi.org/10.1007/s10710-024-09491-5
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s10710-024-09491-5