Genetic algorithms optimization for normalized normal constraint method under Pareto construction
M.Martínez,S.García-Nieto *,J.Sanchis,X.Blasco
Department of Systems Engineering and Control,Polytechnic University of Valencia,Spain
a r t i c l e i n f o Article history:
Received 2August 2006
Received in revid form 25February 2008Accepted 18April 2008
Available online 2June 2008Keywords:
Pareto frontier
Multiobjective optimization Non-linear optimization Genetic algorithms Engineering
a b s t r a c t
This paper prents the resolution of multiobjective optimization problems as a tool in engineering d
esign.In the literature,the solutions of this problems are bad on the Pareto frontier construction.Therefore,substantial efforts have been made in recent years to develop methods for the construction of Pareto frontiers that guarantee uniform distribution and exclude the non-Pareto and local Pareto points.The normalized normal constraint is a recent contribution that generates a well-distributed Pareto frontier.Nevertheless,the methods are susceptible of improvement or modifications to obtain the same level of results more efficiently.This paper propos a modification of the original normalized nor-mal constraint method using a genetic algorithms in the optimization task.The results prented in this paper show a suitable behavior for the genetic algorithms method compared to classical Gauss–Newton optimization methods which are ud by the original normalized normal constraint method.
Ó2008Elvier Ltd.All rights rerved.
1.Introduction
Usually,the desired goals in engineering design,management,and decision making in general,can be addresd as the resolution of an optimization problem.In general,the state problem is de-fined as a single objective function expresd as a mathematical function bad on some criteria.In many ca
s,the principle objec-tive is the optimization of a cost function which describes the pro-ject or design cost,since this variable should be the dominant decision term.However,not only the cost can be focud on the design,since a designer or decision maker needs to make tradeoffs between disparate and conflicting design objectives.At this point,the definition of a multiobjective optimization (MO)problem can be interesting,given that the field of MO defines the art and science of making such decisions.The MO techniques offer advantages when compared with single objective optimization techniques be-cau they may produce a solution with different trade-offs among different individual objectives,so that the decision maker (DM)can lect the best final solution.
In some engineering fields,problem design is bad on single objective optimization techniques that weigh different objective functions to obtain the best solution from design variables.Choos-ing weighting factors in the cost index is usually a tedious trial-and-error process,and in many cas,due to the configuration of
the index (for example,linear or quadratic),it is not possible to find good trade-off solutions [1].
MO methodology provides the designer with the possibility of a better lection of the final solution,since there is no part of the arching space ignored.Solutions provided by MO algorithms s
hould be reprentative of the whole space of design variables.Since computational algorithms perform a discrete arch in the space of design variables,the group of solutions found must be evenly distributed to avoid over-explored or under-explored areas.On the other hand,that group of solutions should not contain non-optimal solutions,since this situation could make the DM lect a potentially inappropriate value for some design variables.
Solving an MO problem is usually associated with the construc-tion of the Pareto frontier.A Pareto frontier is a t of solutions in which improvement in one objective can only take place if at least one other objective worns.Therefore,each point of this frontier reprents one solution in the objective function space of the MO problem –given any pair of solutions as vectors of objective func-tion values,an improvement in one of its components involves worning in the others.In this way,any point is better than an-other in this frontier (non-dominated points),and the rest of the points are also dominated by one or more points of this frontier (dominated points).
Recently,a new method for the Pareto frontier construction,de-fined as normalized normal constraint (NNC),has been enunciated in [2,3].The contributions prent a clear methodology for obtaining a well-distributed Pareto frontier for n -dimensionals MO problems.However,NNC prents some drawbacks derived from the u of gradient-bad optimization algorithms,which
0965-9978/$-e front matter Ó2008Elvier Ltd.All rights rerved.doi:10.1016/j.advengsoft.2008.04.004
*Corresponding author.
wake wake
E-mail address:mmiranzo@isa.upv.es (M.Martínez),rgarro@isa.upv.es (S.García-Nieto),jsanchis@isa.upv.es (J.Sanchis),xblasco@isa.upv.es (X.Blasco).Advances in Engineering Software 40(2009)
260–267
Contents lists available at ScienceDirect
Advances in Engineering Software
journal homepage:www.elvie r.c o m /l o c a t e /a d v e n g s o f
t
introduce the local minimum problem.The original NNC method us a Gauss–Newton optimization algorithm,and for this reason the Pareto frontier points obtained with the method are,in all cas,potentially locally Pareto optimal points.This paper explores the application of genetic algorithm(GA)as substitute for the gra-dient-bad optimization techniques.The main goal is to avoid the local Pareto points using a random arch-bad GA.The meth-ods can theoretically obtain better results since they can generate a global optimum solution,but the computational cost is higher than the gradient-bad techniques.
The u of GA in Pareto frontier construction was introduced in [4],where the Pareto GA method is d托福难还是雅思难
efined as bad on the char-acteristic of the GA to arch for non-dominated solutions.Other alternatives can be found in the literature as[5]or[6],however this method lack the ability to generate a t of well-distributed Pareto solutions.For this reason,this paper propos the combina-tion of the NNC method with the GA ,GANNC)since the fusion of the two techniques can generate a t of well-dis-tributed and global solutions which define the Pareto frontier of the MO problem.
This paper is organized as follows.Section2prents the math-ematical foundations of the NNC method.Section3prents the main mathematical foundations of the GA ud method.Section 4introduces the applied examples.In Section5numerical results are provided for comparison.In particular,Section5shows the re-sults in the Pareto frontier construction with NNC and GANNC methods,and demonstrates how,under the initial conditions,the cond algorithm independently generates better results.Finally, Section6provides a summary and the main conclusions of the
improvements and modifications prented in the paper.
2.The normalized normal constraint method
This ction provides the analytical development of the NNC method for MO problems.For the sake
of simplicity,the next the-oretical introduction is focud on a bi-objective problem, although it can be generalized to n-objectives in a relatively simple way.The complete description and development for bi-objective and n-dimensional problems can be found in[2].
Firstly,let us introduce the mathematical reprentation of an MO problem with two objective functions(bi-objective):
min x½l1ðxÞl2ðxÞ ð1Þsubject to:
g
q
ðxÞ60;ð16q6rÞ
h kðxÞ¼0;ð16k6sÞ
x l i6x i6x u i;ð16i6n xÞ
ð2Þ
where x is the n x dimension vector of design variables to optimize;
g
西北师范大学怎么样q
ðxÞand h kðxÞare each of the r inequality and s equality problem constraints respectively;and x l i and x u i are the lower and upper con-straint limits in the n x dimensions of the arch space respectively. With this formulation,the problem does not have a unique solution. Tofind a single optimum solution,a statement of ur preference is required.
Secondly,let us define some relevant elements for the develop-ment(e Figs.1and2for more details):
Anchor pointsðl iÃ2R2Þ:defined as the end of the Pareto fron-tier,are obtained when the i th objective is minimized independently.
Utopia lineðP uÞ:describes the line joining two anchor points in bi-objective cas,and in the multiobjective(n-objective)ca is
a plane that compris all anchor point(Utopia hyperplane). Utopia pointðl u¼½lÃ
1
;lÃ
2
2R2Þ:reprents a point where its components are the optimum vertices(anchor points).This point is not part of the Utopia line or hyperplane.
Optimal decision vectorðx iÃ2R2xÞ:the variable decision vector which guarantees the i th optimal objective.
Generic i th optimal objectiveðlÃ
沪江音乐i
¼lðx iÃÞ2R2Þ.
Once the mathematical preliminaries are introduced,let us de-scribe the NNC method following the ven-step process defined in [2]:
Step1–Anchor points:Obtain the two anchor points l1Ãand l2Ã, resulting from solving the two following optimization
problems:
min x l
i
ðxÞði¼1;2Þð3Þsubject to(2)
The obtained anchor points determine the ends of the Pareto
frontier(Fig.1a).In addition,the Utopian1point,denoted by
l u,is compound by the good elements of each anchor point.
l u¼½l
1
ðx1ÃÞl2ðx2ÃÞ T¼½l1Ãl2Ã Tð4ÞStep2–Objectives normalization:To avoid scaling deficiencies,the optimization takes place in the normalized space.Let l be
the normalized form of l.Defining the vector L as the max-
imum distances in each component of the anchor points
relative to the utopian line,a normalization of the arch-
ing space can be performed.
L¼f l1l2g T¼l NÀl uð5Þ
where
l N¼½l N
recently时态1
l N
2
ð6Þ
l N
i
¼max½l iðx1ÃÞl iðx2ÃÞ ð7Þ
1Since it is the best point,but it cannot be reached.
M.Martínez et al./Advances in Engineering Software40(2009)260–267261
which leads to the normalized design metrics as
l i¼l iÀl iðx iÃÞ
l i
;i¼ð1;2Þð8Þ
The new normalized arching space is described by Fig.1b. Step3–Utopia line vector:Let vector N1defined as the difference between the normalized anchor vectors(Fig.2a).
N1¼l1ÃÀl2Ãð9ÞStep4–Normalized increments:The normalized increment D1is defined for a prescribed number of solutions(Fig.2a)m1as
D1¼
1
1
j N1jð10ÞStep5–Generate utopia line points:Evaluate a t of evenly dis-tributed points on N1are(Fig.2b):
X pj¼a1j l1Ãþa2j l2Ãð11Þ
a2j¼1Àa1jð12Þ
a1j¼
j
m1À1
;j¼0;ÁÁÁ;m1À1ð13Þ
Step6–Pareto points generator:Using the t of evenly distributed points on the utopia line X pj,generate a corresponding t
of Pareto points by solving a succession of minimization
single objective problems in the normalized domain.The
optimization problem can be formulated as(Fig.2b):
min x l2ð14Þ
subject to:
g
q
ðxÞ60;ð16q6rÞ
h kðxÞ¼0;ð16k6sÞð15Þ
x l i6x i6x u i;ð16i6n xÞ
N T
1
ð lÀX pjÞ60ð16Þ l¼½ l1ðxÞ l2ðxÞ T
Note that for each problem j,an additional constraint(16)is added reprenting the scalar product of vectors1and the vector formed by the difference between the points of the feasible area l and point X pj.Forcing that scalar product to be smaller than zero,the optimi-zation is obligated to arch for the minimum value when the vectors are in opposition.This ensures that this minimum in the Pareto frontier will be found for each X pj point(e Fig.2b).If the scalar product inequality(16)is transformed into scalar product equality,it will generate,in general,a Pareto frontier with more points.
Step7–Pareto design metrics values:Evaluate the non-normalized design metrics that correspond to each Pareto point.
3.Numerical optimization approaches
The construction of the Pareto frontier for solving a succession of optimization problems(14)as described in Step6,can include non-Pareto or local Pareto points in its solution.The Local Pareto points are tho that locally are not dominated by any other point and non-Pareto points are even dominated locally.The inclusion of the points derives from the u of local optimization techniques (for example,Gauss–Newton)which do not guarantee a global optimum solution and are nsitive to i
nitial conditions[7].
The NNC method introduced in[2]manages the local optimiza-tion drawbacks using a Paretofilter.This approach is an algorithm that,given a t of points in the objective space,produces a subt of the given points for which none will be dominated by any other. Therefore,the original NNC method cannot handle the appearance of local and non-Pareto points.
This paper propos to u global optimization techniques as a substitute for the original Gauss–Newton optimization method to solve the problems described in(14)and the laterfiltering process propod in[2].In particular,the u of GA algorithms as global optimum archers are propod.The main reason for using this technique is their ability to deal with the typical problems derived from the lection of the initial points,and the high rejection of lo-cal optimum solutions.
In conclusion,the solution for MO problems depends on the optimization technique chon.If an iterative numerical optimiza-tion method bad on linear or quadratic index approach is -lected(as generally happens),and if the cost index prents difficulties due to the prence of local minima,then the optimiza-tion will depend on the initial conditions.From this perspective,it is not guaranteed that the original result really incorporates all the points,of global Pareto frontier,mainly in
areas where the frontier has special difficulties due to its curvature,and therefore,it is pos-sible to arrive at a non-optimal solution.It is possible to construct an appropriate Pareto frontier using different methods bad on non-linear numerical optimization.Although the results are satis-factory,they depend on the initial points lected for arching, and sophisticated algorithms are required to eliminate unwanted points(local and non-Pareto points).
3.1.Genetic algorithms
Genetic algorithms[8–10]are optimization techniques bad on evolution,that is,on the rules of natural lection.In a GA, the population is the t of possible solutions,and each individual from this population is characterized by chromosome-like struc-tures.The possibilities of survival for each individual are evaluated by the cost function(function to optimize).The result of this eval-uation is calledfitness and plays an important role in lection and reproduction.Finally,evolution is achieved through the application of genetic operators,such as:lection,crossover,and mutation.
The main concepts of a GA are:
Codification:every potential solution is encoded by means of a string.
Population evolution(through the application of genetic operators).
3.2.Codification
This process consists of assigning a string to each point of the solution space.This string will belong to a certain alphabet:binary, real,or any other.Codification produces a discretization of the con-tinuos solution space and the precision of this discretization de-pends on the string length.
3.3.Population evolution
Once the codification pha hasfinished,the next step is the application of the evolutive algorithm.The GA ud in this work is the so-called simple genetic algorithm(SGA)and itsflowchart is shown in Fig.3.Thefirst step of the evolutive algorithm is the generation of an initial random population.As a result,a t of ran-dom strings are generated.After the initialization of the popula-tion,thefitness of every individual in the population is obtained through cost function evaluation.If the ending condition is not sat-isfied,the next step will be population evolution(applying genetic operators).The ending condition can be the generation number, the degree of convergence,or any other.
262M.Martínez et al./Advances in Engineering Software40(2009)260–267
3.3.1.Selection
A t of individuals from the previous population must be -lected for reproduction.This lection depends on their fitness val-ues.Individuals with better fitness values (they are clo to the best solution)will more probably survive.Before this lection is carried out,to avoid a premature convergence of the population,the fitness values can be modified:the best fitness values are de-cread and the worst ones are incread.This process is called ranking and can be implemented in veral ways.
There exist different types of lection operators,and the most general approach is stochastic universal sampling (SUS)[11].In a SUS scheme,the population is laid out in random order in a pie gr
aph,and individuals with higher fitness values have a bigger por-tion of the pie graph.The probability of an individual being -lected P ðx i Þis given by:P ðx i Þ¼f ðx i Þ
P ind
i ¼1f ðx i Þ
ð17Þ
where f ðx i Þis the fitness value for individual x i and N ind is the pop-ulation size.
地黄牛A roulette wheel is placed around the pie graph with N (number of individuals to be lected)equally-spaced pointers (e Fig.4).A single spin of the roulette wheel will simultaneously pick all the members of the next population.
3.3.2.Crossover
The crossover operator is applied after lection and this pro-duces new individuals.Not all the lected individuals are crosso-vered,this depends on the crossover probability P c .Crossover consists of merging the chromosomes of two individuals (parents)to obtain two other individuals (children).Parent pairs are ran-domly chon from the lected population and the kind of merg-ing depends on the crossover operator ud.Fig.5contains a scheme of the single-point crossover with binary codification.
3.3.3.Mutation
Mutation is the last genetic operator applied in a SGA scheme (e Fig.6).Each part of the population can be inverted with a probability P m (usually very low).A better exploration of the arching space is carried out using this operator.3.4.Parameter lection
In this work,the GA implementation prents the following characteristics:
(1)Real value coding is ud [9],i.e.each gene has a real value
thus the chromosome x is an array of real values.
(2)l i ðx Þis not directly ud as cost function.A ‘ranking’opera-tion is performed [12,13].Firstly,individuals are sorted out in decreasing l i ðx Þvalue,and then,l i ðx Þis replaced by its position in such a distribution.Each individual has a new cost function value q ðx Þ.The ranking operation prevents clearly dominant individuals from prevailing too soon,thus exhausting the algorithm.
(3)Selection is made by SUS (17).
(4)For crossover the intermediate recombination operator is
ud [14].Child chromosomes x 01and x 02are obtained through the following operation on the parental chromo-somes (x 1and x 2):
x 01¼a 1Áx 1þð1Àa 1Þx 2;a 12½Àd ;1þd x 02¼a 2Áx 2þð1Àa 2Þx 1;
a 22½Àd ;1þd
ð18Þ
The operation can be performed on the chromosome of each gene parately.In this last ca,random parameters a 1
and
M.Martínez et al./Advances in Engineering Software 40(2009)260–267263
a2have to be generated for each gene–increasing arch po-tential but with a higher computational cost.Implemented GA has been adjusted with a1¼a2and d¼0.
(5)The crossover operation is made with a probability P c¼0:8.
(6)The mutation operation is made with a probability P m¼0:1
and a normal distribution with standard deviation t to20% of the arch space range.
The structure and parameters of the GA propod have been validated using multimodal test functions(Rastrigin, Schewefel,Griewank functions,among other)described in
[12].
4.Applied examplesfriendly
The lected example is the three-bar truss structure design, which is a classical benchmark in the literature.Thefirst definition of the problem was introduced in[15],later Messac tested the NNC method introduced in[2]with the same benchmark.However,the equations prented by Messac were not introduced and is difficult to know the objective functions and parameters ud in[2].For that reason,this paper prents an exhaustive description of the design problem,where the equations and parameters have been defined from[16].In this reference the three-bar truss is raid as afinite element analysis problem.The main goal of the exhaus-tive description of the three-bar truss is to give the reader the op-tion of reproducing in a simple way the benchmark ud in this paper.
The original example[15]has been completed with a new ori-ginal objective function bad on the cost design.The objective of this contribution is to prent a more practical design approach since the cost is always a decision parameter in the real world.
The Fig.7describes a three-bar truss broadly ud as a bench-mark to define the best solutions bad on some specifications.
The truss is hyperstatic,thus the solution of force balances have to be supplemented with equations
of the deformations.For this ca,the parameters propod in[2,15]were lected for further comparison.The design variables correspond to the ctions of the barsða¼a1;a2;a3Þwith constraints a i u¼2cm2(maximum ction)and a i l¼0:1cm2(minimum ction)for all of them.The rest of parameters for the truss are:L=1m; h¼45 ;a¼30 ;F¼20Â103N;E¼200Â109Pa(Young modu-lus);r¼200Â106Pa(maximum stress accepted in each bar);½q1q2q3 ¼½785078507850 kg
m3
ðdensity for each barÞ.
4.1.Deformation vs.weight
Thefirst MO problem is defined by the objective functions cor-responding to the total weight of the truss(W)and a linear combi-nation d of the displacement of node P.Thisfirst MO problem is exactly equivalent to the problem solved by Messac and Koski in [2,15],respectively.
The MO optimization problem can be formulated as follows: min a½l1ðaÞl2ðaÞ a¼½a1a2a3 ð19Þsubject to:
j N i j
a i
6r;i¼1::3ð20Þa i l6a i6a i u;i¼1::3ð21Þwhere
N i are the reaction forces in each bar calculated according to: N1¼
a1E
L
ðd1sin hÀd2cos hÞsin hð22ÞN2¼
a2E
L
d1ð23ÞN3¼
a3E
L
ðd1sin aþd2cos aÞsin að24Þ l1ðaÞobjective function for the deformation of node P: l1ðaÞ¼d¼0:25d1þ0:75d2ð25Þ l2ðaÞis the truss weight objective function:
l2ðaÞ¼W¼q Vð26Þwhere V is the truss volume and q the density for each bar.
q¼½q1q2q3 ð27ÞV¼L
a1
La2L
a3
h i
ð28ÞThe deformations d1and d2can be expresd as
d1
d2内双怎么画大眼妆
¼
L
E
c1c2
c2c3足球
À1F
F
c
1
¼a2þa1sin3hþa3sin3a
c2¼Àa1sin2h cos hþa3sin2a cos a
c3¼a1sin h cos2hþa3sin a cos2a
ð29Þ
4.2.st
The cond MO problem is defined by the objective functions corresponding to the total cost of the material(C,e Fig.8)and a linear combination d of the displacement of node P.
The MO optimization problem can be formulated as follows: min a½l1ðaÞl2ðaÞ a¼½a1a2a3 ð30Þsubject to(20)and(22).
l1ðaÞobjective function(25)for the deformation of node P.
l2ðaÞis the total cost objective function.
The total cost has two terms
C¼C mþ
X3
j¼1
C p
j
ð31ÞThefirst term corresponds to the material costkeratin
C m¼K q V K¼15
euro
ð32Þwhere V is the truss volume(28).
The cond term is the manufacturing cost(euros).
264M.Martínez et al./Advances in Engineering Software40(2009)260–267
