搜索
DynamicMulti-objectiveOptimizationandDecision-MakingUsingModifiedNSGA-II:ACaseStudyonHydro-thermalPowerSchedulingKalyanmoyDeb,UdayaBhaskaraRaoN.,andS.KarthikKanpurGeneticAlgorithmsLaboratory(KanGAL)IndianInstituteofTechnologyKanpur,PIN208016,Indiadeb@iitk.ac.in,uday.iitk@gmail.com,ksindhya@iitk.ac.inAbstract.Mostreal-worldoptimizationproblemsinvolveobjectives,constraints,andparameterswhichconstantlychangewithtime.Treatingsuchproblemsasastationaryoptimizationproblemdemandtheknowl-edgeofthepatternofchangeaprioriandeventhentheprocedurecanbecomputationallyexpensive.Althoughdynamicconsiderationusingevolutionaryalgorithmshasbeenmadeforsingle-objectiveoptimizationproblems,therehasbeenalukewarminterestinformulatingandsolvingdynamicmulti-objectiveoptimizationproblems.Inthispaper,wemod-ifythecommonly-usedNSGA-IIprocedureintrackinganewPareto-optimalfront,assoonasthereisachangeintheproblem.Introductionofafewrandomsolutionsorafewmutatedsolutionsareinvestigatedindetail.Theapproachesaretestedandcomparedonatestproblemandareal-worldoptimizationofahydro-thermalpowerschedulingproblem.ThissystematicstudyisabletofindaminimumfrequencyofchangeallowedinaproblemfortwodynamicEMOprocedurestoadequatelytrackPareto-optimalfrontierson-line.Basedontheseresults,thispaperalsosuggestsanautomaticdecision-makingprocedureforarrivingatadynamicsingleoptimalsolutionon-line.1IntroductionAdynamicoptimizationprobleminvolvesobjectivefunctions,constraintfunc-tionsandproblemparameterswhichcanchangewithtime.Suchproblemsoftenariseinreal-worldproblemsolving,particularlyinoptimalcontrolproblemsorproblemsrequiringanon-lineoptimization.Therearetwocomputationalproce-duresusuallyfollowed.Inoneapproach,optimalcontrollawsorrulesareevolvedbysolvinganoff-lineoptimizationproblemformedbyevaluatingasolutiononanumberofrealscenariosofthedynamicproblem[11].Thisapproachisuse-fulinproblemswhicharecomputationallytooexpensiveforanyoptimizationalgorithmtobeappliedon-line.Theotherapproachisadirectoptimizationpro-cedureon-line.Insuchacase,theproblemisconsideredstationaryforsometimeS.Obayashietal.(Eds.):EMO2007,LNCS4403,pp.803–817,2007.cSpringer-VerlagBerlinHeidelberg2007804K.Deb,U.B.N.Rao,andS.Karthikperiodandanoptimizationalgorithmbeallowedtofindoptimalornear-optimalsolution(s)withinthetimespaninwhichtheproblemremainsstationary.There-after,anewproblemisconstructedbasedonthecurrentproblemscenarioandanewoptimizationisperformedforthenewtimeperiod.Althoughthisprocedureisapproximateduetothestaticconsiderationoftheproblemduringthetimeforoptimization,effortsaremadetodevelopefficientoptimizationalgorithmswhichcantracktheoptimalsolution(s)withinasmallnumberofiterationssothattherequiredtimeperiodforfixingtheproblemissmallandtheapproximationerrorisreduced.Inthispaper,weconsidersolvingdynamicoptimizationproblemshavingmorethanoneobjectivefunctionusingthedirecton-lineoptimizationproceduredescribedabove.Althoughsingle-objectivedynamicoptimizationhasreceivedsomeattentioninthepast[2],thedynamicmulti-objectiveoptimizationisyettoreceiveasig-nificantattention.Whenamulti-objectiveoptimizationproblemchangeswithtimeinsteppedmanner,thetaskofandynamicEMOprocedureistofindortrackthePareto-optimalfrontasandwhenthereisachange.Aftertheideahasbeenputforwardearlier[6],therehasbeenalukewarminterestonthistopic[8,7].Inthispaper,wesuggesttwovariationsofNSGA-IIfortrackingdynamicPareto-optimalfrontiers.Theeffectoffrequencyofchangeinaprob-lemandtheproportionofaddedrandomormutatedsolutionsareparameterswhicharesystematicallystudiedtoevaluatethedevelopedproceduresfortheirtrackingefficiency.TheproposedNSGA-IIproceduresareappliedtoacomplexhydro-thermalpowerschedulingprobleminvolvingtwoconflictingobjectives.Thechangeinproblemappearsduetoachangeindemandinpowerwithtime.TheefficacyofmodifiedNSGA-IIproceduresisillustratedbyfindingthesmall-estfrequencyofchangewhichcanbeallowedbeforetheEMOprocedurescantracktheoptimalfrontwithasignificantconfidence.Finally,adecision-makingaidiscoupledwiththedynamicNSGA-IIprocedurestohelpidentifyoneso-lutionfromtheobtainedfrontautomatically(on-line).Interestingconclusionsabouttheparticularproblemandaboutdynamicmulti-objectiveoptimizationproblem,ingeneral,aremadefromthisstudy.2DynamicProblemsasOn-LineOptimizationProblemsManysearchandoptimizationproblemsinpracticechangewithtimeandthere-foremustbetreatedasanon-lineoptimizationproblems.Thechangeintheproblemwithtimetcanbeeitherinitsobjectivefunctionsorinitsconstraintfunctionsorinitsvariableboundariesorinanycombinationofabove.Suchanoptimizationproblemideallymustbesolvedateverytimeinstanttorwhen-everthereisachangeinanyoftheabovefunctionswitht.Insuchoptimiza-tionproblems,thetimeparametercanbemappedwiththeiterationcounterτoftheoptimizationalgorithm.Onedifficultywhichmayariseinsolvingtheaboveon-lineoptimizationtaskisthattheunderlyingoptimizationalgorithmDynamicMulti-objectiveOptimizationandDecision-Making805maynotgettoomanyiterationstofindtheoptimalsolutionsbeforethereisachangeintheproblem.Ifthechangeistoofrequent,thebesthopeofanop-timizationtaskistotracktheoptimalsolutionsasc