A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> C. RESEARCH DIRECTIONS OF MOEA/D <s> Decomposition is a basic strategy in traditional multiobjective optimization. However, it has not yet been widely used in multiobjective evolutionary optimization. This paper proposes a multiobjective evolutionary algorithm based on decomposition (MOEA/D). It decomposes a multiobjective optimization problem into a number of scalar optimization subproblems and optimizes them simultaneously. Each subproblem is optimized by only using information from its several neighboring subproblems, which makes MOEA/D have lower computational complexity at each generation than MOGLS and nondominated sorting genetic algorithm II (NSGA-II). Experimental results have demonstrated that MOEA/D with simple decomposition methods outperforms or performs similarly to MOGLS and NSGA-II on multiobjective 0-1 knapsack problems and continuous multiobjective optimization problems. It has been shown that MOEA/D using objective normalization can deal with disparately-scaled objectives, and MOEA/D with an advanced decomposition method can generate a set of very evenly distributed solutions for 3-objective test instances. The ability of MOEA/D with small population, the scalability and sensitivity of MOEA/D have also been experimentally investigated in this paper. <s> BIB001 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> C. RESEARCH DIRECTIONS OF MOEA/D <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> BIB002 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> C. RESEARCH DIRECTIONS OF MOEA/D <s> This paper presents Differential Evolution with Self-adaptation and Local Search for Constrained Multiobjective Optimization algorithm (DECMOSA-SQP), which uses the self-adaptation mechanism from DEMOwSA algorithm presented at CEC 2007 and a SQP local search. The constrained handling mechanism is also incorporated in the new algorithm. Assessment of the algorithm using CEC 2009 special session and competition on constrained multiobjective optimization test functions is presented. The functions are composed of unconstrained and constrained problems. Their results are assessed using the IGD metric. Based on this metric, algorithm strengths and weaknesses are discussed. <s> BIB003 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> C. RESEARCH DIRECTIONS OF MOEA/D <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> BIB004 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> C. RESEARCH DIRECTIONS OF MOEA/D <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> BIB005 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> C. RESEARCH DIRECTIONS OF MOEA/D <s> MOEA/D is a recently proposed methodology of Multiobjective Evolution Algorithms that decomposes multiobjective problems into a number of scalar subproblems and optimizes them simultaneously. However, classical MOEA/D uses same weight vectors for different shapes of Pareto front. We propose a novel method called Pareto-adaptive weight vectors (paλ) to automatically adjust the weight vectors by the geometrical characteristics of Pareto front. Evaluation on different multiobjective problems confirms that the new algorithm obtains higher hypervolume, better convergence and more evenly distributed solutions than classical MOEA/D and NSGA-II. <s> BIB006 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> C. RESEARCH DIRECTIONS OF MOEA/D <s> Combining ant colony optimization (ACO) and the multiobjective evolutionary algorithm (EA) based on decomposition (MOEA/D), this paper proposes a multiobjective EA, i.e., MOEA/D-ACO. Following other MOEA/D-like algorithms, MOEA/D-ACO decomposes a multiobjective optimization problem into a number of single-objective optimization problems. Each ant (i.e., agent) is responsible for solving one subproblem. All the ants are divided into a few groups, and each ant has several neighboring ants. An ant group maintains a pheromone matrix, and an individual ant has a heuristic information matrix. During the search, each ant also records the best solution found so far for its subproblem. To construct a new solution, an ant combines information from its group's pheromone matrix, its own heuristic information matrix, and its current solution. An ant checks the new solutions constructed by itself and its neighbors, and updates its current solution if it has found a better one in terms of its own objective. Extensive experiments have been conducted in this paper to study and compare MOEA/D-ACO with other algorithms on two sets of test problems. On the multiobjective 0-1 knapsack problem, MOEA/D-ACO outperforms the MOEA/D with conventional genetic operators and local search on all the nine test instances. We also demonstrate that the heuristic information matrices in MOEA/D-ACO are crucial to the good performance of MOEA/D-ACO for the knapsack problem. On the biobjective traveling salesman problem, MOEA/D-ACO performs much better than the BicriterionAnt on all the 12 test instances. We also evaluate the effects of grouping, neighborhood, and the location information of current solutions on the performance of MOEA/D-ACO. The work in this paper shows that reactive search optimization scheme, i.e., the “learning while optimizing” principle, is effective in improving multiobjective optimization algorithms. <s> BIB007 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> C. RESEARCH DIRECTIONS OF MOEA/D <s> This letter suggests an approach for decomposing a multiobjective optimization problem (MOP) into a set of simple multiobjective optimization subproblems. Using this approach, it proposes MOEA/D-M2M, a new version of multiobjective optimization evolutionary algorithm-based decomposition. This proposed algorithm solves these subproblems in a collaborative way. Each subproblem has its own population and receives computational effort at each generation. In such a way, population diversity can be maintained, which is critical for solving some MOPs. Experimental studies have been conducted to compare MOEA/D-M2M with classic MOEA/D and NSGA-II. This letter argues that population diversity is more important than convergence in multiobjective evolutionary algorithms for dealing with some MOPs. It also explains why MOEA/D-M2M performs better. <s> BIB008 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> C. RESEARCH DIRECTIONS OF MOEA/D <s> Recently, MOEA/D multi-objective evolutionary algorithm based on decomposition has achieved great success in the field of evolutionary multi-objective optimization and has attracted a lot of attention. It decomposes a multi-objective optimization problem MOP into a set of scalar subproblems using uniformly distributed aggregation weight vectors and provides an excellent general algorithmic framework of evolutionary multi-objective optimization. Generally, the uniformity of weight vectors in MOEA/D can ensure the diversity of the Pareto optimal solutions, however, it cannot work as well when the target MOP has a complex Pareto front PF; i.e., discontinuous PF or PF with sharp peak or low tail. To remedy this, we propose an improved MOEA/D with adaptive weight vector adjustment MOEA/D-AWA. According to the analysis of the geometric relationship between the weight vectors and the optimal solutions under the Chebyshev decomposition scheme, a new weight vector initialization method and an adaptive weight vector adjustment strategy are introduced in MOEA/D-AWA. The weights are adjusted periodically so that the weights of subproblems can be redistributed adaptively to obtain better uniformity of solutions. Meanwhile, computing efforts devoted to subproblems with duplicate optimal solution can be saved. Moreover, an external elite population is introduced to help adding new subproblems into real sparse regions rather than pseudo sparse regions of the complex PF, that is, discontinuous regions of the PF. MOEA/D-AWA has been compared with four state of the art MOEAs, namely the original MOEA/D, Adaptive-MOEA/D, -MOEA/D, and NSGA-II on 10 widely used test problems, two newly constructed complex problems, and two many-objective problems. Experimental results indicate that MOEA/D-AWA outperforms the benchmark algorithms in terms of the IGD metric, particularly when the PF of the MOP is complex. <s> BIB009 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> C. RESEARCH DIRECTIONS OF MOEA/D <s> This paper studies the replacement schemes in MOEA/D and proposes a new replacement named global replacement. It can improve the performance of MOEA/D. Moreover, trade-offs between convergence and diversity can be easily controlled in this replacement strategy. It also shows that different problems need different trade-offs between convergence and diversity. We test the MOEA/D with this global replacement on three sets of benchmark problems to demonstrate its effectiveness. <s> BIB010 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> C. RESEARCH DIRECTIONS OF MOEA/D <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> BIB011 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> C. RESEARCH DIRECTIONS OF MOEA/D <s> The resulting set of solutions obtained by MOEA/D depends on the weights used in the decomposition. In this work, we use this feature to incorporate user preferences into the search. We use co-evolutionary approach to change the weights adaptively during the run of the algorithm. After the user specifies their preferences by assigning binary preference values to the individuals, the co-evolutionary step improves the distribution of weights by creating new (offspring) weights and selecting those that better match the user preferences. The algorithm is tested on a set of benchmark functions with a set of different user preferences. <s> BIB012 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> C. RESEARCH DIRECTIONS OF MOEA/D <s> The multiobjective evolutionary algorithm based on decomposition (MOEA/D) has been shown to be very efficient in solving multiobjective optimization problems (MOPs). In practice, the Pareto-optimal front (POF) of many MOPs has complex characteristics. For example, the POF may have a long tail and sharp peak and disconnected regions, which significantly degrades the performance of MOEA/D. This paper proposes an improved MOEA/D for handling such kind of complex problems. In the proposed algorithm, a two-phase strategy (TP) is employed to divide the whole optimization procedure into two phases. Based on the crowdedness of solutions found in the first phase, the algorithm decides whether or not to delicate computational resources to handle unsolved subproblems in the second phase. Besides, a new niche scheme is introduced into the improved MOEA/D to guide the selection of mating parents to avoid producing duplicate solutions, which is very helpful for maintaining the population diversity when the POF of the MOP being optimized is discontinuous. The performance of the proposed algorithm is investigated on some existing benchmark and newly designed MOPs with complex POF shapes in comparison with several MOEA/D variants and other approaches. The experimental results show that the proposed algorithm produces promising performance on these complex problems. <s> BIB013 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> C. RESEARCH DIRECTIONS OF MOEA/D <s> Multiobjective evolutionary algorithms based on decomposition (MOEA/D) decompose a multiobjective optimization problem into a set of simple optimization subproblems and solve them in a collaborative manner. A replacement scheme, which assigns a new solution to a subproblem, plays a key role in balancing diversity and convergence in MOEA/D. This paper proposes a global replacement scheme which assigns a new solution to its most suitable subproblems. We demonstrate that the replacement neighborhood size is critical for population diversity and convergence, and develop an approach for adjusting this size dynamically. A steady-state algorithm and a generational one with this approach have been designed and experimentally studied. The experimental results on a number of test problems have shown that the proposed algorithms have some advantages. <s> BIB014 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> C. RESEARCH DIRECTIONS OF MOEA/D <s> In evolutionary multiobjective optimization, maintaining a good balance between convergence and diversity is particularly crucial to the performance of the evolutionary algorithms (EAs). In addition, it becomes increasingly important to incorporate user preferences because it will be less likely to achieve a representative subset of the Pareto-optimal solutions using a limited population size as the number of objectives increases. This paper proposes a reference vector-guided EA for many-objective optimization. The reference vectors can be used not only to decompose the original multiobjective optimization problem into a number of single-objective subproblems, but also to elucidate user preferences to target a preferred subset of the whole Pareto front (PF). In the proposed algorithm, a scalarization approach, termed angle-penalized distance, is adopted to balance convergence and diversity of the solutions in the high-dimensional objective space. An adaptation strategy is proposed to dynamically adjust the distribution of the reference vectors according to the scales of the objective functions. Our experimental results on a variety of benchmark test problems show that the proposed algorithm is highly competitive in comparison with five state-of-the-art EAs for many-objective optimization. In addition, we show that reference vectors are effective and cost-efficient for preference articulation, which is particularly desirable for many-objective optimization. Furthermore, a reference vector regeneration strategy is proposed for handling irregular PFs. Finally, the proposed algorithm is extended for solving constrained many-objective optimization problems. <s> BIB015 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> C. RESEARCH DIRECTIONS OF MOEA/D <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> BIB016 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> C. RESEARCH DIRECTIONS OF MOEA/D <s> Deep convolutional neural networks achieved remarkably performance on computer vision tasks. However, they are always over-parameterized and computationally intensive to deploy on computing platforms with limited hardware resources. In this paper, a MOEA/D based pruning approach is proposed. We exploit the crucial structure of convolution kernels using MOEA/D based pruning approach and find 88% computational redundancy in convolutional layers of LeNet-5 without any accuracy loss. Networks are encoded as chromosomes in continues or discrete spaces. A multi-objective evolutionary algorithm, MOEA/D, is employed to evolve multiple convolutional neural networks simultaneously subject to accuracy and computational cost as two conflicting objectives. Several experiments are conducted on three classical image classification tasks. Statistical results demonstrate that our proposed method is both effective and superior to other methods. <s> BIB017 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> C. RESEARCH DIRECTIONS OF MOEA/D <s> The portfolio optimization problem is a multi-objective problem which takes risk and return as optimization objectives. It is complicated in reality with many restrictions which results in an complex pareto front. MOEA/D is a popular multi-objective evolutionary algorithm framework with decomposition method, which has widely been used to solve multi-objective problems. In order to solve portfolio optimization problem with complex pareto front more effectively, we propose a new algorithm named MOEA/D-CP based on MOEA/D, which utilizes a new weight vector generation approach to generate a evenly distributed set of weight vectors. The experimental results show that the MOEA/D-CP performs much better than algorithm based on original MOEA/D. <s> BIB018 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> C. RESEARCH DIRECTIONS OF MOEA/D <s> The decomposition-based evolutionary multiobjective optimization (EMO) algorithm has become an increasingly popular choice for a posteriori multiobjective optimization. However, recent studies have shown that their performance strongly depends on the Pareto front (PF) shapes. This can be attributed to the decomposition method, of which the reference points and subproblem formulation settings are not well adaptable to various problem characteristics. In this paper, we develop a learning-to-decompose (LTD) paradigm that adaptively sets the decomposition method by learning the characteristics of the estimated PF. Specifically, it consists of two interdependent parts, i.e., a learning module and an optimization module. Given the current nondominated solutions from the optimization module, the learning module periodically learns an analytical model of the estimated PF. Thereafter, useful information is extracted from the learned model to set the decomposition method for the optimization module: 1) reference points compliant with the PF shape and 2) subproblem formulations whose contours and search directions are appropriate for the current status. Accordingly, the optimization module, which can be any decomposition-based EMO algorithm in principle, decomposes the multiobjective optimization problem into a number of subproblems and optimizes them simultaneously. To validate our proposed LTD paradigm, we integrate it with two decomposition-based EMO algorithms, and compare them with four state-of-the-art algorithms on a series of benchmark problems with various PF shapes. <s> BIB019 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> C. RESEARCH DIRECTIONS OF MOEA/D <s> A convolutional neural network (CNN) is a type of multilayered neural network, which has a structure superior in handling images and natural languages. L1-regularization may be used as a means to prevent overfitting of CNN and improve generalization performance. However, it is difficult to set an appropriate coefficient of the regularization term. Therefore, in this research, we use MOEA/D to determine the value of hyper parameter. Experimental results on MNIST show the effectiveness of the proposed approach. <s> BIB020 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> C. RESEARCH DIRECTIONS OF MOEA/D <s> Portfolio optimization is an important financial problem, which involves an optimal allocation of finite capital to a series of assets to achieve an acceptable trade-off between profit and risk in a given investment period. In this paper, an extended Markowitz’s mean-variance portfolio optimization model, which is converted as a constrained multi-objective problem, is studied. Since this model involves both discrete and continuous variables, a multi-dimensional mapping coding scheme (MDM) has been adopted to convert discrete variables to continuous ones. Although the basic MDM is effective for dealing with the constrained multi-objective portfolio optimization problems, it sometimes prefers to choose some balanced investments, in which the allocation of funds for each selected asset is very similar. This may result in a focus on the low-risk and low-yield solutions. To solve this problem, an improved multi-dimensional mapping coding scheme is proposed in this paper. This new coding scheme is integrated into the decomposition based multi-objective evolutionary algorithm (MOEA/D). The algorithm is then applied to some test data, with the asset size ranging from 31 to 255, and the experimental results have indicated that the improved MDM coding scheme can significantly improve the performance comparing to the basic MDM coding scheme. <s> BIB021
As shown in Fig. 3 , the research on MOEA/D mainly involves two aspects of component improvements and extensions to other fields. The motivation for improvement is to overcome the limitations in designing components of the MOEA/D framework and to improve algorithm performance for solving various complex problems. For the wider application, MOEA/D needs to be further extended to some increasingly concerned areas, such as many-objective optimization and constrained multiobjective optimization. The main improvement on the original MOEA/D components could be divided into three subaspects further, including decomposition methods, weight vector generation methods, and evolutionary operators. Traditional decomposition methods have been improved BIB011 - BIB016 , combined with each other BIB004 , BIB005 and adaptively selected BIB002 , BIB019 . Liu et al. BIB008 decomposed an MOP into several multiobjective subproblems without using any aggregation functions. Weight vectors constructed by the simplex lattice design BIB001 cannot guarantee the uniformity of the solution set on some issues. Researchers proposed various techniques to improve the Algorithm 1 MOEA/D Input: N : population size λ 1 , . . . , λ N : weight vectors distributed uniformly T : neighborhood size G: maximum generation Output: EP: external population {Step I: Initialization} 1 set EP= ∅; 2 foreach i = j ≤ N do BIB001 calculate Euclidean distance between λ i and λ j ; 4 end 5 foreach i ≤ N do BIB020 set neighborhood of i as B(i) ={i 1 , . . . , i T }, where λ i 1 , . . . , λ i T are the T closest weight vectors to λ i ; 7 end 8 generate initial population {x 1 , . . . , x N } randomly; 9 calculate objective function required by each subproblem  or PF geometry shape BIB006 , BIB009 , user preferences-based BIB012 , and hybrid  . Evolution operators consist of mating selection, reproduction and replacement. The range and related techniques of mating selection  - BIB013 and replacement mechanisms BIB010 , BIB014 have been investigated to enhance population diversity. New reproduction operators like differential evolution (DE)  , BIB003 and other heuristic algorithms BIB007 have been introduced into MOEA/D. The other investigations addressed the extension of the MOEA/D framework to many-objective optimization  - BIB015 , constrained multiobjective optimization BIB021 -  , and real-world optimization BIB017 - BIB018 . For the five aspects shown in Fig. 3 , we will present a detailed review of each aspect in the section below. 