(复杂系统的性能评价与优化课件资料)Ordina.ppt

(复杂系统的性能评价与优化课件资料)Ordina.ppt

《(复杂系统的性能评价与优化课件资料)Ordina.ppt》由会员分享，可在线阅读，更多相关《(复杂系统的性能评价与优化课件资料)Ordina.ppt（44页珍藏版）》请在冰点文库上搜索。

（复杂系统的性能评价与优化课件资料）OrdinalOptimizationSoftOptimizationforHardProblems,2/40,Acknowledgment,JointworkwithProf.Yu-ChiHo（何毓琦）Prof.Qian-ChuanZhao（赵千川）Prof.Xiao-HongGuan（管晓宏）Dr.ChenSong（宋宸）SupportedbyNationalScienceFoundation,ChinaNewCenturyExcellentTalentsinUniversity,China973fundamentalresearchgrants,ChinaArmyResearchOfficeAirForceOfficeofScientificResearch,3/40,Outline,Background:

simulation-basedoptimizationOrdinaloptimizationComparisonofselectionrulesConstrainedordinaloptimizationVectorordinaloptimizationApplicationExamplePerformanceoptimizationinaremanufacturingsystemTheWitsenhausenproblemConclusion,4/40,Human-madecomplexsystems,Transportationsystem,Manufacturingsystem,Communicationsystem,Electricpowergrid,Supplychain,5/40,Time-consumingsimulation,6/40,Majordifficulties,Simulation-basedperformanceevaluationTime-consumingsimulationNoisyobservationDiscreteparametersLargedesignspace:

curseofdimensionalityNogradientinformation,7/40,OrdinalOptimization（OO）,OOisanimportanttooltodealwithsimulation-basedoptimization.FirstdevelopedbyProf.Y.-C.Ho,R.S.Sreenivas,andP.Vakiliin1992Ho,SreenivasandVakili1992.Inthepastdecade,morethan200publicationsandmanysuccessfulapplications.AnonlineincompleteOOpublicationslistisavailableat:

http:

/ThefirstbookonOOispublished:

Ho,Y.-C.,Zhao,Q.-C.,andJia,Q.-S.,OrdinalOptimization:

SoftOptimizationforHardProblems,NewYork,NY:

Springer,2007.,8/40,Basicideas（I）,Ordinalcomparison,v.s.,Whichoneisbigger?

Howmuchbigger,sayinunitofcmormm?

Itiseasiertofindoutwhichdesignisbetterthantoanswerhowmuchbetter.,9/40,Basicideas（II）,Goalsoftening,Whichboardiseasiertohit?

Why?

Itiseasiertofindagoodenoughdesignthantofindtheoptimaldesign.,v.s.,10/40,Basicideas-summary,OrdinalcomparisonComparedesignsusingacrudemodel,computationallyfastbutroughperformanceestimate.GoalsofteningFindingtheglobaloptimalispracticallyinfeasible.Amorereasonablegoal:

findagoodenough（top-n%）design.Notonlyintuitivelyreasonable,butalsocanbeshowninamathematicallyrigorouswayObservedorderconvergestotrueorderexponentiallyfastw.r.t.#ofobservationsDai1996,Xie1997.Theprobabilitythatsomeoftheobservedtop-n%designsaretrulygoodenoughconvergesto1exponentiallyfastw.r.t.nLeeLauHo1999.Insteadoffindingthebestforsure,OOfindsagoodenoughdesignwithhighprobability.Whatdowesaveinthisway?

Andhowmuch?

11/40,ApplicationProcedure,G,S,k,Q,Q:

designspaceG:

goodenoughsetS:

selectedset:

trueoptimum:

estimatedoptimumPr|GS|k:

alignmentprobability,12/40,Demonstration,200designsTrueperformanceJ（qi）=i,i=1,2200.Observedperformancei.i.d.uniformlydistributednoiseU0,W.Question:

Howmanyobservedtop-12（6%）designsaretrulytop-12ontheaverage?

demonstration,13/40,Demonstration-summary,W=100,Pr|GS|30.95.|GS|5onaverage.W=10000（BlindPick）,|GS|1onaverage.|GS|isrobustw.r.t.noise.Thecrudemodelhelpstofindsomegoodenoughdesigns,andsavesthecomputingbudgetbyoneorderofmagnitude（from200to12）.,14/40,Problemtype,Foragiveng,k,noiselevel,andproblemtype,thevalueofscanbecalculatedusingatableinLauHo1997,s.t.Pr|GS|k0.95.,15/40,OOSummary,Step1:

