A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> 1) METHODS BASED ON UNIFORM DESIGN <s> The 0/1 knapsack problem is a well known problem occurring in many real world problems. The problem is NP-complete. The multiobjective 0/1 knapsack problem is a generalization of the 0/1 knapsack problem in which multiple knapsacks are considered. A new version of MOEA/D for solving multiobjective 0/1 knapsack problem is proposed in this paper. This algorithm adopts the uniform design method to generate the aggregation coefficient vectors so that the decomposed scalar optimization sub problems are uniformly scattered, and therefore the algorithm could explore uniformly the region of interest from the initial iteration. Experimental results demonstrate that the proposed algorithm outperforms NSGA-II, SPEA2 and PESA significantly for the 2-objective, 3-objective and 4-objective benchmark knapsack problems. <s> BIB001 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> 1) METHODS BASED ON UNIFORM DESIGN <s> In order to exploit the enhancement of the multi-objective evolutionary algorithm based on decomposition (MOEA/D), we propose an improved algorithm with uniform design (UD), i.e. MOEA/D-UD. Three mechanisms in MOEA/D-UD are modified by introducing an experimental design method called UD. To fully employ the information contained in the domain of the multi-objective problem, we apply UD to initialize a uniformly scattered population. Then, motivated by the analysis of the relationship between weight vectors and optimal solutions of scalar subproblems in the study of MOEA/D with adaptive weight adjustment (MOEA/D-AWA), a new weight vector design method based on UD is introduced. To distinguish real sparse regions from pseudo sparse regions, i.e. discontinuous regions, of the complex Pareto front, the weight vector adjustment strategy in MOEA/D-UD adequately utilizes the information from neighbors of individuals. In the experimental study, we compare MOEA/D-UD with three outstanding algorithms, namely MOEA/D with the differential evolution operator (MOEA/D-DE), MOEA/D-AWA and the nondominated sorting genetic algorithm II (NSGA-II) on nineteen test instances. The experimental results show that MOEA/D-UD is capable of obtaining a well-converged and well diversified set of solutions within an acceptable execution time. <s> BIB002
The goal of these methods is to make weight vectors be distributed more uniformly in the objective spaces. Zhang et al. BIB002 introduced a uniform design method into MOEA/D and named the resulting algorithm as MOEA/D-UD, which initializes the population and weight vectors based on the mixed uniform experiment, and could uniformly explore the region of interest (ROI) of DMs from the initial iteration. The proposed weight vector adjustment strategy makes full use of the information on neighboring individuals to identify crowding regions and sparse regions for the complex PF, and then a PF distributed uniformly is found by removing weight vectors from and adding weight vectors into two regions, respectively. Compared with three outstanding algorithms, namely, NSGA-II, MOEA/D-DE, and MOEA/D-AWA (adaptive weight vector adjustment) on 19 test instances, MOEA/D-UD can obtain a well-converged and diversified solution set within an acceptable execution time. To solve the 0/1 knapsack problem that has been proved to be NP-complete, Tan et al. BIB001 embedded the so-called good lattice point (GLP) in the MOEA/D framework, and termed the resulting algorithm as uniform design multiobjective evolutionary algorithm based on decomposition (UMOEA/D), which determines a set of weight vectors distributed uniformly and thus disperses the decomposed scalar optimization subproblems evenly. GLP first constructs a lattice point set S N with the smallest discrepancy among all possible generating vectors over the design ROI. Then N weight vectors scattered uniformly are obtained by using S N under certain restrictions. Experimental results indicated that the proposed algorithm significantly outperforms the NSGA-II, SPEA2, and PESA.