2024年4月5日发(作者：游戏手柄哪个牌子的好)

284IEEETRANSACTIONSONEVOLUTIONARYCOMPUTATION,VOL.13,NO.2,APRIL2009

MultiobjectiveOptimizationProblemsWith

ComplicatedParetoSets,MOEA/DandNSGA-II

HuiLiandQingfuZhang,SeniorMember,IEEE

Abstract—Partlyduetolackoftestproblems,theimpactof

theParetoset(PS)shapesontheperformanceofevolutionary

perin-

troducesageneralclassofcontinuousmultiobjectiveoptimization

testinstanceswitharbitraryprescribedPSshapes,whichcould

beusedforstudyingtheabilityofmultiobjectiveevolutionary

pro-

posesanewversionofMOEA/Dbasedondifferentialevolution

(DE),i.e.,MOEA/D-DE,andcomparestheproposedalgorithm

withNSGA-IIwiththesamereproductionoperatorsonthetest

erimentalresults

indicatethatMOEA/DcouldsignificantlyoutperformNSGA-II

eststhatdecompositionbasedmul-

tiobjectiveevolutionaryalgorithmsareverypromisingindealing

withcomplicatedPSshapes.

IndexTerms—Aggregation,decomposition,differentialevolu-

tion,evolutionaryalgorithms,multiobjectiveoptimization,Pareto

optimality,testproblems.

I.I

NTRODUCTION

A

multiobjectiveoptimizationproblem(MOP)canbestated

asfollows:

minimize

subjectto(1)

istheobjectivewhereisthedecision(variable)space,

consistsofreal-valuedobjectivespace,and

losedandconnectedregionin

objectivesarecontinuousof,wecallproblem(1)acontinuous

MOP.

,betwoLet

forall,vectors,issaidtodominateif

1

iscalled(globally)Paretooptimal

ifthereisno

,iscalledtheofalltheParetooptimalpoints,denotedby

ofalltheParetoobjectivevectors,

,iscalledtheParetofront[1].

ManuscriptreceivedOctober18,2007;revisedJanuary28,ub-

lishedSeptember26,2008;currentversionpublishedApril01,2009.

iththeDepartmentofComputingandElectronicSystems,Uni-

versityofEssex,ColchesterCO43SQ,wwiththeSchoolofCom-

puterScience,UniversityofNottingham,NottinghamNG81BB,U.K.(e-mail:

hzl@).

swiththeDepartmentofComputingandElectronicSystems,Uni-

versityofEssex,ColchesterCO43SQ,U.K.(e-mail:qzhang@).

DigitalObjectIdentifier10.1109/TEVC.2008.925798

1

Thisdefiinequalitiesshould

Undercertainsmoothnessassumptions,itcanbeinduced

fromtheKarush–Kuhn–TuckerconditionthatthePSofa

-di-

continuousMOPdefinesapiecewisecontinuous

mensionalmanifoldinthedecisionspace[1],[2].Therefore,

thePSofacontinuousbi-objectiveoptimizationproblemisa

whilethePSofacontin-

piecewisecontinuous1-Dcurvein

uousMOPwiththreeobjectivesisapiecewisecontinuous2-D

theso-calledregularitypropertyofcontinuous

MOPs.

Recentyearshavewitnessedsignificantprogressinthede-

velopmentofevolutionaryalgorithms(EAs)formultiobjective

optimizationproblems[3]–[16].Multiobjectiveevolutionary

algorithms(MOEAs)aimatfindingasetofrepresentative

gelytothe

natureofMOEAs,theirbehaviorsandperformancesaremainly

uousmultiobjectivetestprob-

lemsaremostwidelyusedforthispurposesincetheyareeasy

eenwell-understood(as

reviewedin[17])thatthegeometricalshapesofthePF,among

othercharacteristicsofanMOP,couldaffecttheperformanceof

,arangeofPFshapessuchasconvex,concave,

andmixedPFscanbefoundincommonlyusedcontinuous

testproblems[18]–[21],whichcanbeusedforstudyinghow

r,thePS

shapesofmostexistingtestproblemsareoftenstrikingly

mple,thePSsoftheZDTtestinstances[19]

withtwoobjectivesarepartofalinesegmentdefinedby

andthePSsoftheDTLZtestinstances[20]withthreeobjectives

aresubsetsof

Thereisnoreasonthatrealworldproblemshavesuchsimple

PSs.

2

ObservingtheseoversimplifiedPSsintheexistingtestin-

stances,Okabeetal.firstarguedthenecessityofconstructing

testinstanceswithcomplicatedPSsandprovidedamethodfor

controllingPSshapes[24].Theyhaveconstructedseveraltest

r,theirtestinstances

cently,

Hubandetal.[17]andDebetal.[25]emphasizedthatvariable

,parameterdependencies)shouldbeconsideredin

constructingtestinstancesandproposedusingvariabletrans-

lelinkages

r,thePSshapesinthe

exampleswithcomplicatedPSshapescanbefoundinavehicledy-

namicdesignproblemin[22]andapowerplantdesignoptimizationin[23].

2

Two

bereversedifthegoalistomaximizetheobjectivesin(1).“Dominate”means

“bebetterthan.”

1089-778X/$25.00©2008IEEE

Authorized licensed use limited to: UNIVERSITY OF ESSEX. Downloaded on May 6, 2009 at 06:50 from IEEE Xplore. Restrictions apply.

LIANDZHANG:MULTIOBJECTIVEOPTIMIZATIONPROBLEMSWITHCOMPLICATEDPARETOSETS,MOEA/DANDNSGA-II285

