A-Grid-Based-Evolutionary-Algorithm-for-Many-Objec

IEEETRANSACTIONSONEVOLUTIONARYCOMPUTATION,VOL.17,NO.5,OCTOBER2013721AGrid-BasedEvolutionaryAlgorithmforMany-ObjectiveOptimizationShengxiangYang,Member,IEEE,MiqingLi,XiaohuiLiu,andJinhuaZhengAbstract—Balancingconvergenceanddiversityplaysakeyroleinevolutionarymultiobjectiveoptimization(EMO).MostcurrentEMOalgorithmsperformwellonproblemswithtwoorthreeobjectives,butencounterdifficultiesintheirscalabilitytomany-objectiveoptimization.Thispaperproposesagrid-basedevolutionaryalgorithm(GrEA)tosolvemany-objectiveoptimizationproblems.Ouraimistoexploitthepotentialofthegrid-basedapproachtostrengthentheselectionpressuretowardtheoptimaldirectionwhilemaintaininganextensiveanduniformdistributionamongsolutions.Tothisend,twoconcepts—griddominanceandgriddifference—areintroducedtodeterminethemutualrelationshipofindividualsinagridenvironment.Threegrid-basedcriteria,i.e.,gridranking,gridcrowdingdistance,andgridcoordinatepointdistance,areincorporatedintothefitnessofindividualstodistinguishtheminboththematingandenvironmentalselectionprocesses.Moreover,afitnessadjustmentstrategyisdevelopedbyadaptivelypunishingindividualsbasedontheneighborhoodandgriddominancerelationsinordertoavoidpartialovercrowdingaswellasguidethesearchtowarddifferentdirectionsinthearchive.Sixstate-of-the-artEMOalgorithmsareselectedasthepeeralgorithmstovalidateGrEA.Aseriesofextensiveexperimentsisconductedon52instancesofninetestproblemstakenfromthreetestsuites.TheexperimentalresultsshowtheeffectivenessandcompetitivenessoftheproposedGrEAinbalancingconvergenceanddiversity.ThesolutionsetobtainedbyGrEAcanachieveabettercoverageoftheParetofrontthanthatobtainedbyotheralgorithmsonmostofthetestedproblems.Additionally,aparametricstudyrevealsinterestinginsightsofthedivisionparameterinagridandalsoindicatesusefulvaluesforproblemswithdifferentcharacteristics.IndexTerms—Convergence,diversity,evolutionarymultiobjec-tiveoptimization(EMO),grid,many-objectiveoptimization.ManuscriptreceivedFebruary27,2012;revisedAugust4,2012;acceptedOctober11,2012.DateofpublicationJanuary1,2013;dateofcurrentversionSeptember27,2013.ThisworkwassupportedinpartbytheEngineeringandPhysicalSciencesResearchCouncilofU.K.,underGrantEP/K001310/1,andtheNationalNaturalScienceFoundationofChinaunderGrant61070088.S.YangiswiththeSchoolofComputerScienceandInformatics,DeMontfortUniversity,LeicesterLE19BH,U.K.(e-mail:[e-mail]).M.LiandX.LiuarewiththeDepartmentofInformationSystemsandComputing,BrunelUniversity,Uxbridge,MiddlesexUB83PH,U.K.(e-mail:[e-mail];[e-mail]).J.ZhengiswiththeCollegeofInformationEngineering,XiangtanUniver-sity,Xiangtan411105,China(e-mail:[e-mail]).Thispaperhassupplementarydownloadablematerialavailableatfiguresinthispaperareavailableonlineat(MOP).Duetotheconflictingnatureofobjectives,thereisusuallynosingleoptimalsolutionbutratherasetofalternativesolutions,calledtheParetoset,forMOPs.Evolutionaryalgorithms(EAs)havebeenrecognizedtobewellsuitedforMOPsduetotheirpopulation-basedpropertyofachievinganapproxima-tionoftheParetosetinasinglerun.Overthepastfewdecades,anumberofstate-of-the-artevolutionarymultiob-jectiveoptimization(EMO)algorithmshavebeenproposed.Generallyspeaking,thesealgorithmssharetwocommonbutoftenconflictinggoals—minimizingthedistanceofsolutionstotheoptimalfront(i.e.,convergence)andmaximizingthedistributionofsolutionsovertheoptimalfront(i.e.,diversity).Amany-objectiveoptimizationproblemusuallyreferstoanoptimizationproblemwithmorethanthreeobjectives.Itappearswidelyinindustrialandengineeringdesign,suchaswaterresourceengineering[38],industrialschedulingproblems[64],controlsystemdesign[19],[23],moleculardesign[44],andsoon[18],[31],[36].Inrecentyears,many-objectiveoptimizationhasbeengainingattentionintheEMOcommunity[60],[63].Somerelatedtechniqueshavebeendevelopedrapidlyinthedomain,includingtestfunctionsscalabletoanynumberofconflictingobjectives[16],[24],[25],[61],performanceassessmentmetricssuitableforahigh-dimensionalspace[14],[34],andvisualizationtoolsdesignedforthedisplayofsolutionswithfourormoreobjectives[33],[43],[55],[67].Thesehavemadeitpossibletodeeplyinvestigatetheperformanceofalgorithmsonmany-objectiveproblems.Asaconsequence,variousexperimental[9],[21],[32]andanalytical[8],[62],[65]studieshavebeenpresentedandsomenewobservationsandconclusionshavebeenmadeinthemany-objectiveoptimizationlandscape[18],[42],[56].Balancingconvergenceanddiversityisnotaneasytaskinmany-objectiveoptimization.MostclassicalPareto-