外文翻译--鲁棒优化设计的多目标遗传算法 英文版.pdf

AMulti-ObjectiveGeneticAlgorithmforRobustDesignOptimizationMianLiGraduateResearchAssistantDepartmentofMechanicalEngineeringUniversityofMarylandCollegePark,MD20742Tel.+13014054919E-mail:mli6umd.eduShapourAzarmProfessorDepartmentofMechanicalEngineeringUniversityofMarylandCollegePark,MD20742Tel.+13014055250E-mail:azarmumd.eduVikrantAuteFacultyResearchAssistantDepartmentofMechanicalEngineeringUniversityofMarylandCollegePark,MD20742Tel.+13014058726E-mail:vikrantumd.eduABSTRACTReal-worldmulti-objectiveengineeringdesignoptimizationproblemsoftenhaveparameterswithuncontrollablevariations.Theaimofsolvingsuchproblemsistoobtainsolutionsthatintermsofobjectivesandfeasibilityareasgoodaspossibleandatthesametimeareleastsensitivetotheparametervariations.Suchsolutionsaresaidtoberobustoptimumsolutions.Inordertoinvestigatethetrade-offbetweentheperformanceandrobustnessofoptimumsolutions,wepresentanewRobustMulti-ObjectiveGeneticAlgorithm(RMOGA)thatoptimizestwoobjectives:afitnessvalueandarobustnessindex.Thefitnessvalueservesasameasureofperformanceofdesignsolutionswithrespecttomultipleobjectivesandfeasibilityoftheoriginaloptimizationproblem.Therobustnessindex,whichisbasedonanon-gradientbasedparametersensitivityestimationapproach,isameasurethatquantitativelyevaluatestherobustnessofdesignsolutions.RMOGAdoesnotrequireapresumedprobabilitydistributionofuncontrollableparametersandalsodoesnotutilizethegradientinformationoftheseparameters.Threedistancemetricsareusedtoobtaintherobustnessindexandrobustsolutions.Toillustrateitsapplication,RMOGAisappliedtotwowell-studiedengineeringdesignproblemsfromtheliterature.CategoriesandSubjectDescriptorsG.1.6OptimizationNonlinearProgramming；GeneralTermsDesign,algorithmsKeywordsMulti-objectivegeneticalgorithms,robustdesignoptimization,performanceandrobustnesstrade-off1.INTRODUCTIONTherearemanyengineeringoptimizationproblemsintherealworldthathaveparameterswithuncontrollablevariationsduetonoiseoruncertainty.Thesevariationscansignificantlydegradetheperformanceofoptimumsolutionsandcanevenchangethefeasibilityofobtainedsolutions.Theimplicationsofsuchvariationsaremoreseriousinengineeringdesignproblemsthatoftenhaveaboundedfeasibledomainand/orwheretheoptimumsolutionslieontheboundaryofthefeasibledomain.Manymethodsandapproacheshavebeenproposedintheliteraturetoobtainrobustdesignsolutions；thatis,feasibledesignalternativesthatareoptimumintheirobjectivesandwhoseobjectiveperformanceorfeasibility(orboth)isinsensitivetotheparametervariations.Generally,thoseapproachescanbeclassifiedintotwotypes:stochasticapproachesanddeterministicapproaches.Stochasticapproachesusetheprobabilityinformationofthevariableparameters,i.e.,theirexpectedvalueandvariance,tominimizethesensitivityofsolutions(e.g.,Parkinsonetal.1,YuandIshii2,JungandLee3forobjectiverobustoptimization；andDuandChen4,Chenetal.5,Tu,ChoiandPark6,7,Younetal.8andRay9forfeasibilityrobustoptimizationalsocalledreliabilityoptimization.Also,JinandSendhoff10proposedanevolutionaryapproachtodealwiththetrade-offbetweenperformanceandrobustnessusingvarianceinformation).Themainshortcomingofstochasticapproachesisthattheprobabilitydistributionfortheuncontrollableparametersisknownorpresumed.However,itisdifficult(orevenimpossible)toobtainsuchinformationbeforehandinreal-worldengineeringdesignproblems.Deterministicapproaches,ontheotherhand,obtainrobustoptimumdesignsolutionsusinggradientinformationoftheparameters(e.g.,Ballingetal.11,Sundaresanetal.12,13,ZhuandTing14,LeeandPark15,SuandRenaud16,MessacandYahaya17)orusinganon-gradientbasedparametersensitivityestimation(GunawanandAzarm18-21).TheaimoftheGunawanandAzarmsapproach18-21istoobtainoptimumsolutionswhichessentiallysatisfyanadditionalrobustnessconstraintthatisprescribedbythedecisionmaker(DM).Inthispaper,wepresentanewdeterministicapproachtoinvestigatethetrade-offbetweentheperformanceandrobustnessPermissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprofitorcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationonthefirstpage.Tocopyotherwise,orrepublish,topostonserversortoredistributetolists,requirespriorspecificpermissionand/orafee.GECCO05,June25-29,2005,Washington,DC,USA.Copyright2005ACM1-59593-010-8/05/0006$5.00.771ofoptimumsolutions,basedonaMulti-ObjectiveGeneticAlgorithm(MOGA).Thegoalofourapproachistosimultaneouslyoptimize:i)ameasureoftheoptimumsolutionsperformance,i.e.,thefitnessvalue,thataccountsforobjectiveandconstraintvaluesintheoriginaloptimizationproblem(definedinSection2),andii)ameasureoftheoptimumsolutionsrobustness,therobustnessindex,originallyproposedbyGunawanandAzarm18-21,extendedinthispaperwiththeuseoftwoadditionaldistancenorms.Thisapproachisadeterministicmethodusingnon-gradientbasedparametersensitivityestimation,whichcanbeappliedtooptimizationproblemshavingobjectiveand/orconstraintfunctionsthatarenon-differentiablewithrespecttotheparameters.AnyMOGAintheliteraturecanbeappliedtothisapproach.InGunawanandAzarmsapproach18-21,theauthorstriedtoobtainoptimumsolutionsthatareinsensitivetotheparametervariation.Inotherwords,therobustnessrequirementwasconsideredasaconstraintintheirapproach.Onthecontrarywetreat“robustness”asoneofourobjectivesandformanewtwo-objectiverobustoptimizationproblem(regardlessofhowmanyobjectivestheoriginalproblemhas),toinvestigatetherelationbetweentheperformanceandrobustnessofsolutions.TheRMOGAhereaimsatsimultaneouslymaximizingperformanceandmaximizingrobustness.Theorganizationoftherestofthispaperisasfollows:InSection2,wepresenttheoriginaloptimizationproblemandexplainsomedefinitionsandterminologies.Basedonabriefdescriptionoftheobjectiveandfeasibilityrobustoptimizationapproach,wepresentournewapproachinSection3.Section4demonstratestheapplicationofourapproachtotwotestproblemsfollowedbyadiscussionoftheresults.ThepaperconcludeswithasummaryinSection5.2.PROBLEMDEFINITIONInthissection,weformallydefinetheproblemandexplainseveraldefinitionsandterminologiesusedinthispaper.Ageneralformulationofmulti-objectiveoptimizationproblemisshownin(1).upperlowerjmxxxxJjpxgMmpxf=,10),(s.t.,1),(minKK(1)(f1,fM)taretheobjectivefunctions(treferstoatransposeoftherowvector),x=(x1,xN)tisthedesignvariablevector(controlledinanoptimizationrun),p=(p1,pG)tistheuncontrollableparametervector.Notethatdesignvariablesthatthemselveshaveuncontrollablevariationsareincludedinbothxandp.xlowerandxupperarethelowerandupperboundsofx,respectively.TheproblemhasJinequalityconstraints,gj,j=1,J.Wepresumethatallconstraintscanberepresentedasinequalityfunctions.Inthispaper,wecalltheoptimizationproblemshownin(1)astheoriginalproblem.Sincetherearetrade-offsamongsttheMobjectives,usuallytheoriginalproblemhasmorethanoneoptimumsolution.ThesetoftheseoptimumsolutionsiscalledtheParetoset,asdiscussedinMiettinen22andinDeb23.Inthefollowing,webrieflydescribesometerminologiesthatareusedinthispaper.Nominalparametervaluep0=(p0,1,p0,G)tistheparametervectorvalues,p=p0,usedtooptimizetheproblemin(1).Theparametersvariationisp=(p1,pG)t.NominalParetosolutionsaretheParetosolutionsoftheoptimizationproblemin(1)whenp=p0.Letx0beadesignsolutionwhoserobustnesswewanttoanalyze.f(x0,p0)=(f1(x0,p0),fM(x0,p0)arethenominalvaluesfortheobjectivefunctions,andg(x0,p0)=(g1(x0,p0),gJ(x0,p0)arethenominalvaluesfortheconstraintfunctions.ToleranceRegionisahyper-rectangularregioninp-spaceformedbyasetofpvalueswithrespecttowhichthedecisionmakerwantstherobustoptimumsolutiontobeinsensitive.Thisregionisusuallyboundedbyupperlowerppp,wheretheknownplowerandpupperarethelowerandupperboundsofp,respectively,plower=(p1lower,pGlower)tandpupper=(p1upper,pGupper)t.Forsimplicity,thetoleranceregionisassumedtobesymmetric,i.e.,-pilower=pT,i=piupper,.,10,GipiTK=>Sincetherecanbemorethanoneuncontrollableparameterwithdifferentmagnitudes,wenormalizethetoleranceregiontoformahyper-square.Parametervariationspace(p-space):AG-dimensionalspaceinwhichtheaxesaretheparametervariationpvalues.AcceptablePerformanceVariationRegion(APVR)istheregionformedintheobjectivefunctionspacearoundthepointf(x0,p0),whichrepresentsthemaximumacceptableperformancevariationchosenbytheDM,i.e.,f0=(f0,1,f0,M)t,whereMifi,1,0,0K=.SeeFigure1(a)fordetails.Fitnessvaluefvisavaluethatmeasuresasolutionsperformanceinacombinedobjectiveandconstraintsense.Thefitnessvalue(orrank)obtainedfromaMOGA,e.g.,NSGA23,canbeusedasthefitnessvalueinourapproach.Robustnessindexisaratiothatcalculatestheradiusoftheworstcasesensitivityregion(definedinSec.3.2)withrespecttopovertheradiusoftheexteriorhyper-sphereofnormalizedtoleranceregion18.Itisusedasarobustnessmeasureinourmethod.WewilldiscussitfurtherinSection3.DistancenormLpforanN-dimensionalvectorxisthevectornormpxforp=1,2andinfinity()definedaspNipipxx11)(=.Theinfinitynormis:iixxmax.3.ROBUSTMOGAInthissection,wefirstbrieflydiscussthesensitivityestimationproposedbyGunawanandAzarm18-21,basedonwhich,themeasuresforrobustnessandperformanceofsolutionsaredefined.Wethenpresentourtwo-objectiveRMOGAapproach.3.1ParameterSensitivityEstimationWefirstdiscusstheapproachformulti-objectiverobustoptimization,followedbytheapproachforfeasibilityrobustoptimizationandthenthecombinedapproach.GivenanAPVRforasolutionx0,thereisasetofpsuchthatthevariationinobjectivefunctionsvaluesduetotheparestillwithintherangesoff0,iforalli=1,.,M.Thissetofpformsahyper-regionaroundtheorigininp-space,whichiscalledtheSensitivityRegion(SR).Theregionisboundedasshownin(2):),(),(where,1,0000,0pxfppxffMiffiiiii+=K(2)Figure1showstheAPVRanditscorrespondingSRforasolutionx0inatwo-parameterandtwo-objectivecase.Graphically,the772pointsinside,outside,andontheboundaryoftheAPVRcorrespondtothepointsinside,outside,andontheboundaryoftheSR(Figure1(b),respectively.Af2Bf(x0,p0)f0,1f0,2CAPVRf(a)BCAp2p1SensitivityRegion(b)Figure1(a)TheAPVRand(b)theSREssentially,theSRrepresentstheamountofparametervariationsthatasolutionx0canabsorbbeforeitviolatestheAPVR.WecanusethesizeoftheSRasameasureforthesensitivityofadesign:thelargertheSRforadesign,themorerobustthatdesignis.However,ingeneral,theshapeoftheSRcanbeasymmetric,whichmeansadesigncanbeverysensitive(ormuchlessrobust)inacertaindirectionofp(suchasdirectioninFigure1(b),butmuchlesssensitive(orveryrobust)inotherdirections(suchasdirectioninFigure1(b).Toovercomethisasymmetry,aWorst-CaseSensitivityRegion(WCSR)isusedtoestimatetheSRofadesign.TheWCSRisasymmetrichyper-spherethatapproximatestheSR.Graphically,theWCSRisthesmallesthyper-spherethattouchestheSRattheclosestpointtotheorigin,asshowninFigure2foratwo-parametercase.SincetheWCSRissymmetric,theradiusoftheWCSR,Rf,insteadofthesizeoftheWCSR,couldbeusedasourrobustnessmeasure.Itmeasurestheoverallrobustnessofadesign.TheradiusoftheWCSRforx0canbecalculatedbysolvingasingle-objectiveoptimizationproblemshownin(3).),(),(where01)(maxs.t.)(min0000,0,11pxfppxffffppRiiiiiMiqGjqjfp+=K(3)Inthisproblem,thedesignvariablesaretheps,theobjectivefunctionistheradiusoftheWCSR.TheequalityconstraintfunctionmeansthattheresultantvectoroffitouchestheboundaryoftheAPVR,whichmeansthatpisontheboundaryofthesensitivityregion.DetaileddiscussionofthisWCSRestimationapproachisgivenelsewhere18,19.Asimilarapproachcanbeusedforthefeasibilityrobustoptimization.Foradesignx0,allppointswhosecorrespondingconstraintfunctionvaluegj(x0,p0+p)0,j=1,J,formtheFeasibilitySensitivityRegion(FSR),whichmeansthepinsidetheFSRwillnotchangethefeasibilityofdesignx0.TheFeasibilityWCSR(orFWCSR)istheworst-caseestimateoftheFSR(similartotheWCSR)andRgistheradiusofthenormalizedFWCSR.Rgcanbecalculatedby(4).0),(maxs.t.)(min00,11=+=ppxgppRjJjqGjqjgpK(4)SincetheSRandtheFSRaredefinedinthesamep-spaceandareofthesamescale,R=min(Rf,Rg)impliesthatwearelookingfortheradiusofworst-caseestimateoftheintersectionoftheSRandtheFSRforadesignsolution,asshowninFigure2.RfWCSRp2p1SRRgFSRFWCSRFigure2TheintersectionofSRandtheFSRTheradiusRcanbecalculatedbysolvingtheoptimizationproblemshownin(5).JjpxgppxgppxgpxggffppRjjjjjJjiiMiqGjqjp,.,1),(),(),(where01),(max),(maxmaxs.t.)(min0000000,1,0,11=+=+=KK(5)Forexample,inthecaseshowninFigure2,R=min(Rf,Rg)=Rf.3.2RobustnessIndexTheradiusRrepresentsasolutionsrobustnessonanordinalscaleanddoesnothaveaphysicalassociationwiththedesignsolutionitself.AssuchitcanbedifficultfortheDMtodothetrade-offanalysisbetweentheperformanceandrobustness,i.e.,givenR,s/hecannotdecidewhetheradesignsolutionisrobustornot.Toovercomethisdifficulty,weusetheradiusoftheexteriorhyper-sphereofthenormalizedtoleranceregion,RE,asareferencefortherobustnessrequirement(Figure3).WedefinetherobustnessindexERR=andusethisrobustnessindexasoneofthetwoobjectivesinourRMOGA.Ristheoptimumsolutioncalculatedin(5).SinceREistheradiusoftheexteriorcircleofthenormalizedtoleranceregion,if1=ERR,thenthedesignx0isrobust.NormalizedtoleranceregionREp2p1Figure3Theexteriorcircleofthenormalizedtoleranceregion7733.3FitnessValueRecallthatourgoalinthispaperistosimultaneouslymaximizetheperformanceandrobustnessofadesign.Therobustnessindexservesasameasureofrobustnessofthedesignsolutions.Henceweneedanothermeasurefortheoverallperformanceofdesignsolutions.Inmulti-objectiveoptimizationproblem,MOGAisagoodtooltoobtainParetooptimumsolutions.MostMOGAsassignafitnessvalueoraranktoeachalternativesolutioninthepopulationtorepresentitsrelativegoodness,accountingforbothobjectivevaluesandconstraints.Sothefitnessvalue(orrankordering)obtainedfromanyMOGAapproach,e.g.therankvaluefromNSGA23,canbeusedastheperformancemeasureinourapproach:thesmallerthefitnessvalue,thebettertheperformanceofthesolution.Formoredetailsonhowtoobtainthisfitnessvaluethereaderisreferredto23.NotethatdifferentMOGAapproachesmaygeneratedifferentsolutionsinourapproach.However,ourgoalhereisnottodevelopanewgeneticalgorithmordistinguishbetweendifferentMOGAs.3.4RMOGAApproachGiventhetwomeasuresforperformanceandrobustnessofadesignsolution,asdiscussedbefore,wecanformulateourproblemthathastwoobjectives:oneistheperformanceandtheotheristherobustnessforadesignsolution.Theformulationofourrobustmulti-objectiveoptimizationproblemisshownin(6)ExGMvxRRggfff=max),(min11KK(6)Herethefitnessvaluefvisafunctionoftheobjectivesandconstraintsthatarecalculatedin(1).Therobustnessindexiscalculatedfrom(5).Anoptimizationapproach(Figure4),withanouter-innerstructure,isutilizedtosolvetheproblemshownin(6).Theoutersub-problem(i.e.,theuppersub-probleminFigure4)istosimultaneouslyminimizethefitnessvaluefvandmaximizetherobustnessindex.Weusetheinnersub-problem(i.e.,thelowersub-probleminFigure4)tocalculatetheradiusR(recall(5)withrespecttop.upperlowerExGMvxxxxRRggfff=max),(min11KK01),(max),(maxmaxs.t.)(min0,1,0,11=pxggffppRjjJjiiMiqGjqjpKKRx0Figure4Outer-inneroptimizationstructureofRMOGAWestartwithanxvalue,calledx0,intheoutersub-problemandsendittotheinnersub-problem(includingthenominalvaluesforfm(x0,p0)andgj(x0,p0).Thenominalvaluesarefixedintheinnersub-problem.WethenoptimizetheradiusRasafunctionofpforthenominaldesignx0,andtheoptimalvalueRissentbacktotheoutersub-problem.Thisisrepeatedforalldesignalternativesunderconsideration(seeFigure4).WenowdiscussthefitnessassignmentprocedureusedintheimplementationofRMOGA.Forconciseness,theMOGAdetailsarenotdiscussedhereandthefocusisontheRMOGA.TheGeneticAlgorithm(GA)requiresascalarfitnessvalueforallthecandidatesolutions.Themajorstepsinthefitnessassignmentprocedureareasfollows:Step1:Evaluatetheobjectivesandconstraintsoftheoriginalproblem(1).Step2:Calculatetherobustnessindexforeachofthecandidatesolutions.Step3:Performanon-dominatedsortonthepopulationbasedontheobjectivevaluesoftheoriginalproblem.Considerthisrankandtheconstraintviolationtoassignafitnessvaluefvtothecandidatesolution.Step4:Performanon-dominatedsortingonthepopulationbasedonrobustindexandfitnessvaluefvastheobjectives.Thisisessentiallyatwo-objectivenon-dominatedsorting.Step5:Assignafitnessbasedonthenon-dominatedrankfromStep4andcontinuetheGAiterationsuntilconvergenceisreached.3.5DistanceNormIn(5)wecouldusethreedifferentqvaluesq=1,2and.DifferentLq-normswillaffectthevalueoftherobustnessindexofadesignsolution.AsshowninFigure5,thedistancefrompointA,BandCtotheorigincorrespondtotheradiussolutionfrom(5)inL1,L2andLnorm.Therobustnessmeasureshouldbespecifiedinaparticulardistance-norm.BCAp2p1SensitivityRegionL2-normL1-normL-normFigure5TheeffectofdifferentLp-norms4.TESTRESULTSInthissection,wewilldemonstrateanapplicationoftheproposedapproachtotwotestproblems.4.1TestProblem14.1.1ProblemDescriptionThefirsttestproblemthatweusetodemonstratetheRMOGA774