MOEA/D Using Constant-Distance Based Neighbors Designed for Many-Objective Optimization


Abstract

Several recent studies showed the effectiveness of MOEA/D for many-objective optimization. However, MOEA/D was originally proposed not for many-objective optimization but for multi-objective optimization. Therefore, its algorithm causes several problems in many-objective optimization. MOEA/D uses the neighbor mating, and neighbors are determined by the user-defined neighbors' size T. For each weight vector which determines a search direction in the objective space, MOEA/D calculates distances to all weights and find T nearest weights as its neighbors. However, the number of weights having the same distance is increased as the number of objectives is increased, and MOEA/D faces the difficulty to determine neighbors by the neighbors' size T in many-objective optimization. Also, especially for the extreme weights to search the extreme objective function values, weights far from them are included as their neighbors. It causes a negative effect on the search of the extreme objective values. To overcome these problems and enhance the search performance of MOEA/D by improving its algorithm appropriately for many-objective optimization, in this work we focus on the handling of neighbors and propose an improved MOEA/D including the constant-distance based neighbors and the tournament selection based on the scalarizing function values. We use many-objective knapsack problems with 2-8 objectives and compare the search performances of the conventional MOEA/D, the improved MOEA/D and NSGA-III. As the results, we show that the improved MOEA/D achieves higher search performance than the conventional MOEA/D and NSGA-III by improving the diversity of the obtained solutions in the objective space.