testinstancesconstructedin[17]and[25]arenoteasytobedi-

er,variablelinkagesand

ly,PSshapes

arenotafocusin[17]and[25].Itispossiblethatacontinuous

MOPwithcomplicatedvariablelinkageshasaverysimplePS.

Partiallyduetolackoftestproblems,theinfluenceofPSshapes

overtheperformanceofMOEAshasattractedlittleattentionin

theevolutionarycomputationcommunity.

Inspiredbythestrategiesforconstructingtestproblems

in[24],[25],wehaverecentlyproposedseveralcontinuous

testinstanceswithvariablelinkages/complicatedPSs[26],in

estin-

stanceshavealsobeenmodifiedandusedin[27]forcomparing

erimental

resultsindicatethatcomplicatedPSshapescouldcausediffi-

r,thePSsofthesetestinstancesare

eitherlinearorquadratic,whicharenotcomplicatedenoughfor

hemajorpurposes

inthispaperistoproposeageneralclassofcontinuoustest

problemswitharbitraryprescribedPSshapesforfacilitating

thestudyoftheabilityofMOEAstodealwiththecomplication

ofPSs.

ThemajorityofexistingMOEAsarebasedonParetodomi-

nance[4]–[6],[8],[9],[11],[12].Inthesealgorithms,theutility

ofeachindividualsolutionismainlydeterminedbyitsPareto

dominancerelationswithothersolutionsvisitedintheprevious

singParetodominancealonecoulddiscourage

thediversityofsearch,sometechniquessuchasfitnesssharing

andcrowdinghaveoftenbeenusedascompensationinthese

MOEAs[5],[9],[11],[28].Arguably,NSGA-II[11]isoneof

r-

acteristicfeatureofNSGA-IIisitsfastnondominatedsorting

procedureforrankingsolutionsinitsselection.

AParetooptimalsolutiontoanMOPcouldbeanoptimalso-

lutionofasingleobjectiveoptimizationprobleminwhichthe

objectiveisanaggregationfunctionofalltheindividualobjec-

ore,approximationofthePFcanbedecomposed

intoanumberofsingleobjectiveoptimizationsubproblems.

Thisisabasicideabehindmanytraditionalmathematicalpro-

grammingmethodsforapproximatingthePF[1].Anumberof

MOEAsadoptthisideafortheirfitnessassignmenttosomeex-

tent[29]–[41].MOGLS[29],[32]optimizesanaggregationof

theobjectiveswithrandomlyselectedaggregationcoefficients

ateachstage,whichmakesitveryeasy,atleastinprinciple,to

usesingleobjectivelocalsearchforimprovingindividualsolu-

sesanumberofscalaraggregationfunctionsto

guideitssearchandhasdemonstrateditsadvantagefortackling

MOPswithmanyobjectives[33],[37],[39].Byusingaggrega-

tionsoftheobjectives,adecisionmaker’spreferencehasbeen

incorporatedintoMOEAsin[41].

MOEA/,ag-

gregations)[34].MOEA/Dsimultaneouslyoptimizesanumber

ectivein

eachoftheseproblemsisanaggregationofalltheobjectives.

Neighborhoodrelationsamongthesesubproblemsaredefined

basedonthedistancesbetweentheiraggregationcoefficient

,scalaraggregationfunction)is

optimizedinMOEA/Dbyusinginformationmainlyfromits

neighboringsubproblems.

WebelievethatcomparisonstudiesbetweenMOEAsbased

,ag-

gregation)ontestproblemswithvariouscharacteristicscould

beveryusefulforunderstandingstrengthsandweaknessesof

thesedifferentmethodologiesandthusidentifyingimportantis-

orcontri-

butionsofthispaperincludethefollowing.

•Ageneralclassofmultiobjectivecontinuoustestinstances

witharbitraryprescribedPSshapeshavebeenproposed.

•AnewimplementationofMOEA/DwithaDEoperator

andpolynomialmutationhasbeensuggested,inwhichtwo

extrameasureshavebeenintroducedformaintainingthe

populationdiversity.

•ExperimentshavebeenconductedtocompareMOEA/D

andNSGA-IIwiththesameDEandmutationoperatoron

thetestinstancesintroducedinthispaper.

nII

introducesaclassofcontinuousmultiobjectiveoptimizationtest

instanceswithcomplicatedPSshapesandprovidesatheorem

nIIIproposesMOEA/D-DE,anew

implementationofMOEA/DwithaDEoperatorandpolyno-

mialmutation,anddescribesNSGA-II-DE,animplementation

ments

nVconcludesthe

paper.

II.M

ULTIOBJECTIVE

T

EST

P

ROBLEM

W

ITH

P

RESCRIBED

P

ARETO

S

ET

Inourproposedgenericcontinuoustestproblem,thedecision

spaceis

(2)

where

forall

objectivestobeminimizedtakethefollowingform:

.

.

.

(3)

,and

aretwosubvectorsof;

•arefunctionsfromto;

arefunctionsfromto;•

•isafunctionfromto

ThefollowingtheoremisaboutthePSandPFofthegeneric

testproblem.

Theorem1:Supposethat

forallifandonlyif.[i]

[ii]ThePSofthefollowing-objectiveoptimization

problem:

minimize

subjectto

is.

(4)

where

•

.Its

Authorized licensed use limited to: UNIVERSITY OF ESSEX. Downloaded on May 6, 2009 at 06:50 from IEEE Xplore. Restrictions apply.