MOEA/D原版英文论文.pdf

发布时间：2022-05-31 发布人：admin 分类：说明书资料大小：1.61M 资料格式：pdf 举报版权申诉

qq_37672864-10384858-4744302542857208969.pdf-第1页.png

第1页 / 共20页

qq_37672864-10384858-4744302542857208969.pdf-第2页.png

第2页 / 共20页

qq_37672864-10384858-4744302542857208969.pdf-第3页.png

第3页 / 共20页

qq_37672864-10384858-4744302542857208969.pdf-第4页.png

第4页 / 共20页

qq_37672864-10384858-4744302542857208969.pdf-第5页.png

第5页 / 共20页

qq_37672864-10384858-4744302542857208969.pdf-第6页.png

第6页 / 共20页

qq_37672864-10384858-4744302542857208969.pdf-第7页.png

第7页 / 共20页

qq_37672864-10384858-4744302542857208969.pdf-第8页.png

第8页 / 共20页

文本预览

712 IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 11, NO. 6, DECEMBER 2007 MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition Qingfu Zhang, Senior Member, IEEE, and Hui Li Abstract—Decomposition is a basic strategy in traditional mul- tiobjective 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 optimiza- tion 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 scal- ability and sensitivity of MOEA/D have also been experimentally investigated in this paper. Index Terms—Computational complexity, decomposition, evolu- tionary algorithm, multiobjective optimization, Pareto optimality. I. INTRODUCTION Amultiobjective optimization problem (MOP) can be stated as follows: is the decision (variable) space, real-valued objective functions and consists where is called the ob- of jective space. The attainable objective set is deﬁned as the set (1) . , all the objectives are continuous and is de- are continuous functions, we call (1) a continuous If scribed by where MOP. Very often, since the objectives in (1) contradict each other, no point in maximizes all the objectives simultaneously. One has to balance them. The best tradeoffs among the objectives can be deﬁned in terms of Pareto optimality. Manuscript received September 4, 2006; revised November 9, 2006. The authors are with the Department of Computer Science, University of Essex, Wivenhoe Park, Colchester, CO4 3SQ, U.K. (e-mail: qzhang@ essex.ac.uk; hlil@essex.ac.uk). Digital Object Identiﬁer 10.1109/TEVC.2007.892759 Let for every , is said to dominate and .1 A point if and only if for at least one index is Pareto optimal to (1) if such that dominates there is no point is then called a Pareto optimal (objective) vector. In other words, any improvement in a Pareto optimal point in one objective must lead to deterioration in at least one other objective. The set of all the Pareto optimal points is called the Pareto set (PS) and the set of all the Pareto optimal objective vectors is the Pareto front (PF) [1]. . In many real-life applications of multiobjective optimization, an approximation to the PF is required by a decision maker for selecting a ﬁnal preferred solution. Most MOPs may have many or even inﬁnite Pareto optimal vectors. It is very time-con- suming, if not impossible, to obtain the complete PF. On the other hand, the decision maker may not be interested in having an unduly large number of Pareto optimal vectors to deal with due to overﬂow of information. Therefore, many multiobjec- tive optimization algorithms are to ﬁnd a manageable number of Pareto optimal vectors which are evenly distributed along the PF, and thus good representatives of the entire PF [1]–[4]. Some researchers have also made an effort to approximate the PF by using a mathematical model [5]–[8]. It is well-known that a Pareto optimal solution to a MOP, under mild conditions, could be an optimal solution of a scalar optimization problem in which the objective is an aggregation of ’s. Therefore, approximation of the PF can be decom- all the posed into a number of scalar objective optimization subprob- lems. This is a basic idea behind many traditional mathemat- ical programming methods for approximating the PF. Several methods for constructing aggregation functions can be found in the literature (e.g., [1]). The most popular ones among them in- clude the weighted sum approach and Tchebycheff approach. Recently, the boundary intersection methods have also attracted a lot of attention [9]–[11]. There is no decomposition involved in the majority of the current state-of-the-art multiobjective evolutionary algorithms (MOEAs) [2]–[4], [12]–[19]. These algorithms treat a MOP as a whole. They do not associate each individual solution with any particular scalar optimization problem. In a scalar objective optimization problem, all the solutions can be compared based on their objective function values and the task of a scalar ob- jective evolutionary algorithm (EA) is often to ﬁnd one single optimal solution. In MOPs, however, domination does not deﬁne a complete ordering among the solutions in the objective space and MOEAs aim at producing a number of Pareto op- timal solutions as diverse as possible for representing the whole PF. Therefore, conventional selection operators, which were 1This deﬁnition of domination is for maximization. All the inequalities should be reversed if the goal is to minimize the objectives in (1). “Dominate” means “be better than.” Authorized licensed use limited to: UNIVERSITY OF ESSEX. Downloaded on May 6, 2009 at 06:54 from IEEE Xplore. Restrictions apply. 1089-778X/$25.00 © 2007 IEEE

