NSGA-III
An Evolutionary Many-Objective Optimization Algorithm Using Reference-point Based Non-dominated Sorting Approach,
Part I:Solving Problems with Box Constraints
Kalyanmoy Deb,Fellow,IEEE and Himanshu Jain
Abstract—Having developed multi-objective optimization al-gorithms using evolutionary optimization methods and demon-strated their niche on various practical problems involving mostly two and three objectives,there is now a growing need for developing evolutionary multi-objective optimization(EMO) algorithms for handling many-objective(having four or more objectives)optimization problems.In this paper,we recognize a few recent efforts and discuss a number of viable directions for developing a potential EMO algorithm for solving many-objective optimization problems.Thereafter,we suggest a reference-point based many-objective NSGA-II(we call it NSGA-III)that em-phasizes population members which are non-dominated yet close to a set of supplied reference points.The proposed NSGA-III is applied to a number of many-objective test problems having two to15objectives and compared with two versions of a recently suggested EMO algorithm(MOEA/D).While each of the two MOEA/D methods works well on different classes of problems, the proposed NSGA-III is found to produce satisfactory results on all problems considered in this study.This paper presents results on unconstrained problems and the sequel paper considers constrained and other specialties in handling many-objective optimization problems.
Index Terms—Many-objective optimization,evolutionary com-putation,large dimension,NSGA-III,non-dominated sorting, multi-criterion optimization.
I.I NTRODUCTION
Evolutionary multi-objective optimization(EMO)method-ologies have amply shown their niche in?nding a set of well-converged and well-diversi?ed non-dominated solutions in different two and three-objective optimization problems since the beginning of nineties.However,in most real-world problems involving multiple stake-holders and functionalities, there often exists many optimization problems that involve four or more objectives,sometimes demanding to have10to 15objectives[1],[2].Thus,it is not surprising that handling a large number of objectives had been one of the main research activities in EMO for the past few years.Many-objective K.Deb is with Department of Electrical and Computer Engineering. Michigan State University,428S.Shaw Lane,2120EB,East Lansing,MI 48824,USA,e-mail:kdeb@https://www.wendangku.net/doc/2f10679090.html,(see https://www.wendangku.net/doc/2f10679090.html,/?kdeb). Prof.Deb is also a visiting professor at Aalto University School of Business, Finland and University of Sk¨o vde,Sweden.
H.Jain is with Eaton Corporation,Pune411014,India,email:himan-shu.j689@https://www.wendangku.net/doc/2f10679090.html,.
Copyright(c)2012IEEE.Personal use of this material is permitted. However,permission to use this material for any other purposes must be obtained from the IEEE by sending a request to pubs-permissions@https://www.wendangku.net/doc/2f10679090.html,.problems pose a number of challenges to any optimization algorithm,including an EMO.First and foremost,the propor-tion of non-dominated solutions in a randomly chosen set of objective vectors becomes exponentially large with an increase of number of objectives.Since the non-dominated solutions occupy most of the population slots,any elite-preserving EMO faces a dif?culty in accommodating adequate number of new solutions in the population.This slows down the search process considerably[3],[4].Second,implementation of a diversity-preservation operator(such as the crowding distance operator[5]or clustering operator[6])becomes a computationally expensive operation.Third,visualization of a large-dimensional front becomes a dif?cult task,thereby causing dif?culties in subsequent decision-making tasks and in evaluating the performance of an algorithm.For this purpose, the performance metrics(such as hyper-volume measure[7]or other metrics[3],[8])are either computationally too expensive or may not be meaningful.
An important question to ask is then‘Are EMOs useful for many-objective optimization problems?’.Although the third dif?culty related to visualization and performance measures mentioned above cannot be avoided,some algorithmic changes to the existing EMO algorithms may be possible to address the?rst two concerns.In this paper,we review some of the past efforts[9],[10],[11],[12],[13],[14]in devising many-objective EMOs and outline some viable directions for designing ef?cient many-objective EMO methodologies. Thereafter,we propose a new method that uses the framework of NSGA-II procedure[5]but works with a set of supplied or prede?ned reference points and demonstrate its ef?cacy in solving two to15-objective optimization problems.In this paper,we introduce the framework and restrict to solving unconstrained problems of various kinds,such as having normalized,scaled,convex,concave,disjointed,and focusing on a part of the Pareto-optimal front.Practice may offer a number of such properties to exist in a problem.Therefore,an adequate test of an algorithm for these eventualities remains as an important task.We compare the performance of the proposed NSGA-III with two versions of an existing many-objective EMO(MOEA/D[10]),as the method is somewhat similar to the proposed method.Interesting insights about working of both versions of MOEA/D and NSGA-III are revealed.The proposed NSGA-III is also evaluated for its use in a few other interesting multi-objective optimization and
decision-making tasks.In the sequel of this paper,we suggest an extension of the proposed NSGA-III for handling many-objective constrained optimization problems and a few other special and challenging many-objective problems.
In the remainder of this paper,we?rst discuss the dif?-culties in solving many-objective optimization problems and then attempt to answer the question posed above about the usefulness of EMO algorithms in handling many objectives. Thereafter,in Section III,we present a review of some of the past studies on many-objective optimization including a recently proposed method MOEA/D[10].Then,in Section IV, we outline our proposed NSGA-III procedure in detail.Results on normalized DTLZ test problems up to15objectives using NSGA-III and two versions of MOEA/D are presented next in Section V-A.Results on scaled version of DTLZ problems suggested here are shown next.Thereafter in subsequent sections,NSGA-III procedure is tested on different types of many-objective optimization problems.Finally,NSGA-III is applied to two practical problems involving three and nine objective problems in Section VII.Conclusions of this extensive study are drawn in Section VIII.
II.M ANY-O BJECTIVE P ROBLEMS
Loosely,many-objective problems are de?ned as problems having four or more objectives.Two and three-objective prob-lems fall into a different class as the resulting Pareto-optimal front,in most cases,in its totality can be comprehensively visualized using graphical means.Although a strict upper bound on the number of objectives for a many-objective optimization problem is not so clear,except a few occasions [15],most practitioners are interested in a maximum of10 to15objectives.In this section,?rst,we discuss dif?culties that an existing EMO algorithm may face in handling many-objective problems and investigate if EMO algorithms are useful at all in handling a large number of objectives.
A.Dif?culties in Handling Many Objectives
It has been discussed elsewhere[4],[16]that the current state-of-the-art EMO algorithms that work under the principle of domination[17]may face the following dif?culties:
1)A large fraction of population is non-dominated:It is
well-known[3],[16]that with an increase in number of objectives,an increasingly larger fraction of a ran-domly generated population becomes non-dominated.
Since most EMO algorithms emphasize non-dominated solutions in a population,in handling many-objective problems,there is not much room for creating new solutions in a generation.This slows down the search process and therefore the overall EMO algorithm be-comes inef?cient.
2)Evaluation of diversity measure becomes computation-
ally expensive:To determine the extent of crowding of solutions in a population,the identi?cation of neigh-bors becomes computationally expensive in a large-dimensional space.Any compromise or approximation in diversity estimate to make the computations faster
may cause an unacceptable distribution of solutions at the end.
3)Recombination operation may be inef?cient:In a many-
objective problem,if only a handful of solutions are to be found in a large-dimensional space,solutions are likely to be widely distant from each other.In such a population,the effect of recombination operator(which is considered as a key search operator in an EMO) becomes questionable.Two distant parent solutions are likely to produce offspring solutions that are also distant from parents.Thus,special recombination operators (mating restriction or other schemes)may be necessary for handling many-objective problems ef?ciently.
4)Representation of trade-off surface is dif?cult:It is
intuitive to realize that to represent a higher dimensional trade-off surface,exponentially more points are needed.
Thus,a large population size is needed to represent the resulting Pareto-optimal front.This causes dif?culty for
a decision-maker to comprehend and make an adequate
decision to choose a preferred solution.
5)Performance metrics are computationally expensive to
compute:Since higher-dimensional sets of points are to be compared against each other to establish the performance of one algorithm against another,a larger computational effort is needed.For example,computing hyper-volume metric requires exponentially more com-putations with the number of objectives[18],[19].
6)Visualization is dif?cult:Finally,although it is not a
matter related to optimization directly,eventually visu-alization of a higher-dimensional trade-off front may be dif?cult for many-objective problems.
The?rst three dif?culties can only be alleviated by certain modi?cations to existing EMO methodologies.The fourth,?fth,and sixth dif?culties are common to all many-objective optimization problems and we do not address them adequately here.
B.EMO Methodologies for Handling Many-Objective Prob-lems
Before we discuss the possible remedies for three dif?culties mentioned above,here we highlight two different many-objective problem classes for which existing EMO method-ologies can still be used.
First,existing EMO algorithms may still be useful in?nding a preferred subset of solutions(a partial set)from the complete Pareto-optimal set.Although the preferred subset will still be many-dimensional,since the targeted solutions are focused in a small region on the Pareto-optimal front,most of the above dif?culties will be alleviated by this principle.A number of MCDM-based EMO methodologies are already devised for this purpose and results on as large as10-objective problems have shown to perform well[20],[21],[22],[23]. Second,many problems in practice,albeit having many objectives,often degenerate to result in a low-dimensional Pareto-optimal front[4],[11],[24],[25].In such problems, identi?cation of redundant objectives can be integrated with an EMO to?nd the Pareto-optimal front that is low-dimensional.
Since the ultimate front is as low as two or three-dimensional, existing EMO methodologies should work well in handling such problems.A previous study of NSGA-II with a principal component analysis(PCA)based procedure[4]was able to solve as large as50-objective problems having a two-objective Pareto-optimal front.
C.Two Ideas for a Many-Objective EMO
Keeping in mind the?rst three dif?culties associated with a domination-based EMO procedure,two different strategies can be considered to alleviate the dif?culties:
1)Use of a special domination principle:The?rst dif?culty
mentioned above can be alleviated by using a special domination principle that will adaptively discretize the Pareto-optimal front and?nd a well-distributed set of points.For example,the use of?-domination principle
[26],[27]will make all points within?distance from a
set of Pareto-optimal points?-dominated and hence the process will generate a?nite number of Pareto-optimal points as target.Such a consideration will also alleviate the second dif?culty of diversity preservation.The third dif?culty can be taken care of by the use of a mating restriction scheme or a special recombination scheme in which near-parent solutions are emphasized(such as SBX with a large distribution index[28]).Other special domination principles[29],[30]can also be used for this purpose.Aguirre and Tanaka[31]and Sato et al.[32] suggested the use of a subset of objectives for dominance check and using a different combination of objectives in every generation.The use of?xed cone-domination[33],
[34]or variable cone-domination[35]principles can also
be tried.These studies were made in the context of low-dimensional problems and their success in solving many-objective optimization is yet to be established.
2)Use of a prede?ned multiple targeted search:It has
been increasingly clear that it is too much to expect from a single population-based optimization algorithm to have convergence of its population near the Pareto-optimal front and simultaneously its distributed uni-formly around the entire front in a large-dimensional problem.One way to handle such many-objective opti-mization problems would be to aid the diversity mainte-nance issue by some external means.This principle can directly address the second dif?culty mentioned above.
Instead of searching the entire search space for Pareto-optimal solutions,multiple prede?ned targeted searches can be set by an algorithm.Since optimal points are found corresponding to each of the targeted search task, the?rst dif?culty of dealing with a large non-dominated set is also alleviated.The recombination issue can be addressed by using a mating restriction scheme in which two solutions from neighboring targets are participated in the recombination operation.Our proposed algorithm (NSGA-III)is based on this principle and thus we discuss this aspect in somewhat more detail.We suggest two different ways to implement the prede?ned multiple targeted search principle:
a)A set of prede?ned search directions spanning
the entire Pareto-optimal front can be speci?ed
beforehand and multiple searches can be performed
along each direction.Since the search directions
are widely distributed,the obtained optimal points
are also likely to be widely distributed on the
Pareto-optimal front in most problems.Recently
proposed MOEA/D procedure[10]uses this con-
cept.
b)Instead of multiple search directions,multiple pre-
de?ned reference points can be speci?ed for this
purpose.Thereafter,points corresponding to each
reference point can be emphasized to?nd set of
widely distributed set of Pareto-optimal points.A
few such implementations were proposed recently
[36],[37],[38],[14],and this paper suggests
another approach extending and perfecting the al-
gorithm proposed in the?rst reference[36].
III.E XISTING M ANY-O BJECTIVE O PTIMIZATION
A LGORITHMS
Garza-Fabre,Pulido and Coello[16]suggested three single-objective measures by using differences in individual objective values between two competing parents and showed that in5to 50-objective DTLZ1,DTLZ3and DTLZ6problems the con-vergence property can get enhanced compared to a number of existing methods including the usual Pareto-dominance based EMO approaches.Purshouse and Fleming[39]clearly showed that diversity preservation and achieving convergence near the Pareto-optimal front are two contradictory goals and usual genetic operators are not adequate to attain both goals simul-taneously,particularly for many-objective problems.Another study[40]extends NSGA-II by adding diversity-controlling operators to solve six to20-objective DTLZ2problems. K¨o ppen and Yoshida[41]claimed that NSGA-II procedure in its originality is not suitable for many-objective optimiza-tion problems and suggested a number of metrics that can potentially replace NSGA-II’s crowding distance operator for better performance.Based on simulation studies on two to 15-objective DTLZ2,DTLZ3and DTLZ6problems,they suggested to use a substitute assignment distance measure as the best strategy.Hadka and Reed[42]suggested an ensemble-based EMO procedure which uses a suitable recombination operator adaptively chosen from a set of eight to10different pre-de?ned operators based on their generation-wise success rate in a problem.It also uses?-dominance concept and an adaptive population sizing approach that is reported to solve up to eight-objective test problems successfully.Bader and Zitzler[43]have suggested a fast procedure for computing sample-based hyper-volume and devised an algorithm to?nd a set of trade-off solutions for maximizing the hyper-volume.A growing literature on approximate hyper-volume computation [44],[18],[45]may make such an approach practical for solving many-objective problems.
The above studies analyze and extend previously-suggested evolutionary multi-objective optimization algorithms for their suitability to solving many-objective problems.In most cases,
the results are promising and the suggested algorithms must be tested on other more challenging problems than the usual normalized test problems such as DTLZ problems.They must also be tried on real-world problems.In the following paragraphs,we describe a recently proposed algorithm which ?ts well with our description of a many-objective optimization algorithm given in Section II-C and closely matches with our proposed algorithm.
MOEA/D[10]uses a prede?ned set of weight vectors to maintain a diverse set of trade-off solutions.For each weight vector,the resulting problem is called a sub-problem.To start with,every population member(with size same as the number of weight vectors)is associated with a weight vector randomly. Thereafter,two solutions from neighboring weight vectors (de?ned through a niching parameter(T))are mated and an offspring solution is created.The offspring is then associated with one or more weight vectors based on a performance metric.Two metrics are suggested in the study.A penalized distance measure of a point from the ideal point is formed by weighted sum(weightθis another algorithmic parameter)of perpendicular distance(d2)from the reference direction and distance(d1)along the reference direction:
PBI(x,w)=d1+θd2.(1) We call this procedure here as MOEA/D-PBI.The second approach suggested is the use of Tchebycheff metric using a utopian point z?and the weight vector w:
TCH(x,w,z?)=M
max
i=1
w i|f i(x)?z?i|.(2)
In reported simulations[10],the ideal point was used as z?and zero-weight scenario is handled by using a small number. We call this procedure as MOEA/D-TCH here.An external population maintains the non-dominated solutions.The?rst two dif?culties mentioned earlier are negotiated by using an explicit set of weight vectors to?nd points and the third dif?culty is alleviated by using a mating restriction scheme. Simulation results were shown for two and three-objective test problems only and it was concluded that MOEA/D-PBI is better for three-objective problems than MOEA/D-TCH and the performance of MOEA/D-TCH improved with an objective normalization process using population minimum and maxi-mum objective values.Both versions of MOEA/D require to set a niching parameter(T).Based on some simulation results on two and three-objective problems,authors suggested the use of a large fraction of population size as T.Additionally, MOEA/D-PBI requires an appropriate setting of an additional parameter–penalty parameterθ,for which authors have suggested a value of5.
A later study by the developers of MOEA/D suggested the use of differential evolution(DE)to replace genetic recombination and mutation operators.Also,further modi?-cations were done in de?ning neighborhood of a particular solution and in replacing parents in a given neighborhood by the corresponding offspring solutions[46].We call this method as MOEA/D-DE here.Results on a set of mostly two and a three-objective linked problems[47]showed better performance with MOEA/D-DE compared to other algorithms.As mentioned,MOEA/D is a promising approach for many-objective optimization as it addresses some of the dif?culties mentioned above well,but the above-mentioned MOEA/D studies did not quite explore their suitability to a large number of objectives.In this paper,we apply them to problems having up to15objectives and evaluate their applicability to truly many-objective optimization problems and reveal interesting properties of these algorithms.
Another recent study[14]follows our description of a many-objective optimization procedure.The study extends the NSGA-II procedure to suggest a hybrid NSGA-II(HN algorithm)for handling three and four-objective problems. Combined population members are projected on a hyper-plane and a clustering operation is performed on the hyper-plane to select a desired number of clusters which is user-de?ned.Thereafter,based on the diversity of the population, either a local search operation on a random cluster member is used to move the solution closer to the Pareto-optimal front or a diversity enhancement operator is used to choose population members from all clusters.Since no targeted and distributed search is used,the approach is more generic than MOEA/D or the procedure suggested in this paper.However, the ef?ciency of HN algorithm for problems having more than four objectives is yet to be investigated to suggest its use for many-objective problems,in general.We now describe our proposed algorithm.
IV.P ROPOSED A LGORITHM:NSGA-III
The basic framework of the proposed many-objective NSGA-II(or NSGA-III)remains similar to the original NSGA-II algorithm[5]with signi?cant changes in its selec-tion mechanism.But unlike in NSGA-II,the maintenance of diversity among population members in NSGA-III is aided by supplying and adaptively updating a number of well-spread reference points.For completeness,we?rst present a brief description of the original NSGA-II algorithm.
Let us consider t-th generation of NSGA-II algorithm. Suppose the parent population at this generation is P t and its size is N,while the offspring population created from P t is Q t having N members.The?rst step is to choose the best N members from the combined parent and offspring population R t=P t∪Q t(of size2N),thus allowing to preserve elite members of the parent population.To achieve this,?rst,the combined population R t is sorted according to different non-domination levels(F1,F2and so on).Then,each non-domination level is selected one at a time to construct a new population S t,starting from F1,until the size of S t is equal to N or for the?rst time exceeds N.Let us say the last level included is the l-th level.Thus,all solutions from level (l+1)onwards are rejected from the combined population R t.In most situations,the last accepted level(l-th level)is only accepted partially.In such a case,only those solutions that will maximize the diversity of the l-th front are chosen.In NSGA-II,this is achieved through a computationally ef?cient yet approximate niche-preservation operator which computes the crowding distance for every last level member as the summation of objective-wise normalized distance between two
neighboring solutions.Thereafter,the solutions having larger crowding distance values are chosen.Here,we replace the crowding distance operator with the following approaches (subsections IV-A to IV-E).
A.Classi?cation of Population into Non-dominated Levels The above procedure of identifying non-dominated fronts using the usual domination principle[17]is also used in NSGA-III.All population members from non-dominated front level1to level l are?rst included in S t.If|S t|=N,no further operations are needed and the next generation is started with P t+1=S t.For|S t|>N,members from one to(l?1)
fronts are already selected,that is,P t+1=∪l?1
i=1F i,and the
remaining(K=N?|P t+1|)population members are chosen from the last front F l.We describe the remaining selection process in the following subsections.
B.Determination of Reference Points on a Hyper-Plane
As indicated before,NSGA-III uses a prede?ned set of reference points to ensure diversity in obtained solutions. The chosen reference points can either be prede?ned in a structured manner or supplied preferentially by the user.We shall present results of both methods in the results section later. In the absence of any preference information,any prede?ned structured placement of reference points can be adopted,but in this paper we use Das and Dennis’s[48]systematic approach1 that places points on a normalized hyper-plane–a(M?1)-dimensional unit simplex–which is equally inclined to all objective axes and has an intercept of one on each axis.If p divisions are considered along each objective,the total number of reference points(H)in an M-objective problem is given by:
H= M+p?1p .(3) For example,in a three-objective problem(M=3),the reference points are created on a triangle with apex at(1,0,0), (0,1,0)and(0,0,1).If four divisions(p=4)are chosen for each objective axis,H= 3+4?14 or15reference points will be created.For clarity,these reference points are shown in Figure1.In the proposed NSGA-III,in addition to emphasiz-ing non-dominated solutions,we also emphasize population members which are in some sense associated with each of these reference points.Since the above-created reference points are widely distributed on the entire normalized hyper-plane,the obtained solutions are also likely to be widely distributed on or near the Pareto-optimal front.In the case of a user-supplied set of preferred reference points,ideally the user can mark H points on the normalized hyper-plane or indicate any H,M-dimensional vectors for the purpose.The proposed algorithm is likely to?nd near Pareto-optimal solutions cor-responding to the supplied reference points,thereby allowing this method to be used more from the point of view of a combined application of decision-making and many-objective optimization.The procedure is presented in Algorithm1.
1Any other structured distribution with or without a biasing on some part of the Pareto-optimal front can be used as well.
Fig.1.15reference points are shown on a normalized reference plane for a three-objective problem with p=4.
Input:H structured reference points Z s or supplied aspira-tion points Z a,parent population P t
Output:P t+1
1:S t=?,i=1
2:Q t=Recombination+Mutation(P t)
3:R t=P t∪Q t
4:(F1,F2,...)=Non-dominated-sort(R t)
5:repeat
6:S t=S t∪F i and i=i+1
7:until|S t|≥N
8:Last front to be included:F l=F i
9:if|S t|=N then
10:P t+1=S t,break
11:else
12:P t+1=∪l?1
j=1
F j
13:Points to be chosen from F l:K=N?|P t+1|
14:Normalize objectives and create reference set Z r: Normalize(f n,S t,Z r,Z s,Z a)
15:Associate each member s of S t with a reference point: [π(s),d(s)]=Associate(S t,Z r)%π(s):closest
reference point,d:distance between s andπ(s)
16:Compute niche count of reference point j∈Z r:ρj= s∈S t/F l((π(s)=j)?1:0)
17:Choose K members one at a time from F l to construct P t+1:Niching(K,ρj,π,d,Z r,F l,P t+1)
18:end if
w being the axis direction:
ASF(x,w)=M
max
i=1
f′i(x)/w i,for x∈S t.(4)
For w i=0,we replace it with a small number10?6.For i-th translated objective direction f′i,this will result in an extreme objective vector,z i,max.These M extreme vectors are then used to constitute a M-dimensional linear hyper-plane.The intercept a i of the i-th objective axis and the linear hyper-plane can then be computed(see Figure2)and the objective functions can be normalized as follows:
f n i(x)=f′i(x)
a i?z min
i
,for i=1,2,...,M.
(5)
Note that the intercept on each normalized objective axis is now at f n i=1and a hyper-plane constructed with these intercept points will make M i=1f n i=1.
2
f’
Fig.2.Procedure of computing intercepts and then forming the hyper-plane from extreme points are shown for a three-objective problem.
In the case of structured reference points(H of them),the original reference points calculated using Das and Dennis’s [48]approach already lie on this normalized hyper-plane.In the case of preferred reference points by the user,the reference points are simply mapped on to the above-constructed normal-ized hyper-plane using equation5.Since the normalization procedure and the creation of the hyper-plane is done at each generation using extreme points ever found from the start of the simulation,the proposed NSGA-III procedure adaptively maintains a diversity in the space spanned by the members of S t at every generation.This enables NSGA-III to solve problems having a Pareto-optimal front whose objective values may be differently scaled.The procedure is also described in Algorithm2.Input:S t,Z s(structured points)or Z a(supplied points) Output:f n,Z r(reference points on normalized hyper-plane) 1:for j=1to M do
2:Compute ideal point:z min
j
=min s∈S
t
f j(s)
3:Translate objectives:f′j(s)=f j(s)?z min
j
?s∈S t 4:Compute extreme points:z j,max=s: argmin s∈S
t
ASF(s,w j),where w j=(?,...,?)T ?=10?6,and w j j=1
5:end for
6:Compute intercepts a j for j=1,...,M
7:Normalize objectives(f n)using Equation5
8:if Z a is given then
9:Map each(aspiration)point on normalized hyper-plane using Equation5and save the points in the set Z r 10:else
11:Z r=Z s
12:end if
Algorithm4Niching(K,ρj,π,d,Z r,F l,P t+1)procedure Input:Z r,S t
Output:π(s∈S t),d(s∈S t)
1:for each reference point z∈Z r do
2:Compute reference line w=z
3:end for
4:for each s∈S t do
5:for each w∈Z r do
6:Compute d⊥(s,w)=s?w T s/ w
7:end for
8:Assignπ(s)=w:argmin w∈Z r d⊥(s,w)
9:Assign d(s)=d⊥(s,π(s))
10:end for
parent solutions(to take care of third dif?culty mentioned in
Section II-A),we suggest using a relatively larger value of
distribution index in the SBX operator.
https://www.wendangku.net/doc/2f10679090.html,putational Complexity of One Generation of NSGA-III
The non-dominated sorting(line4in Algorithm1)of a
population of size2N having M-dimensional objective vec-
tors require O(N log M?2N)computations[49].Identi?cation
of ideal point in line2of Algorithm2requires a total
of O(MN)computations.Translation of objectives(line3)
requires O(MN)computations.However,identi?cation of
extreme points(line4)require O(M2N)computations.De-
termination of intercepts(line6)requires one matrix inversion
of size M×M,requiring O(M3)operations.Thereafter,
normalization of a maximum of2N population members
(line7)require O(N)computations.Line8of Algorithm2
requires O(MH)computations.All operations in Algorithm3
in associating a maximum of2N population members to
H reference points would require O(MNH)computations.
Thereafter,in the niching procedure in Algorithm4,line3will
require O(H)comparisons.Assuming that L=|F l|,line5
requires O(L)checks.Line8in the worst case requires O(L)
computations.Other operations have smaller complexity.How-
ever,the above computations in the niching algorithm need to
be performed a maximum of L times,thereby requiring larger
of O(L2)or O(LH)computations.In the worst case scenario
(S t=F1,that is,the?rst non-dominated front exceeds the
population size),L≤2N.In all our simulations,we have used
N≈H and N>M.Considering all the above considerations
and computations,the overall worst-case complexity of one
generation of NSGA-III is O(N2log M?2N)or O(N2M),
whichever is larger.
H.Parameter-Less Property of NSGA-III
Like in NSGA-II,NSGA-III algorithm does not require to set any new parameter other than the usual genetic parameters such as the population size,termination parameter,crossover and mutation probabilities and their associated parameters. The number of reference points H is not an algorithmic parameter,as this is entirely at the disposal of the user.The population size N is dependent on H,as N≈H.The location of the reference points is similarly dependent on the preference information that the user is interested to achieve in the obtained solutions.
We shall now present simulation results of NSGA-III for various many-objective scenarios and compare its performance with MOEA/D and classical methods.
V.R ESULTS
In this section,we provide the simulation results of NSGA-III on three to15-objective optimization problems.Since our method has a framework similar to MOEA/D in that both types of algorithms require a set of user-supplied reference points or weight vectors,we compare our proposed method with different versions of MOEA/D(codes from MOEA/D web-site[50]are used).The original MOEA/D study proposed two procedures(MOEA/D-PBI and MOEA/D-TCH),but did not solve four or more objective problems.Here,along with our algorithm,we investigate the performance of these MOEA/D algorithms on three to15-objective problems.
As a performance metric,we have chosen the inverse generational distance(IGD)metric[51],[47]which as a single metric which can provide a combined information about the convergence and diversity of the obtained solutions. Since reference points or reference directions are supplied in NSGA-III and MOEA/D algorithms,respectively,and since in this section we show the working of these methods on test problems for which the exact Pareto-optimal surface is known, we can exactly locate the targeted Pareto-optimal points in the normalized objective space.We compute these targeted points and call them a set Z.For any algorithm,we obtain the?nal non-dominated points in the objective space and call them the set A.Now,we compute the IGD metric as the average Euclidean distance of points in set Z with their nearest members of all points in set A:
IGD(A,Z)=1
No.of NSGA-III
Ref.dirn.popsize
(M)(N)
392
210210
8156
275275
15136
we have used p=12in order to obtain H= 3?1+1212 or
91reference points(refer to equation3).For?ve-objective
problems,we have used p=6,so that H=210reference
points are obtained.Note that as long as p≥M is not chosen,
no intermediate point will be created by Das and Dennis’s
systematic approach.For eight-objective problems,even if we
use p=8(to have at least one intermediate reference point),
it requires5,040reference points.To avoid such a situation,
we use two layers of reference points with small values of p.
On the boundary layer,we use p=3,so that120points are
created.On the inside layer,we use p=2,so that36points
are created.All H=156points are then used as reference
points for eight-objective problems.We illustrate this scenario
in Figure4for a three-objective problem using p=2for
boundary layer and p=1for the inside layer.For
10-objective
Fig.4.The concept for two-layered reference points(with six points on
the boundary layer(p=2)and three points on the inside layer(p=1))is
shown for a three-objective problem,but are implemented for eight or more
objectives in the simulations here.
problems as well,we use p=3and p=2for boundary and
inside layers,respectively,thereby requiring a total of H=
220+55or275reference points.Similarly,for15-objective
problems,we use p=2and p=1for boundary and inside
layers,respectively,thereby requiring H=120+15or135
reference points.
3Since no tournament selection is used in NSGA-III,a factor of two would
be adequate as well,but as we re-introduce tournament selection in the
constrained NSGA-III in the sequel paper[52],we keep population size as a
multiple of four here as well to have a uni?ed algorithm.
Table II presents other NSGA-III and MOEA/D parameters used in this study.MOEA/D requires additional parameters
TABLE II
P ARAMETER VALUES USED IN NSGA-III AND TWO VERSIONS OF
MOEA/D.n IS THE NUMBER OF VARIABLES.
NSGA-III
SBX probability[28],p c1
Polynomial mutation prob.[3],p m1/n
ηc[28]20
ηm[28]20
TABLE III
B EST,MEDIAN AND WORST IGD V ALUES OBTAINED FOR NSGA-III AND TWO VERSIONS OF MOEA/D ON M-OBJECTIVE DTLZ1,DTLZ2,DTLZ3
AND DTLZ4PROBLEMS.B EST PERFORMANCE IS SHOWN IN BOLD.
M NSGA-III MOEA/D-TCH
DTLZ14.095×10?45.470×10?3
4001.495×10?31.778×10?2
4.743×10?33.394×10?1
5.116×10?41.124×10?1
59.799×10?41.129×10?1
1.979×10?31.137×10?1
3.914×10?33.849×10?2
7506.106×10?34.145×10?2
8.537×10?34.815×10?2
2.215×10?32.072×10?1
103.462×10?32.147×10?1
6.869×10?32.400×10?1
1.236×10?28.048×10?2
15001.431×10?28.745×10?2
1.692×10?21.008×10?1
1.262×10?37.499×10?2
31.357×10?37.574×10?2
2.114×10?37.657×10?2
1.219×10?31.595×10?1
3501.437×10?31.820×10?1
1.727×10?31.935×10?1
1.371×10?25.989×10?1
81.571×10?26.301×10?1
1.811×10?26.606×10?1
2.474×10?32.629×10?1
7502.778×10?32.873×10?1
3.235×10?33.337×10?1
1.360×10?21.000
151.726×10?21.084
2.114×10?21.120
DTLZ39.773×10?45.610×10?2
10003.426×10?31.439×10?1
9.113×10?38.887×101
3.086×10?32.938×10?1
55.960×10?32.948×10?1
1.196×10?2
2.956×10?1
6.459×10?32.607×10?1
10001.948×10?23.321×10?1
1.1233.923
8.849×10?37.174×10?1
101.188×10?27.398×10?1
2.083×10?28.047×10?1
4.360×10?32.202×10?1
20001.664×10?23.219×10?1
1.2604.681×10?1
2.915×10?42.168×10?1
35.970×10?43.724×10?1
4.286×10?14.421×10?1
1.080×10?11.090×10?1
10005.787×10?11.479×10?1
7.348×10?14.116×10?1
5.079×10?3
6.676×10?1
87.054×10?39.036×10?1
6.051×10?11.035
3.966×10?12.102×10?1
20009.203×10?12.885×10?1
1.0776.422×10?1
7.110×10?31.056
153.431×10?11.162
1.0731.220
Fig. 5.Obtained solutions by NSGA-III for
DTLZ1.
Fig.6.Obtained solutions by MOEA/D-PBI for DTLZ1.Fig.7.Obtained solutions by MOEA/D-TCH for DTLZ1.
Fig.8.Obtained solutions by NSGA-III for
DTLZ2.
Fig.9.Obtained solutions by MOEA/D-PBI for DTLZ2.
Fig.10.Obtained solutions by MOEA/D-TCH for DTLZ2.
Fig.11.Variation of IGD metric value with NSGA-III and MOEA/D-PBI for DTLZ2.Fig.12.Variation of IGD metric value with NSGA-III and MOEA/D-PBI for DTLZ3.
Table II)mainly because this value was chosen in the original MOEA/D study [10].Next,we investigate MOEA/D-PBI’s performance with ηc =30(which was used with NSGA-III).Table IV shows that the performance of MOEA/D does not change much with the above change in ηc value.
Next,we apply NSGA-III and MOEA/D-PBI approaches to two WFG test problems.The parameter settings are the same as before.Figures 18and 19show the obtained points on WFG6problem.The convergence is slightly better with NSGA-III approach.Similarly,Figures 20and 21show a similar performance comparison of the above two approaches for WFG7problem.Table V shows the performances of
the two approaches up to 15-objective WFG6and WFG7problems.
Based on the results on three to 15-objective normalized DTLZ and WFG test problems,it can be concluded that (i)MOEA/D-PBI performs consistently better than MOEA/D-TCH approach,(ii)MOEA/D-PBI performs best in some problems,whereas the proposed NSGA-III approach performs best in some other problems,and (iii)in a non-uniformly distributed Pareto-optimal front (like in the DTLZ4problem),both MOEA/D approaches fail to maintain a good distribution of points,while NSGA-III performs well.
Fig.13.
Obtained solutions by NSGA-III for
DTLZ4.
Fig.14.Obtained solutions by MOEA/D-PBI for DTLZ4.
Fig.15.Obtained solutions by MOEA/D-TCH for DTLZ4.
Fig.16.NSGA-III Solutions are shown using 10-objective value path format for DTLZ4.Fig.17.MOEA/D-PBI Solutions are shown using 10-objective value path format for
DTLZ4.
Fig.18.NSGA-III solutions are shown on three-objective WFG6prob-
lem.Fig.19.MOEA/D-PBI solutions are shown on three-objective WFG6
problem.Fig.20.NSGA-III solutions are shown on three-objective WFG7prob-
lem.
Fig.21.
MOEA/D-PBI solutions are shown on three-objective WFG7
problem.
TABLE IV
IGD VALUES OF MOEA/D-PBI APPROACH WITHηc=30.
M NSGA-III
DTLZ14.047×10?4
4001.797×10?3
5.699×10?3
5.116×10?4
59.799×10?4
1.979×10?3
4.053×10?3
7506.839×10?3
1.127×10?2
2.215×10?3
103.462×10?3
6.869×10?3
1.301×10?2
15001.653×10?2
2.695×10?2
1.262×10?3
31.357×10?3
2.114×10?3
1.096×10?3
3501.208×10?3
1.370×10?3
1.371×10?2
81.571×10?2
1.811×10?2
2.286×10?3
7502.433×10?3
2.910×10?3
1.360×10?2
151.726×10?2
2.114×10?2
DTLZ31.001×10?3
10005.080×10?3
1.154×10?2
3.086×10?3
55.960×10?3
1.196×10?2
6.285×10?3
10002.032×10?2
1.133
8.849×10?3
101.188×10?2
2.083×10?2
4.647×10?3
20001.110×10?2
1.271
2.915×10?4
35.970×10?4
4.286×10?1
2.342×10?1
10004.384×10?1
7.347×10?1
5.079×10?3
87.054×10?3
6.051×10?1
5.083×10?1
20008.321×10?1
1.024
7.110×10?3
153.431×10?1
1.073
TABLE V
IGD V ALUES FOR NSGA-III AND MOEA/D-PBI APPROACHES ON THREE
TO15-OBJECTIVE WFG PROBLEMS.
M NSGA-III
WFG61.015×10?2
4003.522×10?2
1.066×10?1
5.065×10?3
51.965×10?2
4.474×10?2
1.757×10?2
15005.551×10?2
1.156×10?1
1.060×10?2
102.491×10?2
6.129×10?2
1.513×10?2
30006.782×10?2
1.637×10?1
WFG71.033×10?2
4001.358×10?2
1.926×10?2
8.249×10?3
59.111×10?3
1.050×10?2
1.355×10?2
15001.573×10?2
2.626×10?2
3.228×10?2
104.292×10?2
9.071×10?2
7.552×10?3
30001.063×10?2
2.065×10?2
P
r
o
b
.
NSGA-III
IGD IGD
D
T
L
Z
14.880×10?46.400×10?2
6.526×10?41.808×101
4.880×10?31.083×10?1
2
2
,
7
5
01.264×10?39.678×10?5
1.357×10?36.597×10?3
1.274×10?31.082×10?4
B.Classical Generative Method
For solving many-objective optimization problems,we re-quire a set of reference points–either supplied by the user or systematically constructed as discussed earlier.One may then ponder how the proposed NSGA-III method will compare with a classical generative method in which multiple scalarized single-objective optimization problems can be formulated for each of the preferred or structured reference points and solved independently.For this purpose,we minimize the PBI-metric for each case.Along the reference direction obtained by joining the ideal point(z?)to the supplied reference point(ˉz) dictated by a w-vector(a unit vector w=(ˉz?z?)/|ˉz?z?|), the distance(d1)along the w-direction and the distance(d2) perpendicular to the w-direction are computed for any point x.A weighted-sum of these two directions is then minimized, as follows:
Minimize x d1+θd2=w T f(x)+θ f(x)?w T f(x)w .(7) The parameterθis set to5for all reference points[10].In other words,the above minimization process is likely to?nd the intersection point between the reference direction w and the Pareto-optimal surface,if there exists an intersection.Since the ideal point(z?)is required to be known for this method, we assume origin to be the ideal vector for this problem.
To make a fair comparison,for H reference points,we allo-cate a maximum of T=FE NSGA-III/H(where FE NSGA-III is the total number of solution evaluations needed by NSGA-III)function evaluations to each optimization process.For three-objective DTLZ1and DTLZ2problems,FE NSGA-III= 92×400or36,800was required to?nd91solutions.Therefore, we allocate36,800/91or405function evaluations to each optimization run by fmincon routine of Matlab.A random solution is used for initialization.Figures22and23show the ?nal solutions obtained by this generative method.
The DTLZ1problem has multiple local fronts and Matlab’s fmincon routine could not?nd a Pareto-optimal solution every time with the allotted number of function evaluations. Table VI shows the IGD and GD metric(average distance of obtained points from the closest reference points,a metric opposite in sense to IGD metric)values.For three-objective DTLZ2problem,the generative method is able to?nd a well-distributed set of points,as shown in the?gure.However,the table indicates that the distribution of points is not as good as that obtained by NSGA-III with the number of function evaluations restricted in this study.The inherent parallel search of NSGA-III constitutes a more ef?cient optimization.
C.Scaled Test Problems
To investigate the algorithm’s performance on problems having differently scaled objective values,we consider DTLZ1 and DTLZ2problems again,but now we modify them as follows.Objective f i is multiplied by a factor10i.To illustrate, objectives f1,f2and f3for the three-objective scaled DTLZ1 problem are multiplied by100,101and102,respectively. To handle different scaling of objectives and make the distances(d1and d2)along and perpendicular to reference directions in MOEA/D-PBI approach,we normalize the objec-tive values using the procedure suggested for MOEA/D-TCH approach in the original MOEA/D study[10].We also use the code from MOEA/D web-site[50]to obtain the points.Fig-ures24,25,and26show the obtained distribution of points us-ing NSGA-III,MOEA/D-PBI and MOEA/D-TCH approaches, respectively.It is clear that both MOEA/D approaches with objective normalization are not able to handle the scaling involved in the objectives adequately,whereas NSGA-III’s operators,normalization of objectives,and adaptive hyper-plane construction process are able to negotiate the scaling of the objectives quite well.In the scaled problems,IGD metric is computed by?rst normalizing the objective values using the ideal and nadir points of the exact Pareto-optimal front and then computing the IGD value using the reference points as before.Resulting IGD values are shown in Table VII.Similar
TABLE VII
B EST,MEDIAN AND WORST IGD VALUES FOR THREE-OBJECTIVE SCALED
DTLZ1AND DTLZ2PROBLEMS USING NSGA-III AND MOEA/D ALGORITHMS.A SCALING FACTOR OF10i,i=1,2,...,M,IS USED.
M
a
x
G
e
n
MOEA/D
-PBI
D
T
L
Z
13.853×10?48.047×10?2
1.214×10?3
2.051×10?1
1.103×10?2
2.704×10?1
D
T
L
Z
21.347×10?32.350×10?1
2.069×10?35.308×10?1
5.284×10?35.321×10?1
performance is also observed for the scaled DTLZ2problem, as shown in Figures27,28,and29and results are tabulated in Table VII.
It is interesting to note that the MOEA/D-PBI algorithm that worked so well in the normalized test problems in the previous subsection did not perform well for the scaled version of the same problems.Practical problems are far from being normalized and the objectives are usually scaled differently. An ef?cient optimization algorithm must handle different scaling of objectives as effectively as shown by NSGA-III. Next,Table VIII shows the IGD values of the obtained solutions for5,8,10,and15-objective scaled DTLZ1and DTLZ2problems.Although dif?cult to visualize,a small IGD value in each case refers to a well-distributed set of points. Due to the poor performance of MOEA/D algorithms in scaled problems,we did not apply them further to the above higher-dimensional scaled problems.
D.Convex DTLZ2Problem
DTLZ1problem has a linear Pareto-optimal front and DTLZ2to DTLZ4problems have concave Pareto-optimal fronts.To investigate the performance of NSGA-III and both versions of MOEA/D on scalable problems having a con-vex Pareto-optimal front,we suggest a new problem based on DTLZ2problem.After the objective values(f i,i= 1,2,...,M)are computed using the original DTLZ2problem
Fig.22.Solutions obtained by classical generative method for DTLZ1. Only the points obtained close to the true Pareto-optimal front are shown.
Fig.23.Solutions obtained by classical generative method for DTLZ2.
Fig.24.Obtained solutions by NSGA-III for
scaled DTLZ1.Fig.25.Obtained solutions by MOEA/D-PBI for
scaled DTLZ1.
Fig.26.Obtained solutions by MOEA/D-TCH for
scaled DTLZ1.
Fig.27.Obtained solutions by NSGA-III for
scaled DTLZ2.Fig.28.Obtained solutions by MOEA/D-PBI for
scaled
DTLZ2.
Fig.29.Obtained solutions by MOEA/D-TCH for
scaled DTLZ2.
description,we map them as follows:
f i←f4i,i=1,2,...,M?1,
f M←f2M.
Thus,the Pareto-optimal surface is given as
f M+
M?1
i=1
Fig.30.Obtained solutions by NSGA-III for the convex Pareto-optimal front problem.
Fig.31.Obtained solutions by MOEA/D-PBI for
the convex Pareto-optimal front problem.
Fig.32.Obtained solutions by MOEA/D-TCH for
the convex Pareto-optimal front problem.
TABLE VIII
B EST,MEDIAN AND WORST IGD V ALUES FOR SCALED M-OBJECTIVE
DTLZ1AND DTLZ2PROBLEMS.
M MaxGen
DTLZ13.853×10?4
10i1.214×10?3
1.103×10?2
5600
4.659×10?3
3i1.051×10?2
1.167×10?1 101000
3.450×10?3
1.2i6.183×10?3
1.367×10?2 3250
1.005×10?2
10i2.564×10?2
8.430×10?2 8500
2.113×10?2
3i3.334×10?2
2.095×10?1 151000M NSGA-III MOEA/D-TCH
3.050×10?2
2503.274×10?2
3.477×10?2
7.950×10?31.211×10?1 51.341×10?21.223×10?1
1.917×10?21.235×10?1
2.079×10?1
20002.086×10?1
2.094×10?1
7.389×10?22.373×10?1 109.126×10?22.472×10?1
1.051×10?1
2.514×10?1
3.681×10?1
45003.682×10?1
3.683×10?1
Fig.33.NSGA-III Solutions are shown using15-objective value path format for the convex
problem.Fig.34.MOEA/D-PBI Solutions are shown using10-objective value path format for the convex problem.
extreme solution,thereby wasting in computational ef-forts.
2)Interestingly,depending on the parameterθ,MOEA/D-
PBI is potentially capable of generating dominated solu-tions.This certainly results in a waste of computational effort.
Although special care can be taken to reduce the chance of above,they are important for one to be aware while working with MOEA/D-PBI or MOEA/D-TCH approaches.
VI.F URTHER I NVESTIGATIONS OF NSGA-III Having performed well on all test problems in above sec-tions,we now investigate NSGA-III’s performance in certain special types of many-objective problem solving tasks.
A.Finding a Preferred Part of Pareto-front
In many-objective optimization problems,the user may not always be interested in?nding the entire Pareto-optimal front.Practically speaking,an user is often interested in a preferred part of the Pareto-optimal front.In such a scenario, the user may represent his/her preferred region using a few representative reference
points(or aspiration points).The aim in such a many-objective optimization task is
to?nd the Pareto-optimal points that are in some sense closest to the supplied reference points.
Recall from Section IV-B that the proposed NSGA-III algorithm can also be applied with a set of H user-supplied reference points,instead of Das and Dennis’s structured refer-ence points used so far.Here,we demonstrate the working of NSGA-III for scaled DTLZ1and DTLZ2problems for a few user-supplied preference information.In such a case,in order to determine the right normalized hyper-plane,by default,we supply M additional reference points,one at each objective axis at an intercept of unity.The presence of these extreme points will attempt to keep extreme Pareto-optimal points, thereby forming a proper normalized hyper-plane needed to have appropriate scaling of the objectives.
For both scaled DTLZ1and DTLZ2problems,we supply 10reference points in the middle of the normalized hyper-plane(scenario1,as shown in Figure35).As mentioned,three additional reference points(1,0,0)T,(0,1,0)T and(0,0,1)T are also included for the execution of the algorithm,thereby making a total of13supplied reference points.Figure37Fig.35.Reference points used
for Scenario1on normalized hyper-
plane.
Fig.36.Reference points used
for Scenario2on normalized hyper-
plane.
shows the points obtained by NSGA-III on the scaled Pareto-optimal front of DTLZ1problem.Figure38shows10obtained points for the scaled DTLZ2problem for scenario1.Next,we supply a set of10reference points on a different part of the Pareto-optimal,as shown as scenario2in Figure36.Figure38 shows the obtained points on the scaled DTLZ2problem.In both cases,a set of10near-Pareto-optimal points are obtained close to where the reference points were supplied.
Best,median and worst IGD values for the obtained points for three and10-objective scaled DTLZ1and DTLZ2problems are shown in Table X.The IGD values are computed by normalizing the obtained objective values by theoretical ideal and nadir points and by projecting10supplied reference points on the normalized Pareto-optimal front.A small IGD value in each case ensures the convergence and diversity of the obtained solutions.The success of NSGA-III in?nding just10Pareto-optimal points on10-objective scaled problems indicates its potential use in?nding a handful of preferred solutions in a many-objective practical optimization problem.
B.Randomly generated preferred reference points
The supplied preferred reference points considered in the previous subsection are structured.In fact,they were created using Das and Dennis’s[48]structured reference point creation procedure.Here,we investigate NSGA-III’s ability to deal with a set of randomly created reference points.The procedure used here is the same as in previous subsection–M additional axis points are included for NSGA-III to adaptively create its hyper-plane.
Fig.37.Preferred solutions(scenario1)obtained by NSGA-III for three-objective DTLZ1.
Fig.38.Preferred solutions(scenario1)obtained by NSGA-III for three-objective DTLZ2.
Fig.39.Preferred solutions(scenario2)obtained
by NSGA-III for three-objective DTLZ2.
Fig.40.Preferred solutions obtained by NSGA-III for three-objective
DTLZ1.
Fig.41.Preferred solutions obtained by NSGA-III for three-objective
DTLZ2.
For decision-making purposes,only a few trade-off points
can be analyzed,even for a many-objective problem.Here,
we investigate if the proposed NSGA-III is able to?nd only
?ve Pareto-optimal points in a preferred region for three
and10-objective scaled DTLZ1and DTLZ2problems.Five
random points are supplied in the intermediate region of the
normalized hyper-plane(within z i∈[0.4,0.6]for all i).
Figures40and41show the obtained points on scaled three-
objective DTLZ1and DTLZ2problems,respectively.Table XI
shows the IGD values for three and10-objective problems.
In each case,a small IGD value indicates that NSGA-III
is adequate to successfully?nd the desired solutions.This
application shows promise in applying NSGA-III to many-
objective problems(10-objective or like)with a handful(?ve
or like)of preferred reference points–a matter which is of
great importance to practitioners.
C.Small population size
Previous subsections have shown that NSGA-III can work
with a small number of reference points in order to?nd a
few Pareto-optimal points in a preferred region.In previous
sections,we have used a population size that is almost equal to
the number of reference points.A natural question then arises:
‘Can NSGA-III work well with a small population size?’.We
investigate this aspect here.
Table XII tabulates the number of reference points(H)
and corresponding layer-wise p and the maximum number of
generations considered for different many-objective DTLZ2
problems.We perform this study for three,?ve,and10-
objective scaled DTLZ2problems.Identical scaling factors as
those shown in Table VIII are used here.In each case,the pop-
ulation size(N)is always kept as the smallest number multiple
of four and greater than the number of reference points(H).
A larger number of generations is kept for higher objective
problems.The chosen maximum number of generations are
also tabulated in the table.
For the three-objective DTLZ2problem,when we are
interested in?nding10well-distributed Pareto-optimal points,
we?nd that a population of size12is adequate to?nd all
10Pareto-optimal points after250generations(Figure42).
For the10-objective problem,if we desire65reference points
(with p=2),we?nd that a population of size68is adequate to
?nd all65solutions after1,000generations.The best,median
and worst IGD values are shown in the table for three,?ve
and10-objective DTLZ2problems.These results show that
NSGA-III can work with a small population size due to its
focus and balanced emphasis for?nding near Pareto-optimal
points corresponding to a supplied set of reference points.
TABLE X
B EST,MEDIAN AND WORST IGD V ALUES FOR SCALED DTLZ1AND
DTLZ2PROBLEMS WITH10REFERENCE POINTS.
M MaxGen
DTLZ14.945×10?4
284.076×10?3
1.898×10?2
102000
DTLZ12.742×10?4
282.875×10?3
1.741×10?2
102000
3250
2.840×10?3
(Scenario1)1004.907×10?3
(Figure35)1.074×10?2
3250
1.576×10?2
(Scenario2)1002.548×10?2
(Figure36)5.893×10?2
TABLE XI
B EST,MEDIAN AND WORST IGD V ALUES FOR SCALED DTLZ1AND
DTLZ2PROBLEMS WITH RANDOMLY SUPPLIED REFERENCE POINTS.
M MaxGen
DTLZ11.621×10?3
289.870×10?3
3.186×10?1
102000
3250
1.317×10?2
1002.463×10?2
6.439×10?2
D.Nadir Point Estimation
In multi-objective optimization problems,the nadir point is important to be found for various reasons.A nadir point is constructed from the worst objective values for the entire Pareto-optimal set.Thus,along with the ideal point,nadir point can be used to normalize the objective functions for a systematic and reliable execution of many classical and non-classical optimization methods.In another study,a nadir point estimation strategy was proposed based on a bilevel evolutionary approach[54].In that study,three to20-objective DTLZ1and DTLZ2problems were considered for estimating the nadir point.Since studies in the previous two subsections have shown amply that NSGA-III can be used to?nd a few Pareto-optimal solutions even in10-objective problems,here we apply NSGA-III to?nd only the extreme Pareto-optimal points so that the nadir point can be estimated accurately. For this purpose,we suggest using M reference points,one on each objective axis,located at unity.We apply NSGA-III to
TABLE XII
M INIMUM POPULATION SIZE AND BEST,MEDIAN AND WORST IGD
VALUES OF THE OBTAINED SOLUTIONS FOR THE SCALED DTLZ2
PROBLEM.
(p B,p I)MaxGen NSGA-III
1.464×10?3
31012
1.524×10?1
4.952×10?3
52020
1.195×10?1
8.641×10?3
106568
1.842×10?2
Fig.42.Obtained points using NSGA-III for the scaled DTLZ2with a small population size of12.
three to20-objective DTLZ1and DTLZ2problems and record the overall function evaluations needed to?nd the true nadir point with the following termination condition.When the error value(E)computed as below
E=
z nad i?z?i 2,(9)
is less than a threshold(0.01,used here),the run is terminated. Here,z?,z nad and z est are the ideal point,the true nadir point,and the estimated nadir point by NSGA-III,respectively. Table XIII presents the results and compares them with the evaluations needed to?nd the nadir point with an identical termination condition in the previous study[54].In most cases, NSGA-III requires smaller number of function evaluations than the previous procedure to locate the nadir point reliably. Figure43shows the value path plot of obtained points for estimating the nadir point for the10-objective DTLZ2 problems.Understandably,the points near the extreme of the Pareto-optimal front are found.From this plot,the nadir point of the problem is estimated to be(1,1,1,1,1,1,1,1,1,1)T.
VII.T WO P ROBLEMS FROM P RACTICE
After solving a number of test problems,we now apply NSGA-III to a couple of engineering design optimization problems.The?rst problem has three objectives and the second one has nine objectives.
TABLE XIII
N ADIR POINT ESTIMATION BY NSGA-III IN THREE TO20-OBJECTIVE
DTLZ1AND DTLZ2PROBLEMS.
M NSGA-II[54]
318,800
16,660
45,700
25,000
58,400
152,040
10239,800
259,760
358,000
356,460
1,100,000
1,200,000
202,600,000
956,960
4,000,000
DTLZ21,368
4,900
2,532
59,400
6,900
14,200
31,400
92,800
76,080
15346,500
213,060
810,000
309,440
1,415,000
734,400