Decomposition-Based-Sorting and Angle-Based-Selection for Evolutionary Multiobjective and Many-Objective Optimization

摘要

Multiobjective evolutionary algorithm based on decomposition (MOEA/D) decomposes a multiobjective optimization problem (MOP) into a number of scalar optimization subproblems and then solves them in parallel. In many MOEA/D variants, each subproblem is associated with one and only one solution. An underlying assumption is that each subproblem has a different Pareto-optimal solution, which may not be held, for irregular Pareto fronts (PFs), e.g., disconnected and degenerate ones. In this paper, we propose a new variant of MOEA/D with sorting-and-selection (MOEA/D-SAS). Different from other selection schemes, the balance between convergence and diversity is achieved by two distinctive components, decomposition-based-sorting (DBS) and angle-based-selection (ABS). DBS only sorts L closest solutions to each subproblem to control the convergence and reduce the computational cost. The parameter L has been made adaptive based on the evolutionary process. ABS takes use of angle information between solutions in the objective space to maintain a more fine-grained diversity. In MOEA/D-SAS, different solutions can be associated with the same subproblems; and some subproblems are allowed to have no associated solution, more flexible to MOPs or many-objective optimization problems (MaOPs) with different shapes of PFs. Comprehensive experimental studies have shown that MOEA/D-SAS outperforms other approaches; and is especially effective on MOPs or MaOPs with irregular PFs. Moreover, the computational efficiency of DBS and the effects of ABS in MOEA/D-SAS are also investigated and discussed in detail.