ZHANG AND LI: MOEA/D: A MULTIOBJECTIVE EVOLUTIONARY ALGORITHM BASED ON DECOMPOSITION 713 originally designed for scalar optimization, cannot be directly used in nondecomposition MOEAs. Arguably, if there is a ﬁtness assignment scheme for assigning an individual solution a relative ﬁtness value to reﬂect its utility for selection, then scalar optimization EAs can be readily extended for dealing with MOPs, although other techniques such as mating restric- tion [20], diversity maintaining [21], some properties of MOPs [22], and external populations [23] may also be needed for enhancing the performances of these extended algorithms. For this reason, ﬁtness assignment has been a major issue in current MOEA research. The popular ﬁtness assignment strategies include alternating objectives-based ﬁtness assignment such as the vector evaluation genetic algorithm (VEGA) [24], and domination-based ﬁtness assignment such as Pareto archived evolutionary strategy (PAES) [14], strength Pareto evolutionary algorithm II (SPEA-II) [15], and nondominated sorting genetic algorithm II (NSGA-II) [16]. The idea of decomposition has been used to a certain extent in several metaheuristics for MOPs [25]–[29]. For example, the two-phase local search (TPLS) [25] considers a set of scalar op- timization problems, in which the objectives are aggregations of the objectives in the MOP under consideration, a scalar opti- mization algorithm is applied to these scalar optimization prob- lems in a sequence based on aggregation coefﬁcients, a solution obtained in the previous problem is set as a starting point for solving the next problem since its aggregation objective is just slightly different from that in the previous one. The multiob- jective genetic local search (MOGLS) aims at simultaneous op- timization of all aggregations constructed by the weighted sum approach or Tchebycheff approach [29]. At each iteration, it op- timizes a randomly generated aggregation objective. In this paper, we propose a new multiobjective evolutionary al- gorithm based on decomposition (MOEA/D). MOEA/D explic- scalaroptimizationsubprob- itlydecomposestheMOP(1)into lems. It solves these subproblems simultaneously by evolving a population of solutions. At each generation, the population is composed of the best solution found so far (i.e. since the start of the run of the algorithm) for each subproblem. The neighborhood relations among these subproblems are deﬁned based on the dis- tances between their aggregation coefﬁcient vectors. The optimal solutions to two neighboring subproblems should be very similar. Each subproblem (i.e., scalar aggregation function) is optimized in MOEA/D by using information only from its neighboring sub- problems. MOEA/D has the following features. • MOEA/D provides a simple yet efﬁcient way of intro- ducing decomposition approaches into multiobjective evo- lutionary computation. A decomposition approach, often developed in the community of mathematical program- ming, can be readily incorporated into EAs in the frame- work MOEA/D for solving MOPs. • Since MOEA/D optimizes scalar optimization problems rather than directly solving a MOP as a whole, issues such as ﬁtness assignment and diversity maintenance that cause difﬁculties for nondecomposition MOEAS could become easier to handle in the framework of MOEA/D. • MOEA/D has lower computational complexity at each generation than NSGA-II and MOGLS. Overall, MOEA/D outperforms, in terms of solution quality, MOGLS on 0–1 multiobjective knapsack test instances when both algo- rithms use the same decomposition approach. MOEA/D with the Tchebycheff decomposition approach performs similarly to NSGA-II on a set of continuous MOP test instances. MOEA/D with an advanced decomposition approach performs much better than NSGA-II on 3-ob- jective continuous test instances. MOEA/D using a small population is able to produce a small number of very evenly distributed solutions. • • Objective normalization techniques can be incorporated into MOEA/D for dealing with disparately scaled objec- tives. It is very natural to use scalar optimization methods in MOEA/D since each solution is associated with a scalar optimization problem. In contrast, one of the major short- comings of nondecomposition MOEAs is that there is no easy way for them to take the advantage of scalar optimiza- tion methods. This paper is organized as follows. Section II introduces three decomposition approaches for MOPs. Section III presents MOEA/D. Sections IV and V compare MOEA/D with MOGLS and NSGA-II and show that MOEA/D outperforms or performs similarly to MOGLS and NSGA-II. Section VI presents more experimental studies on MOEA/D. Section VII concludes this paper. II. DECOMPOSITION OF MULTIOBJECTIVE OPTIMIZATION There are several approaches for converting the problem of approximation of the PF into a number of scalar optimization problems. In the following, we introduce three approaches, which are used in our experimental studies. A. Weighted Sum Approach [1] This approach considers a convex combination of the dif- be a weight vector, ferent objectives. Let i.e., . Then, the optimal solution to the following scalar optimization problem: for all and (2) is a Pareto optimal point to (1),2 where we use to em- phasize that is a coefﬁcient vector in this objective function, is the variables to be optimized. To generate a set of while different Pareto optimal vectors, one can use different weight in the above scalar optimization problem. If the PF vectors is concave (convex in the case of minimization), this approach could work well. However, not every Pareto optimal vector can be obtained by this approach in the case of nonconcave PFs. To overcome these shortcomings, some effort has been made to -constraint into this ap- incorporate other techniques such as proach, more details can be found in [1]. B. Tchebycheff Approach [1] In this approach, the scalar optimization problem is in the form where is the reference point, i.e., 3 for each . For each Pareto (3) 2If (1) is for minimization, “maximize” in (2) should be changed to “mini- mize.” 3In the case when the goal of (1) is minimization, z = minff (x)jx 2 g. Authorized licensed use limited to: UNIVERSITY OF ESSEX. Downloaded on May 6, 2009 at 06:54 from IEEE Xplore. Restrictions apply.