randomsampleNdesignsfromQStep2:

userdefinesgandk.Step3:

evaluatethedesignsusingacrudemodelStep4:

estimatethenoiselevelandproblemtypeStep5:

calculatethevalueofss.t.Pr|GS|k0.95.Step6:

selecttheobservedtop-sdesignsStep7:

OOtheoryensuresthereareatleastktrulygoodenoughdesignsinSwithhighprobability.Usuallysavesthecomputingbudgetbyatleastoneorderofmagnitude.Usefultofastscreenoutsomegoodenoughdesigns,andeasilycombinedwithotheroptimizationmethods.,16/40,Selectionrules,BlindPickHorseRaceMotivatedbysportsgamesPair-wiseeliminationasinU.S.TennisOpenRoundRobinasinNBAseasongames,Round1:

q1vs.q2,q3vs.q4Round2:

q1vs.q3,q2vs.q4Round3:

q1vs.q4,q2vs.q3,17/40,Selectionrules-continued,OptimalComputingBudgetAllocation（OCBA）:

nottowasteonbaddesigns.distinguishthetrulybestfromtherestdesigns.Breadthvs.Depth:

automaticbalancebetweenexplorationandexploitation,18/40,Comparison,Question:

WhichselectionruleneedstoselectthesmallestSs.t.Pr|GS|k0.95?

TheoreticalstudyandabundantexperimentsWefindeasywaystopredictagoodselectionrulewhentheproblemisgiven.Alsosomepropertiesofgoodselectionrules.Somequickanddirtyrules:

HorseRaceisingeneralagoodselectionrule.,19/40,ConstrainedOrdinalOptimization,Simulation-basedconstraints:

EJi（q）0,Manyinfeasibledesigns,G,S,Q,Estimatedfeasibledesigns,Lessinfeasibledesigns,G,S,DirectlyapplyOO,ConstrainedOO,20/40,COO-continued,Basicidea:

Useafeasibilitymodeltoscreenoutthefeasibledesignsfirst,withasmallprobabilitytomakemistakes.ThenapplyOOinthesetofestimatedfeasibledesigns.RequiresasmallerselectedsetthandirectlyapplyingOOwithoutafeasibilitymodel.Thesizeoftheselectedsetalsodependsontheaccuracyofthefeasibilitymodel.FormulawerealsoobtainedGuan,Song,Ho,Zhao2006.,21/40,VectorOrdinalOptimization,Multi-objectivesimulation-basedoptimizationWhatistheorderamongdesigns?

Theconceptoflayers,3rdLayer,1stLayer:

ParetoFrontierDesignswithinthesamelayerareincomparable.Designswithasmallerlayerindexarebetter.Goodenoughset:

designsinthefirstnlayers.Selectedset:

designsintheobservedfirstnlayers.,22/40,Problemtype,Hard,Neutral,Easy,Trueperformance,#ofdesignsineachlayer,#ofdesignsinthefirstxlayers,23/40,VOO-continued,Therelationshipbetweeng,s,k,noiselevel,andproblemtypehasalsobeentabularizedZhao,Ho,Jia2005.,24/40,AircraftEngine,Life-criticalparts,expensive,failure,teardowntorepair.,25/40,RemanufacturingSystem,Parameterstooptimize:

Eachseason,#ofmachinesintheworkshopand#ofpartstoorderintheinventory.Objectivefunction:

maintenancecost（machinecost,inventoryholdingcost,costoforderingnewparts）Constraint:

PrTurnAroundTime（TAT）i.e.,departuretimearrivaltimeT0P0,26/40,Trueperformances,Feasibledesigns,Infeasibledesigns,InefficientifdirectlyapplyOO.,27/40,ApplicationofCOO,RandomlysampleN=1000designs.Timeconsumingperformanceevaluation:

30minuteseach,500hoursintotal.Crudemodel:

singlereplication,1.8secondeach,30minutesintotal.Afeasibilitymodelbasedonroughsettheory,withaccuracy98.5%Song,Guan,Zhao,Ho2005.Screenoutfeasibledesignswithsmallmistakes.ThenapplyOOtofindsomefeasibleandtrulygoodenough（top-5%）designs.,ByreducingfromN=1000to|S|,COOsavesthecomputingbudgetbyatleast25folds.,28/40,ApplicationofVOO,Motivation:

