A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> I. INTRODUCTION <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> I. INTRODUCTION <s> Related to the safety of public lives and property in the lower area of reservoirs, flood control is a priority for most large reservoirs. Considering both dam safety and downstream flood control, reservoir flood control is a multi-objective problem (MOP). To meet the needs of irrigation and generating electricity after the flood, the decision maker usually has his/her preferred final scheduling water level. To deal with this kind of MOP with user-preference information, we incorporate user-preference information into the framework of MOEA/D (multi-objective evolutionary algorithm-based decomposition). The widely used preference information is mainly composed of reference points and preference directions. Compared with the Pareto dominance-based multi-objective evolutionary algorithms (MOEAs), MOEA/D can naturally include two kinds of preference information since MOEA/D is directly based on the reference point and the preference direction. The weight vector of a subproblem in MOEA/D is just its preference. Aiming to obtain uniformly distributed solutions on the objective space, one of innovation points in this paper is using modified Tchebycheff decomposition instead of Tchebycheff decomposition as the decomposition method. To focus the search on the interesting regions of decision maker, the other innovation point in this paper is to integrate biased subproblem (weight vector) adjustment into the framework of MOEA/D. The distribution of subproblems (weight vectors) are adjusted periodically so that the subproblems are re-distributed adaptively to search the interesting regions. Some subproblems, which are far away from the preference regions, are deleted. And then some new subproblems, which are expected to search the preference regions, are added into the current evolutionary population. The efficiency and the effectiveness of the proposed algorithm are assessed through multi-objective reservoir flood control problem and two- to ten-objective test problems. <s> BIB002 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> I. INTRODUCTION <s> Decomposition is a well-known strategy in traditional multiobjective optimization. However, the decomposition strategy was not widely employed in evolutionary multiobjective optimization until Zhang and Li proposed multiobjective evolutionary algorithm based on decomposition (MOEA/D) in 2007. MOEA/D proposed by Zhang and Li decomposes a multiobjective optimization problem into a number of scalar optimization subproblems and optimizes them in a collaborative manner using an evolutionary algorithm (EA). Each subproblem is optimized by utilizing the information mainly from its several neighboring subproblems. Since the proposition of MOEA/D in 2007, decomposition-based MOEAs have attracted significant attention from the researchers. Investigations have been undertaken in several directions, including development of novel weight vector generation methods, use of new decomposition approaches, efficient allocation of computational resources, modifications in the reproduction operation, mating selection and replacement mechanism, hybridizing decomposition- and dominance-based approaches, etc. Furthermore, several attempts have been made at extending the decomposition-based framework to constrained multiobjective optimization, many-objective optimization, and incorporate the preference of decision makers. Additionally, there have been many attempts at application of decomposition-based MOEAs to solve complex real-world optimization problems. This paper presents a comprehensive survey of the decomposition-based MOEAs proposed in the last decade. <s> BIB003 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> I. INTRODUCTION <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> BIB004 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> I. INTRODUCTION <s> This paper focuses on the connecting structure of deep neural networks and proposes a layerwise structure learning method based on multiobjective optimization. A model with better generalization can be obtained by reducing the connecting parameters in deep networks. The aim is to find the optimal structure with high representation ability and better generalization for each layer. Then, the visible data are modeled with respect to structure based on the products of experts. In order to mitigate the difficulty of estimating the denominator in PoE, the denominator is simplified and taken as another objective, i.e., the connecting sparsity. Moreover, for the consideration of the contradictory nature between the representation ability and the network connecting sparsity, the multiobjective model is established. An improved multiobjective evolutionary algorithm is used to solve this model. Two tricks are designed to decrease the computational cost according to the properties of input data. The experiments on single-layer level, hierarchical level, and application level demonstrate the effectiveness of the proposed algorithm, and the learned structures can improve the performance of deep neural networks. <s> BIB005 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> I. INTRODUCTION <s> With the developing of green economy, energy-efficient scheduling has raised great interest recently. In our paper, we propose a modified multiobjective evolutionary algorithm based on decomposition (MMOEA/D) for the energy-efficient flexible job shop scheduling problem (EEFJSP) to optimize makespan and total energy consumption. A cooperative search operator is designed to improve the exploration. At the same time, a local intensification based on the properties of this problem is added to enhance the exploitation. Besides, the effect of parameter setting is investigated by the design-of experiment. Finally, comparison experiments are carried out between the MMOEA/D and the shuffled frog-leaping algorithm (SFLA). The results have shown that the MMOEA/D outperforms SFLA on this problem. <s> BIB006 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> I. INTRODUCTION <s> The order scheduling problem plays a significant role in the warehouse management for manufacturing corporations, and how to solve it efficiently will have direct impact on a company's strategy. In this paper, we take both the outbound orders and inbound orders into account, formulating the order scheduling problem as a constrained bi-objective optimization problem that minimizes both the total completion time and the maximum tardiness of outbound orders. A nearest-neighbor strategy is adopted to find a suitable storage location more efficiently when the storage/retrieve machine moves are executed as a dual command. We propose a modified multi-objective evolutionary algorithm based on decomposition, combined with shuffled frog leaping algorithm, to successfully solve the order scheduling problem. Our experimental results demonstrate the proposed algorithm is competitive compared with other multiobjective algorithms in solving order scheduling problem for automated warehouse system. <s> BIB007 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> I. INTRODUCTION <s> Abstract In Wireless Sensor Networks (WSN), maintaining a high coverage and extending the network lifetime are two conflicting crucial issues considered by real world service providers. In this paper, we consider the coverage optimization problem in WSN with three objectives to strike the balance between network lifetime and coverage. These include minimizing the energy consumption, maximizing the coverage rate and maximizing the equilibrium of energy consumption. Two improved hybrid multi-objective evolutionary algorithms, namely Hybrid-MOEA/D-I and Hybrid-MOEA/D-II, have been proposed. Based on the well-known multi-objective evolutionary algorithm based on decomposition (MOEA/D), Hybrid-MOEA/D-I hybrids a genetic algorithm and a differential evolutionary algorithm to effectively optimize sub-problems of the multi-objective optimization problem in WSN. By integrating a discrete particle swarm algorithm, we further enhance solutions generated by Hybrid-MOEA/D-I in a new Hybrid-MOEA/D-II algorithm. Simulation results show that the proposed Hybrid-MOEA/D-I and Hybrid-MOEA/D-II algorithms have a significant better performance compared with existing algorithms in the literature in terms of all the objectives concerned. <s> BIB008 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> I. INTRODUCTION <s> Network function vitalization (NFV) as a new research concept, for both academia and industry, faces many challenges to network operators before it can be accepted into mainstream. One challenge addressed in this paper is to find the optimal placement f or a set of incoming requests with VNF service chains to serve in suitable Virtual Machines (VMs) such that a set of conflicting objectives are met. Mainly, focus is placed on maximizing the total saving cost by increasing the total CPU utilization during the processing time and increasing the processing time for every service request in the cloud network. Moreover, we aim to maximize the admitted traffic simultaneously while considering the system constraints. We formulate the problem as a multi-objective optimization problem and use a Resource Utilization Multi-Objective Evolutionary Algorithm based on Decomposition (RU-MOEA/D) algorithm to solve the problem considering the two objectives simultaneously. Extensive simulations are carried out to evaluate the effects of the different network sizes, genetic parameters and the number of server resources on the acceptable ratio of the arrival chains to serve in the available VMs. The empirical results illustrate that the proposed algorithm can solve the problem efficiently and compute the optimal solution for two objectives together within a reasonable running time. <s> BIB009 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> I. INTRODUCTION <s> Internet of Things (IoT) is a recent technology of connecting and communicating people, process, devices, and data; and it is expected to facilitate future communication and to increase quality of lives. Due to a very wide range of application areas, this technology needs some requirements such as sensing the targets in the network field, minimizing energy consumption, connecting with other IoT devices securely. For these reasons, many constraints need to be taken into account when deploying devices into the field. In this study, a multi-objective evolutionary algorithm based on decomposition (MOEA/D) is proposed to relocate to IoT devices randomly distributed in a certain area to optimize the efficient and secure coverage problem. Simulation results are evaluated by comparing MOEA/D with another well-known algorithm called non-dominated sorting algorithm - II (NSGA-II). According to the results, there is a trade-off between the number of covered targets and the secure connection between devices. Also, MOEA/D achieves higher coverage ratio (higher number of covered targets), while NSGA-II provides higher number of secure connections. <s> BIB010 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> I. INTRODUCTION <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> BIB011 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> I. INTRODUCTION <s> By separating network functions from hardware-dependent middleboxes, network function virtualization (NFV) is expected to lead to significant cost reduction and the flexibility improvement in network management. Elastic orchestration of virtual network functions (VNF) is a key factor to achieve NFV goals. However, most existing VNF orchestration researches are limited to offline policy, ignoring the dynamic characteristics of the workload. To reduce the operational expenditure of NFV providers, this paper proposes an Elastic Virtual Network Function Orchestration (EVNFO) policy based on workload prediction. We adapt the online learning algorithm for predicting the flows rate of service function chains (SFC), which can help to obtain the VNF scaling decision. We further design the online instance provisioning strategy (OIPS) to accomplish the deployment of VNF instances according to the decision. The simulation proves that EVNFO can provide good performance with dynamic resource provision. The throughput of VNF is improved by 11.1%–22.9%, and the total operational expenditure can be reduced by 13.8% compared with other online approaches. <s> BIB012 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> I. INTRODUCTION <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> BIB013 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> I. INTRODUCTION <s> Efficient scheduling benefits productivity promotion, cost savings, and customer satisfaction. In recent years, with a growing concern about the energy price and environmental impact, energy-oriented scheduling is going to be a key issue for sustainable manufacturing. In this paper, we investigate an energy-oriented scheduling problem deriving from the hybrid flow shop with limited buffers. First, we formulate the scheduling problem with a mixed integer linear programming (MILP) model, which considers two objectives including minimizing the total weighted tardiness (TWT) and non-processing energy (NPE). To solve the NP-hard problem in the strong sense, we develop an efficient multi-objective optimization algorithm under the framework of the multi-objective objective evolutionary algorithm based on decomposition (MOEA/D). We devise a job-permutation vector to represent the scheduling solution and cover its search space. Since NPE is a non-regular function, we develop a two-pass decoding procedure composed of a discrete-event system (DES) simulation procedure and a greedily post-shift procedure. Besides, we apply an external archive population (EAP) to guide the algorithm to converge on a Pareto frontier and a local search procedure to enhance the diversity of the population. Finally, we conduct extensive computational experiments to verify the effectiveness of the proposed energy-oriented multi-objective optimization (EOMO) algorithm. The results presented in this paper may be useful for future research on energy-oriented scheduling problems in realistic production systems. <s> BIB014 </s> A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition: Variants, Challenges and Future Directions <s> I. INTRODUCTION <s> The stochastic nature of intermittent energy resources has brought significant challenges to the optimal operation of the hybrid energy systems. This article proposes a probabilistic multiobjective evolutionary algorithm based on decomposition (MOEA/D) method with two-step risk-based decision-making strategy to tackle this problem. A scenario-based technique is first utilized to generate a stochastic model of the hybrid energy system. Those scenarios divide the feasible domain into several regions. Then, based on the MOEA/D framework, a probabilistic penalty-based boundary intersection (PBI) with gradient descent differential evolution (GDDE) algorithm is proposed to search the optimal scheme from these regions under different uncertainty budgets. To ensure reliable and low risk operation of the hybrid energy system, the Markov inequality is employed to deduce a proper interval of the uncertainty budget. Further, a fuzzy grid technique is proposed to choose the best scheme for real-world applications. The experimental results confirm that the probabilistic adjustable parameters can properly control the uncertainty budget and lower the risk probability. Further, it is also shown that the proposed MOEA/D-GDDE can significantly enhance the optimization efficiency. <s> BIB015
There are many multiobjective optimization problems (MOPs) in various fields, for example, how to reasonably allocate resources in the network for implementing several goals jointly, such as maximizing resource utilization and minimizing operational expenditure BIB012 . These optimization objectives usually conflict with each other, in such a way that an objective cannot be improved without causing degradation to some others. Therefore, it is impossible to make them all The associate editor coordinating the review of this manuscript and approving it for publication was Sotirios Goudos . optimal at the same time, and we could seek multiple Pareto optimal solutions (POSs) for a tradeoff among all objectives instead of a globally optimal solution. For any two feasible solutions x 1 and x 2 of an MOP, x 1 dominates x 2 if x 1 is not inferior to x 2 on all objectives and x 1 is superior to x 2 on at least one objective, and x 1 is a POS if it is not dominated by all the others in the solution set. Single-objective optimization algorithms that often find a single optimal solution are no longer suitable for solving MOPs. Some researchers have proposed scalarization-based techniques and meta-heuristic algorithms based on swarm intelligence, and corresponding examples are the weighted sum and evolutionary algorithms (EAs). The multiobjective evolutionary algorithms (MOEAs) based on multi-population co-evolution (CE) have gained great popularity in recent years. In a single simulation run, a set of POSs with optimal tradeoffs among approximately conflicting objective functions can be obtained, and decision makers (DMs) can thus choose solutions based on different preferences. According to different selection strategies, MOEAs can be broadly classified into three categories that are based on domination, indicator and decomposition BIB003 . When the number of objectives becomes large, it is increasingly hard for domination-based MOEAs to select solutions, because almost all the solutions in the population become nondominated with each other. In the second category, the exact indicator calculation is highly complex and the computational resources required grow exponentially with the increasing number of objectives. Compared with other MOEAs, the decomposition-based framework can enhance population diversity by using a group of weight vectors or reference points distributed properly, and allow parallel computation to speed up the solution convergence. As a representative of decomposition-based MOEAs, MOEA/D has been receiving focus on the multiobjective optimization field since it was introduced in 2007 BIB001 . It decomposes an MOP into a number of single-objective subproblems through aggregation functions and simultaneously optimizes them by using EAs. Each individual in the population represents the current best solution to one of the subproblems, and each subproblem is optimally solved with the solutions of all its surrounding subproblems. Thanks to the inherent advantages in terms of decomposition and parallelism, MOEA/D has been widely used to solve many practical engineering optimization problems, including: 1) machine learning problems, most of which can be attributed to optimization problems, and sometimes have more than one objective to optimize, such as fuzzy classifier design BIB004 , optimization of deep neural network connection structure BIB005 and determination of a hyper-parameter for the regularization term of convolutional neural network BIB013 ; 2) scheduling problems, allocating resources to different tasks in real time under certain constraints, such as hybrid flow shop scheduling BIB014 , job shop scheduling BIB006 , and order scheduling BIB007 ; 3) design problems, usually achieving the goals of low cost, low consumption, and large profit while meeting the needs of users, such as wireless sensor network coverage design BIB008 and resource optimization for network function virtualization (NFV) requests BIB009 ; 4) control problems, addressing the optimal parameters and mechanism in such a system as the Internet of Things BIB010 or reservoir flood control BIB002 ; 5) operation problems, studying the cost reduction in the operation and maintenance of a system like hybrid energy systems BIB015 ; and 6) investment problems, considering how to invest limited funds in a number of projects to maximize returns like portfolio optimization problem BIB011 . This article consists mainly of three parts: 1) a comprehensive overview of the improvements and the extensions with some new techniques; 2) findings of this survey in seven aspects; and 3) some challenges and research directions in four categories. Our work makes three contributions to the field of multiobjective optimization: 1) different from the earlier survey BIB003 , this is a more comprehensive and timely survey covering the recent advanced studies on MOEA/D, which provides innovative research ideas and methods for scholars. Further, we organize the article according to the methods or techniques used by these variants in the review, which will help readers to find appropriate methods to solve the practical problems; 2) findings of this survey in seven aspects are discussed, including the utilized techniques and related references. The tables and figures in this article will aid researchers to understand the algorithms more systematically and to select some algorithms they are interested in for further study; 3) new challenges and future research directions are discussed from diverse perspectives, such as theoretical analysis, practical application, and hotspot topics, which are more detailed and timely compared to the survey of MOEA/D in 2017. We believe that this survey will attract more researchers to pay attention to MOEA/D and encourage them to develop more efficient and intelligent algorithms, so as to cope with new challenges in solving complex optimization problems, especially in some cutting-edge areas of large-scale optimization, machine learning, software defined networking (SDN) and NFV. The rest of this article is organized as shown in Fig. 1 . Section II describes the framework and characteristics of MOEA/D, and outlines its different research directions. Section III discusses the detailed component improvements of MOEA/D and its extensions to other fields. Section IV presents the findings of this survey. Open problems or challenges and possible solutions are addressed in Section V. The conclusion is given in Section VI. For convenience, the list of abbreviations used in this article is presented in Table 1 .