714 IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 11, NO. 6, DECEMBER 2007 such that there exists a weight vector optimal point is the optimal solution of (3) and each optimal solution of (3) is a Pareto optimal solution of (1). Therefore, one is able to obtain different Pareto optimal solutions by altering the weight vector. One weakness with this approach is that its aggregation function is not smooth for a continuous MOP. However, it can still be used in the EA framework proposed in this paper since our algorithm does not need to compute the derivative of the aggregation function. C. Boundary Intersection (BI) Approach Several recent MOP decomposition methods such as Normal-Boundary Intersection Method [9] and Normalized Normal Constraint Method [10] can be classiﬁed as the BI approaches. They were designed for a continuous MOP. Under some regularity conditions, the PF of a continuous MOP is part of the most top right4 boundary of its attainable objective set. Geometrically, these BI approaches aim to ﬁnd intersection points of the most top boundary and a set of lines. If these lines are evenly distributed in a sense, one can expect that the resultant intersection points provide a good approximation to the whole PF. These approaches are able to deal with noncon- cave PFs. In this paper, we use a set of lines emanating from the reference point. Mathematically, we consider the following scalar optimization subproblem5: and (4) , as in the above subsection, are a weight vector where and the reference point, respectively. As illustrated in Fig. 1, the is always in , constraint the line with direction . The goal is to push as high as possible so that it reaches the boundary of the attainable objective set. and passing through ensures that One of the drawbacks of the above approach is that it has to handle the equality constraint. In our implementation, we use a penalty method to deal with the constraint. More precisely, we consider6: where (5) is a preset penalty parameter. Let on the line . As shown in Fig. 2, is the distance between be the projection of is the distance be- tween is set appropriately, the solutions to (4) and (5) should be very close. Hereafter, we call this method the penalty-based boundary in- tersection (PBI) approach. and . If and . The advantages of the PBI approach (or general BI ap- proaches ) over the the Tchebycheff approach are as follows. 4In the case of minimization, it will be part of the most left bottom. 5In the case when the goal of (1) is minimization, this equality constraint in this subproblem should be changed to F (x) z = d. 6In the case when the goal of (1) is minimization, d k(F (x) z ) k=kk and to d = kF (x) (z + d )k. = Fig. 1. Illustration of boundary intersection approach. Fig. 2. Illustration of the penalty-based boundary intersection approach. • • In the case of more than two objectives, let both the PBI approach and the Tchebycheff approach use the same set of evenly distributed weight vectors, the resultant optimal solutions in the PBI should be much more uniformly dis- tributed than those obtained by the Tchebycheff approach [9], particularly when the number of weight vectors is not large. If , it is still possible that dominates , while it is rare for and other BI aggrega- tion functions. However, these beneﬁts come with a price. One has to set the value of the penalty factor. It is well-known that a too large or too small penalty factor will worsen the performance of a penalty method. The above approaches can be used to decompose the approxi- mation of the PF into a number of scalar optimization problems. A reasonably large number of evenly distributed weight vectors usually leads to a set of Pareto optimal vectors, which may not be evenly spread but could approximate the PF very well. There are many other decomposition approaches in the liter- ature that could also be used in our algorithm framework. Since Authorized licensed use limited to: UNIVERSITY OF ESSEX. Downloaded on May 6, 2009 at 06:54 from IEEE Xplore. Restrictions apply.

