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.
- NVIDIA CUDA Programming Guide 2.0. 2008.Google Scholar
- 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 Scholar
- J. Bacardit, E. Burke, and N. Krasnogor. Improving the scalability of rule-based evolutionary learning. Memetic Computing, 1(1):55--67, March 2009.Google ScholarCross Ref
- J. Bacardit, D. Goldberg, M. Butz, X. Llora, and J. Garrell. Speeding-up pittsburgh learning classifier systems: Modeling time and accuracy. 2004.Google Scholar
- 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 ScholarDigital Library
- 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 ScholarCross Ref
- C. Blake, E. Keogh, and C. Merz. UCI repository of machine learning databases. 1998. (www.ics.uci.edu/mlearn/MLRepository.html).Google Scholar
- 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 Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- D. Loiacono and P. Lanzi. Speeding up matching in XCS. In 12th International Workshop on Learning Classifier Systems, 2009.Google Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- NVIDIA. Data-Parallel algorithms. http://developer.download.nvidia.com/compute/cuda/sdk/website/Data-Parallel Algorithms.html#reduction, September 2009.Google Scholar
- R. Prabhu. SOMGPU: an unsupervised pattern classifier on graphical processing unit. In IEEE Congress on Evolutionary Computation, pages 1011--1018, 2008.Google Scholar
- K. Sastry. Principled efficiency enhancement techniques, 2005. Genetic and Evolutionary Computation Conference - GECCO 2005- Tutorial.Google Scholar
- T. Sharp. Implementing decision trees and forests on a GPU. In Computer Vision - ECCV 2008, pages 595--608. 2008.Google ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- S. W. Wilson. Classifier fitness based on accuracy. Evolutionary Computation, 3(2):149--175, June 1995. Google ScholarDigital Library
Index Terms
- Speeding up the evaluation of evolutionary learning systems using GPGPUs
Recommendations
A mixed discrete-continuous attribute list representation for large scale classification domains
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computationDatasets with a large number of attributes are a difficult challenge for evolutionary learning techniques. The recently proposed attribute list rule representation has shown to be able to significantly improve the overall performance (e.g. run-time, ...
Genetics-based machine learning for rule induction: state of the art, taxonomy, and comparative study
The classification problem can be addressed by numerous techniques and algorithms which belong to different paradigms of machine learning. In this paper, we are interested in evolutionary algorithms, the so-called genetics-based machine learning ...
Use of the q-Gaussian mutation in evolutionary algorithms
Special issue on advances in computational intelligence and bioinformaticsThis paper proposes the use of the q-Gaussian mutation with self-adaptation of the shape of the mutation distribution in evolutionary algorithms. The shape of the q-Gaussian mutation distribution is controlled by a real parameter q. In the proposed ...
Comments