skip to main content
10.1145/1830483.1830672acmconferencesArticle/Chapter ViewAbstractPublication PagesgeccoConference Proceedingsconference-collections
research-article

Speeding up the evaluation of evolutionary learning systems using GPGPUs

Published:07 July 2010Publication History

ABSTRACT

In this paper we introduce a method for computing fitness in evolutionary learning systems based on NVIDIA's massive parallel technology using the CUDA library. Both the match process of a population of classifiers against a training set and the computation of the fitness of each classifier from its matches have been parallelized. This method has been integrated within the BioHEL evolutionary learning system. The methodology presented in this paper can be easily extended to any evolutionary learning system. The method has been tested using a broad set of problems with varying number of attributes and instances. The evaluation function by itself achieves speedups up to 52.4X while its integration with the entire learning process achieves speedups up to 58.1X. Moreover, the speedup increases when the CUDA-based fitness computation is combined with other efficiency enhancement mechanisms.

References

  1. NVIDIA CUDA Programming Guide 2.0. 2008.Google ScholarGoogle Scholar
  2. J. Bacardit. Pittsburgh Genetics-Based Machine Learning in the Data Mining era: Representations, generalization, and run-time. PhD thesis, Ramon Llull University, Barcelona, Spain, 2004.Google ScholarGoogle Scholar
  3. J. Bacardit, E. Burke, and N. Krasnogor. Improving the scalability of rule-based evolutionary learning. Memetic Computing, 1(1):55--67, March 2009.Google ScholarGoogle ScholarCross RefCross Ref
  4. J. Bacardit, D. Goldberg, M. Butz, X. Llora, and J. Garrell. Speeding-up pittsburgh learning classifier systems: Modeling time and accuracy. 2004.Google ScholarGoogle Scholar
  5. J. Bacardit and N. Krasnogor. A mixed discrete-continuous attribute list representation for large scale classification domains. In GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation, pages 1155--1162, New York, NY, USA, 2009. ACM. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. J. Bacardit, M. Stout, J. Hirst, A. Valencia, R. Smith, and N. Krasnogor. Automated alphabet reduction for protein datasets. BMC Bioinformatics, 10(1):6, 2009.Google ScholarGoogle ScholarCross RefCross Ref
  7. C. Blake, E. Keogh, and C. Merz. UCI repository of machine learning databases. 1998. (www.ics.uci.edu/mlearn/MLRepository.html).Google ScholarGoogle Scholar
  8. M.V. Butz. Rule-Based Evolutionary Online Learning Systems: A Principled Approach to LCS Analysis and Design, volume 109 of Studies in Fuzziness and Soft Computing. Springer, 2006.Google ScholarGoogle Scholar
  9. M.V. Butz, P.L. Lanzi, X. Llora, and D. Loiacono. An analysis of matching in learning classifier systems. In GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation, pages 1349--1356, New York, NY, USA, 2008. ACM. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. B. Catanzaro, N. Sundaram, and K. Keutzer. Fast support vector machine training and classification on graphics processors. In Proceedings of the 25th International Conference on Machine Learning (ICML 2008), pages 111, 104, 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. W. B. Langdon and A. P. Harrison. GP on SPMD parallel graphics hardware for mega bioinformatics data mining. Soft Comput., 12(12):1169--1183, 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. X. Llora and K. Sastry. Fast rule matching for learning classifier systems via vector instructions. In GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computation, pages 1513--1520, New York, NY, USA, 2006. ACM. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. D. Loiacono and P. Lanzi. Speeding up matching in XCS. In 12th International Workshop on Learning Classifier Systems, 2009.Google ScholarGoogle Scholar
  14. O. Maitre, L. A. Baumes, N. Lachiche, A. Corma, and P. Collet. Coarse grain parallelization of evolutionary algorithms on GPGPU cards with EASEA. In Proceedings of the 11th Annual conference on Genetic and evolutionary computation, pages 1403--1410, Montreal, Quebec, Canada, 2009. ACM. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. D. Mellor and S. P. Nicklin. A population-based approach to finding the matchset of a learning classifier system efficiently. In Proceedings of the 11th Annual conference on Genetic and evolutionary computation, pages 1267--1274, Montreal, Quebec, Canada, 2009. ACM. Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. NVIDIA. Data-Parallel algorithms. http://developer.download.nvidia.com/compute/cuda/sdk/website/Data-Parallel Algorithms.html#reduction, September 2009.Google ScholarGoogle Scholar
  17. R. Prabhu. SOMGPU: an unsupervised pattern classifier on graphical processing unit. In IEEE Congress on Evolutionary Computation, pages 1011--1018, 2008.Google ScholarGoogle Scholar
  18. K. Sastry. Principled efficiency enhancement techniques, 2005. Genetic and Evolutionary Computation Conference - GECCO 2005- Tutorial.Google ScholarGoogle Scholar
  19. T. Sharp. Implementing decision trees and forests on a GPU. In Computer Vision - ECCV 2008, pages 595--608. 2008.Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. D. Steinkraus, I. Buck, and P.Y. Simard. Using GPUs for machine learning algorithms. In Proc. of the Eighth International Confernece on Document Analysis and Recognition, volume 2, pages 1115--1120, 2005. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. M. Stout, J. Bacardit, J.D. Hirst, and N. Krasnogor. Prediction of recursive convex hull class assignments for protein residues. Bioinf., 24(7):916--923, 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. G. Venturini. SIA: a supervised inductive algorithm with genetic search for learning attributes based concepts. In Machine Learning: ECML-93 - Proc.n of the European Conference on Machine Learning, pages 280--296. Springer-Verlag, 1993. Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. S. W. Wilson. Classifier fitness based on accuracy. Evolutionary Computation, 3(2):149--175, June 1995. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Speeding up the evaluation of evolutionary learning systems using GPGPUs

        Recommendations

        Comments

        Login options

        Check if you have access through your login credentials or your institution to get full access on this article.

        Sign in
        • Published in

          cover image ACM Conferences
          GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation
          July 2010
          1520 pages
          ISBN:9781450300728
          DOI:10.1145/1830483

          Copyright © 2010 ACM

          Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

          Publisher

          Association for Computing Machinery

          New York, NY, United States

          Publication History

          • Published: 7 July 2010

          Permissions

          Request permissions about this article.

          Request Permissions

          Check for updates

          Qualifiers

          • research-article

          Acceptance Rates

          Overall Acceptance Rate1,669of4,410submissions,38%

          Upcoming Conference

          GECCO '24
          Genetic and Evolutionary Computation Conference
          July 14 - 18, 2024
          Melbourne , VIC , Australia

        PDF Format

        View or Download as a PDF file.

        PDF

        eReader

        View online with eReader.

        eReader