ZHANG AND LI: MOEA/D: A MULTIOBJECTIVE EVOLUTIONARY ALGORITHM BASED ON DECOMPOSITION 715 our major purpose is to study the feasibility and efﬁciency of the algorithm framework. We only use the above three decomposi- tion approaches in the experimental studies in this paper. Step 1) Initialization: Step 1.1) Set . III. THE FRAMEWORK OF MULTIOBJECTIVE EVOLUTIONARY ALGORITHM BASED ON DECOMPOSITION (MOEA/D) A. General Framework Multiobjective evolutionary algorithm based on decomposi- tion (MOEA/D), the algorithm proposed in this paper, needs to decompose the MOP under consideration. Any decomposition approaches can serve this purpose. In the following description, we suppose that the Tchebycheff approach is employed. It is very trivial to modify the following MOEA/D when other de- composition methods are used. Let be a set of even spread weight vectors and be the reference point. As shown in Section II, the problem of scalar approximation of the PF of (1) can be decomposed into optimization subproblems by using the Tchebycheff approach and the objective function of the th subproblem is (6) where objective functions simultaneously in a single run. . MOEA/D minimizes all these Note that is continuous of should be close to that of , the optimal solution of and are close to each other. Therefore, any information about should be helpful . This is a major motivation behind ’s with weight vectors close to if these for optimizing MOEA/D. In MOEA/D, a neighborhood of weight vector is deﬁned as a set of its several closest weight vectors in . The neighborhood of the th subproblem consists of all the sub- problems with the weight vectors from the neighborhood of . The population is composed of the best solution found so far for each subproblem. Only the current solutions to its neigh- boring subproblems are exploited for optimizing a subproblem in MOEA/D. At each generation , MOEA/D with the Tchebycheff ap- proach maintains: • a population of points current solution to the th subproblem; , where is the • • , where for each is the -value of , i.e., ; , where is the best value found so far for objective ; • an external population (EP), which is used to store non- dominated solutions found during the search. The algorithm works as follows: Input: • MOP (1); • a stopping criterion; • the number of : MOEA/D; the subproblems considered in • a uniform spread of weight vectors: • : the number of the weight vectors in the neighborhood ; of each weight vector. Output: . Step 1.2) Compute the Euclidean distances between any closest weight two weight vectors and then work out the , set vectors to each weight vector. For each closest , where are the weight vectors to . Step 1.3) Generate an initial population randomly or by a problem-speciﬁc method. Set . Step 1.4) Initialize method. Step 2) Update: For , do by a problem-speciﬁc Step 2.1) Reproduction: Randomly select two indexes from , and then generate a new solution from and by using genetic operators. Step 2.2) Improvement: Apply a problem-speciﬁc repair/ improvement heuristic on to produce . Step 2.3) Update of : For each , then set . , if Step 2.4) Update of Neighboring Solutions: For each index , if and . Step 2.5) Update of : , then set Remove from all the vectors dominated by Add to if no vectors in dominate . . Step 3) Stopping Criteria: If stopping criteria is satisﬁed, then stop and output . Otherwise, go to Step 2. In initialization, contains the indexes of the closest vectors of . We use the Euclidean distance to measure the ’s closeness between any two weight vectors. Therefore, closest vector is itself, and then , the th subproblem can be regarded as a neighbor of the th sub- problem. . If In the th pass of the loop in Step 2, the problems of the th subproblem are considered. Since neighboring sub- and in Step 2.1 are the current best solutions to neighbors of the th subproblem, their offspring should hopefully be a good solution to the th subproblem. In Step 2.2, a problem-speciﬁc heuristic7 is used to repair invalidates any constraints, and/or optimize the th . Therefore, the resultant solution is feasible and very likely to have a lower function value for the neighbors of th subproblem. Step 2.4 considers all the neighbors of the th subproblem, it replaces performs better than with regard to the th subproblem. is needed in computing the value of in the case when in Step 2.4. with if Since it is often very time-consuming to ﬁnd the exact ref- , we use , which is initialized in Step 1.4 by a erence point 7An exemplary heuristic can be found in the implementation of MOEA/D for the MOKP in Section IV. Authorized licensed use limited to: UNIVERSITY OF ESSEX. Downloaded on May 6, 2009 at 06:54 from IEEE Xplore. Restrictions apply.

