GPU-accelerated Evolutionary Multiobjective Optimization Using Tensorized RVEA
Authors: 
Zhenyu Liang, 
Tao Jiang, Kebin Sun, Ran ChengAuthors Info & Claims
Pages 566 - 575
Abstract
Evolutionary multiobjective optimization has witnessed remarkable progress during the past decades. However, existing algorithms often encounter computational challenges in large-scale scenarios, primarily attributed to the absence of hardware acceleration. In response, we introduce a Tensorized Reference Vector Guided Evolutionary Algorithm (TensorRVEA) for harnessing the advancements of GPU acceleration. In TensorRVEA, the key data structures and operators are fully transformed into tensor forms for leveraging GPU-based parallel computing. In numerical benchmark tests involving large-scale populations and problem dimensions, TensorRVEA consistently demonstrates high computational performance, achieving up to over 1000× speedups. Then, we applied TensorRVEA to the domain of multiobjective neuroevolution for addressing complex challenges in robotic control tasks. Furthermore, we assessed TensorRVEA's extensibility by altering several tensorized reproduction operators. Experimental results demonstrate promising scalability and robustness of TensorRVEA. Source codes are available at https://github.com/EMI-Group/tensorrvea.
Supplemental Material
PDF File
Supplementary Material
- Download
- 646.12 KB
References
[1]
Anton Aguilar-Rivera. 2020. A GPU Fully Vectorized Approach to Accelerate Performance of NSGA-2 Based on Stochastic Non-Domination Sorting and Grid-Crowding. Applied Soft Computing 88 (March 2020), 106047.
[2]
Lucas N. Alegre, Florian Felten, El-Ghazali Talbi, Grégoire Danoy, Ann Nowé, Ana L. C. Bazzan, and Bruno C. da Silva. 2022. MO-Gym: A Library of Multi-Objective Reinforcement Learning Environments. In Proceedings of the 34th Benelux Conference on Artificial Intelligence BNAIC/Benelearn 2022.
[3]
Johannes Bader and Eckart Zitzler. 2011. HypE: An Algorithm for Fast Hypervolume-Based Many-Objective Optimization. Evolutionary Computation 19, 1 (March 2011), 45--76.
[4]
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang. 2018. JAX: composable transformations of Python+NumPy programs. http://github.com/google/jax
[5]
Ran Cheng and Yaochu Jin. 2015. A Competitive Swarm Optimizer for Large Scale Optimization. IEEE Transactions on Cybernetics 45, 2 (2015), 191--204.
[6]
Ran Cheng, Yaochu Jin, Markus Olhofer, and Bernhard Sendhoff. 2016. A Reference Vector Guided Evolutionary Algorithm for Many-Objective Optimization. IEEE Transactions on Evolutionary Computation 20, 5 (Oct. 2016), 773--791.
[7]
Ran Cheng, Tobias Rodemann, Michael Fischer, Markus Olhofer, and Yaochu Jin. 2017. Evolutionary many-objective optimization of hybrid electric vehicle control: From general optimization to preference articulation. IEEE Transactions on Emerging Topics in Computational Intelligence 1, 2 (2017), 97--111.
[8]
Carlos A Coello Coello and Nareli Cruz Cortés. 2005. Solving multiobjective optimization problems using an artificial immune system. Genetic Programming and Evolvable Machines 6 (2005), 163--190.
[9]
Kalyanmoy Deb, Ram Bhushan Agrawal, et al. 1995. Simulated binary crossover for continuous search space. Complex Systems 9, 2 (1995), 115--148.
[10]
Kalyanmoy Deb, Mayank Goyal, et al. 1996. A combined genetic adaptive search (GeneAS) for engineering design. Computer Science and informatics 26 (1996), 30--45.
[11]
Kalyanmoy Deb, Mayank Goyal, et al. 1996. A Combined Genetic Adaptive Search (GeneAS) for Engineering Design. Computer Science and Informatics 26 (1996), 30--45.
[12]
Kalyanmoy Deb and Himanshu Jain. 2014. An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints. IEEE Transactions on Evolutionary Computation 18, 4 (Aug. 2014), 577--601.
[13]
K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. 2002. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6, 2 (April 2002), 182--197.
[14]
Kalyanmoy Deb, Lothar Thiele, Marco Laumanns, and Eckart Zitzler. 2005. Scalable Test Problems for Evolutionary Multiobjective Optimization. In Evolutionary Multiobjective Optimization, Ajith Abraham, Lakhmi Jain, and Robert Goldberg (Eds.). Springer-Verlag, London, 105--145.
[15]
Roman Denysiuk, António Gaspar-Cunha, and Alexandre C.B. Delbem. 2019. Neuroevolution for Solving Multiobjective Knapsack Problems. Expert Systems with Applications 116 (Feb. 2019), 65--77.
[16]
Russell Eberhart and James Kennedy. 1995. A new optimizer using particle swarm theory. In MHS'95. Proceedings of the sixth international symposium on micro machine and human science. IEEE, 39--43.
[17]
C. Daniel Freeman, Erik Frey, Anton Raichuk, Sertan Girgin, Igor Mordatch, and Olivier Bachem. 2021. Brax - A Differentiable Physics Engine for Large Scale Rigid Body Simulation. http://github.com/google/brax
[18]
Masoud Gheitasi, Hesam Seyed Kaboli, and Alireza Keramat. 2021. Multi-objective optimization of water distribution system: a hybrid evolutionary algorithm. Journal of Applied Water Engineering and Research 9, 3 (2021), 203--215.
[19]
David E Goldberg. 1989. Genetic Algorithms in Search, Optimization and Machine Learning.
[20]
Samarth Gupta and Gary Tan. 2015. A Scalable Parallel Implementation of Evolutionary Algorithms for Multi-Objective Optimization on GPUs. In 2015 IEEE Congress on Evolutionary Computation (CEC). IEEE, Sendai, Japan, 1567--1574.
[21]
Jiang Hao, Jixin Liu, Sijie Lan, and Zhiwei Wang. 2022. Many-objective optimization scheduling method of arrival flights. In Sixth International Conference on Electromechanical Control Technology and Transportation (ICECTT 2021), Qingsehng Zeng (Ed.), Vol. 12081. International Society for Optics and Photonics, SPIE, 120812I.
[22]
Kaibin Hu, Cheng Lu, Bocheng Yu, Li Yang, and Yu Rao. 2023. Optimization of Bionic Heat Sinks with Self-Organized Structures Inspired by Termite Nest Morphologies. International Journal of Heat and Mass Transfer 202 (2023), 123735.
[23]
Beichen Huang, Ran Cheng, Zhuozhao Li, Yaochu Jin, and Kay Chen Tan. 2024. EvoX: A Distributed GPU-accelerated Framework for Scalable Evolutionary Computation. IEEE Transactions on Evolutionary Computation (2024).
[24]
Yuwang Ji, Qiang Wang, Xuan Li, and Jie Liu. 2019. A Survey on Tensor Techniques and Applications in Machine Learning. IEEE Access 7 (2019), 162950--162990.
[25]
Robert Tjarko Lange. 2023. evosax: JAX-Based Evolution Strategies. In Proceedings of the Companion Conference on Genetic and Evolutionary Computation (Lisbon, Portugal) (GECCO '23 Companion). Association for Computing Machinery, New York, NY, USA, 659--662.
[26]
Si-Chao Lei, Xiaolin Xiao, Yue-Jiao Gong, Yun Li, and Jun Zhang. 2024. Tensorial Evolutionary Computation for Spatial Optimization Problems. IEEE Transactions on Artificial Intelligence 5, 1 (Jan. 2024), 154--166.
[27]
David Luebke. 2008. CUDA: Scalable parallel programming for high-performance scientific computing. In 2008 5th IEEE International Symposium on Biomedical Imaging: From Nano to Macro. 836--838.
[28]
Bashista Kumar Mahanta, Rajesh Jha, and Nirupam Chakraborti. 2022. Data-driven optimization of blast furnace iron making process using evolutionary deep learning. Machine Learning in Industry (2022), 47--81.
[29]
Amir Nuhanović, Jasna Hivziefendić, and Amir Hadžimehmedović. 2013. Distribution network reconfiguration considering power losses and outages costs using genetic algorithm. Journal of Electrical Engineering 64, 5 (2013), 265--271.
[30]
John D. Owens, Mike Houston, David Luebke, Simon Green, John E. Stone, and James C. Phillips. 2008. GPU Computing. Proc. IEEE 96, 5 (2008), 879--899.
[31]
Qingfu Zhang and Hui Li. 2007. MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition. IEEE Transactions on Evolutionary Computation 11, 6 (Dec. 2007), 712--731.
[32]
Shubhkirti Sharma and Vijay Kumar. 2022. A Comprehensive Review on Multi-objective Optimization Techniques: Past, Present and Future. Archives of Computational Methods in Engineering 29, 7 (Nov. 2022), 5605--5633.
[33]
Murilo Zangari De Souza and Aurora Trinidad Ramirez Pozo. 2014. A GPU Implementation of MOEA/D-ACO for the Multiobjective Traveling Salesman Problem. In 2014 Brazilian Conference on Intelligent Systems. IEEE, Sao Paulo, Brazil, 324--329.
[34]
Kenneth O Stanley, Jeff Clune, Joel Lehman, and Risto Miikkulainen. 2019. Designing neural networks through neuroevolution. Nature Machine Intelligence 1, 1 (2019), 24--35.
[35]
Fergal Stapleton, Edgar Galván, Ganesh Sistu, and Senthil Yogamani. 2022. Neuroevolutionary Multi-Objective Approaches to Trajectory Prediction in Autonomous Vehicles. In Proceedings of the Genetic and Evolutionary Computation Conference Companion. ACM, Boston Massachusetts, 675--678.
[36]
Rainer Storn and Kenneth Price. 1997. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. Journal of global optimization 11 (1997), 341--359.
[37]
Yujin Tang, Yingtao Tian, and David Ha. 2022. EvoJAX: hardware-accelerated neuroevolution. In Proceedings of the Genetic and Evolutionary Computation Conference Companion (Boston, Massachusetts) (GECCO '22). Association for Computing Machinery, New York, NY, USA, 308--311.
[38]
Ye Tian, Ran Cheng, Xingyi Zhang, and Yaochu Jin. 2017. PlatEMO: A MATLAB Platform for Evolutionary Multi-Objective Optimization [Educational Forum]. IEEE Computational Intelligence Magazine 12, 4 (Nov. 2017), 73--87.
[39]
Ye Tian, Langchun Si, Xingyi Zhang, Ran Cheng, Cheng He, Kay Chen Tan, and Yaochu Jin. 2022. Evolutionary Large-Scale Multi-Objective Optimization: A Survey. Comput. Surveys 54, 8 (Nov. 2022), 1--34.
[40]
Qingzhu Wang, Lingling Zhang, Shuang Wei, and Bin Li. 2021. Tensor Decomposition-Based Alternate Sub-Population Evolution for Large-Scale Many-Objective Optimization. Information Sciences 569 (Aug. 2021), 376--399.
[41]
Qingzhu Wang, Lingling Zhang, Shuang Wei, Bin Li, and Yang Xi. 2022. Tensor Factorization-Based Particle Swarm Optimization for Large-Scale Many-Objective Problems. Swarm and Evolutionary Computation 69 (March 2022), 100995.
[42]
Man Leung Wong. 2009. Parallel Multi-Objective Evolutionary Algorithms on Graphics Processing Units. In Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers. ACM, Montreal Québec Canada, 2515--2522.
[43]
Jie Xu, Yunsheng Tian, Pingchuan Ma, Daniela Rus, Shinjiro Sueda, and Wojciech Matusik. 2020. Prediction-Guided Multi-Objective Reinforcement Learning for Continuous Robot Control. In Proceedings of the 37th International Conference on Machine Learning.
[44]
Shuguang Zhang, Wenku Shi, and Zhiyong Chen. 2021. Modeling and parameter identification of seated human body with the reference vector guided evolutionary algorithm. Advances in Mechanical Engineering 13, 11 (2021).
[45]
Xia Zhang, Bei Ding, Ran Cheng, Sebastian C. Dixon, and Yao Lu. 2018. Computational Intelligence-Assisted Understanding of Nature-Inspired Superhydrophobic Behavior. Advanced Science 5, 1 (Jan. 2018), 1700520.
[46]
Luisa M Zintgraf, Timon V Kanters, Diederik M Roijers, Frans Oliehoek, and Philipp Beau. 2015. Quality assessment of MORL algorithms: A utility-based approach. In Benelearn 2015: proceedings of the 24th annual machine learning conference of Belgium and the Netherlands.
[47]
Eckart Zitzler and Simon Künzli. 2004. Indicator-Based Selection in Multiobjective Search. In Parallel Problem Solving from Nature - PPSN VIII, David Hutchison, Takeo Kanade, Josef Kittler, Jon M. Kleinberg, Friedemann Mattern, John C. Mitchell, Moni Naor, Oscar Nierstrasz, C. Pandu Rangan, Bernhard Steffen, Madhu Sudan, Demetri Terzopoulos, Dough Tygar, Moshe Y. Vardi, Gerhard Weikum, Xin Yao, Edmund K. Burke, José A. Lozano, Jim Smith, Juan Julián Merelo-Guervós, John A. Bullinaria, Jonathan E. Rowe, Peter Tiňo, Ata Kabán, and Hans-Paul Schwefel (Eds.). Vol. 3242. Springer Berlin Heidelberg, Berlin, Heidelberg, 832--842.
[48]
E. Zitzler and L. Thiele. 1999. Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Transactions on Evolutionary Computation 3, 4 (1999), 257--271.
Index Terms
- GPU-accelerated Evolutionary Multiobjective Optimization Using Tensorized RVEA
Recommendations
Convergence acceleration operator for multiobjective optimization
A convergence acceleration operator (CAO) is described which enhances the search capability and the speed of convergence of the host multiobjective optimization algorithm. The operator acts directly in the objective space to suggest improvements to ...
GECCO 2016 Tutorial on Evolutionary Multiobjective Optimization
GECCO '16 Companion: Proceedings of the 2016 on Genetic and Evolutionary Computation Conference CompanionMany optimization problems are multiobjective in nature in the sense that multiple, conflicting criteria need to be optimized simultaneously. Due to the conflict between objectives, usually, no single optimal solution exists. Instead, the optimum ...
GECCO 2012 tutorial on evolutionary multiobjective optimization
GECCO '12: Proceedings of the 14th annual conference companion on Genetic and evolutionary computationMany optimization problems are multiobjective in nature in the sense that multiple, conflicting criteria need to be optimized simultaneously. Due to the conflict between objectives, usually, no single optimal solution exists. Instead, the optimum ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2024
1657 pages
Copyright © 2024 Copyright is held by the owner/author(s). Publication rights licensed to 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 the author(s) 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].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 14 July 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
GECCO '24
Sponsor:
GECCO '24: Genetic and Evolutionary Computation Conference
July 14 - 18, 2024
VIC, Melbourne, Australia
Acceptance Rates
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 62Total Downloads
- Downloads (Last 12 months)62
- Downloads (Last 6 weeks)7
Reflects downloads up to 13 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in