The DOI matches its Crossref record; 40 of the 41 references it cites were found in a registry or an index.
Accelerating genetic algorithms with GPU computing: A selective overview
Abstract
The emergence of GPU-CPU heterogeneous architectures has led to a fundamental paradigm shift in parallel programming. Accelerating Genetic Algorithms (GAs) on these architectures has received significant attention from both practitioners and researchers ever since GPUs emerged. In the past decade we have witnessed many progresses on migrating parallel GAs from CPU to GPU (Graphical Processing Unit) architecture, which makes this research field truly enter into the world of High Performance Computing (HPC), and demonstrates a great potential to many research disciplines and industrial worlds that can benefit from the power of GPU accelerated stochastic global search to explore large and complex search spaces for better solutions. Designing a parallel algorithm on GPU is quite different from designing one on CPU. On CPU architecture, we typically consider how to distribute data across tens of CPU threads, while on GPU architecture, we have more than hundreds of thousands of GPU threads running simultaneously. Therefore, we should rethink the design approaches and implementation strategies of parallel algorithms to fully utilize the computing power of GPUs to accelerate the computation of GAs. The intention of this paper is to give an overview on selective works of parallel GAs designed for GPU architecture. In this survey paper, we first reexamine the concept of granularity of parallelism for GAs on GPU architecture, discuss how the aspect of data layout affect the kernel design to maximize memory bandwidth, and explain how to organize threads in grid and blocks to expose sufficient parallelism to GPU. The comprehensive overview on selective works since 2010 then follows. The focus is mainly on the perspective of GPU architecture: how to accelerate GAs with GPU computing. Performance issues are not touched in this review, because most of these works are conducted on very early GPU cards, which are out of date already. We finally discuss some future research suggestions in the last section, especially about how to build up an efficient implementation of parallel GAs for hyper-scale computing. Many industrial and academic disciplines will be benefited from the GPU accelerated parallel GAs, one of the promising area is to evolve better deep neural networks.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“standard CPUs consume generally up to 85 watts and standard GPUs consume between 200 watts to 500 watts [11] [12].”
From A Comprehensive Survey on TinyML (2023) · cites this paper as [11]
Citations
Cites
Evolving artificial neural networks
Yao, X. (1999) · Proceedings of the IEEE · doi:10.1109/5.784219 · Cited by 2,981
Genetic Algorithms and Engineering Optimization
Gen, M., & Cheng, R. (1999) · doi:10.1002/9780470172261 · Cited by 2,548
Self-citationGenetic Algorithms and Engineering Design
Gen, M., & Cheng, R. (1996) · Wiley eBooks · doi:10.1002/9780470172254 · Cited by 2,460
Self-citationA Survey of Parallel Genetic Algorithms
Cantú‐Paz, E. (2000) · Cited by 900
The master algorithm: how the quest for the ultimate learning machine will remake our world
(2016) · Choice Reviews Online · doi:10.5860/choice.194685 · Cited by 805
A tutorial survey of job-shop scheduling problems using genetic algorithms—I. representation
Cheng, R., Gen, M., & Tsujimura, Y. (1996) · Computers & Industrial Engineering · doi:10.1016/0360-8352(96)00047-2 · Cited by 635
Self-citationA Survey on the Parallel Genetic Algorithms
Nang, J., & Matsuo, K. (1994) · Jidō seigyo/Jido seigyo · Cited by 401
Xu, Y., Li, K., Hu, J., & Li, K. (2014) · Information Sciences · doi:10.1016/j.ins.2014.02.122 · Cited by 390
Burkard, R. E. (1984) · European Journal of Operational Research · doi:10.1016/0377-2217(84)90093-6 · Cited by 378
Professional CUDA C Programming
Cheng, J. R., Grossman, M., McKercher, T., & Chapman, B. (2014) · Cited by 371
Self-citationCheng, R., Gen, M., & Tsujimura, Y. (1999) · Computers & Industrial Engineering · doi:10.1016/s0360-8352(99)00022-4 · Cited by 323
Self-citationProceedings of the Genetic and Evolutionary Computation Conference
(2019) · doi:10.1145/3321707 · Cited by 319
Serial and Parallel Genetic Algorithms as Function Optimizers
Gordon, V. S., & Whitley, L. D. (1993) · Cited by 316
Cheng, R., Gen, M., & Tsujimura, Y. (1999) · Computers & Industrial Engineering · doi:10.1016/s0360-8352(99)00136-9 · Cited by 303
Self-citationHandbook of Combinatorial Optimization
Pardalos, P. M., Du, D., & Graham, R. L. (2013) · Springer eBooks · doi:10.1007/978-1-4419-7997-1 · Cited by 294
Alba, E., & Dorronsoro, B. (2008) · Operations research, computer science. Interface series · doi:10.1007/978-0-387-77610-1 · Cited by 284
Izzo, D., Ruciński, M., & Biscani, F. (2012) · Studies in computational intelligence · doi:10.1007/978-3-642-28789-3_7 · Cited by 106
GPU-based island model for evolutionary algorithms
Luong, T. V., Melab, N., & Talbi, E. (2010) · Genetic and Evolutionary Computation Conference (GECCO) · doi:10.1145/1830483.1830685 · Cited by 90
Theoretical Foundations of Order-Based Genetic Algorithms
Wróblewski, J. (1996) · Fundamenta Informaticae · doi:10.3233/fi-1996-283414 · Cited by 82
Parallel genetic algorithms: a survey and problem state of the art
Кныш, Д. С., & Курейчик, В. М. (2010) · Journal of Computer and Systems Sciences International · doi:10.1134/s1064230710040088 · Cited by 65
Solving very large instances of the scheduling of independent tasks problem on the GPU
Pinel, F., Dorronsoro, B., & Bouvry, P. (2012) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2012.02.018 · Cited by 63
Task Scheduling in Multiprocessor System Using Genetic Algorithm
Gupta, S., Kumar, V., & Agarwal, G. (2010) · International Conference on Machine Learning and Computing (ICMLC) · doi:10.1109/icmlc.2010.50 · Cited by 60
Parallelization of binary and real-coded genetic algorithms on GPU using CUDA
Arora, R., Tulshyan, R., & Deb, K. (2010) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2010.5586260 · Cited by 55
A multi-GPU implementation of a Cellular Genetic Algorithm
Vidal, P. J., & Alba, E. (2010) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2010.5586530 · Cited by 39
Multi-GPU island-based genetic algorithm for solving the knapsack problem
Jaroš, J. (2012) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2012.6256131 · Cited by 36
A Survey: Genetic Algorithms and the Fast Evolving World of Parallel Computing
Munawar, A., Wahib, M., Munetomo, M., & Akama, K. (2008) · IEEE International Conference on High Performance Computing and Communications; IEEE International Conference on Smart City; IEEE International Conference on Data Science and Systems (HPCC/SmartCity/DSS) · doi:10.1109/hpcc.2008.77 · Cited by 34
Parallel Genetic Algorithms: A Survey
Chipperfield, A. J., & Fleming, P. J. (1994) · White Rose Research Online (University of Leeds, The University of Sheffield, University of York) · Cited by 34
Bitwise operations for GPU implementation of genetic algorithms
Pedemonte, M., Alba, E., & Luna, F. (2011) · Genetic and Evolutionary Computation Conference Companion (GECCO Companion) · doi:10.1145/2001858.2002031 · Cited by 24
REVIEW OF PARALLEL GENETIC ALGORITHM BASED ON COMPUTING PARADIGM AND DIVERSITY IN SEARCH SPACE
Umbarkar, A. J., & Joshi, M. S. (2013) · ICTACT Journal on Soft Computing · doi:10.21917/ijsc.2013.0089 · Cited by 24
Holder functions and deception of genetic algorithms
Lutton, É., & Véhel, J. L. (1998) · IEEE Transactions on Evolutionary Computation · doi:10.1109/4235.728208 · Cited by 23
Architecture-based Performance Evaluation of Genetic Algorithms on Multi/Many-core Systems
Zheng, L., Lu, Y., Ding, M., Shen, Y., Guoz, M., & Guo, S. (2011) · IEEE International Conference on Computational Science and Engineering (CSE) · doi:10.1109/cse.2011.65 · Cited by 21
Genetic Algorithm Modeling with GPU Parallel Computing Technology
Cavuoti, S., Garofalo, M., Brescia, M., Pescapè, A., Longo, G., & Ventre, G. (2012) · Smart innovation, systems and technologies · doi:10.1007/978-3-642-35467-0_4 · Cited by 16
Zhao, Y., Chen, L., Xie, G., Zhao, J., & Ding, J. (2016) · Journal of Combinatorial Optimization · doi:10.1007/s10878-016-0007-y · Cited by 16
Gene pool recombination, genetic algorithm, and the onemax function
Mühlenbein, H., & Chakraborty, U. K. (1997) · Journal of Computing and Information Technology · Cited by 11
Gómez, E. C., Chaves, R. P., & Orlando Garcia, H. (2017) · Applied Mathematical Sciences · doi:10.12988/ams.2017.710319 · Cited by 9
Accelerating Genetic Algorithm for Solving Graph Coloring Problem Based on CUDA Architecture
Zhang, K., Qiu, M., Li, L., & Liu, X. (2014) · Communications in computer and information science · doi:10.1007/978-3-662-45049-9_95 · Cited by 7
A Fast Parallel Genetic Algorithm for Graph Coloring Problem Based on CUDA
Chen, B., Bo, C., Liu, H., & Zhang, X. (2015) · International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC) · doi:10.1109/cyberc.2015.33 · Cited by 6
Runtime Analysis of OneMax Problem in Genetic Algorithm
Du, Y., Ma, Q., Sakamoto, M., Furutani, H., & Zhang, Y. (2014) · Journal of Robotics Networking and Artificial Life · doi:10.2991/jrnal.2014.1.3.12 · Cited by 5
Research works printed but not linked: 4
- Dorronsoro, B., Arias, D., Luna, F., Nebro, A., Alba, E. (2007). A grid-based hybrid cellular genetic algorithm for very large scale instances of the CVRP. In: Smari, W. W. editor, High performance computing & simulation conference (pp. 759–765).
- Gruau, F. (1994). Neural Network Synthesis Using Cellular Encoding and the Genetic Algorithm. Unpublished doctoral dissertation, L’Universite Claude Bernard-Lyon I.
- Oiso, 2011, Implementation genetic algorithms to CUDA environment using data parallelization, The Journal Tehnički vjesnik, 18, 511
- Pinel, 2012, Solving very large instances of the scheduling of independent tasks problem on the GPU, Journal of Parallel and Distributed Computing, 16, 1
Cited by
A Comprehensive Survey on TinyML
Abadade, Y., Temouden, A., Bamoumen, H., Benamar, N., Chtouki, Y., & Hafid, A. S. (2023) · IEEE Access · doi:10.1109/access.2023.3294111 · Cited by 366
Variable neighborhood strategy adaptive search for solving green 2-echelon location routing problem
Pitakaso, R., Sethanan, K., & Theeraviriya, C. (2020) · Computers and Electronics in Agriculture · doi:10.1016/j.compag.2020.105406 · Cited by 49
Qualities, challenges and future of genetic algorithms: a literature reviewPreprint
Vié, A., Kleinnijenhuis, A. M., & Farmer, D. J. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2011.05277 · Cited by 48
Embedded Intelligence: State-of-the-Art and Research Challenges
Seng, K. P., & Ang, L.-M. (2022) · IEEE Access · doi:10.1109/access.2022.3175574 · Cited by 36
Aibibu, T., Lan, J., Zeng, Y., Lu, W.-J., & Gu, N. (2023) · Remote Sensing · doi:10.3390/rs16010025 · Cited by 35
Metadata
- Authors
- Cheng, J. R., & Gen, M.
- Affiliations
- Tokyo University of Science (JP)
- Corresponding author
- Cheng, John Runwei
- ORCID
- Gen, Mitsuo
- Venue
- Computers & Industrial Engineering
- Publisher
- Elsevier BV
- Published
- 2019-02
- Volume
- 128
- Pages
- 514-525
- ISSN
- 0360-8352 (ISSN-L)
- OpenAlex
- W2907478628
- Cited by
- 102
- References
- 41
- Citations by year
- 2026: 15 · 2025: 12 · 2024: 11 · 2023: 20 · 2022: 8 · 2021: 18 · 2020: 15 · 2019: 3
- FWCI
- 9.92
- Type
- journal article
- Language
- en
- Open access
- closed
- Licence
- www.elsevier.com/tdm/userlicense/1.0/ (tdm)
- Locations
- Computers & Industrial Engineering (publishedVersion)
- Funders
- National Natural Science Foundation of China (61572100)
- Japan Society of Promotion of Science (15K00357)
- Topics
- Physical Sciences › Computer Science › Hardware and Architecture › Parallel Computing and Optimization Techniques
- Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
- Physical Sciences › Computer Science › Artificial Intelligence › Evolutionary Algorithms and Applications
- Keywords
- genetic algorithm, GPU computing, parallel genetic algorithm, data layout, kernel design, memory bandwidth
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.