716 IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 11, NO. 6, DECEMBER 2007 problem-speciﬁc method8 and updated in Step 2.3, as a substi- , initialized in Step tute for 1.1, is updated by the new generated solution . The external population in Step 2.5. in In the case when the goal in (1) is to minimize , the inequality in Step 2.3 should be reversed. B. Discussions 1) Why a Finite Number of Subproblems are Considered in MOEA/D: A weight vector used in MOEA/D is one of the preselected weight vectors. MOEA/D spends about the same aggregation functions, while amount of effort on each of the MOGLS randomly generates a weight vector at each iteration, aiming at optimizing all the possible aggregation functions. Re- call that a decision maker only needs a ﬁnite number of evenly distributed Pareto solutions, optimizing a ﬁnite of selected scalar optimization subproblems is not only realistic but also appropriate. Since the computational resource is always limited, optimizing all the possible aggregation functions would not be very practical, and thus may waste some computational effort. 2) How Diversity is Maintained in MOEA/D: As mentioned in Section I, a MOEA needs to maintain diversity in its pop- ulation for producing a set of representative solutions. Most, if not all, of nondecomposition MOEAs such as NSGA-II and SPEA-II use crowding distances among the solutions in their selection to maintain diversity. However, it is not always easy to generate a uniform distribution of Pareto optimal objective vectors in these algorithms. In MOEA/D, a MOP is decom- posed into a number of scalar optimization subproblems. Dif- ferent solutions in the current population are associated with different subproblems. The “diversity” among these subprob- lems will naturally lead to diversity in the population. When the decomposition method and the weight vectors are properly chosen, and thus the optimal solutions to the resultant subprob- lems are evenly distributed along the PF, MOEA/D will have a good chance of producing a uniform distribution of Pareto so- lutions if it optimizes all these subproblems very well. 3) Mating Restriction and the Role of in MOEA/D: is is too small, two solutions chosen ( the size of the neighborhood. Only current solutions to the closest neighbors of a subproblem are used for optimizing it in MOEA/D. In a sense, two solutions have a chance to mate only when they are for two neighboring subproblems. This is a . If mating restriction. Attention should be paid to the setting of ) for undergoing genetic operators in Step 2.1 may be very similar since they are for very similar subproblems, consequently, , the solution generated in Step 2.2, could be very close to their parents and areas in the search space. On the other hand, if and may be poor for the subproblem under consideration, and so is their offspring . Therefore, the exploitation ability of the algorithm is weakened. Moreover, a too large will increase the computational overhead of Step 2.4. . Therefore, the algorithm lacks the ability to explore new is too large, and C. Variants of MOEA/D We can use any other decomposition methods in MOEA/D. When the weighted sum approach is used, MOEA/D does not need to maintain . Step 2.2 allows MOEA/D to be able to make use of a scalar optimization method very naturally. One can take the as the objective function in the heuristic in Step 2.2. Although it is one of the major features of MOEA/D, Step 2.2 is not a must in MOEA/D, particularly if Step 2.1 can produce a feasible solution. or Using the external population is also an option, although it is often very helpful for improving the performance of the algorithm. An alternative is to return the ﬁnal internal popula- is not maintained. tion as an approximation to the PF when Of course, other sophisticated strategies [21] for updating can be easily adopted in the framework of MOEA/D. One can to avoid any possible memory overﬂow also limit the size of problem. The cellular multiobjective genetic algorithm (cMOGA) of Murata et al. [40] can also be regarded as an evolutionary algorithm using decomposition. In essence it uses the same neighborhood relationship for mating restriction. cMOGA differs from MOEA/D in selecting solutions for genetic oper- ators and updating the internal population, and it has to insert solutions from its external population to its internal population at each generation for dealing with nonconvex PFs, since it uses weighted sums of the objectives as its guided functions and there is no mechanism for keeping the best solution found so far to each subproblem in its internal population. IV. COMPARISON WITH MOGLS In the following, we ﬁrst introduce MOGLS and then analyze the complexity of MOGLS and MOEA/D. We also compare the performances of these two algorithms on a set of test instances of the multiobjective 0/1 knapsack problem. The major reasons for choosing MOGLS for comparison are that it is also based on decomposition and performs better than a number of popular algorithms on the multiobjective 0/1 knapsack problem [29]. A. MOGLS MOGLS was ﬁrst proposed by Ishibuchi and Murata in [28], and further improved by Jaszkiewicz [29]. The basic idea is to reformulate the MOP (1) as simultaneous optimization of all weighted Tchebycheff functions or all weighted sum functions. In the following, we give a brief description of Jaszkiewicz’s version of MOGLS. At each iteration, MOGLS maintains: • a set of current solutions (CS), and the -values of these solutions; • an external population (EP), which is used to store non- dominated solutions. If MOGLS optimizes weighted Tchebycheff functions, it should also maintain: • far for objective , where . is the largest value found so MOGLS needs two control parameters and . 8Two exemplary methods can be found in Sections IV and V. of its temporary elite population and Authorized licensed use limited to: UNIVERSITY OF ESSEX. Downloaded on May 6, 2009 at 06:54 from IEEE Xplore. Restrictions apply. is the initial size of is the size .

