GP-SAEA量子算法进展

GaussianProcessAssistedData-DrivenOptimization:HandlingConstrained,Multi-objectiveandHigh-dimensionalProblemsProfessorYaochuJin,IEEEFellowDepartmentofComputerScience,UniversityofSurrey,Guildford,[e-mail]–MainSteps1.Choosesomepriormeasureoverthespaceofpossibleobjectivesf[Offlinetrainingdata]2.Combinepriorandthelikelihoodtogetaposteriormeasureovertheobjectivegivensomeobservations[Predicttheobjectivevalueofsomecandidatesolutions]3.Usetheposteriortodeterminewheretotakethenextevaluationaccordingtosomeacquisition/lossfunction[Surrogatemanagement/infillsamplingcriterion]4.Augmentthedata[Sampletheselectednewdata]5.Iteratebetween2and4untiltheevaluationbudgetisexhausted.Iteration3Iteration4B.Bischl,J.Richter,J.Bossek,D.Horn,J.Thomas,M.Lang.mlrMBO:Amodularframeworkformodel-basedoptimizationofexpensiveblack-boxfunctions.•OfflinesamplingUniformlyselectedrandomlocationsLatinhypercubedesignHaltonsequencesDeterminantalpointprocesses•OptimizationofhyperparametersSQPEvolutionaryalgorithms…InfillSamplingCriterion/AcquisitionFunction•PopularinfillcriteriaLowerconfidencebound(LCB)f=(x)-(x)(0)ProbabilityofImprovement(PI)ExpectedImprovement(EI)ThompsonsamplingEntropysearch•BalancebetweenexploitationandexplorationM.Emmerich,K.C.Giannakoglou,B.Naujoks,Single-andmultiobjectiveevolutionaryoptimizationassistedbyGaussianrandomfieldmetamodels.IEEETransactionsonEvolutionaryComputation,10(4):421–439(2006)B.Shahriari,K.Swersky,Z.Wang,R.P.AdamsandN.deFreitas.Takingthehumanoutoftheloop:AreviewofBayesianoptimization.ProceedingsoftheIEEE,104(1):148-175,2016GP-AssistedEvolutionaryOptimization•Infillcriteriondrivensurrogate-assistedevolutionaryalgorithmshavebeenpopularandsuccessfulinsolvinglow-dimensional(lowerthan15)unconstrainedoptimizationproblems•Challenges:ConstrainedproblemsHigh-dimensionalproblemsMulti-objectiveoptimizationproblemsHandlingConstraintsR.Jiao,S.Zeng,C.Li,Y.Jiang,Y.Jin.Acompleteconstrainedexpectedimprovementforexpensiveoptimizationwithindependentobjectiveandconstraint.InformationSciences(underreview)InfillCriteriaforConstrainedOptimization•Penalizedexpectedimprovement(Schonlau,1998)•Forhighlyconstrainedproblems,orforlargenumberofconstraints,theabovecriterionmayfailtoworkwhennofeasiblesolutionhasevenbeenobserved•AvarianthasbeenproposedthatmaximizestheprobabilityoffeasibilitybeforeanyfeasiblesolutionsarefoundandthenswitchestopenalizedexpectedimprovementAnImprovedInfillCriterionforConstrainedOptimization•Ifnofeasiblesolutionhasbeenfound,theacquisitionfunctionwillbethemaximizationoftheexpectedimprovementofconstraintviolation:whereisthecurrentminimumconstraintviolation•Ifatleastonefeasiblesolutionhasbeenfound,penalizedexpectedimprovementisthenusedEmpiricalEvaluationsHandlingMultiple(Many)ObjectivesT.Chugh,Y.Jin,K.Miettinen,J.Hakanen,andK.Sindhya.Asurrogate-assistedreferencevectorguidedevolutionaryalgorithmforcomputationallyexpensivemany-objectiveoptimization.IEEETransactionsonEvolutionaryComputation,21(1):129-142,2018MainApproachestoCandidateSelectionHorn,D.,Wagner,T.,Biermann,D.,Weihs,C.,andBischl,B.(2015).Model-basedmulti-objectiveoptimization:Taxonomy,multi-pointproposal,toolboxandbenchmark.InEvolutionaryMulti-CriterionOptimization,LNCS9018,pages64–78AReferenceVectorGuidedEvolutionaryAlgorithm(RVEA)•ComponentsofRVEA-Referencevectorgeneration-Assignmentofindividualstoreferencevectors-Selectionmechanism-Adaptationofreferencevectors•Referencevectorgeneration–Uniformlydistributedsetofreferencepointsona–ProjectingpointstohyperspheretogetunitvectorsR.Cheng,Y.Jin,M.Olhofer,andB.Sendhoff.Areferencevectorguidedevolutionaryalgorithmformanyobjectiveoptimization,IEEETransactionsonEvolutionaryComputation,20,773-791,2016RVEA•Assignmentofindividuals-Translatetheobjectivefunctions-Initialpointiscoordinateorigin-Referencevectorsareinfirstquadrant•Selectionmechanism–Twomaingoals:Improvementanddiversity–Anglepenalizeddistance(APD)tobalancebetweenconvergenceanddiversity•AdaptationofthereferencevectorsSelectionCriteria•Improvementcriterion:thedistancefromeachsolutiontotheidealpoint•Diversitycriterion:theangelbetweeneachsolutionandtheclosestreferencevector•Challenge:howtocombinethetwocriteriatogether?•adaptiontogenerations•anglenormalizationThisselectioncriterionfocusesontheimprovementintheearlysearchstageandthenonthediversityofthesolutionsinthelaterstageSelectionCriteria:Angle-PenalizedDistance(APD)•Surrogate:Krigingthatprovidespredictionanduncertainty•Modelmanagementanddatamanagement–Modelmanagement:APDanduncertaintyfromKriging–WhenconvergenceisprioritisedselectingmoreaccurateindividualsaccordingtoAPD(selectioncriterioninRVEA)–Incasediversityisprioritised,selectingmoreuncertainindividualstoexplore–Trainingdatamanagement–BasedondistributionofreferencevectorKriging-AssistedRVEA(K-RVEA)DiversityManagementinK-RVEAScenariooffixedreferencevectorsduringthepreviousupdateCase1:Scenariooffixedreferencevectorsduringthecurrentupdate,numberofinactive𝑉