Distributed NSGA-II Sharing Extreme Non-Dominated Solutions for Constrained Knapsack Problems

摘要

A recent trend in multiobjective evolutionary algorithms is to increase the population size to approximate the Pareto front with high accuracy. On the other hand, the NSGA-II algorithm widely used in multiobjective optimization performs non-dominated sorting in solution ranking, which means an increase in computational complexity proportional to the square of the population. This execution time becomes a problem in engineering applications. It is also difficult to achieve high speeds while maintaining the accuracy of solution searching by simply applying fast, parallel processing to standard genetic operations. In this paper, we propose NSGA-II distributed processing in a many-core environment and a migration method that shares extreme Pareto solutions of the current generation among all cores after performing compensation of the non-dominated solution set obtained by distributed processing. Using typical real-valued functions and a two-objective and three-objective constrained knapsack problem for evaluation, we show that the proposed method is effective in improving diversity in solution searching while shortening execution time and increasing the accuracy of solution searching for both real-valued functions and discrete optimization problems.