ZHANG AND LI: MOEA/D: A MULTIOBJECTIVE EVOLUTIONARY ALGORITHM BASED ON DECOMPOSITION 717 MOGLS works as follows: B. Comparison of Complexity of MOEA/D and MOGLS Input: • MOP (1); • a stopping criterion; • • : the size of temporary elite population; : the size of initial population. Output: . Step 1) Initialization: Step 1.1) Generate or by a problem-speciﬁc method. Then, be initial solutions . randomly is initialized to Step 1.2) Initialize method. by a problem-speciﬁc Step 1.3) all the nondominated solutions in is initialized to be the set of the . -values of Step 2) Update: Step 2.1) Reproduction: Uniformly randomly generate a weight vector . From Tchebycheff aggregation function best solutions, with regard to the with the weight vector select the , to form a temporary elite population (TEP). Draw at random two solutions from a new solution operators. , and then generate from these two solutions by using genetic Step 2.2) Improvement: Apply a problem-speciﬁc repair/ improvement heuristic on to generate . Step 2.3) Update of : For each , then set . , if Step 2.4) Update of Solutions in TEP: If in is better than the worst solution in with the weight vector with regard to and different from any solutions with regard to -values, then add it to the set . If the size of solution in . is larger than , delete the oldest Step 2.5) Update of EP: Remove from all the vectors dominated by Add to if no vectors in dominates . . Step 3) Stopping Criteria: If stopping criteria is satisﬁed, then stop and output . Otherwise, go to Step 2. As in MOEA/D with the Tchebycheff approach, is used as a substitute for . In the case of MOGLS with the in should be replaced by and there weighted sum approach, is no need to store . Therefore, Step 2.3 should be removed. -values of all the current solutions MOGLS needs to keep the since these -values will be used in Step 2.4 for computing the . values of and its external population to maintain its internal population of population 1) Space Complexity: During the search, MOEA/D needs solutions, and external , while MOGLS stores the set of current solutions increases until it reaches its upper bound, which is suggested to be set as in [29]. Therefore, if in MOGLS is much larger than in MOEA/D and both algorithms produce about the same number of nondominated solutions, then the space com- plexity of MOEA/D is lower than that of MOGLS. . The size of 2) Computational Complexity: The major computational costs in both MOEA/D and MOGLS are involved in their Step 2. Both a single pass of Step 2 in MOEA/D and Step 2 in . Let us compare MOGLS generates one new trial solution the computational complexity in a single pass of Step 2 in MOEA/D and Step 2 in MOGLS. , which needs . One has to compute the • Step 2.1 in MOEA/D versus Step 2.1 in MOGLS: MOGLS -values has to generate of all the points in basic basic operations for operations. It also needs if a naive selection method is employed, selecting while Step 2.1 in MOEA/D only needs to randomly pick , the size two solutions for genetic operators. Note that , could be very large (e.g, it was set from 3000 to 7000 of in [29]), the computational cost of Step 2.1 in MOGLS is much higher than that of Step 2.1 in MOEA/D. • Steps 2.2 and 2.3 in MOEA/D are the same as Steps 2.2 and 2.3 in MOGLS, respectively. • Step 2.4 in MOEA/D versus Step 2.4 in MOGLS: Step 2.4 basic operations, while Step 2.4 basic operations. In the case when are close as in our experiments, there is no sig- in MOEA/D needs in MOGLS needs and niﬁcant difference in computational costs between them. Therefore, we can conclude that each pass of Step 2 in MOEA/D involves less computational cost than Step 2 in MOGLS does. C. Multiobjective 0–1 Knapsack Problem Given a set of items and a set of knapsacks, the multiob- jective 0–1 knapsack problem (MOKP) can be stated as (7) is the proﬁt of item in knapsack , where is the weight of item in knapsack , and knapsack . the knapsacks. is the capacity of means that item is selected and put in all The MOKP is NP-hard and can model a variety of applica- tions in resource allocation. A set of nine test instances of the above problem have been proposed in [13] and widely used in testing multiobjective heuristics. MOGLS outperforms a number of MOEAs on these test instances [29]. In this paper, Authorized licensed use limited to: UNIVERSITY OF ESSEX. Downloaded on May 6, 2009 at 06:54 from IEEE Xplore. Restrictions apply.

