A Multiobjective Evolutionary Algorithm Based On Decomposition And Sorting

Due to the population-based nature of evolutionary algorithms that is able to approximate a Pareto set in a single run, multi-objective evolutionary algorithms(MOEAs) have become prevalent and efficient approaches for solving multi-objective optimization problems(MOPs). This paper incorporates the methods of decomposition and sorting into the framework of multi-objective evolutionary algorithms to solve multi-objective optimization problems. The paper mainly includes the following parts.First, multiobjective evolutionary algorithm based on decomposition(MOEA/D) decomposes a multiobjective optimization problem into a number of scalar optimization subproblems and then solves them in parallel. To better balance the convergence and diversity during the evolutionary process, we propose a new selection method, which sorts the solutions based on their ensemble convergence performance, then selects the solutions based on diversity. The selection method is integrated into MOEA/D. The proposed algorithm is compared with three classical MOEAs and one state-of-art MOEA. The results indicate that our proposed algorithm is very competitive.Second, in MOEA/D and most of its 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 some special Pareto fronts(PFs), e.g., disconnected and incomplete ones. In this paper, we propose a new variant of MOEA/D, multiobjective evolutionary algorithm based on decomposition with sorting-and-selection(MOEA/D-SAS). In MOEA/D-SAS, different solutions can be associated with the same subproblem; and some subproblems are allowed to have no associated solution, more flexible to multiobjective optimization problems(MOPs) with different shapes of PFs. 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). To reduce its computational cost, DBS only conducts sorting among the local neighboring solutions for each subproblem; and ABS takes use of angle information between solutions in the objective space to maintain a more fine-grained diversity. Comprehensive experimental studies have shown that MOEA/D-SAS outperforms other approaches; and is especially effective on MOPs with disconnected and incomplete Pareto fronts. Moreover, the computational efficiency of DBS and the effects of ABS in MOEA/D-SAS are also investigated and discussed in details.