A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> 1) IMPROVEMENT OF THE ORIGINAL DECOMPOSITION METHODS <s> MOEA/D is one of the promising evolutionary approaches for solving multi and many-objective optimization problems. MOEA/D decomposes a multi-objective optimization problem into a number of single objective optimization problems. Each single objective optimization problem is defined by a scalarizing function using a weight vector. In MOEA/D, there are several scalarizing approaches such as weighted Tchebycheff, reciprocal weighted Tchebycheff, weighted sum (WS) and penalty-based boundary intersection (PBI). Each scalarizing function has a characteristic effect on the search performance of MOEA/D and provides a scenario of multi-objective solution search. To improve the availability of MOEA/D framework for solving various kinds of problems, it is important to provide a new scalarizing function which has different characteristics from the conventional scalarizing functions. In particular, the conventional scalarizing approaches face a difficulty to approximate a widely spread Pareto front in some problems. To approximate the entire Pareto front by improving the spread of solutions in the objective space and enhance the search performance of MOEA/D in multi and many-objective optimization problems, in this work we propose the inverted PBI scalarizing approach which is an extension of the conventional PBI and WS. In this work, we analyze differences between inverted PBI and other scalarizing functions, and compare the search performances of NSGA-III and five MOEA/Ds using weighted Tchebycheff, reciprocal weighted Tchebycheff, WS, PBI and inverted PBI in many-objective knapsack problems and WFG4 problems with 2---8 objectives. As results, we show that the inverted PBI based MOEA/D achieves higher search performance than other algorithms in problems with many-objectives and the difficulty to approximate a widely spread Pareto front in the objective space. Also, we show the robustness of the inverted PBI on Pareto front geometry by using problems with four representative concave, linear, convex and discontinuous Pareto fronts. <s> BIB001 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> 1) IMPROVEMENT OF THE ORIGINAL DECOMPOSITION METHODS <s> A decomposition approach decomposes a multiobjective optimization problem into a number of scalar objective optimization subproblems. It plays a key role in decomposition-based multiobjective evolutionary algorithms. However, many widely used decomposition approaches, originally proposed for mathematical programming algorithms, may not be very suitable for evolutionary algorithms. To help decomposition-based multiobjective evolutionary algorithms balance the population diversity and convergence in an appropriate manner, this letter proposes to impose some constraints on the subproblems. Experiments have been conducted to demonstrate that our proposed constrained decomposition approach works well on most test instances. We further propose a strategy for adaptively adjusting constraints by using information collected from the search. Experimental results show that it can significantly improve the algorithm performance. <s> BIB002 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> 1) IMPROVEMENT OF THE ORIGINAL DECOMPOSITION METHODS <s> It has been increasingly reported that the multiobjective optimization evolutionary algorithm based on decomposition (MOEA/D) is promising for handling multiobjective optimization problems (MOPs). MOEA/D employs scalarizing functions to convert an MOP into a number of single-objective subproblems. Among them, penalty boundary intersection (PBI) is one of the most popular decomposition approaches and has been widely adopted for dealing with MOPs. However, the original PBI uses a constant penalty value for all subproblems and has difficulties in achieving a good distribution and coverage of the Pareto front for some problems. In this paper, we investigate the influence of the penalty factor on PBI, and suggest two new penalty schemes, i.e., adaptive penalty scheme and subproblem-based penalty scheme (SPS), to enhance the spread of Pareto-optimal solutions. The new penalty schemes are examined on several complex MOPs, showing that PBI with the use of them is able to provide a better approximation of the Pareto front than the original one. The SPS is further integrated into two recently developed MOEA/D variants to help balance the population diversity and convergence. Experimental results show that it can significantly enhance the algorithm’s performance. <s> BIB003 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> 1) IMPROVEMENT OF THE ORIGINAL DECOMPOSITION METHODS <s> Abstract Penalty-based boundary intersection (PBI) method is a frequently used scalarizing method in decomposition based multi-objective evolutionary algorithms (MOEAs). It works well when a proper penalty value is provided, however, the determination of a suitable penalty value depends on the problem itself, more precisely, the Pareto optimal front (PF) shape. As the penalty value increases, the PBI method becomes less effective in terms of convergence, but is more capable of handling various PF shapes. In this study, a simple yet effective method called Pareto adaptive PBI ( PaP ) is proposed by which a suitable penalty value can be adaptively identified, which therefore can maintain fast convergence speed, meanwhile, leading to a good approximation of the PF. The PaP strategy integrated into the state-of-the-art decomposition algorithm, MOEA/D, denoted as MOEA/D-PaP, is examined on a set of multi-objective benchmarks with different PF shapes. Experimental results show that the PaP strategy is more effective than the weighted sum, the weighted Tchebycheff and the PBI method with (representative) fixed penalty values in general. In addition, the MOEA/D-PaP is examined on a real-world problem – multi-objective optimization of a hybrid renewable energy system whose PF is unknown. The outcome of the experiment further confirms its feasibility and superiority. <s> BIB004 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> 1) IMPROVEMENT OF THE ORIGINAL DECOMPOSITION METHODS <s> Decomposition-based multiobjective evolutionary algorithms (MOEAs) decompose a multiobjective optimization problem (MOP) into a set of scalar objective subproblems and solve them in a collaborative way. Commonly used decomposition approaches originate from mathematical programming and the direct use of them may not suit MOEAs due to their population-based property. For instance, these decomposition approaches used in MOEAs may cause the loss of diversity and/or be very sensitive to the shapes of Pareto fronts (PFs). This paper proposes a constrained decomposition with grids (CDG) that can better address these two issues thus more suitable for MOEAs. In addition, different subproblems in CDG defined by the constrained decomposition constitute a grid system. The grids have an inherent property of reflecting the information of neighborhood structures among the solutions, which is a desirable property for restricted mating selection in MOEAs. Based on CDG, a constrained decomposition MOEA with grid (CDG-MOEA) is further proposed. Extensive experiments are conducted to compare CDG-MOEA with the domination-based, indicator-based, and state-of-the-art decomposition-based MOEAs. The experimental results show that CDG-MOEA outperforms the compared algorithms in terms of both the convergence and diversity. More importantly, it is robust to the shapes of PFs and can still be very effective on MOPs with complex PFs (e.g., extremely convex, or with disparately scaled objectives). <s> BIB005 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> 1) IMPROVEMENT OF THE ORIGINAL DECOMPOSITION METHODS <s> Tchebycheff decomposition represents one of the most widely used decomposition approaches that can convert a multiobjective optimization problem into a set of scalar optimization subproblems. Nevertheless, the geometric properties of the subproblem objective functions in Tchebycheff decomposition have not been explicitly studied. This paper proposes a Tchebycheff decomposition with ${l_{p}}$ -norm constraint on direction vectors in which the subproblem objective functions are endowed with clear geometric property. Especially, the Tchebycheff decomposition with ${l_{2}}$ -norm constraint on direction vectors is taken as an example to illustrate its advantage. A new unary ${R_{2}}$ indicator is also introduced to approximate the hyper-volume metric and justify the efficiency of the proposed Tchebycheff decomposition. A resultant Tchebycheff decomposition-based multiobjective evolutionary algorithm (MOEA) with ${l_{2}}$ -norm constraint and a new population update strategy is proposed to solve multiobjective optimization problems. The experimental results on both benchmark and real-world multiobjective optimization problems show that the proposed algorithm is capable of obtaining high quality solutions compared with other state-of-the-art MOEAs. <s> BIB006 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> 1) IMPROVEMENT OF THE ORIGINAL DECOMPOSITION METHODS <s> Decomposition-based multiobjective evolutionary algorithms (MOEAs) have received increasing research interests due to their high performance for solving multiobjective optimization problems. However, scalarizing functions (SFs), which play a crucial role in balancing diversity and convergence in these kinds of algorithms, have not been fully investigated. This paper is mainly devoted to presenting two new SFs and analyzing their effect in decomposition-based MOEAs. Additionally, we come up with an efficient framework for decomposition-based MOEAs based on the proposed SFs and some new strategies. Extensive experimental studies have demonstrated the effectiveness of the proposed SFs and algorithm. <s> BIB007
The original PBI decomposition method becomes unreliable if the obtained reference point is far from the ideal point, then we could not get the expected PF. An inverted PBI (IPBI) decomposition method was presented in BIB001 , which is an extension of conventional PBI and WS. PBI evolves solutions toward the reference point by minimizing the scalarizing function value. Contrarily, IPBI evolves solutions from the worst objective vector in the current population by maximizing the scalarizing function value, i.e., a solution with a larger d 1 is considered a better solution close to the PF, where d 1 denotes the distance between the reference point and the projection of Pareto optimal (objective) vector in the weight vector direction. IPBI can conduct a wide range of searches on the objective space that WS cannot reach, thus enabling the PF to be disseminated widely. Yang et al. BIB003 studied the impact of the penalty factor in PBI on algorithm performance, which is not considered in BIB001 . The results concluded that a smaller factor is needed for a faster convergence during the early search, while a larger factor is required to maintain population diversity at the later search stage. Then, two new penalty schemes, adaptive penalty scheme (APS) and subproblem-based penalty scheme (SPS), were suggested to adaptively adjust the penalty factor in the algorithm at different search stages, which can significantly improve the algorithm performance. Ming et al. BIB004 proposed a simple and effective method called Pareto adaptive PBI (PaP) to adjust the penalty factor online according to the approximated PF shape and PBI decomposition method contours. Specifically, an appropriate θ value is identified from a set of factor candidates, i.e., the optimal solution obtained by the PBI method with this value is closer to the weight vector compared with the same method with other θ values. The effectiveness of the PaP method was verified on a real-world problem, i.e., the design of a hybrid renewable energy system with an unknown PF. Another improvement over the original decomposition method is to reduce the volume of the improvement region, which is determined by the current solution, the optimal solution, and the contour of a subproblem, thus promoting population diversity. In Refs. BIB002 and BIB005 , the improvement region of the solution x i for the subproblem i in the objective space was defined as the set of all solution vectors that are better than the x i vector, and indicated that a larger one can decrease population diversity, i.e., a better new solution could replace several different old solutions, resulting in the same solution for several different subproblems. To address this issue, various improved MOEA/D algorithms were proposed. Wang et al. BIB002 proposed an adaptively constrained decomposition (ACD) approach, which adds constraints on unconstrained subproblems and uses a parameter θ to control the improvement region size of each subproblem, making it much smaller than the original one. Also, the approach adaptively adjusts θ to maintain a balance between population diversity and convergence. Cai et al. BIB005 presented a constrained decomposition with grids (CDG), in which the objective space is divided into multiple grids. Each subproblem has a grid coordinate and a neighbor defined by the grid distance between two solutions, which is simple and intuitive. The grid system is renewed by updating the ideal point and nadir point to evolve the solution mapping vectors toward the PF. The proposed decomposition method can effectively reduce the improvement region and has strong robustness to the PF shape. Combining the mathematical idea with the original decomposition method, Ma et al. BIB006 proposed Tchebycheff decomposition with L p norm constraint (p-TCH) on the direction vector, where the objective function of each subproblem has clear geometric properties. On the basis of such properties, a generalized subproblem objective function can be defined, and it is then possible to adjust the weights or significances of subproblems in competition, mainly by changing the p value to accommodate the preference region of each subproblem. Therefore, more update chances can be assigned to some subproblems to which users pay more attention, accelerating their convergence. Jiang et al. BIB007 presented two new decomposition methods with adjustable contours or improvement regions, namely the multiplicative scalarizing function (MSF) and penalty-based scalarizing function (PSF), both of which use a parameter α to control the improvement region of each subproblem. The influence of α on the improvement region was investigated through simulation experiments, and the results showed that the size of the improvement region decreases with the increase of α and both methods degenerate to TCH when α = 0. Population diversity can be well guaranteed by changing α for different subproblems.