Distributed NSGA-II Sharing Extreme Non-dominated Solutions for Improving Accuracy and Achieving Speed-up
Yuji Sato, Mikiko Sato, Minami Miyakawa · 2019
A recent trend of multi-objective evolutionary algorithms is to approximate the Pareto optimal front with high accuracy by increasing the size of the population. On the other hand, the cconventional method NSGA-II algorithm widely used in multi-objective optimization ranks solutions using non-dominant sorting that increase in computational complexity proportional to the population size squared. In engineering applications, the increased execution time can be a problem. Also, even if standard techniques for parallel processing of genetic manipulation are applied to multi-objective evolutionary computation, it is difficult to speed up while maintaining the accuracy of the solution search. This paper proposes the distributed NSGA-II which performs a hierarchical non-dominated sorting in a many-core environment, and migration that shares the extreme solutions of the latest Pareto optimal solutions among all cores. In the evaluation, using the test functions provided by the NSGA-II source code and the constrained knapsack problem with two-objective and three- objective, we describe that our proposed method contributes to the improvement of solution diversity search and for enhancing solution accuracy and speeding up.