Gary-G.-Yen教授的报告：多目标粒子群算法

MANY-OBJECTIVEPARTICLESWARMOPTIMIZATIONBASEDONPARALLELCELLCOORDINATESYSTEMGaryG.Yen,Ph.D.,FIEEE,FIETProfessor,OklahomaStateUniversityPastPresident,IEEEComputationalIntelligenceSocietyFoundingEditor-in-Chief,IEEEComputationalIntelligenceMagazine

PaperSubmissionDeadline:December20,2013July24-29,2016MultiobjectiveOptimization

OptimizationproblemsinvolvemorethanoneobjectivefunctionVerycommon,yetdifficultproblemsinthefieldofscience,engineering,andbusinessmanagementNonconflictingobjectives:achieveasingleoptimalsolution satisfiesallobjectivessimultaneouslySOPsCompetingobjectives:cannotbeoptimizedsimultaneouslyMOP–searchforasetof“acceptable”–maybeonlysuboptimalforoneobjective–solutionsisourgoalInoperationresearch/managementterms–multiplecriteriondecisionmaking(MCDM)WhyMOP?BuyinganAutomobileObjective=reducecost,whilemaximizecomfortWhichsolution(1,A,B,C,2)isbest???NosolutionfromthissetmakesbothobjectiveslookbetterthananyothersolutionfromthesetNosingleoptimalsolutionTradeoffbetweenconflictingobjectives-costandcomfortMathematicalDefinitionMathematicalmodeltoformulatetheoptimizationproblem

DesignVariables:decisionandobjectivevectorConstraints:equalityandinequalityGreater-than-equal-toinequalityconstraintcanbeconvertedtoless-than-equal-toconstraintbymultiplying-1ObjectiveFunction:maximizationcanbeconvertedtominimizationduetothedualityprincipleObjectivevectorsDecisionvectorsEqualityconstraintsInequalityconstraintsVariableboundsEnvironmentstatesParetoOptimalityFormalDefinition:theminimizationofthencomponents

ofavectorfunctionfofavectorvariablexinauniverse,whereThenadecisionvectorissaidtobePareto-optimalifand onlyifthereisnoforwhich dominates,thatis,thereisnosuchthatNondominatedset(Paretofront)f1f2objectivespaceABCParetoOptimalSet–thesetofallPareto-optimaldecisionvectors,whichyieldsasetofnondominatedsolutionsNon-dominatedSet–correspondingobjectivevectorset-ParetoFrontx2x1ParetooptimalsetABCdecisionspaceDZDTTestSuiteAnunorthodox,stochastic,andpopulationbasedparallelsearchingheuristicsmaybemoresuitableforMOPsClassificationofEA’s–GeneticAlgorithm;GeneticProgramming;EvolutionaryProgramming;EvolutionaryStrategy;AntColony;ArtificialImmuneSystem;ParticleSwarmOptimization;DifferentialEvolution;MemeticAlgorithmWhyPopulation-BasedHeuristics?abilityofhandlingcomplexproblemswithdiscontinuities,multimodality,disjointfeasiblespacesanddynamismResearchIssuesforMOPsModifyingthefitnessassignmentEnhancingtheconvergencePreservingthediversityManagingthepopulationConstraintsanduncertaintyhandlingProgressionsofdevelopmentinEMOcommunity-

fromevolutionary&nature-inspiredcomputationalmetaphors,

tosolvingsingle-objective

optimizationproblems,

tosolvingconstrained

optimizationproblems,

tosolvingdynamic

optimizationproblems,

tosolvingmulti-objectiveoptimizationproblems,

andtosolvingnowMany-ObjectiveOptimizationProblems.Multi-ObjectiveOptimizationProblems(MOPs)withalargenumberofobjectives(ingeneraloverfive)arereferredtoasMaOPs.

ProgressioninEMODevelopmentsWhenencounterproblemswithmanyobjectives(morethanfive),nearlyallalgorithmsperformspoorlybecauseoflossofselectionpressureinfitnessevaluationsolelybaseduponParetodomination.Withtheincreasingnumberofobjectives,thereareafewchallengestobeaddressed:IneffectivedefinitioninthePareto-dominancedeterioratestheconvergenceabilityofMOEAsAnexponentiallylargenumberofsolutionsarerequiredtoapproximatethewholeParetofrontInbalanceofcomputationalcomplexityandqualityofthesolutionfoundVisualizationofalarge-dimensionalfrontisreallydifficultMetricstoquantifytheperformanceofthedesignsResearchIssuesforMaOPsObjectiveReductionNon-Pareto-BasedTechniquesIncorporationofPreferenceInformationGradientInformationModificationsofMOEAsforMaOPsParetoDominationRevisionsDominanceAreaControl,ɛ-Dominance,k-Optimality,GridDominance,Fuzzy-basedParetoDominanceFD-NSGA-II,FD-SPEA2(He&Yen,TEVC,2013)DecompositionMethodsMOEA/D(Zhang&Li,TEVC,2007);NSGA-III(Deb&Jain,TEVC,2013)GridBasedApproachesTDEA(Pierroetal.,TEVC,2007);e-MOEA(Debetal.,EvolComput,2005);GrEA(Yangetal.,TEVC,2013)IndicatorBasedMethodsSMS-EMOA(Beumeetal.,EJOperResearch;2007)HypE(Bader&Zitzler,EvolComput.,2011)State-of-the-ArtMaOEAsInPSOside…Meta-heuristicallyinspiredbythesocialbehaviorofbirdflockingorfishschooling,therelativesimplicityandthesuccessasasingle-objectiveoptimizerhavemotivatedresearcherstoextendPSOfromSOPstoMOPs.However,apartfromthecommonissueinMOEAstomaintainanarchive,therearetwoparticularissuesinMOPSO:ManagingconvergenceanddiversityfastconvergenceofPSOincursarapidlossofdiversityduringtheevolutionaryprocessSelectingglobalbest(gBest)andpersonalbest(pBest)thereisnoabsolutebestsolutionbutratherasetofnon-dominatedsolutions.ManymechanismswereproposedintheexistingMOPSOsintermofleaderselection,archivemaintenance,andperturbationtotackletheseissues.However,fewMOPSOsaredesignedtodynamicallyadjustthebalanceinexplorationandexploitationaccordingtothefeedbackinformationthroughinteractingtheevolutionaryenvironment.ThechallengesinMOPSOformanagingtheconvergenceanddiversity:updatingarchiveselectinggBestandpBestSelf-adaptingflightparametersperturbingstagnationMotivationsAmechanism(differentfromgrid-basedapproaches)for:assessingdiversitytoselectglobalbestforaparticleandupdatearchiveevaluatingtheevolutionaryenvironmenttodynamicallyadjusttheevolutionarystrategiesParallelcoordinates