718 IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 11, NO. 6, DECEMBER 2007 we will also use these nine instances for comparing the perfor- mances of MOEA/D and MOGLS. D. Implementations of MOEA/D and MOGLS for MOKP 1) Repair Method: To apply an EA for the MOKP, one needs a heuristic for repairing infeasible solutions. Several repair ap- proaches have been proposed for this purpose [13], [29]. Let and be an infeasible solution to in (7) are nonnegative, one can remove (7). Note that from 1 to some items from it (i.e., change the values of some 0) for making it feasible. Recently, Jaszkiewicz proposed and used the following greedy repair method9. Input: • MOP (7); • a solution: • an objective function to be maximized: ; Output: a feasible solution . 4. Add by . to , then add . Remove from to EP if no vectors in all the vectors dominated dominate • Genetic operators in Step 2.1: The genetic operators used are the one-point crossover operator and the standard mutation operator. The one-point crossover is ﬁrst applied to the two solutions and generates one child solution, then the standard mutation operator mutates it to produce a new solution . The mutation mutates each position of the child solution independently with probability 0.01. • Heuristic in Step 2.2: The repair method described in this section is used. 3) Implementation of MOEA/D: We use the same genetic operators in Step 2.1 and the repair method in Step 2.2 as in the is also the implementation of MOGLS. The initialization of (the initial solution to same as in MOGLS. Initialization of the th subproblem) is performed as follows. Step 1) If is feasible, then set and return . • Initialization of in Step 1.3: Taking Step 2) Set Step 3) Select such that and . where for all Set is different from only in position , i.e., and . and go to Step 1. In this approach, items are removed one by one from until becomes feasible. An item with the heavy weights (i.e., ) in the overﬁlled knapsacks and little contribution to (i.e., ) is more likely to be removed. 2) Implementation of MOGLS: To have a fair comparison, we directly use Jaszkiewicz’s latest implementation of MOGLS for the MOKP, the details of MOGLS with the Tchebycheff ap- proach are given as follows. • Initialization of as the objective function, apply the repair method on a randomly to generated point and produce a feasible solution. Set be the value of the resultant point. : Taking each • Initialization of and : Set and . Then, Repeat times: 1. Randomly generate a weight vector sampling method described in [29]. by using the 2. Randomly generate a solution , where the probability of equals to 0.5. 3. Taking repair method to as the objective function, apply the and obtain a feasible solution . 9This approach is used in the latest version of his implementation, which can be downloaded from his web http://www-idss.cs.put.poznan.pl/~jaszkiewicz/ and is slightly better than that used in his earlier paper [29]. as the objective function, apply the repair method to a randomly generated solution. Set to be the resultant solution. Tchebycheff aggregation function is used in the above implementations of MOEA/D and MOGLS. The implementations of these two algorithms with the weighted sum approach in our experimental studies are the same as their counterparts with the Tchebycheff approach, as the objective in the repair method except that they use and do not maintain . E. Parameter Setting and The setting of , is the same as in [29]. of The values of in MOGLS, which determines the size is set to 20 for all the instances. for different instances are given in Table I. in MOEA/D is set to 10 for all the test instances. The set- in MOEA/D is controlled by a param- are all the weight vectors in ting of eter which each individual weight takes a value from . More precisely, and Therefore, the number of such vectors is Table I lists the value of instance. For the instances with two objectives, the value of in MOEA/D is the same as that of instances with three objectives, , and therefore in MOEA/D for each test in MOGLS. For all the and . For all the instances with four objectives, , and . It should be noted that the size of the internal in MOGLS can reach , much larger than then population that of the internal population in MOEA-D. The above method for generating weight vectors in MOEA-D works well in our experiments. It could, however, result in a very large when , the number of the objectives is large. To over- come this shortcoming, one should resort to advanced experi- mental design methods [30], [31] to generate weight vectors. Authorized licensed use limited to: UNIVERSITY OF ESSEX. Downloaded on May 6, 2009 at 06:54 from IEEE Xplore. Restrictions apply.

