Improving the Energy Efficiency of Evolutionary Multi-objective Algorithms

Problems for which many objective functions have to be simultaneously optimized can be easily found in many fields of science and industry. Solving this kind of problems in a reasonable amount of time while taking into account the energy efficiency is still a relevant task. Most of the evolutionary multi-objective optimization algorithms based on parallel computing are focused only on performance. In this paper, we propose a parallel implementation of the most time consuming parts of the Evolutionary Multi-Objective algorithms with major attention to energy consumption. Specifically, we focus on the most computationally expensive part of the state-of-the-art evolutionary NSGA-II algorithm the Non-Dominated Sorting (NDS) procedure. GPU platforms have been considered due to their high acceleration capacity and energy efficiency. A new version of NDS procedure is proposed (referred to as EFNDS). A made-to-measure data structure to store the dominance information has been designed to take advantage of the GPU architecture. NSGA-II based on EFNDS is comparatively evaluated with another state-of-art GPU version, and also with a widely used sequential version. In the evaluation we adopt a benchmark that is scalable in the number of objectives as well as decision variables (the DTLZ test suite) using a large number of individuals (from 500 up to 30000). The results clearly indicate that our proposal achieves the best performance and energy efficiency for solving large scale multi-objective optimization problems on GPU.