isa

popularwayofvisualizing

high-dimensionalgeometry

andanalyzingmultivariate

data.Transformamulti-objective

spaceintoa2-Dgridto

evaluatethedistribution

ofanapproximateParetofrontParallelCellCoordinateSystemMaptheindividualsinglobalarchivefromCartesianCoordinateSystemintoParallelCellCoordinateSystem(PCCS)KbyMcellsKnon-dominatedindividualsinM-objectivespaceestimatingdensitytoupdatearchiveandselectdiversitygBest(d_gBest)withminimaldensityThedistancebetweentwovectors,namedParallelCellDistance,ismeasuredbythesumofnumbersofcellsawayfromeachotherinallobjectives.ThedensityofPi,inthehyperspaceformedbythearchivecanbemeasuredbytheParallelCellDistancebetweenPiandallothermembers,Pj(j=1,2,…,K,j≠i),inthearchive.rankingnon-dominatedsolutionsinarchiveforselectingconvergencegBest(c_gBest),withminimalpotential.c_gBestThepotentialquantifiesanon-dominatedsolutionamongitscompetitorsinthearchivebycombiningtheorderrelationalongtheoptimizationdirectionandthedegreeintheunitofcellinPCCS.DetectingtheEvolutionaryEnvironmentbyEntropyAbruptchangesindicateaconvergencestatusbecauseanewsolutiondominatessomeoldsolutionsinarchiveandthepopulationmakesaprogressorbreaksthroughalocalParetofront.Mildchangesindicateadiversitystatusbecauseanewsolutionwithbetterdensityreplacesanoldsolutioninarchive.Nochangeindicatesastagnationstatus.CurvesofEntropyandΔEntropydetectedfromZDT4withmanylocalParetofronts.ProposedpccsAMOPSOUpdatingarchiveComplexity:O(ML2)M:thenumberofobjectivesL:thenumberofMembersinarchiveSelectinggBestLeaderGroupMc_gBests&Md_gBeststhetypeofcandidatesbetweenc-gBestandd-gBestisdecidedinprobabilityacandidateforaparticleisrandomlydrawnfromthechosentypeofgBestAcandidateisrandomlydrawnfromthechosentypeThethresholdisthemaximalprobablevariationofentropy.SelectingpBestfrompArchivepArchivewithaquarterboundedsizeofgArchivetodecreasethecostofpArchivemaintenancepBestisselectedaccordingtotheminimalhyperbox:Self-AdaptivePSOflight-Anexampleofself-adaptiveparametersobtainedbypccsAMOPSOforZDT4withmanylocalParetofrontsPerturbingaparticletoacceleratetheconvergenceorescapefromlocalParetofrontsElitismLearningStrategy[fromZ.H.Zhan,J.Zhang,Y.Li,andH.S.Chung,“Adaptiveparticleswarmoptimization,”IEEETrans.Syst.Man,Cybern.B,Cybern.,vol.39,no.6,pp.1362-1381,Dec.2009.]RandomlyperturbadimensionofgBestPerturbationrangeisdampedbyaGaussianfunction,G(0,lr2)learningrate,lr,islinearlydecreasedfrom1.0downto0.1.TheintegratedalgorithmofpccsAMOPSOpccsAMOPSOforDTLZ2(3)ExperimentPeeralgorithmssigmaMOSPO:SigmavaluemethodbyMostaghimandTeich,2003agMOPSO:adaptivegridbyPadhye,2009cdMOPSO:crowdingdistancebyCoello,PulidoandLechuga,2004clusterMOPSO:clusteringpopulationbyMostaghimandTeich,2003pdMOPSO:ROUND+RAND+PROBbyAlvarez-Ben’itez.EversonandFieldsend,2005TestinstancesZTDseries(2-objective):fiveinstancesDTLZseries(3-objective):seveninstancesMetric:IGD&HyperVolume(HV)referencepointat11ineachobjectiveforHVHypervolume1-pccsAMOPSO2-sigmaMOPSO3-agMOPSO4-cdMOPSO5-clusterPOPSO6-pdMOPSO1-pccsAMOPSO2-sigmaMOPSO3-agMOPSO4-cdMOPSO5-clusterPOPSO6-pdMOPSOScoresofMeriton12testinstancesforHVProposedMOPSOsigmaMOPSOagMOPSOcdMOPSOclusterMOPSOpdMOPSONSGA-IISPEA2MOE