ZHANG AND LI: MOEA/D: A MULTIOBJECTIVE EVOLUTIONARY ALGORITHM BASED ON DECOMPOSITION 719 PARAMETER SETTING OF MOEA/D AND MOGLS FOR THE TEST INSTANCES OF THE 0/1 KNAPSACK PROBLEM TABLE I AVERAGE CPU TIME (IN SECONDS) USED BY MOEA/D AND MOGLS TABLE II Both of the algorithms stop after 500 calls of the repair method. AVERAGE SET COVERAGE BETWEEN MOEA/D (A) AND MOGLS (B) TABLE III In our experimental studies, both have been used in the repair method. In the following, W-MOEA/D (W-MOGLS) stands for MOEA/D (MOGLS) in which is used, while T-MOEA/D (T-MOGLS) represents MOEA/D (MOGLS) in which is used. and F. Experimental Results Both MOGLS and MOEA/D have been independently run for 30 times for each test instance on identical computers (Pentium(R) 3.2 GHZ, 1.00 GB). Due to the nature of MOPs, multiple performance indexes should be used for comparing the performances of different algorithms [2], [32]. In our experiments, the following performance indexes are used. • Set Coverage ( -metric): Let imations to the PF of a MOP, percentage of the solutions in least one solution in , i.e., and be two approx- is deﬁned as the that are dominated by at is not necessarily equal to means that all solutions in . are dominated implies that by some solutions in no solution in , while is dominated by a solution in • Distance from Representatives in the PF ( . -metric): be a set of uniformly distributed points along the be an approximation to the PF, the average dis- Let PF. Let tance from to is deﬁned as . If where and the points in is the minimum Euclidean distance between is large enough to represent could measure both the diver- in a sense. To have a low value , set must be very close to the PF and cannot the PF very well, sity and convergence of of miss any part of the whole PF. In the case when we do not know the actual PF, we can set to be an upper approximation of the PF. Jaszkiewicz has produced a very good upper approximation to each 0/1 knapsack test instance by solving the linear program- ming relaxed version of (3) with a number of uniformly ’s [29]. The number of the points in the distributed upper approximation is 202 for each of the bi-objective instances, 1326 for the 3-objective instances, and 3276 for is set as such an the 4-objectives. In our experiments, approximation. Table II gives the average CPU time used by each algorithm -metric for each instance. Table III presents the means of the values of the ﬁnal approximations obtained by the two algo- rithms with two different repair methods. from Table IV shows the mean and standard deviation of the -metric values in MOEA/D and MOGLS for each instance. Fig. 3 shows the evolution of the average -metric value in 30 runs with the number of the calls of of the repair method in each algorithm for each test instance. -metric values are large, we use the Since the ranges of -metric value logarithmic scale for the axes of the average with the in Fig. 3. Figs. 4 and 5 plot the distributions of -metric value found in each algorithm for the three lowest bi-objective instances. We can make the following remarks: • With the same number of the calls of a repair method (i.e., the same number of trial solutions), it is evident from Table II that MOEA/D needs less computational Authorized licensed use limited to: UNIVERSITY OF ESSEX. Downloaded on May 6, 2009 at 06:54 from IEEE Xplore. Restrictions apply.

分享到：

赞收藏

资料库

MOEA/D原版英文论文.pdf

相关推荐

人工智能

热门标签

最新资料