ItisnotclearwhatistheappropriatevalueofP0intheconstraintsPrTATT0P0.ObjectivefunctionsJ1:

PrTATT0J2:

maintenancecostRandomlysampleN=1000designs.G:

designsinthefirsttwolayers.S:

observedtop-slayers,sgivenbyVOOtheory,s.t.Pr|GS|k0.95.,29/40,TruePerformances,Thereare14designsinthetruefirsttwolayers.,30/40,ApplicationofVOO-continued,Formostk,VOOreducesthecomputingbudgetfromN=1000tolessthan100.,31/40,TheWitsenhausenProblem,Two-stagedecisionmakingproblemWitsenhausen1968Stage1（DM1）:

initialstatex,controlu1=g1（x）,newstatex1=x+u1Stage2（DM2）:

observey=x1+v,controlu2=g2（y）,stopsatx2=x1+u2.Costfunction:

J（g1,g2）=Ek2（u1）2+（x2）2Find（g1,g2）tominimizeJ（g1,g2）Benchmark:

xN（0,s2）,vN（0,1）,s=5,k=0.2,32/40,Difficulty,ThegloballyoptimalcontrollawforsuchasimpleLQGproblemisstillunknownafternear40years.Majordifficulty:

informationstructureindecentralizedcontrolTradeoff:

costlycontrolwithperfectinformationvs.freecontrolwithnoisyobservationDiscreteversionoftheproblemisNP-completePapadimitriouandTsitsiklis1986.Best-so-farnumericalsolutionLeeetal.2001.（slightlyimprovedbyN.LiandJ.S.Shammain2007,reducedby0.17%）,33/40,Milestone1Witsenhausen1968,Letf（x）=x+g1（x）,g（y）=g2（y）,J（f,g）=Ek2（f（x）-x）2+（f（x）-g（f（x）+v）2.Stage1cost:

Ek2（f（x）-x）2Stage2cost:

E（f（x）-g（f（x）+v）2Optimallinearcontrol:

f（x）=lx,g（y）=my,l=m=0.5（1+（1-4k2）0.5）,Jlinear*=1-k2=0.96BetternonlinearcontrolfW（x）=ssgn（x）,gW（y）=stanh（sy）,JW=0.4042Givenf*（x）,gf*=Ef（x）f（y-f（x）/Ef（y-f（x）.Findtheoptimalf*（x）,34/40,Milestone2Banal&Basar1987,Theconceptofsignaling:

DM1cancels/enhancespartsofthestatex,sothatx1concentratesonagivennegative/positivevalue.DM2ascertainsthesignofx1withhighprobability,cancelsalmostallx1,makesx20.BanalandBasaroptimizedtheone-stepfunction:

fBB（x）=sgn（x）s（2/p）0.5,JBB=0.3634.,35/40,Milestone3Deng&Ho1999,Simulation-basedcrudemodelofgf*:

gfRandomsampledifferenttypesoff（x）.UseOOtocomparewhichtypehasahighprobabilitytocontainmoregoodenoughf（x）s.Identifyseveralpropertiesofagoodf（x）.,JDH=0.1901,47%betterthanJBB.,36/40,Milestone4Leeetal.2001,FurtherexplorethestepfunctionideaAcrudemodelofgf*basedonnumericalintegration,fasterandmoreaccuratethanMonteCarlosamplinginDeng&Ho1999,JLLH=0.1673thebest-so-farsolution.（furtherreducedto0.1670byLiandShammain2007,0.17%）,37/40,Pursuitofgoodandsimplesolutions,Eachmilestonefisbetterthanbefore,butalsobecomemoreandmorecomplicated.fLLHisa27-stepfunction.Canwefindgoodandsimplef?

Kolmogorovcomplexitymeasuressimplicity,butingeneralincomputableLi&Vitnyi1997.Jiaetal.2006ConstructacrudemodeltoestimatetheKCUseOOtofindgoodandsimplesolutions,38/40,Withminorperformancedegradation（5%,w.r.t.fLLH）,fsgsavesthememoryspacebyover30folds.,39/40,Conclusion,Simulation-basedoptimizationTime-consumingsimulation-basedperformanceevaluationOrdinalOptimizationOrdinalcomparisonGoalsofteningUseacrudemodeltoscreenoutgoodenoughdesigns,savesthecomputingbudgetHorseraceisingeneralagoodselection