A Parallel Multi-Objective Dividing Rectangles Algorithm Based on Normalized Decomposition

Multi-objective optimization problems are common in real-world applications. However, the high computational complexity severely hinders their solution. Currently, multi-objective evolutionary algorithms are mostly used for their solving. Nevertheless, these methods usually contain random operations in the process of population initialization and evolution to maintain diversity, which leads to non-reproducibility and lacking the theoretical guarantee of global convergence. Therefore, a novel multi-objective Dividing Rectangles(DIRECT) algorithm is introduced based on decomposition strategy. In this algorithm, the original problem is decomposed into a series of subproblems by a normalized decomposition method that can better capture the complex frontier to reduce the computational complexity of the problem. Meanwhile, the Dividing Rectangles algorithm is used to simultaneously optimize the decomposed subproblems, and the generated candidate solutions are assigned to the corresponding subproblems based on the global association mechanism in the optimization process to better retain the good candidate solutions and improve the algorithm search efficiency. Finally, the convergence of the algorithm is demonstrated. To further improve the computational efficiency, a multi-level and multi-granularity parallel scheme based on the adaptive associative migration strategy is proposed, based on which the proposed algorithm is parallelized. Furthermore, the proposed algorithm and its parallel version are applied to several benchmark optimization problems, and the experimental results show that the proposed algorithm can obtain a Pareto set with better convergence and diversity than NSGA-II, and the parallel version can further improve the accuracy of Pareto frontier approximation while massively reducing the problem-solving time.