A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> 5) SUMMARY <s> It is well-known that multiobjective problems with many objectives are difficult for Pareto dominance-based algorithms such as NSGA-II and SPEA. This is because almost all individuals in a population are non-dominated with each other in the presence of many objectives. In such a population, the Pareto dominance relation can generate no strong selection pressure toward the Pareto front. This leads to poor search ability of Pareto dominance-based algorithms for many-objective problems. Recently it has been reported that better results can be obtained for many-objective problems by the use of scalarizing functions. The weighted sum usually works well in scalarizing function-based algorithms when the Pareto front is convex. However, we need other functions such as the weighted Tchebycheff when the Pareto front is non-convex. In this paper, we propose an idea of automatically choosing between the weighted sum and the weighted Tchebycheff for each individual in each generation. The characteristic feature of the proposed idea is to use the weighted Tchebycheff only when it is needed for individuals along non-convex regions of the Pareto front. The weighted sum is used for the other individuals in each generation. The proposed idea is combined with a high-performance scalarizing function-based algorithm called MOEA/D (multiobjective evolutionary algorithm based on decomposition) of Zhang and Li (2007). Effectiveness of the proposed idea is demonstrated through computational experiments on modified multiobjective knapsack problems with non-convex Pareto fronts. <s> BIB001 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> 5) SUMMARY <s> The use of Pareto dominance for fitness evaluation has been the mainstream in evolutionary multiobjective optimization for the last two decades. Recently, it has been pointed out in some studies that Pareto dominance-based algorithms do not always work well on multiobjective problems with many objectives. Scalarizing function-based fitness evaluation is a promising alternative to Pareto dominance especially for the case of many objectives. A representative scalarizing function-based algorithm is MOEA/D (multiobjective evolutionary algorithm based on decomposition) of Zhang & Li (2007). Its high search ability has already been shown for various problems. One important implementation issue of MOEA/D is a choice of a scalarizing function because its search ability strongly depends on this choice. It is, however, not easy to choose an appropriate scalarizing function for each multiobjective problem. In this paper, we propose an idea of using different types of scalarizing functions simultaneously. For example, both the weighted Tchebycheff (Chebyshev) and the weighted sum are used for fitness evaluation. We examine two methods for implementing our idea. One is to use multiple grids of weight vectors and the other is to assign a different scalarizing function alternately to each weight vector in a single grid. <s> BIB002 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> 5) SUMMARY <s> MOEA/D is a generic multiobjective evolutionary optimization algorithm. MOEA/D needs a approach to decompose a multiobjective optimization problem into a number of single objective optimization problems. The commonly-used weighted sum approach and the Tchebycheff approach may not be able to handle disparately scaled objectives. This paper suggests a new decomposition approach, called NBI-style Tchebycheff approach, for MOEA/D to deal with such objectives. A portfolio management MOP has been used as an example to test the effectiveness of MOEA/D with NBI-style Tchebycheff approach. <s> BIB003 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> 5) SUMMARY <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> BIB004 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> 5) SUMMARY <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> BIB005 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> 5) SUMMARY <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> BIB006 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> 5) SUMMARY <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> BIB007 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> 5) SUMMARY <s> MOEA/D is one of the most popular multi-objective evolutionary algorithms. To extend the effective application scope of MOEA/D for high-dimensional objectives, an improved MOEA/D design for many-objective optimization problems, named I-MOEA/D, is proposed in this paper. Comparing with the original MOEA/D, we redesigned the weight vectors used in the subproblems, making the distribution of the weight vectors broader and more effective to ensure the diversity and convergence of solutions in the objective space. Moreover, a new decomposition approach, called the weighted mixture-style method, which combines the advantages of the weighted sum decomposition and the Tchebycheff decomposition approaches, is adopted in I-MOEA/D to improve the effectiveness of the algorithm. A three-part experimental comparison using DTLZ1-DTLZ4, with the number of objectives ranging from three to fifteen, is performed. Experimental results verify the effectiveness of each strategy and reveal that the proposed I-MOEA/D method achieves better performance than the other related state-of-the-art algorithms in solving this type of many-objective optimization problems. <s> BIB008 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> 5) SUMMARY <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> BIB009
The decomposition methods introduced in this subsection are summarized in Table 2 , from which we can obtain the following key findings. • Many studies BIB001 , BIB006 , BIB007 introduce adaptive mechanisms into MOEA/D, which adaptively adjusts the parameters of the methods proposed in previous studies, and balances population diversity and convergence of each algorithm at different search stages. • There is a highly promising prospect if we make full use of the advantages of different decomposition methods by using mixed mechanisms BIB002 , BIB003 , BIB008 . • It is helpful to enhance the solution quality by improving original decomposition methods in terms of properties of decomposition methods such as ideal points BIB004 and contours BIB005 , or proposing new mechanisms with mathematical methods BIB009 . If the PF shape is regular or known in advance, weight vectors generated by the uniform design method can make the distribution of solutions more uniform. The adaptive adjustment strategy is more suitable for MOPs with complex PFs, which may have discrete regions, sharp peaks, and a long low-tail. According to the geometrical characteristics of the PF or the search difficulty of each subproblem, the weight vector is adjusted adaptively to realize the reasonable allocation of computational resources and to make solution mapping vectors be distributed more evenly in the objective space. Also, user preferences can be used as a guidance to adaptively assign the weight vector to each subproblem, aiming at providing diverse preference solutions. As the main step in the MOEA/D framework and key procedure for each subproblem to produce the promising offspring, evolution is reviewed in this subsection, which includes mating selection, reproduction, and replacement. Table 4 presents the main idea, evolutionary operator and classification for each reference. Some valuable conclusions are given below. • To maintain population diversity, it is promising to reasonably set the ranges of both mating selection and replacement, or to achieve a match between solutions and subproblems, which effectively reduces the probability that a new solution replaces old ones. • According to the solutions distribution in an evolutionary process, the adaptive selection of different evolutionary operators or their combination with other heuristic algorithms, and even with hyper-heuristic algorithms, is beneficial to further improving the algorithm performance. • Different evolutionary operators can be applied to different algorithm stages or populations to better accommodate the different performance requirements of an algorithm. In this subsection, we describe the main challenges that MOEA/D faces in solving MaOPs in the high-dimensional objective space. Then a series of improved algorithms to overcome these challenges are reviewed. Table 5 presents a summary of these algorithms based on their techniques, such as decomposition, uniform design, and user preferencesbased. The high-dimensional objective space makes it more difficult for MOEA/D to obtain a set of solutions distributed widely and uniformly. Objective region decomposition transforms an MaOP into several multiobjective subproblems and divides the population into multiple subpopulations, each of which solves a subproblem. Thus, the whole objective region can be well searched through CE among subpopulations, which greatly reduces the difficulty in searching over a highdimensional objective space. Uniform design can effectively alleviate the difficulties of weight vector generation and population design. Using user preference information allows an algorithm to search only within the ROI of DMs and to generate a well-distributed solution set in the preference region, significantly saving the computational resources required for searching. Briefly, many-objective optimization presents one of the hotspots and challenges in future research and deserves further exploration.