HARNESSINGEVOLUTIONARYCOMPUTATIONFORTHEDESIGNAND GENERATIONOFADAPTIVEEMBEDDEDCONTROLLERSWITHINTHE CONTEXTOFUNCERTAINTY By ChadMichaelByers ADISSERTATION Submittedto MichiganStateUniversity inpartialentoftherequirements forthedegreeof ComputerScience-DoctorOfPhilosophy 2015 ABSTRACT HARNESSINGEVOLUTIONARYCOMPUTATIONFORTHEDESIGNAND GENERATIONOFADAPTIVEEMBEDDEDCONTROLLERSWITHINTHE CONTEXTOFUNCERTAINTY By ChadMichaelByers Acriticalchallengeforthedesignofembeddedcontrollersisincorporatingdesirablequal- itiessuchasrobustness,faulttolerance,andadaptabilityintothecontrolprocessinorder torespondtodynamicenvironmentalconditions.Anembeddedcontrollergovernstheexe- cutionofatask-spsystembymonitoringinformationfromitsenvironmentviasensors andproducinganappropriateresponsethroughthesystem'sactuators,often independent ofanysupervisorycontrol.Forahumandeveloper,identifyingthesetofallpossiblecom- binationsofconditionsasystemmightexperienceanddesigningasolutiontoaccommodate thissetisburdensome,costly,andoften,infeasible.Toalleviatethisburden,avarietyof techniqueshavebeenexploredtoautomatethegenerationofembeddedcontrollersolutions. Inthisdissertation,wefocusonthebio-inspiredtechniquereferredtoas evolutionarycom- putation whereweharnessevolution'spowerasapopulation-based,globalsearchtechnique tobuildupgoodbehavioralcomponents.Inthisway,evolution naturally selectsforthese desirablequalitiesinorderforasolutiontoremaincompetitiveovertimeinthepopulation. Often,thesesearchtechniquesoperateinthecontextofuncertaintywhereaspectsofthe (1)problemdomain,(2)solutionspace,and(3)searchprocessitselfaresubjecttovariation andchange.Tomitigateissuesassociatedwithuncertaintyintheproblemdomain,wepro- posethedigitalenzyme,abiologically-inspiredmodelthatmapsthecomplexityofboththe environmentandthesystemintothespaceofvaluesratherthaninstructions.Toaddress uncertaintyinthesolutionspace,weremoveconstraintsinourinitialdigitalenzymemodel toallowthegenomestructuretobedynamicandopen-ended,accommodatingawiderrange ofevolvedsolutiondesigns.Finally,tohelpexploretheinherentuncertaintythatexistsin thesearchprocess,weuncoverahiddenfeatureinteractionpresentbetweenthediversity- preservingsearchoperatorofapopularevolutionaryalgorithmandproposeanewwayto usenichingasameanstomitigateitsunwantedandbiasonsearch. TABLEOFCONTENTS LISTOFTABLES .................................... vi LISTOFFIGURES ................................... vii Chapter1Introduction ................................ 1 1.1ProblemDescription...............................2 1.1.1UncertaintyintheProblemDomain...................2 1.1.2UncertaintyintheSolutionSpace....................4 1.1.3UncertaintyinEvolutionarySearch....................5 1.2ThesisStatement.................................6 1.3KeyResearchContributions...........................6 1.4OrganizationofDissertation...........................9 Chapter2Background ................................. 11 2.1BiologicalProcesses................................11 2.1.1CellularControlModel..........................12 2.1.2EnzymesandMolecules.........................13 2.2Search-basedTechniques.............................14 2.2.1GlobalOptimizationandSearch.....................15 2.2.2EvolutionaryComputation........................17 2.2.3GeneticAlgorithms............................20 2.2.4Multi-ObjectiveEvolutionaryAlgorithms................21 2.2.5Non-DominatedSortingGeneticAlgorithms..............32 Chapter3UncertaintyintheProblemDomain ................. 35 3.1DigitalMolecule..................................37 3.2TheDigitalEnzyme(DZ)Model........................38 3.3TheCentral-PlaceForagingProblem......................44 3.4ExperimentalSetupandResults.........................47 3.5RelatedWork...................................51 3.5.1Avida...................................51 3.5.2GeneticProgramming..........................54 3.5.3Neuroevolution..............................56 3.5.4FSMs,Cellular-Automata,andMembraneComputing.........59 3.6Discussion.....................................61 Chapter4UncertaintyintheSolutionSpace ................... 63 4.1TheDynamicDigitalEnzyme(DDZ)Model..................65 4.2Empirical-BasedModelComparison.......................68 4.3RelatedWork...................................73 4.4Discussion.....................................75 iv Chapter5UncertaintyintheSearchProcess:Objective-based ....... 77 5.1RemoteDataMirroringSystems.........................78 5.2Plato........................................80 5.3LinearWeightedFitness.............................82 5.4TargetGoal-basedFitness............................87 5.5RelatedWork...................................91 5.5.1Non-EvolutionarySearch-BasedTechniques...............91 5.5.2EvolutionarySearch-BasedTechniques..................92 5.6Discussion.....................................93 Chapter6UncertaintyintheSearchProcess:Operator-based ........ 96 6.1DiscoveringaHiddenFeatureInteraction....................97 6.2ParetoSurfaceDetection.............................99 6.3BasinsofAttractionRemoval.....................100 6.4NearestNeighborDistanceAnalysis.......................101 6.5CrossoverImpactAnalysis............................103 6.6MutationDistanceAnalysis......................106 6.7EdgeConnectivityAnalysis...........................108 6.8MutationAnalysis.............................110 6.9IncreasedMutationProbabilityAnalysis....................112 6.10RelatedWork...................................114 6.11Discussion.....................................117 Chapter7MitigatingOperator-basedUncertaintyintheSearchProcess . 118 7.1DesiredSearchProperties............................119 7.1.1DiverseSolutionSet...........................119 7.1.2Non-Dominated,Pareto-OptimalSolutions...............120 7.1.3ManageNon-UniformMutational................121 7.2LeveragingReference-basedNiching.......................122 7.3RelatedWork...................................126 7.4Discussion.....................................127 Chapter8ConclusionsandFutureWork ..................... 130 8.1SummaryofContributions............................130 8.2FutureWork....................................132 8.2.1UncertaintyintheProblemDomain...................132 8.2.2UncertaintyintheSolutionSpace....................133 8.2.3UncertaintyduringSearch.........................134 BIBLIOGRAPHY .................................... 137 v LISTOFTABLES Table5.1:PropertiesofRDMnetworkingprotocols[65]...............79 vi LISTOFFIGURES Figure2.1:Thethreecomponentsofbiologicalsignaltransduction:receptionof signal,internalinteractionsamongsecondarymessengers,andare- sponseofthecell(e.g.,geneexpression).................13 Figure2.2:Theevaluationfunctionperformsamappingbetweenthesolutionspace andtheobjectivespace..........................18 Figure2.3:Threecommonformsofcrossoverbetweentwoparentgenomes:One- Point,Two-Point,andUniform.....................22 Figure2.4:Pointmutationsandswapmutationsintroducenewinformationinto anEA...................................23 Figure2.5:Asolution x dominates y ( x y )bybeingcontainedwithinthevolume by y intheobjectivespace....................24 Figure2.6:Thethreeoutcomesofthedominancerelation: x is dominatedby y (red), x dominates y (green),and x is incomparableto y (yellow)...27 Figure2.7:Solutionsplacedintolevelsofnon-domination,orfronts,thatrepresent asolution'sdominancerank.......................28 Figure2.8:Referencepoint-basednichingwhereeachsolutionisassociatedtoits nearestreferenceline(niche).......................34 Figure3.1:Themappingofbitswithinadigitalmoleculeusedtoencodeproperties oftherobot'senvironmentandactuators................38 Figure3.2:Theworldviewofanagentwithafooditemandfellowagentemitting thecolorofhome..............................40 Figure3.3:Adetailedviewofthecomponentsusedineachphaseofadigital enzyme-basedcontroller..........................41 Figure3.4:Thevirtualhardwareofadigitalenzyme.................42 Figure3.5:Anunboundedworldwherefoodisplaced6unitsfromhome'sperime- ter,correspondingtothecontroller'scurrentylevel......46 Figure3.6:Comparisonofthelevelofachievement(averagethatevolved controllersreachedasfoodwasplacedfartherfromhome'sperimeter withtheoriginalmodel(DZ)illustratedbythegreenlineanddynamic (DDZ)modelbytheredline........................48 vii Figure3.7:The\RedArm"Strategywhereagentsworktoextendthenotionof Home....................................49 Figure3.8:The\GreenArm"Strategywhereagentsworktoextendthenotionof Food.....................................50 Figure3.9:Themaincomponentsofanneuralnetworkincludingsensory neuronswhereinputsarereceived,hiddenneurons,andmotorneurons whereoutputsignalsarereturned.....................57 Figure3.10:ThemaincomponentsofanindividualneuroninanANNincluding weightedinputsandbiaspassedintoasummationand/oractivation functionthatemitsitsoutputsignal...................58 Figure4.1:Atypicalembeddedsystemcontainingsensorsandactuatorsinteract- ingwiththeenvironmentwhereabroadrangeofcontrollerdesignsare possibletoproducethedesiredsystembehavior,rangingfromsingle- program-single-instancedesigns(1:1)tomulti-program-multi-thread designs(T:P)................................64 Figure4.2:Adetailedviewofthecomponentsusedineachphaseofthenew dynamicdigitalenzyme(DDZ)controllerwheretheinternalcontrol structurecanfreelyevolveovertime...................66 Figure4.3:Avisualdepictionofthettreatment(feature)combinations usedthroughouttheforagingexperiments................69 Figure4.4:Theaverageessforeachcombinationofsystemfeaturesonthe foragingproblemwiththeoriginalstaticmodel(DZ)andnewdynamic (DDZ)modelhighlighted.........................70 Figure4.5:Theaveragedistancess)achievedbyevolvedcontrollersbasedon tfeaturegroupings.Thedirectionfeatureisshowntohavethe mostt..........................72 Figure4.6:The\Mimic"Strategywhereagentsworktoextendthenotionofboth HomeandFood...............................73 Figure5.1:Twosampleoverlayencodingsindicatingactivelinksandtheircorre- spondingRDMprotocols..........................80 Figure5.2:Thetop5%solutionsofall Plato runsplottedwithinthe3Dobjective space.....................................84 viii Figure5.3:Theaveragemeasuredvaluewithinaparticulardimensionofthetop 5%ofevolved Plato networkscomparedagainsttheweightingco- cientsettingduringtheevolutionaryrun.................87 Figure5.4:Thetop5%solutionsofall TargetingPlato runsplottedwithinthe3D objectivespace...............................89 Figure5.5:Theaveragemeasuredvaluewithinaparticulardimensionofthetop 5%ofevolvednetworkscomparedagainstthetargetvaluesettingdur- ingtheevolutionaryrun..........................90 Figure6.1:OriginalNSGA-IIsolutions(red)comparedagainstsolutionsonPareto surface(grey)returnedbyepsilon-constrainedNSGA-II........98 Figure6.2: NSGA-II-MinEuc solutions(green)comparedagainstsolutionsonPareto surface(grey)...............................101 Figure6.3:TheaverageEuclideandistancetothenearestneighboringsolution using NSGA-II-MinEuc ...........................103 Figure6.4:Theoverallfrequencydistributionofsolutionsusing NSGA-II-MinEuc .103 Figure6.5:Thenumberofsolutions(with Cost > 0.50)usingtwo-pointcrossover fromawell-mixedpopulation.......................106 Figure6.6:Thenumberofsolutions(with Cost > 0.50)usingonlymutationfrom awell-mixedpopulation..........................106 Figure6.7:AverageparenEuclideancrowdingdistance.......108 Figure6.8:Locationswhere NSGA-II-MinEuc solutionswerereturned.......108 Figure6.9:Percentageofactivelinkstoremoveanddisconnectnetworks......110 Figure6.10:Thenetofmutationonthe Cost objectiveofsolutionsreturned throughouttheobjectivespace......................113 Figure6.11:Thenetofmutationonthe ResourceConsumption objectiveof solutionsreturnedthroughouttheobjectivespace...........114 Figure6.12:Thenetectofmutationonthe DataatRisk objectiveofsolutions returnedthroughouttheobjectivespace.................115 Figure6.13:ThepercentageofsolutionsfoundintheTreatmentregionacrossvar- iousmutationratesettings.........................116 ix Figure7.1:Thereturnedsolutionsfor NSGA-IIIPlato plottedwithinthree- dimensionalobjectivespace........................124 Figure7.2:AveragepercentageofthehypervolumedominatedbyeachPlatoap- proach'ssolutions.............................125 x Chapter1 Introduction Assoftwaresystemscontinuetotakeonnew,complexrolesandapplicationsforprovid- ingautomatedcontrol,thereisanincreasingdemandforsystemsthatcanremainadaptive andresilienttotheuncertaintiespresentinthedeployedenvironment,systemobjectives/- goals,andproblemconstraints.Incontrasttotraditionalgeneral-purposecomputerssuchas PCs,an embeddedcontroller istypicallyintendedforasptaskorapplicationwithexam- plesincludingcontrolsystems,factoryandpowerplantcontrolsystems,androbotics toonlynameafew.Embeddedcontrollersinterfacewiththeirenvironmentbymonitoring informationviasensors,incorporatingthissensinginformationintheirdecisionlogic,and producingaresponsethroughactuatingsystemcomponents.Inaddition,thesecontrollers executeatophardwarewithbothprocessingpowerandmemoryconstraints.Moreover, manyembeddedcontrollersareintendedtooperateindependentofanyformofsupervisory controllerwithnodirectconnectiontoahumaninterface. Abiologically-inspiredapproachoftenusedtodesignsuchsystemsis evolutionarycom- putation (EC),abottom-upapproachwherethebehavioral\program"undergoesthepro- cessesofmutationandnaturalselection,harnessingevolution'spowerasapopulation-based, globalsearchtechniquetobuildupgoodbehavioralcomponents.Akeyobjectivewithusing evolutionarycomputationistoprovideprimitives,suchasinstructionsforsensingstimuli andgeneratingactuatorresponses,thatcanbeassembledovertimebyevolutionintowork- ingsolutions.Sincereproductivesuccessislinkedtothequalityofasolutionandspacein 1 thepopulationforthenextgenerationisalimitedresource,aninherentselectivepressure existsforsolutionstoberobustagainstsinglepointsoffailure.Thisselectivepressurenat- urallybuildsbpropertiesintosolutionssuchasdecentralization,cooperation,and faulttolerance. 1.1ProblemDescription Often,achallengingconcernforthedevelopersofadaptivesystemsisdesigningone withinthecontextof uncertainty ,thatweexplicitlyas,\aconditionorstatethatis neithernorexplicitlyanticipated."Thisprovidesuswithaframeworkthat encompassesthemyriadofwaysinwhichuncertaintycanmanifestitselfinthelifetimeof asoftwaresystem.Forsystemdevelopers,hand-designingsoftwarethatisadaptivetoa representativesetofconditionsfromvarioussourcesofuncertaintypresentsanarduousand burdensometask.Inharnessingevolutionarysearchforthegenerationofadaptivesoftware, thisdissertationaddressesthreecontextswhereuncertaintycanpresentitself:(1)inthe problemdomain,(2)inthesolutionspace,and(3)duringtheevolutionarysearchprocess. 1.1.1UncertaintyintheProblemDomain. Whentailoringaninstruction-basedevolutionarycomputationtechniqueforaproblem, oftenfeaturesofthe problemdomain (e.g.,sensorvalues)orsystem(e.g.,spcactuator responses)becomeincorporatedintotheinstructionset.Examplesofinstruction-basedEC techniqueswherethisreadilyoccursareAvida[83]andGeneticProgramming(GP)variants [9,23,39,72,77,89,102,105,106].Inapplicationsthatcontainonlyalimitednumber ofthesefeatures,thisapproachdoesnotbecomeamajorissue.However,inapplications withalargenumberofsensorvaluesandactuatorresponses,severalissuesmaybeginto emerge:(1)instructionsetbloat,(2)unrealizableinstructions,and(3)highlyspecialized instructions. Toillustratetheseissuesandtheirimpactonevolutionarysearch,weuseanexample 2 wherearoboticcontrollerisbeingevolvedtoforageforresourcesinanunknownenvi- ronmentandtoreturntheseresourcestoadesignatedhomeregion.Eachroboticagent maycontainahostofactuatorsformovementaswellasemittingcolorsandsoundsfor communication.Inaddition,featuresinanagent'senvironment,suchasthecolorsand soundsofnearbyagents,maybesensedbytherobotandusedtoperformitstask. Instruc- tionsetbloat referstothetendencytotransformeachsensorvalue(e.g., If RedColor Seen , If BlueColor Seen ,etc.)oractuatorresponse(e.g., Emit RedColor , Emit BlueColor ,etc.) intoitsownuniqueinstruction,causingtheinstructionsettobecomeunwieldyduringevolu- tionarysearch.Inadditiontobloat,aninstruction'simplementationmayalsobeunrealizable (e.g., Turn Towards Home )duetoassumptionsofglobalinformationthatwouldnotbeavail- abletoadeployedsystem. Unrealizableinstructions canrestrictourlevelofunderstanding ofcomplex, adaptive behaviorsseenintherealworldbytrivializingtheirimplementation andexecutioninanideal,simulatedworld.Instructionsetsdesignedwiththisnotionof perfectknowledgeinmindalsohindertheabilitytotransferanevolvedsolutionfromsimu- lationintothenoisyandimperfectenvironmentsfoundintherealworld.Moreover,highly customizedinstructionsets canmakeittocomparethesolutionsgeneratedfortwo tapplicationdomainsforcommonalitiesandidenofgeneralizableevolved behaviors. Withineachproblemdomain,thereisacantinhowevolutionarycom- putationcanbeusedbaseduponthedeployedenvironmentinwhichthesolutionisintended tooperate.Forexample,inastaticallydproblemdomainsuchasanautomatedfac- torysettingwithroboticarmsandconveyors,thesetofinputs,rangeofmotion,ortiming ofspeceventsforanembeddedcontrollermaybepreciseandwellHowever, inadynamicchangingenvironmentsuchasasearch-and-rescuesetting,thereisoftena greaterdegreeofuncertaintyregardingtheconditionsandscopeofthesystemenvironment aseventsoccurasynchronouslyandunpredictably.Embeddedsystemsareoftenmeantto operateinthesedynamicenvironmentswhereuncertaintyinenvironmentalconditionscan 3 leadtosensingandtimingchallengeswithinevolvedsolutions.Forexample,inAvida[83], eachagentisconstantlyexecutinginstructionsalongitsgenomeduringoperationmeaning thatanenvironmentalstimulus,criticaltoitsdecisionlogic,mustbedetectedbyasp pointinthegenomeinorderfortheagenttoproperlyrespond.Inadynamicenvironment, strictlyadheringtothisrequirementcanleadtobrittlenessandfragilityinanagent'sability todetectandadapttoitsenvironment.Tomitigatethisproblem,evolutionarysearchoften favorsagentswhosegenomescontainhighlevelsofredundancyforsensing,or\polling,"their environment.Whilethisbiasedgenomestructuremayincreaseanagent'sresponsivenessto stimuli,itmayalsomakeitmorechallengingtoevolveappropriateresponseandcontrol mechanismsaroundtheseredundantsensingregionsasthegenomebecomesmorebloated. 1.1.2UncertaintyintheSolutionSpace. Aswithmanysoftware-basedsystems,thereexistmanywaystocodifyasolution. Similarly,uncertaintycanalsoariseinthespaceofsolutionsthatcanbegeneratedby instruction-basedECtechniques.Thedesignusedtoimplementacontroller'sdecisionlogic cantakeonavastnumberofpossibilitieswithrespecttothenumberofparallelprogramsand numberofinstancesofeachparallelprogramexecutingwithinacontroller.Aswehaveseen innature,anorganism'scontrolstructureisgenerallydividedintoastaticlibraryofgenetic programs(genes)thatbecomeinstantiatedasproteinswithaspfunction, byconditionsintheirlocalenvironment.Thenumberofgenetic programs , instantiations of eachprogram,aswellasthe parameters their\execution"are,therefore,open- endedquestionsintheevolutionarysearchprocess.Withtheadditionofthesedegreesof freedom,thereisalsouncertaintyin howtoprovidedistributedcontrol overeachactuator containedwithinanagent.Forexample,thedecisionlogicforproducingaresponseinone actuator(e.g.,directiontoturn)maybedistributedacrossasetofprocesses,whilethe logicforproducingaresponseinaseparateactuator(e.g.,colortoemit)maybecontained withinasingleprocess.Providingasolutionthatcanbalanceandprioritize 4 thesecompetingconcernsforactuatorcontrolrequiresastructure,absentincurrent instruction-basedECtechniques. 1.1.3UncertaintyinEvolutionarySearch. Uncertaintycanalsooccurwithintheevolutionarysearchprocessthatconnectsthe problemdomainandthesolutionspace.Duringthisprocess,uncertaintymaypresentitself invariousaspects.Anindustry-providedapplicationhighlightedtwoofthesesourcesof uncertainty:(1)the objectives or goals thatguidesearchinthedirectionofoptimalsolutions and(2)thechoiceofevolutionary searchoperators thatfacilitatethediscoveryofmeaningful anddesiredsolutions. Objective-baseduncertainty pertainstothescales,orsearchdimensions,alongwhich evolvedsolutionsareevaluated,measured,andcompared.Forexample,anadaptivesoft- waresystemforasmartenergygridapplicationmightbeevaluatedalongthefollowing dimensions:costorcomplexitytodeploy,performanceinbeingabletotlydistribute andmanageresources,reliabilityandresiliencytofailures,anddecentralizationamongthe system'scomponents.Whenusingevolutionary-basedapproaches,thechoiceofobjectives andhowtheyareutilizedare vital tothesearchalgorithm'senessaswellasthequal- ityorvalidityofreturnedsolutions.Objective-baseduncertaintyencompasses:(1)deciding whichdimensionsarenecessaryandienttothediscoveryofdesiredsolutionsgiventhat thesearchspaceexpandsexponentiallyandbecomesmorevastwiththeadditionofeach newdimension,(2)decidinghowtodealwithmixeddimensiontypes,suchascontinuous versusdiscrete,andtheirimpactonsearch,(3)determiningthetypesofinteractionsthat existbetweendimensions,suchascomplementaryversuscompeting,andwhetherasearch biasisintroducedasaresultoftheseinteractions,(4)determiningwhetheraprioritization shouldexistamongdimensionsandifso,thetypeofprioritizationschemetouse,(5)deter- miningwhetherexistandifso,wheretheylie,and(6)respondingtotheaddition, removal,orreprioritizationofsearchdimensionsovertimeduringsearch,oftenreferredto 5 asDynamicOptimizationProblems(DOPs)[13]. Operator-baseduncertainty ,resultsfromthechoiceofsearchoperatorsthathavebeen incorporatedintotheevolutionaryalgorithmthatthediscoveryandmaintenanceof desiredsolutions.Withrespecttospoperatorsusedduringevolutionarysearch,ava- rietyofchoicesexistsuchas:(1) crossover operatorsusedtorecombine,or\mix",solution subcomponentsfromparentsolutions,(2) mutation operatorsusedtointroducenew,random geneticinformationintothepopulation,(3) elitism operatorsusedtoprioritizewhichsolu- tionsshouldpersistfromonegenerationtothenext,(4) selection operatorsthat thelevelofexplorationversusexploitation,orconvergence,takingplaceduringsearch,and (5) diversity-preserving operatorsusedtodiscoveraswellasmaximizethenovelty inthereturnedsolutionset.Uncertaintyispresentinboththechoiceofoperatorstoin- corporateforaspproblemdomainbutmoreimportantly,thehidden interactions that mayexistbetweenoperatorsaswellastheironsearch. 1.2ThesisStatement Thisresearchaddressesuncertaintyasitoccurswithinevolutionarycomputationfor thegenerationofadaptiveembeddedcontrollers,aswellastostudyitsctsandrolein theevolutionarysearchprocess. ThesisStatement Evolutionarycomputationcanbeharnessedtosupportthedesign andgenerationofadaptiveembeddedcontrollerswithinthefollowingcontextsofuncertainty: (1)theproblemdomain,(2)thesolutionspace,(3)duringtheevolutionarysearchprocess. 1.3KeyResearchContributions Inthisdissertation,forharnessingevolutionarycomputationinthegenerationofadap- tiveembeddedcontrollers,weaddressuncertaintyasitoccursinthesethreedistinctcontexts: 1. Uncertaintyinthe ProblemDomain 6 2. Uncertaintyinthe SolutionSpace 3. Uncertaintyduring EvolutionarySearch Thefollowingoverviewsthekeycontributionsofthisworktoaddressthethreeareasof uncertainty. TheDigitalEnzymeModel. Toaddressthechallengesofinstruction-setbloat, unrealizableinstructions,andinstructionspeyintroducedby uncertaintyin theproblemdomain ,wedesignedanevolutionarycomputationsystemtermedthe DigitalEnzyme (DZ)model[20].Inthismodel,thecomplexityofboththeenvi- ronmentandthesystem'sactuatorsismappedintothebitsandvaluesofbitstrings, ratherthanspinstructions,allowingourinstructionsettoremaincompactwith instructionsthatareproblem-independentandrealizable.Aninstructionsetcompris- inggeneral,problem-independentinstructionsenablesresearcherstodiscoverpatterns ofevolvedbehavior between relatedproblemdomainsandassessthetypesofprogram- mingstructures(e.g.,loops,conditionals,etc.)thatarecommonlyincorporatedinto evolvedsolutionstoaidtheevolutionarysearchprocess.Asecondchallengeconcern- inguncertaintyintheproblemdomainissynchronizingtheoccurrenceofeventsin theenvironmentwithgenomeexecutioninordertoberesponsive.Toavoidbloating thegenomewithinstructionregionsdedicatedto\polling"theenvironment,asseen intechniquessuchasAvida[83],ourmodeloperatesonanexecutioncyclecomprising threedistinctphases:(1)Sense,(2)Compute,and(3)Respondtoensurethecontroller hasthemostrecentstateoftheirworld. Open-EndedGenomeStructure. Toaccommodate uncertaintyinthesolu- tionspace withrespecttoanevolvedsolution'sstructure(i.e.,numberofparallel geneticprogramsandinputs),wedesignedanewcomputationalmodel,referredto asthe DynamicDigitalEnzyme (DDZ)modelthatrelaxedthisconstraint[19]in ourDZmodel,thusprovidingadynamicgenomeandamoreopen-endedevolutionary 7 searchspace.Evolvedsolutionsstartinalowerdimensionalsearchspaceandcanin- crementallybecomemorecomplexwithregardstotheirinternalcontrolstructureas necessaryfortheparticularproblemdomain.Thisprocessofstartingwithaprimitive structureandincrementallyelaboratingonanexistingstructure,whileretainingits strategy,isreferredtoas cation [100].Inaddition,weimplementeda iblestructuretobalancethecompetingconcernsforprovidingbothdistributedand prioritizedcontrolovervarioussystemactuators.Inanempiricalstudy,weevaluated variouscombinationsoffeatureimplementationsinourDZandDDZmodelstoassess whichfeaturescontributedtothegreatestsystemperformance.Theresultsfromthis studydemonstratedthatadynamicgenomeandvotingstructurewereable toevolvesolutionsassuccessful,andoftenbetter,thansystemdesignsthatdidnot accommodateuncertaintyintheevolvedsolution'sstructure. DiscoveringandMitigatingObjectiveandOperator-basedInteractions. To bettermanagetheinherent uncertainty thatexists duringthesearchprocess , wedetectedthepresenceofcompetinginteractionsinthe objectives ofanindustrial remotedatamirroringapplication.Tomitigatetheseinteractionsandprovideamore reliable,intuitivespmethodforendusers,weincorporatedatargetgoal- basedmethodintotheevolutionarysearchprocess.Usingthismethod, ourapproachwasabletoreturnsolutionsfoundinregionsoftheobjectivespacethat wereunreachableusingapreviousapproach[91].Whilethetargetgoal-based methodwasdemonstratedtoreducethelevelofuncertaintyforendusersregardingthe prioritization(e.g.,weighting)ofobjectivestocombattheseinteractions,this methodrequiredaprioriknowledgeofthesolution\surface"inordertoreturnoptimal solutionscontainingtheuser'sdesiredproperties. Giventhatknowledgeofthesolutionsurfaceisnotalwaysavailablewithinanappli- cation,weexploredtheuseofmulti-objectiveevolutionaryalgorithms(MOEAs)that weredesignedtobalancecompetingobjectivesintheabsenceofthisknowledgein 8 orderto Pareto-optimal solutions(i.e.,solutionsthatareoptimalwithrespectto theirachievedHowever,duringthisprocess,wedetectedthepresenceof ahiddenfeatureinteractionthathadbeenundiscoveredintheofmulti-objective optimization.WhileusingapopularMOEA,NSGA-II, 1 weobservedatin- teractionbetweenNSGA-II'sdiversity-preserving operator andalargeclassof searchproblems,namely,combinatorialoptimizationproblems.Theimpactofthisin- teractioncausedtheevolutionaryalgorithmtoabandonitsprimaryroleofdiscovering adiverseoptimalsolutionset,andasaresult,searchwasbiasedtoaseverelylimited regionoftheoverallsearchspace.Throughanempiricalstudy,wesystematicallycon- thekeyfeaturesofboththesearchproblemanddiversity-preservingoperators thatleadtothissearchbias. Inordertomitigatethishiddenfeatureinteraction,weproposeanalternativerole foranevolutionarysearchoperator,referredtoas niching ,thatexplicitlycreatesand maintainsfavorableregionstoconstantlydrawsearchtowardsintheobjectivespace. Evaluationofthistechniquedemonstratedthatnichingtlyimprovedoverall searchcoveragewhencomparedtotheoriginaldiversity-preservingoperatorofNSGA- IIandcanbeleveragedtoovercomeunwantedinteractionsstemmingfrom operator- baseduncertainty duringsearch. 1.4OrganizationofDissertation Theremainderofthisdissertationisorganizedasfollows.InChapter2,wediscuss thebiologicalinspirationforboththeDZandDDZmodels,includingthecellularmodelof control,signaltransduction,andtheuseofmoleculesasuniversalinformationcarriers.We alsoprovideabroadoverviewofevolutionarycomputationasafamilyofglobaloptimization andsearchtechniques,includingbothsingle-objectiveandmulti-objectiveevolutionaryal- gorithms.Next,Chapter3introducestheDZcomputationalmodelanddiscusseshowthese 1 Non-dominatedSortingGeneticAlgorithm 9 biologicalpropertieshavebeenincorporatedintoourmodel'sdesigntohandleuncertainty intheapplicationdomainandmitigateissuessuchasinstructionsetbloat,unrealizablein- structions,aswellascouplingbetweentheinstructionsetandtargetproblem.Chapter4 leveragestheDZmodelframeworkandprovidesanewmodeldesigntoaccommodateuncer- taintyinthesolutionspacethroughadynamicgenomethatsupportsopen-endedevolution ofkeycontrolcomponents.InChapter5,wedescribeasourceofuncertaintyuncovered duringsearchinthecompetingobjectivesofanindustry-providedremotedatamirroring application.Wealsodescribehowwemitigatetheiradverseusingatargetgoal- basedapproach.Inordertoincreaseaccesstosolutionsthroughouttheobjective space,Chapter6discusseshowweleveragedanMOEAcapableofsimultaneouslybalancing competingobjectivesand,duringthisprocess,discoveredahiddeninteractioninvolvinga vitalsearchoperator.Chapter7discussesourapproachtomitigatethishiddeninteraction stemmingfromoperator-baseduncertaintyanddescribesthekeypropertyforitssuccess. Finally,inChapter8,wesummarizethekeycontributionsandoverviewfuturedirections forthiswork. 10 Chapter2 Background Inthischapter,weoverviewtopicsusedtoaddressuncertaintyforthegenerationof adaptiveembeddedcontrollers.First,wedescribethekeybiologicalprocessesofsignal transductionandenzymaticreactionsthatinspiredthedesignofourdigitalenzymeframe- workforhandlinguncertaintybothintheproblemdomainandsolutionspace.Next,we overviewtheofglobaloptimizationandsearch,particularlyevolutionarycomputation, andtheutilityofgeneticalgorithmsfornavigatingvast,complexsolutionspaces. 2.1BiologicalProcesses BeforeintroducingtheDigitalEnzymemodel,thissectionoutlinesthepropertiesof cellularcontrolinbiologythatinspireditsdesign.First,weprovideageneraloverviewofthe controlprocessfoundinabiologicalcellbydescribinghowgeneticinformationfoundinthe genomeistransformedintofunctional,parallel-executingentitiesthatprovideadistributed controlstructure.Next,wediscusshowinformationfoundintheenvironmentisincorporated intothecell'sreactivecontrolprocessinordertotriggeranappropriateresponsemechanism. Inparticular,weemphasizethekeyrolethatthesefunctionalentitiesplayinthisprocess aswellasthebpropertiesthatemergefromthisdesign.Finally,wehighlightthe importanceofmoleculesasabiologicalmediumfortheiroverallversatilityandabilityto mapinformationinboththeenvironmentandthecellintoaformatthatisopenlyexchanged 11 betweenallcellularcomponents. 2.1.1CellularControlModel Webeginwithahigh-leveloverviewoftwodistinctprocessesthatformthefoundation ofthecellularcontrolmodel,namely,(1) geneexpression and(2) signaltransduction .At theheartofthecell'sinteriorliesastaticrespositoryofgeneticinformationreferredtoas the genome .Thegenomeperformstheroleofamaster\blueprint"forthecell,inherently dividedintotemplateregionsforeachofthecell'sfunctionalcomponents.Eachtemplate region,or gene ,encodestheinformationnecessarytobeconstructedintoitscorresponding functionalcellentity,orprotein,andreleasedtoperformitsjobwithinthecell.Todrawan analogywithincomputerscience,eachgenecontainsthegeneticsourcecodeofaparticular proteinclassthatbecomesinstantiatedtoexecuteinparallelalongsideotherproteinswithin thecell.Thisprocess,knownas geneexpression ,describeshowinformation,encapsulated ingenes,wsintotheproteinmechanismsdrivingthecell.Severalkeyadvantagesto thisnaturallyevolvedprocessare:(1)reusability,asgenescanproducemultipleinstances fromagiventemplate,(2),ingenomespacesinceduplicategenesarenotrequired inthisprocess,and(3)modularity,whereinformationrelatedtoproteinfunctionisoften collocatedinthegenome.Onedisadvantageofthisdesignisthatmutationsthatdisrupta gene'stemplatecanallinstancesifthereisnoredundancyinthegenome. Geneexpressionisaprocessthatoperatesongeneticinformation internal tothecell, however,itisalsoimportantforacelltobecognizantto external information(i.e.stimuli) initsenvironment.Toachievethisend,naturalselectionhasmaintainedaprocessreferred toas signaltransduction .Signaltransductionisacyclethatcanbedecomposedintothree phases:(1)sense,(2)transduceor\compute",and(3)respond.Duringthesensephase, signalmoleculesinthecell'senvironmentexpressanytowardsreceptorsontheouter surfaceofthecell.Uponsuccessfulbinding,aseriesofintracellular,cascadingreactions begintotakeplaceinthetransducephase.Transductionmeans,\toconvertfromoneform 12 toanother,"which,atthecellularlevel,correspondstocreatingandbreakingchemical bondswithinmoleculestoharnessenergyformolecularprocesses.Theproductsandenergy ofonereactionbecometheinputstolaterreactionsasentities,commonlyproteins,work inconcerttoproduceafunctionalchangewithinthecell.Thisformofdistributedcontrol, showninFigure2.1,leadstothecell'sresponsethatmayincludetheup/down-regulationof spgenes,alteringofmetabolicpathways,energizingofstructuresusedforlocomotion, andvariousotherresponsemechanisms. Figure2.1:Thethreecomponentsofbiologicalsignaltransduction:receptionofsignal, internalinteractionsamongsecondarymessengers,andaresponseofthecell(e.g.,gene expression). 2.1.2EnzymesandMolecules Whilethegenomeisacriticalcomponentinthecellularcontrolmodel,thesp \instances"ofthegeneticprogram,knownasproteins,arethetrue\workhorses"ofthecell, drivingitsinternalmechanics.Themostpredominanttypeofproteinisthe enzyme that formsanintegralpartofthetransducephaseinbiologicalsignaltransduction.Anenzyme isabiochemicalmachinewithinthecellthatbindstomolecules,performsworkthrough forming,breaking,andalteringchemicalbondsbetweenthesemolecules,and,emits theproductsofitsreactionbackintothecelltodrivelaterchemicalprocesses.Thetypeof workperformedbyanenzymeisdeterminedbytwofactors:(1)compositionand(2)confor- 13 mationor\state."Allenzymesorproteinsproducedfromthesametemplatesequenceinthe genomecomprisethesameelements,andtherefore,havethesamecomposition.However, eachenzyme'sconformationorstateisbyitslocalviewoftheenvironmentand howithasbeenthroughoutitsexistenceinthecell. Inbiology,moleculesformauniversal\medium"thatencapsulatesinformationintheir structureconcerningboththecellanditsenvironmentandareavitalpartofcellularcontrol. Upuntilthispoint,wehaveprovidedaholisticviewoftheprocessbywhichacellresponds toitsenvironmentaswellastheroleofakeycellularcomponent,theenzyme,insidethis process.Tobecomplete,however,wealsoacknowledgetheimportanceoftheabstract conceptofamoleculewhoseroleoftenbecomestrivializedandoverlookedinthisprocess. Moleculesenableinformationtobemanipulated,altered,communicated,andexchanged withanycellularcomponent.Intermsofevolutionarysearch,thispropertyofuniversal exchangehelpsreducethecomplexityofthesearchspacebyallowingthe context inwhich themoleculeisinterpretedtoitsmeaningratherthanastatic,underlyingattribute ofthemoleculeitself. 2.2Search-basedTechniques Inthissection,weoverviewsearch-basedtechniquesrelatedtoglobaloptimizationand searchwithanemphasison evolutionarycomputation ,afamilyofstochastic-basedsearch algorithmsinspiredbyprinciplesofDarwinianevolutionfoundinnature.Inparticular,we discussoneofthecanonicalevolution-basedalgorithms,namelythe single-objectivegenetic algorithm ,thathasbeenincorporatedintooneofthetoolsweusedwhileexploringuncer- taintyinthesearchprocess.Next,wediscuss multi-objectivegeneticalgorithms thatwere designedtosimultaneouslyoptimizemultiple,competingobjectivesinordertoreturnadi- versesuiteofsolutionsoptimalwithrespecttothetheyhaveachieved.Finally,we overviewtwomulti-objectivegeneticalgorithms,NSGA-IIandNSGA-III,whereweuncov- eredahiddeninteractioninvolvingoneofevolutionarysearch'skeyoperatorsandmitigated 14 itsunwantedonsearch,respectively. 2.2.1GlobalOptimizationandSearch Acrossmanydisciplines,thereisagrowingneedfortechniquescapableofperforming globaloptimization wherethegoalistosolution(s)whosequalityalongoneormore dimensions(i.e.objectives)hasbeenoptimizedforagivenproblem.Withinthisbroad of GlobalSearchandOptimization techniques,threedistinctcategories [24]emerge:(1) Enumerative ,(2) Deterministic ,and(3) Stochastic . Inanidealworldwithnolimitsontheamountoftime,space,orcomputationalre- sources,thesimplestsearchstrategywouldbetoexhaustively enumerate everypossible solutionandreturnthesetofoptimalsolutionswhensearchiscomplete.However,given thegrowthineithertheexpectedruntimeforevaluatingsolutionsofincreasingcomplexity and/orthesizeofthesearchspace(i.e.totalnumberofcandidatesolutions),enumerative techniquesquicklybecomeinfeasible. Deterministic algorithms,ontheotherhand,aimtoreducethetimeandspacecom- plexityofglobaloptimizationbyleveragingheuristicsthatincorporateknowledgefromthe problemdomainorrepresentingthesearchprocessasasequenceofdecisionsinagraph ortreestructure.Greedyandhillclimbingalgorithms[26]areexamplesofheuristic-based approachesthatoperateundertheworkingassumptionthatchoosingtheoptimallocalde- cisionateachstepofthesearchprocesswillnecessarilyleadtotheglobaloptimalsolution. However,becausethesealgorithmsdonotmaintainanarchiveofpriordecisionstoreturn to,thesealgorithmscaneasilybedeceivedandinsteadreturnsuboptimalsolutionswhen thisassumptiondoesnothold,suchasinproblemscontaininglocaloptima.Toincorporate additionaldomainknowledgeformaking\smart"decisionsaswellastheabilitytoreturn topreviouslyexploredsuboptimaldecisionpoints,newcapabilities[26]weredevelopedsuch asexploringthedecisionhierarchyonelevelatatime(i.e.,search)orone decisionpathatatime(i.e.,search),limitingsearchtodecisionpathsthatare 15 promising(i.e.,bsearchandbranch-and-bound),orwithdrawingfromdecisionpaths thatcannotreturnoptimalsolutions(i.e.,backtracking).Despitethesuccessofdetermin- isticalgorithmsonglobaloptimizationproblemsmorecomplexthanthoseamenabletothe enumerativeapproach,manyoptimizationproblemsstillexistwhosesearchspaceisdiscon- tinuous,missinggradientinformation(e.g.,combinatorialoptimization),deceptive,and/or toovastfortheseapproaches. Tohelpmitigatetheaforementionedchallengesthatdeterministicalgorithmsfaceaswell asexploreamorediversesetofregionsinthesearchspace, stochastic searchalgorithms weredesignedtoaddadegreeofrandomnessduringthesearchprocess.Althoughstochastic algorithmscannot guarantee thattheoptimalsolution(s)willbefound,thereisabroad spectrumtothelevelinwhichrandomnessisincorporatedintoandsearch.For example,RandomSearchandRandomWalkincorporatethemaximumdegreeofrandomness andarethemostncedsincetheseapproachessimplygenerate/evaluatesolutionsfrom thesearchspaceatrandomorfromapreviousrandomlygeneratedsolution,respectively. Movingalongthespectrum,theSimulatedAnnealing(SA)[68]algorithmislessuenced byrandomnessasitemulatesthepropertiesofcoolingmetalsbyallowingsolutions(i.e., atoms)tomovefrequentlyandrandomlyaccordingtosomeprobability p ,orwhetherthey improveuponthecurrentoptimalsolution.Overtime,however,thisprobabilitydecaysand thelikelihoodthatsolutionswillmoverandomlydecreases,similartohowatomswithina metalbegintoformarigidcrystal/structure.Movingfurtherstillalongthespectrum,we EvolutionaryComputation(EC)[52],afamilyofstochasticsearch-basedtechniques oftencharacterizedbytheirabilitytoharnessprinciplesofDarwinianevolution[29]via naturalselectiontoguidesearch.Itisthisfamilyofstochastictechniquesthatisthefocus ofthisresearchanddiscussedinfurtherdetailbelow. 16 2.2.2EvolutionaryComputation AsaofandComputationalIntelligence[33,48],EvolutionaryCompu- tation(EC)[52]isafamilyofstochasticsearch-basedtechniquesthatoriginallycomprised evolutionstrategies[92],evolutionaryprogramming[46],geneticalgorithms[56],andgenetic programming[71]referredtoas evolutionaryalgorithms (EAs).Later,ECencompassed avarietyofothertechniquessuchasant[40]andbee[88]colonyoptimization, immunesystems[44],tialevolution,digitalevolution[83],andparticleswarmopti- mization[66],tonameafew. EAsharnessprinciplesofDarwinianevolution[29]vianaturalselectiontomaintaina largenumberofsolutions,oropensearchavenues,in parallel .Throughouttheevolutionary searchprocess,stochasticityisincorporatedviareproductionoperators,suchasmutation andcrossover,toprovidean unbiased meansofmovingsolutions(i.e.,search)intonewareas ofthesearchspace.Tofocussearchtowardsareasofpotentiallydesirablesolutions,the reproductivesuccessofasolutioninthepopulationispositivelycorrelatedwithits or\quality."Byusingthisrelativemeasure,EAsareconstantlyseekingtheglobal optimumandhavebeenaptlydescribedascomplexadaptivesystemscapableofchanging theirmake-upandresponsesovertimeastheyinteractwithadynamicallychangingland- scape[33].Asaresult,EAstypicallyperformbetterthandeterministicalgorithmsinlarge, complex,anddeceptivesearchlandscapeswheremanylocaloptimumsexistandmorecom- plexsolutionscanbeincrementallyassembledfromsolutionsubcomponents(i.e.,\building blocks")overtime.Inaddition,thesealgorithmsdonotrequirecostlyorunobtainable gradientinformationthatothertechniques,suchashillclimbing,needinordertofunction, allowingthemtobeappliedtosearchlandscapesthatmaybediscontinuous. WhenadeveloperhasdecidedtoapplyanEAtoagivenglobaloptimizationproblem, thestepistoidentifytheelementsand/ordecisionvariablesthatcompriseacandidate solutionandthatshouldbeexploredbytheEA.Adatastructureisusedto encode the decisionvariablesinaformthatcanbeeasilymanipulatedbyevolutionaryoperators[48]. 17 Thecollectivesetofdecisionvariablesthatcompriseacandidatesolutionisoftenreferred toasthe genome whereastheindividualfreeparametersarereferredtoas genes .Avariety ofencodingschemesandgenomestructuresexistandtheirchoicecantlyreduce orincreasethesizeofthesearchspace,therebythelikelihoodthattheoptimal solution(s)willbefound. Asparallelsearchtechniques,EAs simultaneously exploreanumberofopensearchav- enuesbymaintainingmultiplecandidatesolutionsina population .Toexploremorepromising areasofthesearchspace,EAscontainanevaluationfunctioncapableofmappingasp ofdecisionvariablestoeither(1)ascalarvaluethatrepresents thesolution'soverallqualityor(2)avectorofobjectivevaluesthatindividuallymeasurethe solution'squalityalongtproblemdimensions.Theevaluationfunctionisdescribed asperformingamappingbetweenthe solutionspace andthe objectivespace ,asshownin Figure2.2. Figure2.2:Theevaluationfunctionperformsamappingbetweenthesolutionspaceandthe objectivespace ThelifecycleofanEAcantypicallybedecomposedintoiterationsofsearch,referred toas generations ,whereeachgenerationcomprisesthefollowingphases:(1)evaluation, (2)selection,(3)crossover,and(4)mutation.Duringevaluationphase,the\quality"of solutionsinthepopulationaredeterminedbyapplyingtheevaluationfunctionpreviously 18 describedandassigningeachindividualavalue.Next,toguidesearchtowardsareas ofhigherqualitysolutions, selection isusedtoincreasethelikelihoodthat\good,"more solutionsfromthecurrentgenerationarechosentoundergocrossoverandmutation. Variousselectionmethodscanbeused[6,56]thateachabetweenmain- tainingavenuesofsearchtoexploreandfocusingsearchtowardscurrentoptimalregions thathavebeendiscovered,oftenreferredtoasthe explorationversusexploitationtr [42].Forexample,roulettewheel,orproportionate,selectionassignsaprobabilityof beingselectedtoeachsolutionthatisdirectlyproportionaltothesolution'sHow- ever,asaresult,disproportionatelyindividualscancausetheEAtorapidly(andoften prematurely)converge.Incontrast,rankselectionassignsaprobabilityofbeingselectedto eachsolutionthatisproportionaltoitsrankinthepopulation.Althoughrankselection enforcesanorderingbasedonsolutionquality,therelativebetweenindividuals' valuesareoftenlostintheselectionprocessmakingitfortheEAtoconverge towardsmorepromisingregions.Tournamentselection[6]oftenprovidesdeveloperswith theabilitytotunethelevelofexploration/exploitationbyrandomlyselecting k individuals fromthepopulationandallowingtheindividualwiththehighestvaluetosurviveinto thenextgeneration. Finally,inordertogeneratenewsearchavenueswhilealsoleveragingthebuilding blocks,orsolutionsubcomponents,thathavebeenaccumulatedbytheEAinthepopula- tion'sgenomes,individual(s)fromtheselectionphaseareusedtoproducesolutions byundergoingcrossoverand/ormutation.Inspiredbytheroleofsexualrecombinationfound inbiology,the crossover operatorexchangessubsetsofgenesbetweentwoparentsolutions fromtheselectionphasewiththegoalthatcombiningsubcomponentsfromtwopar- entswillproducebetterHowever,ifmeaningfulcrossoverisnotperformed,this operatorcanoftenbemoredisruptivethanbtoevolutionarysearch.Usingsolelya crossoveroperator,theEAwouldbeaclosedsystemwithrespecttoinformation,meaning thealgorithmwouldberestrictedtoonlyrecombining,or\mixing,"existinginformationand 19 subcomponentsinthepopulation.The mutation operatorisusedtoaddnewinformation intothesystembyrandomlyinserting,swapping,ormodifyinggenesinsolutions. Therefore,thisevolutionaryoperatoraddsdiversitytothepopulationwiththegoalthatthis newinformationwillbeincorporatedandassembledintomorecomplexsolutionsinfuture generations.ExecutionoftheEAcontinuesuntileitheramaximumnumberofgenerations isreachedoruntilthequalityoftheoptimalsolution(s)inthecurrentpopulationexceedsa spthreshold,atwhichpoint,thesesolutionsarereturned. 2.2.3GeneticAlgorithms Ageneticalgorithm(GA)[56]isastochasticsearchalgorithmandoneofthecanonical EAs[33]thatiscapableofgeneratingsolutionstocomplexglobaloptimizationproblemsby leveragingprinciplesofevolutionvianaturalselection.Althoughnotarequirement,typically genomesareinlengththroughoutevolutionarysearch.Acommonrepresentationisa lengthvector,asshowninEquation(2.1),wherethegenome( x )comprisesdecision variables( x 1 ;x 2 ;:::;x n )thatareencodedaseitherbinarystringsorinting-point values. x = 2 6 6 6 6 6 6 6 4 x 1 x 2 . . . x n 3 7 7 7 7 7 7 7 5 (2.1) Toguideevolutionarysearchtowardsmorepromisingregionsofthesearchspace,the geneticalgorithmusesadomain-spevaluationfunctiontomeasureanindividualsolu- tion'sperformancealongoneormoreproblemdimensions,orobjectives(e.g., f 1 ( x ) ;f 2 ( x ), etc.).In single-objectiveoptimization ,theevaluationfunctionreturnsasinglenumerical valuedirectlyproportionaltothesolution'squality,suchasthroughalinearweightedsum (i.e., 1 f 1 ( x )+ 2 f 2 ( x ) ::: + m f m ( x )).Byusingalinearweightedsum,thecontribution ofeachproblemobjectivetowardsasolution'soverallqualitycanbeadjustedwitht 20 weightingconts(e.g., 1 ; 2 ,etc.)toguidetheGAtowardsspregionsofthe searchspace. Aftertheevaluationphase,aGAtypicallyappliesacrossoveroperatortoexchange solutionsubcomponentsbetweensolutionsthatwillbeinheritedbysolutionsinthe population.Giventhecommonlyusedvectorrepresentation,severaltraditional crossoveroperatorscanbeappliedinaGAsuchasone-pointcrossover,two-pointcrossover, oruniformcrossover,asillustratedinFigure2.3.Inone-pointcrossover,arandomindex(i.e. gene)isselectedinthegenomeandthegenesbeforeandafterthisindexareexchangedwith anotherindividualinthepopulationtogeneratetwonewIncontrast,two-point crossoverselectstworandomindicesinthegenomeandexchangesthegenesbetweenthese twoindiceswithanotherindividualinthepopulationtogeneratetwonewLastly, uniformcrossoveriteratesthrougheachgeneandexchangesgenesaccordingtoa probabilitytogeneratetwonew Finally,toaddnewinformationintothesearchprocessandmaintaindiversityinthe population,aGAappliesamutationoperatortosuchaspointmutationorswap mutationshowninFigure2.4. Pointmutations typicallyiterateacrossthegenesofagenome andrandomlyalterthegeneaccordingtoaprobability.Ifageneisselectedto receiveapointmutation,itsnewvalueiseitherrandomlychosenwithinthefullparameter range(i.e.uniformmutation)orsettoavaluewithinthevicinityofthegene'soriginal value(i.e.non-uniformmutation).Ifdecisionvariablesareencodedusingabitstring representationorsharearangeofvalueswithanothervariable,a swap mutationcanbe appliedwherethevaluesoftwogenesinthegenomeareexchanged. 2.2.4Multi-ObjectiveEvolutionaryAlgorithms Overtheyears,problemsfromavarietyofdisciplineshavebecomemorecomplexand governedbymultiple competing (i.e.orthogonal)objectiveswhereno single globaloptimal solutionexists.Instead,a set ofsolutionsexistswhosesolutionsareoptimalwithrespect 21 Figure2.3:Threecommonformsofcrossoverbetweentwoparentgenomes:One-Point, Two-Point,andUniform tothe tr madeamongtheproblem'sobjectives,oftenreferredtoas Pareto-optimal solutions[41,84].Multi-objectiveevolutionaryalgorithms(MOEAs)[24]weredesignedto simultaneously optimizemultiplecompetingobjectives,whileleveragingthesameprinciples ofevolutionvianaturalselectionasEAs,inordertoreturna diverse suiteofthesePareto- optimalsolutionstoadomainexpert. In single-objectiveoptimization ,thegoalistosolutions( x =( x 1 ;:::;x n )) thatoptimize(minimizeormaximize)a single scalarvalueofanevaluationfunction, f ( x ), andwhosedecisionvariablessatisfy constraints representedasinequalities( g i 0 ;i = 22 Figure2.4:PointmutationsandswapmutationsintroducenewinformationintoanEA f 1 ;:::;p g )andequalities( h j =0 ;j = f 1 ;:::;q g ).Incontrast,thegoalin multi-objective optimization istosolutionsthatoptimizecomponentsofan objectivefunctionvector , F ( x ),showninEquation(2.2),whilesatisfyingtheseconstraints. F ( x )= 2 6 6 6 6 6 6 6 4 f 1 ( x ) f 2 ( x ) . . . f m ( x ) 3 7 7 7 7 7 7 7 5 (2.2) Althoughasolutioncannotbedeclaredgloballyoptimalinmulti-objectiveproblems, insteadasolution x issaidto dominate ( )anothersolution y when x isnoworsethan y withineachrespectiveobjectivevalueand x improvesuponatleastoneof y 'sobjective values.Assumingamulti-objectiveproblemwherethegoalistominimizeallobjective values,thiscanbemathematicallyexpressedas: x y := 8 if i ( x ) f i ( y ) ^9 if i ( x ) < f i ( y ).Graphically,asolution x dominatesasolution y if x 'slocationintheobjective space( f 1 ( x ) ;:::;f m ( x ))isencapsulatedwithinthevolumeby y ( f 1 ( y ) ;:::;f m ( y )), asshowninFigure2.5.Therefore,asolutionisconsidered non-dominated relativetothe membersofanaggregatesolutionset(e.g.,population)ifnomemberisabletodominate itsobjectivevaluesandtermed Pareto-optimal onceitsobjectivevaluescannotbeimproved anyfurtherwithoutingqualityalonganotherobjective. ThetwofundamentalgoalsinMOEAdesigncenteraroundguidingsearchtowards 23 Figure2.5:Asolution x dominates y ( x y )bybeingcontainedwithinthevolumened by y intheobjectivespace Pareto-optimal solutionsandmaintaininga diverse setofnon-dominatedsolutions.Asa result,MOEAstypicallycontain(1)a assignment operatortorewardprogress inthedirectionofthePareto-optimalsurfaceand(2)a diversitypreserving operator toprioritizenoveltycomparedtoothersolutionsinthepopulation.Theadditionofnew, competingproblemdimensionsinmulti-objectiveoptimizationproblemsallowsforabroader rangeofstrategiesformeasuringasolution'sperformancetowardsthesetwogoals. Unlikesingle-objectiveoptimizationwhereisoftenequivalenttotheobjective valuebeingoptimized,inMOEAsmustincorporatethepresenceofadditionalob- jectivesindeterminingasolution'squalityasabasisforitsselectionduringsearch.Three commonassignmentstrategytypes[24,51,81]are:(1)aggregation-basedstrategies, (2)criterion-basedstrategies,and(3)dominance-basedstrategies. Aggregation-basedstrategies operateontheprincipleofaggregationorproblem decompositiontosolveoneormoresingle-objectiveoptimizationproblems.Often,asolu- tion'sobjectivevaluesareaggregated,orscalarized,intoasinglevaluethatguidessearchin aparticulardirectionwithintheobjectivespace.Asimpleaggregation-basedstrategyisto 24 useatraditionallinear-weightedsumapproach(e.g., 1 f 1 ( x )+ 2 f 2 ( x )+ ::: + m f m ( x )) wheretheparameters( 1 ; 2 ;:::; m )aresystematicallyvariedthroughoutsearchinorder toPareto-optimalsolutionsthatmaximizethissingleobjectivefunction[54,61].How- ever,adrawbacktothisapproachisthatPareto-optimalsolutionscanonlybefoundin non-convexregionsoftheobjectivespacethatintersectwiththehyperplaneformedbythe linearweightedsum.Asaresult,numerousalternativescalarizingfunctions[34]ofvary- ing\shapes"havebeenproposedtoPareto-optimalsolutionsinnon-convexregionsof theobjectivespace.Forexample,amoregeneralizedweightedmetricmethod,shownin Equation(2.3),existswhereareferencepoint( z )andexponentiationsettings( p ) canproducevariousoptimizer\hypershapes"suchashyperplanes(Manhattannorm, L 1 ), hyperellipsoids(Euclideannorm, L 2 ),includinguptohypercubes(Tchebycnorm, L 1 ). Similarly,the -constraintapproach restrictsallbutasingle\free"objectivethatitisseeking tooptimizewithinuser-spvaluesinordertosearchwithinnon-convexregions[22,25]. WhiletheseapproachesmaybesuccessfulinreturningPareto-optimalsolutions,itisoften toocostlytoiterateacrossallpossiblecombinationsofparametersorthereference points. L p ( x )=( P m i =1 w i j f i ( x ) z i j p ) 1 p (2.3) Insteadofaggregatingasolution'sobjectivevalues,analternativestrategyistoaggre- gateitsperformanceonasetoftargetvectors[59,60]orscalarizingfunctions[113]spread acrossthesearchspace.InMSOPS,anindividualisassignedaperformancerankingforeach targetvectorbasedonitsproximitytoanidealreferencepointalongthatvector.These rankingsarethenstoredinascorematrixandsortedinascendingorderforeachtarget vector.Themostsolutionsarethosethatareabletosimultaneouslyoptimizethe single-objectiveoptimizationproblemsassociatedwitheachtargetvectorandachievethe highestoverallrankingsthemostoften.Severaldrawbackstothisstrategyisthatado- mainexpertdoesnotknowaprioriwheretheParetosurfaceliesandtherefore,thenumber 25 oftargetvectorsandtheidealdistributionofthevectorsaresubjecttoatrial-and-error approach. Incontrasttoaggregation-basedstrategiesthatoftencollapsemultipleobjectivesor performancerankingsintoasinglescalarvalue, criterion-basedstrategies swapbetween eachoftheobjectivesbeingoptimizedduringtheselectionphaseoftheMOEA.Forexample, intheVectorEvaluatedGeneticAlgorithm(VEGA)[95],thepopulationisdividedinto M subpopulationswhere M isthenumberofobjectives.Eachsubpopulationisassociatedwith onlyoneofthe M objectivefunctionsforasolution'sassignment.Afterselection andthegenerationofindividualsareshintonewsubpopulationstoobtain thenextgeneration'spopulation.Whilethegoalofconstantlyswappingtheobjectivefunc- tionusedtoevaluateasolutionistopressurethesolutiontobeoptimalwithinmultiple competingobjectives(i.e.,subpopulations),onechallengewiththisstrategyis speciation wherebysolutionsbecomespecializedwithrespecttooneobjective.Solutionsthatattempt tooptimizeacrossmultipleobjectives,referredtoas\generalists,"facetheriskofbeing outcompetedby\specialists"whohaveoptimizedtheobjectivefunctionwithintheirsub- population.Inaddition,theectofshandswappingsubpopulationshasbeenshown tobeequivalenttoalinearweightedsumapproachandtherefore,thisstrategyisunableto Pareto-optimalsolutionsinnon-convexregions. Dominance-basedstrategies arepopularassignmentstrategiesforrewarding progresstowardstheParetosurfacesincetheyusethe dominance operatorinorderto performpairwisecomparisonsandestablisha partialordering amongsolutions.Asshownin Figure2.6,therearethreepossibleoutcomeswhenapplyingthedominanceoperatorbetween twosolutions, x and y ,intheobjectivespace:(1) x is dominatedby y ,(2) x dominates y ,or(3) x is incomparableto y whenadditionalpreferenceinformationisunavailableto quantifythebetweenerentsolution Asaresult,dominance-basedstrategiesestablishpartialorderingswithinthepopulation forselectionbyusingtsummarymeasuresgeneratedfromthesedominancerelations. 26 Figure2.6:Thethreeoutcomesofthedominancerelation: x is dominatedby y (red), x dominates y (green),and x is incomparableto y (yellow). Forexample,the dominancerank measuresthenumberofsolutionsagivensolutionis dominatedby andisusedinalgorithmssuchasMOGA[47],NPGA[57],SPEA/SPEA2[115, 114],andMOMGA/MOMGA-II[103,118].Incontrast,the dominancecount measures thenumberofsolutionsthatagivensolution dominates andisusedinalgorithmssuchas SPEA/SPEA2.Athirdmeasure, dominancedepth ,measuresthenon-dominationlevel, or front ,anindividualislocatedwithinandisusedinalgorithmssuchasNSGA[99]and NSGA-II[37],whicharetheprimaryfocusofthispaper.Forexample,thefront( F 1 ) containssolutionsthatarenon-dominatedwithrespecttoallsolutions,thesecondfront( F 2 ) containssolutionsthatarenon-dominatedwithrespecttoallremainingsolutionsuponthe removalof F 1 ,thethirdfront( F 3 )containssolutionsthatarenon-dominatedwithrespect toallremainingsolutionsupontheremovalof F 1 and F 2 ,thefourthfront( F 4 )contains solutionsthatarenon-dominatedwithrespecttoallremainingsolutionsupontheremoval of F 1 , F 2 ,and F 3 ,andsoforth,asshowninFigure2.7. Whilethesedominance-basedstrategiesarestraightforwardtoimplementandincur relativelylowcomputationaloverheadtocompute,thereareseveraldrawbackstotheir 27 Figure2.7:Solutionsplacedintolevelsofnon-domination,orfronts,thatrepresentasolu- tion'sdominancerank usagethatoftenareproblem-dependent.Withoutpreferenceinformation(e.g.,weightingor ranking)oftheproblemobjectives,thedominanceoperatorisunabletoestablishanordering betweenpairsofsolutionsthathavemadetamongtheobjectivesandare neitherdominatedbynordominateoneanother,so-calledincomparablesolutions.Asthe numberoftheseincomparablesolutionpairsincreases,dominance-basedstrategieslosetheir enessforguidingsolutionsinthedirectionofthetrueParetofront.Similarly,asthe objectivespacebecomesexponentiallymorevastwiththeadditionofeachnewobjective, solutionsbecomefartherspreadoutinthisspaceandarelesslikelytodominateoneanother. Asaresult,anincreasingnumberofindividualsbecomenon-dominatedandalsocause dominance-basedstrategiestolosetheirselectionpressuretodrivesearchtowardsthePareto surfaceinso-called many-objective (3+)optimizationproblems. Whileassignmentstrategiesguideevolutionarysearchinthedirectionofthe Paretosurface,oftena diversity-preserving operatormustbecoupledwithinMOEAtech- niquesthatrewardsasolution's novelty whencomparedtoothersolutionsinthepopulation. Thegoalofincorporatingadiversity-preservingoperatoristodistributesolutionsacrossthe Paretosurfaceinordertoprovideadomainexpertwithawiderangeofsolution 28 WithinMOEAsthatuseanaggregation-basedassignment,a weightvector strategy thatchangesthesetoftargetvectorsortheparameter/weightsbeingoptimized canbeusedtoguidesolutionsintdirectionsduringsearch.However,aspreviously mentioned,drawbackstothisapproacharethatadomainexpertdoesnotknowapriori wheretheParetosurfaceliesorhowmany/whichweightcombinationswillleadtot coverageandauniformdistributionoftheobjectivespace,oftenresultinginatrial-and-error approach. In sharing and clearing strategies[53,57,96],aresource(e.g.,objectivevalue, etc.)isapportionedtoindividualswithinaradius( ˙ share )ineitherthesolution spaceorobjectivespace.Inthesestrategies,solutionsaredriventowardssparsely-populated regionsinordertoavoidsharingandcompetingfortheirresourcewithmorepopulation members.Asaresult,thesestrategiestypicallyperformsomeformof densityestimation suchas kernel-based approaches[47,57]wheredensityisafunctionofthedistancetoother solutionsineitherthesolutionorobjectivespace, nearestneighbor-based approaches[99, 114]wheredensityisbasedonthedistancetothe i -thnearestneighbor,or histogram- based approaches[27]wheredensityisbasedonthenumberofsolutionswithinthesame neighborhoodofahypergrid. In crowding strategies[32,37],competitiontakesplacebetweenparentsand forinclusioninthenextgeneration'spopulation.crowdoutthemostsimilar individual(s)fromeitherarandomlyselectedsubsetofsize,oftenreferredtoas thecrowdingfactor,oraccordingtoacrowdingmetricmeasuredintheobjectivespace.In thesestrategies,solutionsaredrivenawayfromothermemberstolowertheprobabilityof beingselectedforreplacementthusincreasingsolutiondiversity. Clustering operators[97], suchas k -means,canbeusedinplaceofacrowdingmetricbyallocatingindividualsinto k clustersbasedontheirproximitytoacentroidandselectingonlyasubsetofeachcluster. Similarly,the - dominance strategy[36]expandstherangeofobjectivevaluesconsideredto bedominatedbyaparticularsolutionbyaddingasmallvalue( )toeachobjectivemeasure 29 ofasolution.Solutionsaredrivenawayfromoneanothertolowertheprobabilityofbeing placedintoadominatedfront. Grid-based strategiestypicallydividetheobjectivespaceintosubspaceseitherthrough anexplicitdistributionofreferencepoints[35]orbyallowingthesesubspacestoemerge fromthesolutionset.Forexample,theParetoArchivedEvolutionaryStrategy(PAES)[69] performsthelatterbyrecursivelybisectingtherangeofcurrentobjectivevaluestodetermine thecrowdednessofasubspaceandwhetherthesolutionshouldberetainedornot.Therefore, solutionsaredriventowardssubspaces/regionswheretherearefewerindividualstosurvive intosubsequentgenerationsofsearch. AmorerecentdevelopmentinMOEAsare indicator-basedstrategies [45,117]that transformthemulti-objectiveproblemintoasingle-objectiveproblemwherethegoalis tooptimizea qualityindicator valuethat simultaneously rewardsbothprogressinthe directionoftheParetosurfaceaswellasgoodsetcoverage,ordiversity,intheobjective space.Whileoperators,suchasthedominanceoperator,compareindividual solutions , qualityindicatorsweredevelopedinordertocomparetperformancecharacteristics of solutionsets .ToelyprovidegoodcoverageofthetrueParetosurface,these strategiesoftenrelyontheuseof Pareto-compliant indicators[116].Ingeneral,anindicator I isPareto-compliantifitpreservesthedominancerelationbetweenanytwosolutionsets, X and Y ,and I ( X ) I ( Y ).Asolutionset X issaidtodominate( )aset Y ifevery solution y in Y isdominatedbyatleastonesolution x in X ,asinEquation(2.4). Wedescribeseveralcommonindicatorfunctionsbelowaswellasthebanddrawbacks totheirusewithinindicator-basedstrategies. X Y := 8 y 2 Y 9 x 2 X : x y (2.4) The hypervolume indicator( I HV )[116]isPareto-compliantandmeasuresthevol- umeoftheobjectivespacedominatedbyasetofsolutionswithrespecttoareference point.Bymaximizing I HV ,anindicator-basedalgorithmsimultaneouslyrewardssolution 30 setsthatapproachtheParetosurfaceandcoverasmuchofthissurfaceaspossible.Unlike dominance-basedstrategiesthatlosetheabilitytoguidesearchtowardstheParetosurface inmany-objectiveproblems,thehypervolumeindicatorwouldremaine.However, thecomputationalcostofthehypervolumecalculationgrowsexponentially O ( N d 1 )based onthenumberofdimensions d given N solutions,makingitimpracticalforincreasingly complexproblems. The R2 indicator( I R 2 )[55]isPareto-compliantandincurstlylesscomputa- tionaloverheadthanthehypervolumeindicator.Byareferencepointandaset ofscalarizingvectorsthatareuniformlydistributedacrosstheobjectivespace, I R 2 reports thesumofthedistancebetweenthereferencepointandthenearestsolutionalongeach scalarizingvector.Byoptimizing I R 2 ,anindicator-basedalgorithmrewardssolutionsets thatapproachtheParetosurface(i.e.minimizedistancetoreferencepoint)andcoveras manyoftheuniformlydistributedscalarizingvectorsintheobjectivespaceaspossible.A drawbacktothisindicator,however,isthatknowledgeoftheParetosurfaceandoptimal placementofthereferencepointcantlythequalityofsolutionsetsreturned bytheMOEA. IfanapproximationoftheParetosurfaceisknownandcanbenedthroughaset ofreferencepoints R intheobjectivespace,severaladditionalindicatorsareavailableto use.The additive -indicator ( I + )[116]isPareto-compliantandmeasuresthesmallest value( )thatmustbe added totheobjectivevaluesof X 1 suchthat X 1 R .Similarly,the multiplicative -indicator ( I )[116]isalsoPareto-compliantandmeasurestheminimum factorthatmustbe multiplied byeachobjectivevalueof X 1 suchthat X 1 R .Related tothisepsilonfamilyofindicatorsistheInvertedGenerationalDistanceindicator( I IGD ) [104]thatmeasurestheaveragedistancefrom R tothenearestsolutionin X 1 .Although theoriginalversionoftheIGDindicatorwasnotPareto-compliant,amodistance calculation[2]hasbeenproposedthatnowmakesthisindicatoralsoPareto-compliant.One tdrawbacktotheseindicatorsisthattheirsuccessisdependentuponthereference 31 pointsintheobjectivespace,meaningthatlackofaprioriknowledgeofthePareto surfaceorapoorapproximationcantlyimpactsearch. Toguidesearchtowardsanoptimaldistributionofsolutionsusingtheseindicators,a commontechniqueduringtheselectionphaseoftheEAistoprioritizesolutionsthathave agreater contribution towardstheoverallindicatorvalue.Asolution'scontributioncanbe calculatedbymeasuringthe\lossinquality"ofthisindicatorvaluebyexcludingthesolution fromthesolutionset.TwoexampleapproachesthatusethistechniqueareSMS-EMOA[11] thatspusesthehypervolumeindicatorandIBEA[117]whichwasdesignedtobe moreversatilebyaccommodatinganyindicatorfunction. 2.2.5Non-DominatedSortingGeneticAlgorithms TheNon-dominatedSortingGeneticAlgorithmsareafamily[99,37,35]ofMOEAs developedbyDebetal.thatutilize non-dominatedsorting forassignmentandeither crowdingdistance (NSGA-II)[37]or referencepoint-basedniching (NSGA-III)[35]fordiver- sitypreservation.Non-dominatedsortingensuresthatsolutionsapproachthetruePareto surfacebygivingprioritytosolutionswhoseobjectivemeasuresdominate(improveupon) theobjectivemeasuresofothersolutionsinthepopulation.Webeginwithanoverviewof sharedcorefunctionalityfoundinbothNSGA-IIandNSGA-IIIapproachesanddiscusseach oftheirdiversitypreservationmechanismsseparatelybelow. Atthestartofeachgeneration,aparentpopulation P containing N individualsis usedtogenerateanpopulation Q ofequalsizeusingstandardgeneticoperators suchascrossoverandmutation.Next,thesetwopopulationsaremergedintoonecombined population S whereall2 N solutionsaresortedintoaseriesofdisjoint,non-dominated setscalled fronts .Solutionsareiterativelyplacedintosuccessivefronts( F 1 ;F 2 ,etc.)if theyarenon-dominatedwithrespecttoremaining,unsortedsolutions.Toguidesearch towardsPareto-optimalsolutions,frontsaresequentiallyaddedbasedontheirlevelofnon- dominationuntilthepopulationcapacity, N ,ismatchedorexceeded.Ifthepopulation 32 capacityismatcheduponaddingthelastfront( F L ),nofurtheroperationsarenecessary andthenextgenerationbeginsagainusingthisnewlygeneratedpopulation.However,if addingthelastfront( F L )causesthepopulationcapacitytobeexceededsinceonly K slots remain,thenadditionalstepsmustbetakentodeterminewhichsolutionsfrom F L will theseremainingunoccupiedslots.Thetwodistinctdiversity-preservingmechanisms, crowding-distance(NSGA-II)andreferencepoint-basedniching(NSGA-III)usedtomake thisdecisionarediscussedbelow. InNSGA-II[37],the crowdingdistance operatorassignsavaluetoeachsolutionin F L thattotalsthedistancetothenearestneighboringsolutionsalongeachdimension,or objective.Foreachdimension,thesolutionsin F L aresortedinascendingorderbased upontheirobjectivevalues.\Boundarysolutions"aresolutionswhoseobjectivevaluesare theminimumandmaximumofthedimensionandthesesolutionsareawardedthehighest crowdingdistancevalue(i.e.positiveity).Tocalculateanon-boundarysolution's crowdingdistancevalue,thedistancebetweenitsneighbors'(i.e. i 1and i +1)objective valuesisaddedtothesolution'scurrentcrowdingdistance.Afteriteratingthrougheach dimensionandperformingthesesteps,NSGA-IIchoosesthetop K solutionsin F L withthe largestcrowdingdistancevaluestobeaddedtothenextgeneration'spopulation. InNSGA-III[35],the referencepoint-basedniching operatorstartswithasetofreference points,orniches,thateither(1)havebeengeneratedinastructuredmanner,suchasbeing uniformlydistributed,or(2)pre-determinedandsuppliedbytheuser,asshowninFigure2.8. Next,solutionsfrompreviouslyaddedfronts(i.e., F 1 :::F L 1 )are associated toaunique niche.Toassociateasolutiontoaspniche,areferencelineisprojectedfromtheorigin througheachniche'sreferencepoint,andtheperpendiculardistancebetweenasolutionand eachreferencelineiscalculated.Afterwards,eachsolutionisassociatedwiththenichewhose referencelinehastheclosestperpendiculardistance.Totheremaining K slotsinthe nextgeneration'spopulation,thenichewiththeleastassociatedsolutions(excludingniches withnoassociatedsolutions)ischosenandthesolutionin F L withtheclosestperpendicular 33 distancetothisniche'sprojectedreferencelineisaddedtothepopulation.Afterthissolution hasbeenassociatedwiththeniche,thisselectionprocessrepeatsuntilallremaining K slots are Figure2.8:Referencepoint-basednichingwhereeachsolutionisassociatedtoitsnearest referenceline(niche) 34 Chapter3 UncertaintyintheProblemDomain Whenharnessingevolutionarycomputation(EC)forthegenerationofadaptiveem- beddedcontrollers,uncertaintyisinherentintheprocessofapplyingsearchtonewprob- lemdomains.Frequently,systemcapabilitiesand/ortheenvironmentundergot changesduringthetransferofevolutionarysearchfromoneapplicationdomaintothenext. Tominimizecouplingbetweenaparticularinstruction-basedECtechniqueanditsproblem domainaswellasfacilitatethetransferbetweendomains,theimplementationofagiven ECtechniqueshouldminimizethenumberofdomain-spcomponents.Inpreviously- developedtechniques,suchasAvida[83]andGeneticProgramming,featuresoftheproblem domain,suchassensorvaluesandspactuatorresponses,areoftenincorporatedinto theinstructionset.Asthenumberoffeaturesincreases,theapplicabilityofinstructions withinnewdomainsdeclinesandcanleadto bloat withintheinstructionsetaswellas theincorporationof unrealizableinstructions thatassumeaccesstoglobalinformationnot availableinareal-worldimplementation.Moreimportantlyforsearch,problem-sp instructionsinconjunctionwithscalingeithersystemorenvironmentalcomplexity,raises thecomplexityofthesearchspaceduetoinstruction-setbloat,thushinderingthesearch process.Problem-spinstructionsalsorestricttheversatilityofbuildingblocksinan evolvedsolutionby\freezing"informationabouttheenvironmentorsystemintoasp instruction(ex. If Detect Home or Emit Sound3 ),thuspreventingthisinformationfrom beingmanipulatedandrepurposedinordertoreducethesearchspace.Finally,instruction 35 spyreducessharedcommonalitiesbetweentwoinstructionsets,eveninsimilarprob- lemdomains,whichpresentschallengeswhenanalyzing,comparing,andabstractinggeneral patternsfromevolvedsolutions.Thediscoveryofcommoninstructionsorcontrolsequences usedinevolvedsolutionsmaygiveinsightintowaystoimprovethesearchprocesssuchas byaddingcomponentstothegeneralcontrolstructureorprovidinghigher-levelinstructions. Uncertaintyintheproblemdomainalsoincludeshowresponsiveanadaptiveembedded systemmustbetoenvironmentalstimuliduringrun-time.Executinginadynamic,chang- ingenvironmentisgermanetothesesystems,makingitforevolvedsolutionsto beresponsiveandadaptivetoenvironmentalstimuliinECtechniques,suchasAvida[83], thatcanbeexecutingfromanypointintheirgenome.ForECtechniquesthatareinthis continuousformofexecution,inordertoberesponsivetoenvironmentalstimuli,anagent musteither(1)properlytime,or synchronize ,theirexecutionforsensingtheenvironmentin theirgenomewiththeoccurrenceofthestimuli,or(2)minimizetheamountoftimebetween refreshingtheircurrentviewoftheenvironment.However,bothoftheseoptionshavecon- sequencesanddrawbacksinevolutionarysearchforthegenerationofembeddedcontrollers. First,synchronizingone'sexecutiontoitsenvironmentleadstobrittlenessandfragilityin theevolvedsolutionmakingittoimplementinnoisier,real-worldenvironments. Alternatively,tominimizethelengthoftimebetweenupdatinganagent'sviewofitsen- vironment,evolutionarysearchoftenfavorsagentswhosegenomesarelitteredwithsensing regions,makingitmorechallengingtoevolvecontrolmechanismsaroundtheseredundant regions. Inthischapter,weintroduceanevolutionarycomputationsystem,termedthe Digi- talEnzyme (DZ)model,designedtoaddresstheuncertaintyintheproblemdomainwith respecttothe applicabilityofinstructions and timingdependencywiththeen- vironment .InSection3.1,wediscusshowweaddresstheapplicabilityofinstructions, spproblem-spinstructionsthatarenon-transferableorrealizable,bymapping thecomplexityoftheenvironmentandsystemintothebitsandvaluesofbitstrings,rather 36 thaninstructions.Thisapproachenablesourmodel'sinstructionsettoassembleandrepur- poseinformationthroughoutthecontrollerwhileremainingcompact,problem-independent, andrealizable.InSection3.2,wediscusshowweavoidtimingdependencieswiththeenvi- ronmentthatcanleadtoredundant\polling"regionsinthegenomebydesigningourcellular controllertooperateonanexecutioncyclecomprisingthreedistinctphases:(1)Sense,(2) Compute,and(3)Respond.Thisdesignensuresthatthecontrollerhasthemostrecent stateoftheworldduringexecution.Finally,inSection3.3,wedescribetheunbounded, central-placeforagingtargetproblemforwhichsolutionswereevolvedandthesuccessful strategiesthatwereemployed;Section3.4describestheexperimentalsetupandresults. 3.1DigitalMolecule Inbiology,moleculesencapsulateandprovideinformationconcerningacell'scurrent environment.Moleculesformauniversalmediumthatcanbemanipulated,altered,commu- nicated,andusedtodriveinternaloperationsandexternalresponses.Similarly,bitstrings aretheuniversalmediumindigitalsystemsandareusedinthesamefashiontoproduce systembehaviors. Inourmodel,amappingencodesfeaturesoftheenvironmentintobitsandvaluesofbit stringsreferredtoas digitalmolecules .Asanexample,themappingshowninFigure3.1 istailoredfortheforagingproblemwhereagentsaregiventhetaskofandreturning resourceitemsfromtheirenvironmenttoacentralhomeregion.Digitalmoleculesarean untyped,binarymediumthatcanbealteredandfreelyexchangedthroughout all partsof anagent'scontroller,includingsensors,actuators,aswellasinternalcomputingentities.As shownbythelabelsontheright-handsideofFigure3.1,thesamebitsandvaluesencodedina digitalmoleculehavetmeaningsdependingonwherethemoleculeisbeingevaluated withinthesystem.Forexample,adigitalmoleculewiththebinaryrepresentation 1000 wouldsignifythatthecolorof Food isbeingsensed,ifthismoleculewerebeingevaluatedin theagent'scolorsensor.However,amoleculewiththissamebinaryvalueof 1000 residing 37 intheagent'smovementactuatorwouldbeexpressingthe Drop behavior.Todemonstrate howdigitalmoleculescanwfreelyfromonepartofthesystemtothenextwithouthaving anascribedtype,wecanconsiderthefollowingexample.Amoleculecanbegininanagent's colorsensor,encodingcolorssensedinthenearbyenvironment.Later,thismoleculemay beloadedintoaninternalcomputingentity,manipulatedduringexecution,andsenttothe agent'ssoundactuatorwhereitwillhelpproduceasoundinresponsetothisinitialcolor stimulus. Inthisway,weareabletomapattributesoftheenvironmentandsystemthatareoften application-spandmorepronetochange,intothebitsandvaluesofthisuniversally- exchangeddigitalmediumratherthantheinstructionset.Byperformingthismapping, wereducecouplingbetweenourtechniqueandthegivenapplicationdomainandsupporta moregeneralsetofrealizableinstructions.Inaddition,byadjustingthebitsizeofdigital moleculeswecanalsotuneandexperimentallycontrolthe\granularity"ofboththesystem andtheenvironmenttooptimizeforandreducethecomplexityofthesearchspace. Figure3.1:Themappingofbitswithinadigitalmoleculeusedtoencodepropertiesofthe robot'senvironmentandactuators. 3.2TheDigitalEnzyme(DZ)Model Asinnature,wherecooperativeparallelismanddistributedcontrolareharnessedto guideanorganism'sbehavior,wedevelopedour DigitalEnzyme (DZ)modelonthetwo biologicalprocessesofsignaltransductionandenzymaticreactions.IntheDZmodel,the 38 behaviorofeachagentisgovernedbya\single-celled"controllerwhoseexecutioncycle comprisesthethreedistinctphasesofsignaltransduction:(1)Sense,(2)Compute,and (3)Respond.IntheSensephase,thecontrollerencodesinformationaboutthestateof theenvironmentaswellastheagentinamanipulableformat,namely,digitalmolecules. IntheComputephase,uniqueinstancesoftheprogramsfoundinthegenomeexecutein parallelatopvirtualhardwaretoalterandexchangetheinformationstoredwithinthese digitalmoleculesinordertoguidetheagent'sbehavior.Finally,intheRespondphase, theagent'sresponsetoitscurrentenvironmentisgeneratedbasedupontheinformation containedwithinthedigitalmoleculesemittedtotheagent'sactuators. Instruction-basedtechniquesthatareinastateofcontinualexecution,suchasAvida [83],oftenresultintimingdependencieswiththeenvironmentthatcanleadtopollutingthe controller'slogicwithregionsdedicatedto\polling"forstimuli.Ourmodel'suseofdistinct executionphases,asseenalsoinGPs,ensuresthecontrollerhasthemostrecentstateofthe worldtofocusevolutionarysearchonselectinggenomesbasedsolelyontheir decisionlogic ratherthanhowwelltheycopewithbeingresponsiveduringexecution.Thisphase-based designforeachexecutioncyclealsoanupperboundonhowfrequentlysensorswill refreshtheirviewoftheenvironment,naturallyenforcingenergyinasolution. Tofacilitateourdescriptionfortheinternalworkingsofanevolvedcontroller,weuse Figures3.2and3.3asarunningexampletoprovideadetailedviewofsystemcomponents andtheirinteraction.Figure3.2providesa worldview oftheagent,representedasthe whitearrow.Inthisworld,anitemoffoodislocateddirectlyinfrontoftheagentwhilea fellowcolonymemberislocatedfartherawayemittingaparticularcolor,representedbythe redarrow.Next,Figure3.3providesa controllerview oftheagent'sinternalthree-phase controller:Sense,Compute,andRespond.Finally,Figure3.4providesan enzymeview of thevirtualhardwarecontainedinoneofthecontroller'sparallel-executingentities,adigital enzyme. Phase1:Sense -Thephaseofthecontroller'sexecutioncycleistheSensephase, 39 Figure3.2:Theworldviewofanagentwithafooditemandfellowagentemittingthecolor ofhome. wheresensorsareusedtodetectnearbyenvironmentalstimuliandencodethesestimuliinto thebitsofdigitalmolecules.Eachsimulatedagentpossessesthreesensingcapabilitiesfor thedetectionofobstacles,colors,andsounds,asshownatthetopofFigure3.3.Each sensorprovides360-degreedetectionoftheenvironmentdividedinto8sectors.Adigital moleculeisassignedtoeachsectorinordertoencodestimulidetectedwithinitsviewofthe environment. Foreachstimuluswithindetectionrange,thesectorandcorrespondingbitarecalcu- lated.Thisbitisthensettotruewithinthedigitalmoleculeassignedtothecalculated sector.IntheworldshowninFigure3.2,theagentisabletodetectafooditemdirectly North andafellowagentemittingaparticularcolorfromthe Southwest direction.Since thefooditemisdetectedinthe North sector,thecorrespondingbitfor Food issettotrue inboththeobstacleandcolorsensor,indicatedbythebluebitsinPhase1ofFigure3.3. Similarly,thefellowcolonymemberisdetectedinthe Southwest sectoremittingthe Home (red)color.However,thisstimulusisonlydetectedbythecolorsensor,indicatedbythered bitinPhase1ofFigure3.3.TheSensephaseiscompletewhenalldetectablestimulihave 40 Figure3.3:Adetailedviewofthecomponentsusedineachphaseofadigitalenzyme-based controller beensuccessfullyencodedintothedigitalmoleculesoftheirrespectivesensor. Phase2:Compute -Toemulatethebehaviorfoundinbiologicalcellswherein- formationstoredwithinmoleculesisrepurposedtodriveavarietyofcellularprocesses,the designoftheexecutingentitieswithintheComputephaseofourDZcontrollerusesthe(1) virtualhardwareand(2)instructionsetoftheAvidaDigitalLife[83]platform.Thevirtual hardwareelementsofAvida,includingregisters,instructionpointers,andstacks,provide thecapabilityofstoringandincorporatinginformationfrommultiplesources(e.g.,sensors) withineachexecutingentityofourcontrollerandhaveanalogsinreal-worldembeddedcon- trollers,thusallowingthemtobetransferredmoreeasilyintodeployedsystems.Moreover, thecircularprogramdesignislessbrittleandcontainsfewerconstraintswhencomparedto tree-basedandgrid-basedimplementationsofgeneticprogramming(GP).Lastly,theuse ofAvida'sTuring-Completeinstructionset[82]comprisinggeneral-purpose,assembly-like 41 instructionsprovidesexecutingentitieswiththecapabilitytoalterthebits(i.e.informa- tion)withindigitalmoleculesandemitthesemoleculestotheagent'sactuatorsinorderto producetheirresponse.Thisinstructionsetsupportsconditionalbranching,looping/itera- tion,arithmetic,bitwise,controlw,andstackoperationsthatunderliemanytraditional softwareprograms. UnlikeAvidawhereanagent'sresponsearisesfroma single executingprogram,two importantstructuresexistwithintheDZcontrollerforimplementingitsdecisionlogicand supportingtheparallelexecutionof multiple executingprograms,thegenomeandtherun queue,asshowninFigure3.3.Thegenomecontains3genes,oneforeachoftheagent's sensingcapabilities:obstacle,color,andsound,witheachgenecomprisedofgeneral-purpose, assembly-likeinstructions.Asinbiology,theDZgenomecontainsonlythestatic\source code"subjecttotheprocessesofmutation.However,itisthe expression offunctionswithin thesegenesandtheinteractionsofentities\executing"thesegenesthatproducesthephe- notype,suchasbehavior. Figure3.4:Thevirtualhardwareofadigitalenzyme. Therunqueueembodiestheexpressionofgenefunctionbymanagingtheparallelex- ecutionof digitalenzymes .Adigitalenzymeisathreadexecutingaparticulargeneatop virtualhardware.ThevirtualhardwareofanindividualenzymeisshowninFigure3.4. Aninstructionpointer(IP)indicatesthecurrentinstructionbeingexecutedwhileaw headcanbemanipulatedtojumpexecutiontoatpointwithintheprogram.For alteringthebitswithindigitalmolecules,three\molecular"registers(AX,BX,andCX)can 42 beaddressedandcontrolledusingbitwiseandarithmeticinstructions.Lastly,intermediate moleculesduringcomputationcanbepushedfromregistersintotwostacksmaintainedby theenzyme.Therunqueueexecutesenzymes,oneinstructionatatimeinround-robin order,untilamaximuminstructionlimitisreachedorunlessanenzymeexecutesa Halt instruction,therebyceasingitsexecutionfortheremainderoftheComputephase.Inaddi- tiontoastaticgenomecomprisingthreegenes,therunqueueisalsostaticwitheachgene expressedbytheparallelexecutionofeightdigitalenzymes,oneforeachsensordirection, foratotaloftwenty-fourdigitalenzymesintherunqueue. Phase3:Respond -Thephaseofacontroller'sexecutioncycleistodetermine theresponseforeachoftheagent'sactuators.Asimulatedagentinthisworkhasfour actuators:turn,movement,color,andsound,illustratedinFigure3.3.DuringtheCompute phase,digitalenzymescanemitmoleculesfromtheirregisterstoanactuator votingbox by executingoneofthe Emit instructions.Thebitssetwithinanemittedmoleculeserveas \votes"fortheactuator'snextbehavior.Eachactionthatcanbeexpressedbyanactuator isassociatedwithaninternaltallywithinthevotingbox.Whenamoleculeisemittedto anactuator'svotingbox,themoleculemappinginFigure3.1isusedtodeterminewhich action(s)arebeingexpressedbythemolecule'ssetbitsandtheirassociatedtalliesarein- crementedbyone.InFigure3.3,anenzymehasemittedamoleculetothecoloractuator's votingboxwithonevoteforboth NoColor andthe Food color,causingtheirinternaltallies tobeincrementedbyone. Attheendofthisphase,amajority-voteprotocolisusedtodeterminethe\winning" actionforeachagent'sactuators.Eachactuator'svotingboxhasasizeof24 moleculesrequiringthesizelimittobereachedinordertoalterthecurrentmajority.Once thesizelimitisreached,anewlyemittedmoleculerandomlyreplacesanexistingonewithin thevotingbox.Thereisnointernalstructureororderingwithinavotingbox,intendedto capturetheBrownianmotionoftenfoundwithinthecytoplasmofbiologicalcells[94]. Toprovideevolutionwithnew,uniquebehaviors,weallowgeneticinformationtobe 43 addedandremovedfromthegenomeviarandommutation.Variousaspectsofthecontroller's designarestaticsuchasthenumberofgenes,thenumberofdigitalenzymesexecutingeach geneintherunqueue,andthedigitalmoleculesthateachenzymereceiveduponstartup. Asaresult,randommutationoccursstrictlyattheinstructionlevel,allowinginstructions tobeinserted,deleted,andmowithineachofthecontroller'sthreegenes(programs). Intheseexperiments,allmutationratesweresetat2%duringevolution. 3.3TheCentral-PlaceForagingProblem Toevaluateourmodel'sdesign,wechoseachallengingversionofthecentral-placeforag- ingproblem[71,101],duetotheuseof unbounded worlds,wherethetaskincludestly searching,acquiring,andreturningresourcestoacentrallocation,suchasahome.Foraging isafundamentalandessentialtaskformanybiologicalorganismsthatalsocontainsanum- berofsharedfeatureswithsimplerlifeproblemssuchaspredator-prey[8],colony migration[28],andtracking/homing[15].Inaddition,evolvedforagingbehaviorsb deployedengineeringsystemssuchassearch-and-rescue[80]missionswheretheresourceis survivorsledtoalocationofsafety,reconnaissance[58]missionswheretheresourceisin- telligenceinformationbeingretrievedtoalocationofdisseminationandtransmissions,or relief[85]wheretheresourceishazardouswastebeingreturnedforcontainment. Thisunboundedcentral-placeforagingproblem[101]removestheaidofaboundary andrequiresagentstoevolvecooperativestrategiesinordertomaintaingroupintegrity,an importantaspectofbothnaturalanddeployedsystems.Forthisproblem,ahomogeneous colonyof6agentsisassignedthetaskofreturning8itemsoffoodtoacentralregioninthe worlddesignatedashome,asshowinFigure3.5.Homeisa5 5areathatisdetectableby boththecolorandobstaclesensorofeachrobot'scontroller.Atthestartofevaluation,all colonymembersarerandomlypositionedandorientedonhome.Todeterminetheplacement offood,eachcontrollerinheritsa ylevel fromitsparentcontrollerduringevolution. Thisylevelcorrespondstotheminimumnumberofunitsawayfromhome'sperimeter 44 thatfooditemswillbeplaced.Atthestartofevolution,eachcontrollerbeginswitha ylevelof1where,minimally,onefooditemis1unitfromhome'sperimeter.Theonly remainingconstraintonfoodplacementisthatallitemsmustinitiallyresideasacontiguous \clump."Althoughthisconstraintmayappeartomaketheproblemeasier,itspurposewas toproduceaselectivepressureforcooperationbetweenindividualsinthecolony.Tobecome theoptimalstrategyinthissetup,acontrollermustcooperativelyworkwithinthecolonyto exploretheenvironment,maintainhome'sposition,andcommunicateknowledgeaboutthe locationoffoodtoothermembersformaximumduringforaging. Colonymembersareexecutedusingafairschedulingalgorithm,andeachmemberis givenamaximumof600movestoperformtheforagingtask.Aftereachexecution,theagent isalignedtotheappropriatedirection,emitsthechosencolorandsound,andperformsits movementactuator'sassignedmovement.Movementfromtheagent'scurrentpositioncan beachievedbymovingineithertheforwardorreversedirection.Foodthatisdrivenoveris immediatelyacquiredbytheagentregardlessoftheoriginatingmovement.Eachagenthas acarryingcapacityofonefooditem,andonceanitemisinpossession,remainingfooditems becomeobstaclesthatmustbecircumvented.Incontrastto Forward and Reverse ,the Drop actionelicitsnomovementbutinsteadplacesthefooditeminthefacinggridcell,provided itisnotoccupied.Onceafooditemisplacedonhome,theitemiscountedandremoved fromtheworldtoalleviatethenecessityofapackingstrategy.Soundandcolorsensorswere capableofdetectingstimuliwithina3unitradiuswhiletheobstaclesensorcouldonlydetect stimuliimmediatelyadjacenttotheindividual. Ifacontroller'sstrategyledtoasuccessfulforageofall8fooditems,thenthe cultylevelforfoodplacementisincrementedby1unitandinheritedbyallspring.An unsuccessfulforageoflessthan8fooditemsleadstoadecrementof1unitoftheinherited ylevel.Usingthisdesign,eachcontroller'senvironmentalcomplexityistailoredto thesuccessofitslineage'sstructureratherthanthesuccessofthebestcontrollerstructure inthepopulation. 45 Fitness=(food foraged y)+(1 : 0 cycle finish cycle max ) (3.1) Fitnessisassignedbasedonthenumberoffooditemssuccessfullyreturnedtohome asshowninEquation(3.1).Eachreturnedfooditemcarriesatnessrewardequivalentto thespdistanceatwhichtheclumpwasplaced,therebyselectingforstrategiesthat canforagemoreelyatfartherdistances.AsshowninFigure3.5,eachitemoffood successfullyreturnedtohomeincreasestheorganism'sby6.Thefractionofremaining moves,afterall8fooditemshavebeenforaged,isalsoaddedtohelpdistinguishthemore tcontrollerstrategieswithinapopulation. Figure3.5:Anunboundedworldwherefoodisplaced6unitsfromhome'sperimeter,corre- spondingtothecontroller'scurrentylevel 46 3.4ExperimentalSetupandResults Inthissection,wediscusstheoriginalDZmodel'sperformanceusinga static genomein evolvingsuccessfulstrategiesfortheforagingproblemandalsoprovideadetaileddescription forseveralofthemostinterestingevolvedstrategiesthatincludecomplexbehaviorssuch as:(1)swarming,(2)coordinatedmovement,(3)communicationofconceptsviaaprimitive languagebasedonsoundand/orcolor,(4)cooperation,and(5)divisionoflabor. Ineachrunofourexperiments,apopulationcontaining500digitalenzymecontrollers evolvedfor1000generationswheretournamentselectionusing5randomindividualsprovided theingforthenextgeneration.Betweengenerations,eachcontrollerwasevaluatedasa 6-memberhomogeneouscolonyontheforagingproblemdiscussedinSection3.3todetermine thecontroller'stness.Afterarunwascomplete,eachgenomeinthegenerationwas testedon100randomfoodplacementsatincreasingdistancesfromhomeuntilthecolony wasnolongerabletoreturnasinglefooditemataparticulardistance.Theaveragenumber offooditemssuccessfullyforagedandreturnedtohome,bythedominantgenomesineach populationoftheoriginalmodel,isshowninFigure3.6. Uponglance,theseresultssuggestedthat\good"foragingbehaviorswerenot presentinthesegenomes,giventhatforagingsuccessreducedto50%whentheplacement distancereached5unitsfromhome'sperimeter.However,furtheranalysisrevealedseveral interestingbehaviors,asdescribedbelow.Inordertoassesswhetheraforagingstrategy waspresentinthegenomes,wevisuallyinspected100foragingattemptsmadebyseveral ofthecoloniesandfoundtheresultssurprising.Evolvedstrategiesoftenincludedoneor moreofthefollowingbehaviors:(1)swarming,(2)coordinatedmovement,(3)communica- tionofconceptsusingaprimitivelanguagebasedonsoundand/orcolor,(4)cooperation, (5)divisionoflabor,andbehaviorstermedas(6)\smart"behaviors.Examplesof\smart" behaviorsincludeextendingthenotionof\home"throughcolor,increasingthedetection rangeforfoodbydispersingpartoftheclumpoutward,andbriefdasheshomeinsearch oflostgroupmembers. 47 Duetothelimitednumberofcolorsandsoundsthatcanbeemitted,especiallythosenot alreadyemittedbyobjectsintheenvironment,manyoftheevolvedstrategiesweresimilar intheirbehavior.Below,weprovidedetailsfortwoofthemostsuccessfulstrategiesthat usedcolorasameanstoconveytwotconceptstotherestoftheirrespectivecolonies. InbothFigures3.7and3.8,anarrowrepresentsanagentandthedirectionitiscurrently facingintheenvironment.Thecolorofthearrowindicatesthecurrentcolorbeingemitted whileacirclearoundanagentindicatesthattheagentisemittingasound. Figure3.6:Comparisonofthelevelofachievement(averagethatevolvedcontrollers reachedasfoodwasplacedfartherfromhome'sperimeterwiththeoriginalmodel(DZ) illustratedbythegreenlineanddynamic(DDZ)modelbytheredline. 1. TheRedArmStrategy -Intheevolvedstrategy,termed TheRedArm ,each 48 agentcontinuouslyemits Sound1 andthe Home colorwhilenotinpossessionofafood item,asshowninthetop-leftpaneofFigure3.7.Swarm-likebehavioristhenexhibited asagentsremainwithincolordetectionrangeofobjectsemittingthe Home colorand extendoutintotheworldasaredarm.Thisbehaviorallowsagentstoextendthe notionof Home furtherintotheenvironmenttoguideoneanotherbackto Home as wellasremainneartooneanotherastonotgetlost.Asthegroupofagentsmoves throughtheenvironmentaroundhome,anagenteventuallydetectsthepresenceofa nearbyfooditem,immediatelydetachesfromthegroup,andmovestowardthefood clump.Uponacquiringanitemoffood,theagentimmediatelychangesitsbehaviorto remainstationaryandblinkrapidlybetweenthe Home (red)colorand Neutral (green) colorshowninthetop-rightpaneofFigure3.7.Overtime,theremainingagentsfound intheredarmenterwithindetectionrangeofthoseagentswhohaveacquiredfoodand detachcompletelyfromhome(bottom-left).Inmostcases,anindividualremainednear homeroamingtheperimeterandmakingsmalldasheshomeinsearchofothersand subsequentlyextendingthenotionofhomefurtherintotheenvironment.Theforaging partyprogressivelymovedtheremainingfooditemsintheclumptowardsthegeneral directionofhomeonceitwasdetectedagainandsuccessfullycompletedtheforage. Figure3.7:The\RedArm"StrategywhereagentsworktoextendthenotionofHome. 49 2. TheGreenArmStrategy -Inthesecondevolvedstrategy,termedthe GreenArm strategy,eachrobotcontinuouslyemitsthe Neutral (green)colorwhilesearchingfor foodintheenvironment,whethernearorawayfromhome.Individualagentsevolved toremainnaturallyattractedtothe Neutral coloremittedbyoneanother,allowing thecolonytoexhibitswarm-likebehavior.Whenanindividualagenthasdiscovered food,itchangesitsbehaviortoemitthe Food (blue)colorandremainblueuntilthe fooditemwasdropped,asshownontheleftofFigure3.8.IncontrastwiththeRed Armstrategy,anagentpossessingfooddoesnotidlysitinplacewhileemittingits colorbutrathertheagentpicksupanddispersesitemsoffood.Thisbehaviorallows agentstoextendthenotionof\food"intheenvironmentratherthanthenotionof \home"shownpreviously.Agentswhohavenotdetachedfromthecolonyremain circlingaroundhometogetherinsearchofthe Food colorbeingemittedfromthe environmentactingas\lookouts".Whenanagentinpossessionoffooddetectseither the Neutral colorfromalookoutagentorthe Home color,itisthenabletohome andsuccessfullyreturntheitemoffood. Figure3.8:The\GreenArm"StrategywhereagentsworktoextendthenotionofFood. 50 3.5RelatedWork Inthissection,weoverviewresearchrelatedtoinstruction-basedtechniquesincluding AvidaandGeneticProgramming(GP)toprovidecontrastforourmodel,spthose relatedtoparallelanddistributedcontrol.Next,wediscussthechallengesofadistinct computationalmodelofparalleldistributedcontrol,alneuralnetworks.Finally,we provideanoverviewofrelatedresearchinstate-basedandrule-basedsystemsincluding statemachines,cellularautomata,andmembranecomputing. 3.5.1Avida Theinstruction-basedtechnique,Avida[83],isadigitallifeplatformaimedtoallow scientiststostudyandtestevolutionaryhypotheses insilico inordertogaininsightand understandingofevolutioninnature.InAvida,apopulationof self-replicating individuals, termed\digitalorganisms,"areevolvedoveranumberofgenerationstoperformcomputa- tionaltasksinaenvironment.Apopulationconsistsofanumberofcellswhere eachcellcontainsadigitalorganismcomprisedofacircularlistofinstructions(genome) andvirtualhardwareuponwhichthoseinstructionsexecute.Thevirtualhardwareofan organismconsistsofthreeregisters(AX,BX,andCX),twostacks,aninstructionpointer indicatingthecurrentinstructionbeingexecuted,andanadditionalheadthatcanbeused foralteringexecutionowtoanarbitrarypointinthegenome.TheinstructionsetinAvida isTuring-Complete,makingitimpossibletoconstructansyntacticallyincorrectgenome, andcontainsoperationsforarithmetic,bitmanipulation,conditionalbranching,looping,as wellasregister,stack,andinstructionheadmanipulation.Inaddition,manyresearchers whouseAvidacanaddinstructionstothissetthataretailoredtothespproblem underinvestigation. Unlikeotherevolutionarycomputationapproaches,Avidadoesnotuseatraditional function.Instead,organismsearnvirtualCPUcyclesasarewardfortheirabil- itytosuccessfullyperformacomputationaltaskintheenvironment.Taskscaninclude 51 aninput/outputinterfacewiththeenvironment,interactionswithotherorganisms,orany formofphenotypic,observablebehavior.ThesevirtualCPUcyclesareexpendedduring executionasanorganismexecutesinstructionsrelatedtothecompletionoftasksaswell as self-replication .Self-replicationisoneofAvida'stenetsthatseparatesitfrommany otherevolutionarycomputationtechniques.ThedigitalorganismsinAvidaexecuteasyn- chronouslyfromoneanotherandcanreplicateoveranotherindividualinthepopulation dependingonseveralfactorssuchasthevirtualCPUresourcesanindividualhasacquired throughthecompletionoftasks,varyingcostsofinstructionexecution(ifspgenome size,andothers.Withinanorganism'sgenomeliesasequenceofinstructionsthatisin chargeofcreatingareplicategenomeforitsg,dividingthenewlyallocatedgenome fromtheparent,andoverwriting(terminating)anexistingorganismelsewhereinthepop- ulationwhenreplicationiscomplete.Insertion,deletion,andpointmutationsoccurduring thereplicationprocessinordertointroducenewbehaviortothepopulation.Inorderto gainanadvantageoverotherorganismsinthepopulationandsurvive,adigitalorganism iscontinuouslyinacompetitiontooptimizeitsgenometoremoveunnecessarycomplexity andperformagreaternumberoftasksthanotherorganisms. WhileAvidahasbeenwidelyusedtostudyprinciplesofbiologicalevolutionaswellas producesolutionsforengineeredsystems,webelievethatseveralofAvida'sdesignfeatures presentchallengesforthegenerationofembeddedcontrollers.First,althoughself-replication doesprovideacloseparalleltoreproductionofasexualorganismsinbiology,webelievethat requiringanorganismtomaintainaself-replicatingsequenceofinstructionscanbecomea burdenduringtheevolutionaryprocesssinceanymutationthatdisruptsthismechanismis lethal totheorganism.Instead,ourDigitalEnzymemodelusesthetraditionalapproachof directlycopyingthegenome(aswouldoccurduringself-replication)andafterwardsapplying mutationsinthesamefashionasAvida. Second,organismsinAvidaexecuteandreproduceasynchronouslyfromoneanother basedonvirtualCPUcyclesacquiredduringexecution,mimickingevolutioninnature.How- 52 ever,twosidectsofthisapproacharethatnotallsolutionsaregivenequalopportunity tobeevaluateddependingontheirrelativeamountofacquiredresourceandanindirect selectivepressuremayexisttowardsshorter,moreconcisegenomesthatcanreproducemore quicklydespitehinderingtheevolutionofmorecomplexbehaviors.Tomitigatethesetwo issues,wealloweverycandidatesolutiontobegiventhesameamountofevaluationduring theevolutionaryprocessthatisnotdependentonanyformofresourceacquisition.Using thisapproach,wedonotplaceunwantedselectivepressureonasolution'ssizeorcomplexity astonotbiasorcoerceevolution'straversalofthesearchspace. Third,becausegenomescanbeexecutingatanypointoftheirgenomewhiletheyare interactingwiththeirenvironment,thelevelofresponsivenessrequiredfromtheenviron- mentmaytheamountofinstructionsinthegenomefor\polling"orsensingnew information.Asthenumberofthesesensingregionsincreases,itmaymakeitmore toevolveandmaintainproperdecisionlogicorreplication,placinganunnecessary\cap"on complexity.Toavoidtheenvironmentevolutionarysearchinthisway,eachcon- trollerintheDZmodelisexecutedonacycle(Sense-Execute-Respond)wherethecurrent stateoftheenvironmentisinitiallyacquiredanddoesnotchangethroughoutanexecution cycle.Inaddition,eachexecuting\process"withinacontrollerisrestartedataninitial startingpointinthegenome. Finally,eachdigitalorganisminAvidacomprisesonlyonegenome(program)andone instanceofthatprogramforexecutingitsbehavior.However,innature,evolutionhascon- tinuedtoselectforaframeworkbasedonparallelismandcooperationacrossvaryinglevels oforganizationtodrivebehavior.Ongoingresearchhasdemonstratedthatlife's\program" arisesnotsimplyfromstaticinformationencodedinagenomebutalsofromcomplexinter- actionsorchestratedatthecellularlevel[86]. 53 3.5.2GeneticProgramming Thesecondinstruction-basedevolutionarycomputationtechniqueisgeneticprogram- ming(GP)thatisusedtoevolvecomputerprogramscapableofperformingcomputational tasksbytheuser.Historically,atree-basedencodinghasbeencommonwherea program'sinternalnodescontainanoperatorfunctionandterminalnodescontainoperands suchasvariablesorliterals.Althoughtheseencodingsareeasytoevaluaterecursivelyand amenabletoprogramminglanguagessuchasLisp,severalchallengesexistfortheirusage. First,crossoveramongtwoparental,tree-basedsolutionstoformanis since50%ofthenodesthatcanbeselectedresideintheleaves,whichcanleadtogenetic bloatinthetreedepth.Arbitrarylimitsonatree'sdepthandpruningareoften usedtomitigatethisissuebutaresubjecttohumanbias.Inaddition,thediversityoftree types(fulltreesvs.growtrees)inthestartingpopulationcanalsotlythe successofevolutionarysearch.Inresponsetotheseissuesrelatedtotree-basedencodings,al- ternativeencodingssuchasLinearGeneticProgramming,CartesianGeneticProgramming, andothershavebeendeveloped.Therefore,wefocusthemajorityofourliteraturereview inthisdomainonnon-tree-basedencodings,spthosethatincorporateaspectsof parallelismandcooperativecontrol.Withrespecttotheevolutionofparallelprograms, avarietyofapproachesexistintheareaofgeneticprogramming[9]includingCartesian GeneticProgramming[77,106],ParallelDistributedGeneticProgramming[89],Genetic ParallelProgramming[23],andConcurrentGeneticProgramming[102]. InspiredbyMinsky's SocietyofMind [78]proposition,whichstatedthatanindividual's mindiscomposedofmanysmallerprocesses(agents)workingtogether,Bennet[9]allowed theactionsofsimulatedanttobegeneratedthroughamulti-agentarchitecture,whereeach agentwasastandardtree-basedGPoftheformdevelopedbyKoza[71].Incontrasttothis approach,ourdesigndoesnotrelyontree-basedrepresentationsbutinsteadusesacircular taperepresentationasinAvida[83]andisafully-functioningvirtualCPUmaintainingstate. Moreover,theinstructionsetofBennetishighlycoupledwiththeforagingproblemused 54 toevaluatetheirsolutionswhereasourapproachfocusesonmappingstimuliandactuation optionsintothebitsandvaluesofbitstrings,thusremovingthiscouplingbetweenthesystem anditstargetproblem.Asimilartree-basedapproachusingcrossoverhasbeenexploredin arelatedareaofGPreferredtoasConcurrentGPbyTrenaman[102]whereinterleaved programtreesstoreandretrieveinformationfromasinglesharedmemoryarea. InamorerecentareaofGP,Walker etal. [106,105]haveusedCartesianGeneticPro- gramming(CGP)[77]developedbyMiller etal. forevolvingdigitalcircuits.InCartesian GeneticProgramming,thegeneticprogramisrepresentedasatwo-dimensionalCartesian gridofnodesconnectedthroughfeed-forwardconnectionswithoneanothertoforman acyclic,directedgraph.Inputspropagatefromoneendofthegraphthroughdownstream nodescontainingmathematicaloperationsthat,inturn,manipulatetheirinputsfromcon- nectionsandpasstheircomputedvaluesfurtherdownstreamtowardsoutputnodes.Walker etal. extendedthisdesignbyallowingmulti-chromosomalevolutionwhereeachindividual's genomecontainsmultiple,parallel-executingCGPswhosenumberisdeterminedbythenum- berofprogramoutputsrequiredbytheproblem.Inourmodel,eachgeneticprogram(gene) isadynamicandextendablecirculartapeofinstructions,ratherthanthetwo-dimensional representationrequiringalength,width,andnumberoflevelsbackacon- nectingnodecanreside.Inaddition,ourinstructionsetsupportsbranchingandlooping operationsandaricherstatetobemaintainedbyeachenzymethatwasnotsupportedin theirCGPs.Lastly,weremovedtheconstraintofmatchingthenumberofprogramstothe numberofprogramoutputs,namelythenumberofsensorsintheoriginalmodel,allowing thenumberofprogramstomutateandwereabletoevolve moresuccessful solutionsasa result.Despitetheseerences,Walker etal. didnotethattheirmulti-chromosomalevo- lutionallowedthemtosolveproblemswhichtheywouldnothavebeenabletosolvewith asinglechromosomeapproach,thushighlightingtheimportanceofmodelsallowingamore dynamicgenome. InarelatedofGP,Poli[89]hasdevelopedparallelanddistributedgeneticprogram- 55 ming(PDGP)whereeachgeneticprogramisagraphwhosenodescontaineitherfunctionsor terminalsresidinginamulti-dimensionalspace.SimilartoCGPs,controlandresultsw" alongthedirectedlinkswithinthisgraphtoconnectednodesprovidinglessconstrainton theprogram'sstructureandmoreyforthereuseofmoduleswithinthegraph.How- ever,aswithCGPs,thedimensionsofthemulti-dimensionalspacetheseprogramsresidein areandthroughoutevolutionwhereasthegenomesinourmodelcangrow unboundedduetoaselectivepressureformorespace.Aswithpreviousrelatedwork,theter- minalsandnodesfoundwithintheirgeneticprogramsareheavilyproblem-spwhereas ourinstructionsetcloselyalignswithaprimitiveassemblylanguageallowingfortheease oftransferontoreal-world,embeddedsystems.Inaddition,Polialsouseshighlysp hand-designedcrossoveroperationsduringreproductionwhereasweavoidthisevolutionary operatorduetoitsoftendisruptive[3,38]insexuallyreproducingsystems. 3.5.3Neuroevolution Inourfocusonparallelgeneticprograms,oneevolutionarycomputationtechniquewe mustpointoutisevolving neuralnetworks (ANNs)[111,112]alsoreferredto asneuroevolution.Withapplicationsinclustering,functionapproximation, controlsystems,andvariousothers,ANNshavebecomewidelyacceptedasa powerfulcomputationalsystemformanytproblems.ANNshavebecomeespecially popularinroboticcontrolsystemsduetotheirfaulttoleranceandresiliencytonoise.Unlike traditionalsymbolicandlogic-basedsystems,ANNsaremassivelyparallelsystemswhose \program"isnotexplicitlycodedintothenetwork.Instead,theirprogramisadaptedover time,arisingthroughtheprocessofevolutionbynaturalselection. AsshowninFigure3.9,anANNcanberepresentedbyadirectedgraphwherenodesand edgesinthegraphcorrespondtoindividualneuronsandsynapses,respectively.Tomaintain continuitywiththeapplicationofANNsascontrollers,neuronsthatgatherenvironmental informationarereferredtoas sensoryneurons andneuronswhoseoutputcorrespondstothe 56 system'soutput(i.e.,actuators)arereferredtoas motorneurons .Thesensoryneuronsin Figure3.9aredenotedashollownodesbecausetheystrictlyforwardinformationfromthe environmentwithoutapplyinginternalfunctionstotheirinput.Betweenthesensoryand motorneuronsoftheANNlietheinternalprocessingneurons,orfeatureextractors,often referredtoasthe hiddenneurons . Figure3.9:Themaincomponentsofanneuralnetworkincludingsensoryneurons whereinputsarereceived,hiddenneurons,andmotorneuronswhereoutputsignalsare returned. InFigure3.10,wethatthebasiccomponentsusedbyanlneurontoexecute are:(1)inputs,(2)synapseweights,and(3)outputs.Aneuronsinputsconsistofthe individualvaluesthathavebeensentbyprecedingneuronsintheANN.Theseinputstravel alongasynapsethatmaintainsaweightvalueindicatingthesynapse's\strength."Execution ofanneuroncomprisestwophases,summationandactivation/output.Duringthe phase,summation,eachinputvalueismultipliedbyitssynapse'scorrespondingstrength andsummatedwiththeinput-weightproductsofotherincomingconnections.often,an additionalvaluecalleda bias isusedtoraiseorlowerthissummatedvaluefurtherbefore enteringtheactivationfunction.Thebiasisaninputpresenttoeveryneuroninthesystem whoseinputvalueistypically-1.Neuronscantailorthebias'sstaticvaluetoincreaseor decreasetheirthresholdbyadjustingitsedge'scorrespondingweightandsign. Inthesecondphase,thesummationofallinput-weightproductsincludingthebias, 57 Figure3.10:ThemaincomponentsofanindividualneuroninanANNincludingweighted inputsandbiaspassedintoasummationand/oractivationfunctionthatemitsitsoutput signal. producesatotalsum( v i )thatispassedintoanactivationfunction,showninFigure3.10 andEquation(3.2).Anactivationfunctionprovidesameanstomapthewide-rangingvalues ofthesumintoanoutputvaluethatishard-limitedwithinacertainrange(ex.[0,1]or[- 1,1])andproducednonlinearly.Activationfunctionsarenotprohibitedfromusinglinear activationfunctions,however,doingsolimitstheirperformancewhenappliedtoproblems requiringnonlinearfunctionorapproximation.Althoughmanytypesofnonlinear activationfunctionsexist,themostcommontypearesigmoidalfunctionswhosefamiliar S-shapedcurvecanbeshapedwitha\slope"parametertotakeonpropertiesofother activationssuchasstepandlinearfunctions.Theoutputoftheneuron'sactivation function( y i )maybeusedasinputstootherneuronsinthenetwork. y i = n X j =0 w ij x j ) (3.2) Anneuralnetwork's architecture referstotheneuronsandhowtheyareinter- connectedwithoneanotherviadirectedsynapses(topology)aswellastheactivationfunc- tionsfoundwithintheneurons.Architecturescanbeintotwobroadcategories: (1)feedforward{directedacyclicgraphs,and(2)recurrent{wherecyclesofsynapsesare 58 allowedtoforminthenetwork.ThesecyclesproviderecurrentANNswiththepowerful capabilityofprocessingresidual,internalstateinformationofthenetworkfromprevious executions.Inthisway,neuralnetworksexhibit\controlthroughcommunication," [14,93]byoperatingasaparallel,distributedsystem.However,asdescribedbyYao,thear- chitectureofanialneuralnetworkisstrictlyits\hardware,"butthewayinwhichthe weights,outputs,andinteractionsbetweenneuronsorchestraameaningfulresultfromthe ANNisthe\software"thatmustbelearned[111].Althoughconvergenceandhomogeneity canbeanissue,tunableparametersandspeciallydesignedoperators,suchasthosefound inNEAT[100],canbeusedtohelpdiversifythesearch. Althoughfaulttolerantandresilienttonoiseduetotheirdistributednature, neuralnetworksareoftenreferredtoasa\blackboxtechnique"sinceanevolvedsolution existsinanunfamiliarformatthatdoesnoteasilylenditselftohumanunderstanding. SincelimitedknowledgecanbeextractedfromanevolvedANNsolution,vand developinganintuitionfor how itfunctionsisThislimitedunderstandingalso makesittodeterminewhatadditionalinfrastructureormomightaid inproducingbettersolutions.Moreover,arneuralnetworkscanbeacomputational burdenonembeddedsystemsthatdonotgpointsupport.Intheourmodel, wefocusontheuseofassembly-likeinstructionstomoveclosertowardsunderstandingan evolvedsolutioninordertopotentiallyabstracttheevolvedmechanismsintohigh-level modulesaswellasdeterminestructuresthatmightaidevolutionarysearch. 3.5.4FSMs,Cellular-Automata,andMembraneComputing Inadditiontoinstruction-basedtechniques,wealsosurveytheareaofstate-basedap- proachesforcomparisontoourmodelincludingstatemachines(FSMs)[73,21],cellular automata(CA),aswellasmembranecomputing(P-systems). Amachineisanabstractcomputationalmodelrepresentingthebehavior ofaprogramorlogiccircuitasanumberofstates(modes)thatcanbereached 59 viatransitions.Uponinitialization,theprogrambeginsinaninitialstateawaitingthe occurrenceofatriggeringeventthatwillallowittotransitiontoanewstate,barringthat conditions(guard)onthetransitionareAseventsoccurduringexecutionand theFSMtransitionstonewstates,theprogram'sbehaviorisguidedbythesetofallowable eventsfromtheprogram'scurrentstateandtheproperresponsesforthoseevents.The maindisadvantagefortheuseofFSMsascontrollersisthattheyhavelimitedmemoryin comparisontoothercomputationalmodelssuchasTuringmachines.AFSM'scomputational \power"isrestrictedbythenumberofstatesinthemodel. Similarly,acellularautomaton[109,98]consistsofamultidimensionalgridofcellsthat eachareinoneofanumberofstatesthatprogressoveraseriesofdiscrete timesteps.Initially(time=0),eachcellofthegridstartsinaspstate.Astime isincremented,eachcelldeterminesitsnewstatebasedonasetofrulesthatgovern theirbehavior.Sincethecellsresideinamultidimensionallattice,eachcellissurrounded byasetofothercellsreferredtoasits neighborhood .Basedonthestateofcellsfoundin theneighborhood,thecurrentstateoftheobservedcell,andwhichoftherulesare theobservedcellupdatesitsstate.Typically,therulesforupdatingacell'sstate doesnotchangeovertimeandisappliedgloballytotheentiremultidimensionalgridofcells. Lastly,extensionswithinmembranecomputing(P-systems)[90]usingquorum[10]and X-machines[50]sharethemostsimilaritiestotheDZsystem.ThegeneralP-systemdesignby GheorghePaunwasdevelopedtodiscoverthepowerofadistributed,parallelcomputational modelbasedonbiologicalcellsandtheirencapsulatingmembranestructures.Inthismodel, ahierarchicalarrangementofcompartments(membranes)containbothproductionrulesand amultisetofsymbols.Eachmembrane'smultisetkeepstrackofthesymbolsandquantityof eachsymbolwithinthemembraneduringexecutionaswellaspointerstomembranesthatare encapsulatedwithinit.Inaddition,eachmembranecontainsasetofproductionrulesthat are\triggered"byacombinationofsymbolsresidinginthemembrane.Theproductionrule \consumes"thesesymbolsfromthemultisetandproduces\product"symbolsthatcanbe 60 emittedwithinthecurrentmembraneortoothermembraneswithinthesystem.Production rulesareexecutedinparallel,providingadistributedcontrolmodelwhereinputsymbols areinjectedandoutputsymbolsreleasedattherootmembranewhichinterfaceswiththe environment. Unlikestate-basedapproachesthatuseFSMsorcellularautomata,thecomputational entitiesintheDZmodeldonotcontainstatesandmaintaintheirownvirtualCPU thatexecutesinstructionsfromaTuring-Completeprogramminglanguage.Eachagent's stateisdynamic,constantlybyhigh-levelinteractionswiththeenvironmentand othercolonymembersaswellaslow-levelinteractionsamongparallel,executingprograms. Ratherthanusingrulestomapbetweeninputsandoutputs,thedigitalenzymeapproach isbuiltonoperationsthatreducethenumberofelementsneededtoencodeaparticular function.Inaddition,thenumberofinternalentitiesusedtocontrolagentsintheDZ modelisnotlimitedandcanevolvefreely,allowinginternalcooperationtoguideanagent's response. 3.6Discussion Inthischapter,wehavepresentedtheDZcomputationalmodeltoevolvebottom-up, reactivecontrollersbasedonaframeworkofdistributedcontrolviaparallelinteractionsand inspiredbytheroleofsignaltransductionandenzymesinbiologicalcells.Thismodelwas designedtoaddressuncertaintyintheproblemdomainandkeychallengeswithrespectto theapplicabilityofinstructionsandtimingdependencieswiththeenvironment.Bymapping aspectsoftheenvironmentandsystemintomanipulablebitstrings,ratherthantheinstruc- tionset,ourmodel'sinstructionsetcanassembleandrepurposeinformationwhileremaining compact,independentoftheproblemdomain,andrealizable.Inaddition,ourmodelensures thatthemostrecentstateoftheenvironmentisavailablethroughouttheexecutionphaseof thecontrollertherebymitigatingtimingdependencieswiththeenvironment.Evaluationof ourresultsrevealedthesuccessfulevolutionofcomplexbehaviorsincluding:(1)swarming, 61 (2)assignmentofmeaningtocolor,sound,andmovement,(3)communicationof\concepts" viasimulatedactuators,(4)cooperationbothwithintheentitiesofacontrolleraswellas amongthemembersofacolony,and(5)assignmentofroleswithinacolony.Theseresults revealthat\geneticinformation"maybecapturedina\hidden"layerofparallelinteractions inaddition totheinstructionsfoundwithinthegenome. 62 Chapter4 UncertaintyintheSolutionSpace Uncertaintycanalsoariseinthe spaceofsolutions reachablebyanevolutionarysearch technique.InadditiontoourDigitalEnzyme(DZ)model,alternativebio-inspiredsearch techniquessuchasneuralnetworksexploreparallelanddistributedcomputation whereanevolvedprogramarisesoutofaninterconnectednetworkofprocessingunitscom- municatingviaweightedconnections.Althoughfaulttolerantandresilienttonoisedueto theirdistributednature,limitedknowledgecanbeextractedfromanevolvedANNsolution forvordevelopingandintuitionfor how itfunctionssinceitslogicresidesinits connections,weightvalues,andthresholdfunctions.Thischallengeinvolvingthetraceabil- ityofevolvedsolutionlogicmakesittodeterminewhatadditionalinfrastructureor momightaidinproducingbettersolutions. Moreimportantly,theinternaldecisionprocessusedtotranslateenvironmentalinfor- mationintomeaningful,robustbehaviorsisoftena blackbox designquestion,asshown atthetopofFigure4.1.Whilesensinginformationfromtheenvironmentandactivating actuatorsarerelativelystraightforwardtasksforembeddedcontrollers,thedesignusedto implementacontroller'sdecisionlogiccantakeonavastnumberofpossibilitieswithre- specttothenumberofparallelprograms(P)andthenumberofthreads(T)executingeach parallelprogram.Howshouldthedecisionlogicbeimplementedwithinthecontrollerwith respecttothesetwovariables?Shouldcontrolbemanagedbyoneexecutingthreadofone program(a 1:1 design),manyexecutingthreadsofoneprogram( T:1 ),oneexecutingthread 63 Figure4.1:Atypicalembeddedsystemcontainingsensorsandactuatorsinteractingwiththe environmentwhereabroadrangeofcontrollerdesignsarepossibletoproducethedesired systembehavior,rangingfromsingle-program-single-instancedesigns(1:1)tomulti-program- multi-threaddesigns(T:P). ofmanytprograms( 1:P ),ormanyexecutingthreadsofmanytprograms ( T:P )?Ofcourse,thesedesignsareonlykeytransitionpointsalonganentirespectrum towardsmoredistributedcontrol,asshownatthebottomofFigure4.1.Advantagesand disadvantagesintermsofhumandesignrtsandperformanceexistalongthis spectrum.Forexample,the1:1controllerdesignispervasivebecauseadeveloperisnot burdenedbysynchronizationortheoverheadrequiredtosupportparallelexecution,suchas memoryandthreadinglibraries.Ontheotherhand,parallelismandmultithreadingmight greatlyenhancefunctionalityandimproveperformance.However,ascontrollercomplexity movesfarthertotherightalongthisspectrum,itbecomesmoreltfordevelopersto conceptualizethedecisionlogicwhilealsoprovidingbqualitiessuchascoopera- tion,robustness,faulttolerancy,and,especiallywhenapplyingatop-downdesign approach. Inthischapter,wediscusshowweaccommodateuncertaintyinthesolutionspacewith respecttointernalcontrolstructure.Sp,Section4.1introducesourDynamicDigital 64 Enzyme(DDZ)modelthatrelievesconstraintsonourinitialmodelinordertosupporta dynamicgenomeandprovideanopen-endedevolutionarysearchspace.InSection4.2,we isolatethreemainfeaturesofourmodelthatunderwentrevisionanditeratethroughall possiblecombinationsofeachfeatureimplementationsandquantifytheiron Inthiscomprehensiveexperiment,wedemonstratethatourreviseddynamicmodelisable toaccommodateformoreuncertaintyinthesolutionspaceandperformsequallyaswellor betterthanmodelsrestrictingthesolution'sdesign. 4.1TheDynamicDigitalEnzyme(DDZ)Model Thissectionintroducesthe DynamicDigitalEnzyme (DDZ)model[18]designedto overcomeseveralshortcomingsofourinitialDZmodelandprovideopen-endedevolution withrespecttothenumberofprogramsandenzymesusedforcontrollinganagent. InourDZmodel,weprovidedacontrollerwith3genes,eachgenetocontainthe decisionlogicforoneoftherobot'ssensors.Inaddition,eachcontrollercontainedatotal of24parallel-executingdigitalenzymes,oneforeachofthe8sensingdirectionsinthe3 sensors.AlthoughbehavioralanalysisandvisualizationofevolvedstrategiesinourDZmodel revealedthatcomplexbehaviorsdidevolve,bystudyingtheirevolvedgenomes,weobserved thattherewereinstanceswhere(1)no Emit instructionswereexecutedinaparticulargene, (2)anenzymewouldexecutea Halt instructionwithoutemittingamolecule,or(3)an enzymewouldloadamoleculecontaininginformationfromatsensor.Eachofthese observationsrevealedthatourinitialassumptionsaboutthenumberofgenesandenzymes orhowtheywouldinteractwiththeenvironmentwereincorrect. Wehypothesizedthattheinternalstructureofthesecontrollers,containinghumande- signconstraints,mightbehinderingtheevolutionofmoresuccessfulcontrollers.Torelieve theseconstraintsandaccommodateuncertaintywithinthesolutionspace,weintroduceour newDDZmodelthatallows(1)thegenomeand(2)therunqueuecompositiontobe dy- namic ,startingasasinglegene,singleenzymecontrollerandbecomingmorecomplexover 65 timeduetorandommutation.Sp,intheDDZmodel,thegenomeandrunqueue structuresundergothenaturalprocessesofmutationinordertoallowthenumberofgenes, instructionswithineachgene,andthenumberofenzymesexecutingeachgene,tovary asshowninFigure4.2.Insertion,deletion,andpointmutationsoccurateachlevel:the gene-level,theinstruction-level,andtheenzyme-level. Figure4.2:Adetailedviewofthecomponentsusedineachphaseofthenewdynamicdigital enzyme(DDZ)controllerwheretheinternalcontrolstructurecanfreelyevolveovertime. Through[100],solutionsstartinalowerdimensionalsearchspaceand canbecomemorecomplexovertimewithregardstotheirinternalcontrolstructure.Inthe DDZmodel,eachcontrollerbeginsasasinglegene,singleenzymecontrollerwhosesingle geneisconstructedofneutral NoOperation (\ NoOp ")instructions.Whenacontrolleris selectedtoreproduce,insertionanddeletionmutationsoccuratthegeneleveltoadd 66 orremoveprogramsfromthegenome.Whenagene-levelinsertionoccurs,thereisa50% probabilitythatanexistinggenewillbecopiedintothegenome,otherwise,a\blank"gene comprising\ NoOp "instructionsisused.Ifadeletionmutationoccursatthegenelevel, thenthegeneandalldigitalenzymesexecutingitsprogramareremovedfromthecontroller. Next,theinsertion,deletion,andpointmutationsoccurattheinstructionleveltoadd, remove,oralterinstructionswithineachgene.Finally,thesethreemutationsareapplied oncemoreattheenzyme-leveltoaddandremovethenumberofthreadsexecutingand expressingeachgene.Thepointmutationattheenzyme-levelalsodictatesifanenzymeis initializedwithadigitalmoleculefromoneofthecontroller'ssensorsinordertotiate itsexecutionfromotherenzymesofitstypewithintherunqueue. Byallowingthegenomeandrunqueuetobedynamic,anycombinationofthenumberof genesanddigitalenzymescouldariseduringevolutionthusrequiringachangetothevoting boxdesignforeachactuator.IntheoriginalDZmodel,thenumberofmaximumvotes containedwithinavotingboxwasdeterminedbythenumberoftotalenzymesexecutingin thecontroller'srunqueue.However,wesuspectthatthisdesignmadeitmorefor mutationtoproducenovelstrategiesbyrequiringanumberofmutationstooccurtogether inordertoalteranexistingevolvedstrategy.TheoverallintheoriginalDZmodel designisanalogoustoplacingarut,ordepression,aroundanevolvedstrategyinthe landscape,makingitmoreforthestrategytomutatetoaditlocationand discovernewbehaviors.Asaresult,weimplementedacontrolstructurethatcould balanceandadapttocompetingconcernsforprovidingbothdistributedandprioritized controlovervarioussystemactuators.TopermitdistributedcontrolintheDDZmodel,an actuator'svotingboxnolongerhasacapacitybutinsteadisdynamic,thusallowing anynumberofemittedvotestobeusedfordeterminingtheactuator'sresponse.Toprovide prioritizedcontroloveranactuator,wealsoimplementeda Clear Voting Box instructionthat, whenexecutedbyaparticularenzyme,removesalldigitalmoleculevotesfromtheselected actuator'svotingbox.Enzymesmustinternallycooperatetousethesecapabilitiesinorder 67 toprovideasuitablecontrolstrategyforeachactuatorsincetheunitofselectionduring evolutionisthecollectionofenzymescontainedwithinacontroller'sgenome. ThelastfeaturerevisedinthenewDDZmodelinvolvedchangingdirectionsinboththe sensorsandactuatorsfromanabsolutereferenceframe( North , Northeast , East ,etc.)toa relative referenceframe( Front , Front-Right , Right ,etc.).Thismowasintendedto allowthecontrollertobaseitsdecisionsaconstantdirectionrelativetotheorientationof therobotsimilartowhatoccursinnatureratherthanadirectionintheenvironment thatrequiresglobalinformation.Inaddition,thismoalsomakestheproblemmore challengingbyremovingtheabilityforarobottoalignitselftoanabsolutedirectionsince itsinitialorientationisrandomlyassigned.Next,wedescribeexperimentalresultsofthe DDZmodelandadditionallyprovideacomparisontotheDZmodel. 4.2Empirical-BasedModelComparison Inthissection,weempiricallycompareagents'performancewhenusingtheDZmodel andDDZmodelsontheunboundedcentral-placeforagingproblem,discussedinSection3.3, andperformacomprehensiveanalysisoftfeaturecombinationsinordertodetermine themaincontributortoagentperformance.Inparticular,wewereinterestedindetermining howwellouropen-ended,dynamicgenomewasabletocopewithuncertaintyinthesolution spacewithrespecttointernalcontrolstructure. ThreekeyfeaturesoftheDZmodelwereisolatedinordertoevaluatealternativedesign implementationsandtheirimpactonperformanceintheforagingproblem,namely,(1)the actuationfeature,(2)genomefeature,and(3)directionfeature,asshowninFigure4.3.For the actuation feature,threettypesofimplementationwereevaluated:(1) dynamic voting -nomaximumcapacityonvotingboxsize,(2) dvoting -votingboxcapacitywas cappedat24votesrequiringrandomreplacementoncecapacityhasbeenmet,and(3) single vote -thevotingboxstoredthemostrecentlyemittedmolecule.Thesinglevoteoption wasusedtocompareotherinstruction-basedtechniqueswherethelastexecutedinstruction 68 becomesthecommandexecutedbytheagent'sactuator.Forthe genome feature,twoim- plementationswereused:(1) dynamicgenome -thenumberofgenesandenzymesevolved freely,and(2) dgenome -thegenomewaswith3genesand24enzymes.Finally, forthe direction feature,weusedtwoerentimplementations:(1) absolutereferencing - basedontheuseofcompassdirections(ex. North , Northwest ,etc.),and(2) relativereferenc- ing -basedondirectionsrelativetotheagent'scurrentorientation(ex. Front , Front-Right , etc.).Withthesethreefeatures,wewereabletoiteratetcombinationsoffeature implementationsandevaluateeachsystem'sperformanceonthegivenforagingproblem. Figure4.3:Avisualdepictionofthettreatment(feature)combinationsusedthrough- outtheforagingexperiments. Toquantifythethateachfeaturecombinationhadonevolvingsuccessfulsolutions, werecordedthemaximumfoodplacementdistancethatanindividualwasabletomaintain aforagingsuccessrateabove50%across100randomplacements.Theresultsforeach spcombinationoffeaturesaregiveninFigure4.4.Twodistinctsystemsetsseemtobe distinguishableandpresentinthedatasetbasedontheirmaximumforagingdistance.One settendstoaverageamaximumforagingdistanceof3unitsfromhome'sperimeterwhile thesecondsetisabletoforagenearlytwiceasfaratanaveragedistanceof6units.Aswe movealongtheX-axistotheright,weobservetheemergenceofastairsteppatternwhere eachadjacentsystempaircontainsonesystemperforming,onaverage,twiceaswellasthe othersystemgiventhesameenvironment.Byinspectingeachadjacentsystempair,we thatthedirectionfeatureresultsinatwithinapair,suggestingthatthe 69 directionfeatureisonedeterminantformaximumforagingdistance Figure4.4:Theaverageforeachcombinationofsystemfeaturesontheforaging problemwiththeoriginalstaticmodel(DZ)andnewdynamic(DDZ)modelhighlighted. Tofurtherassesswhetherthedirectionfeatureisakeycontributortoforagingsuccess, weanalyzedthetrendswithineachfeaturebycombiningsystemsthatsharedaparticular implementation,showninFigure4.5.Whileatenceamongimplementations oftheactuationandgenomefeatureswaspresent,wefoundastrongcorrelation(p << 0.001,R-squared=0.6335)betweentheuseof relativereferencing andtheforagingsuccess ofsolutionsproducedbythesystem.Thisstrongcorrelationsuggeststhattheprocessof sensingstimulifromtheenvironmentusingdirectionsrelativetotheorientationoftheagent ismorebthanusingcompassdirections.Withrelativereferencing,agentsareable tobasetheirdecisionlogicondirectionstowhicheverdirectiontheyhappentobe currentlyfacingintheenvironment.Incontrast,agentsemployingabsolutereferencingwho 70 focusonaparticularcompassdirection(e.g., North )mustbasetheirdecisionlogiconstimuli thatoccurswithinthisviewoftheenvironment.Althoughrelativereferencingdoesseem toeasetheprocessofsensingone'senvironment,wealsobelievethatthelossofanacces- siblecompassbearingduringnavigationdoesaddtothedegreeofy.Forexample, anagentthatleaveshometoexploretheNorthwestquadrantcouldmaintainthisvalue throughoutexecutionandcalculatethereversedirectiontonavigatebacktowardshome. Incontrast,relativereferencingrequiresconsiderablymoreoverheadforeithercalculatinga generaldirectiontoreturnbasedonpreviousmovementsorusingenvironmentalcues,such ascolorsandsounds,toguidetheirbehavior. Althoughthetypeofactuationandgenomefeaturedidnothaveatimpact onforagingsuccess,weareabletoobservethatthedynamicvotingandgenomeoftheDDZ modelareoftenabletoproducesolutionsassuccessfulormorewhencomparedtoother systemvariants,asshownonthefar-rightofFigure4.4.Thisobservationisimportant becauseitrevealsthattheDDZmodelisabletoevolvesolutionscomparabletothose producedbytheDZmodel,but byusingfewerconstraints ,thusallowingitto(1)startin alowerdimensionalsearchspaceand(2)dynamicallyevolveto any genome whennecessary.Moreimportantly,inthegenerationofadaptiveembeddedcontrollers,our newmodelisabletobetteraddressuncertaintyinthesolutionspace,sp,bynot restrictingtheinternalcontrolstructureofevolvedsolutions. WhencomparingtheresultsoftheoriginalDZmodel(Figure3.6)totheDDZmodel, weseeatincreaseinforagingsuccess.Eachpopulationaverageisrepresented asadatapointrevealingthenumberoffooditemssuccessfullyreturnedtohomeateach foodplacementdistance.Inaddition,theaverageforagingsuccessofdominantgenotypes isplottedforboththeoriginalDZmodelandDDZmodelrevealingamarkedimprovement inforagingsuccess.Onaverage,controllersevolvedunderthedesignofthedynamicDDZ modelwereabletoforagewitha90%successratemorethantwiceasfarasthoseevolved usingthedesignoftheoriginalDZmodel.Uponvisualanalysisofthedominantstrategiesin 71 Figure4.5:Theaveragedistanceachievedbyevolvedcontrollersbasedont featuregroupings.Thedirectionfeatureisshowntohavethemostt eachpopulation,weagaindiscoveredcomplexbehaviorssuchasswarmingandcooperation viathecommunicationofconceptsviacolorand/orsound. AnexampleofanewlyevolvedstrategyusingtheDDZmodelisthe MimicStrategy , showninFigure4.6whereagentshavecombinedthebehaviorsfromthetwopreviousstrate- giesfromtheDZmodelto\mimic"theirsurroundingsduringaforage.Initially,agents areplacedon Home causingthemtoemitthe Home color(red)whentheyareonorwithin detectionrangeofhome.Astheymovefurtherintotheirenvironmentawayfromhome,the frequencyofemittingthe Home colorreducesuntiltheyareoutofdetectionrangeanddo notemitcolor.Asanagentcomeswithinproximitytoafooditem,itwillthenstartto emitthe Food color(blue)thusmimicingitssurroundings.Thecombinationofbothofthese behaviorsenablesanagenttoelyactasaproxyinordertoenlargethedetectionarea ofanearbyitemintheirenvironmentandtherebyreducethedistancebetweenbothfood andhome.AswithmanyoftheotherevolvedstrategiesintheDDZmodel,agentsoften moveinacircularpaththroughtheirenvironment,thusenablingthemtomaximizetheir 72 exposuretonearbysurroundingswhileonlyincrementallymovingawayfromtheirprevious positionintheworld. Figure4.6:The\Mimic"StrategywhereagentsworktoextendthenotionofbothHome andFood. 4.3RelatedWork AsatofourDZmodel,theDDZmodelsharesmanyofthekeyto otherECapproachesastheDZmodel.First,controlofanagentintheDZandDDZmodel iscapableofbeingdistributedacross multiple programsand multiple parallel-executing threadsasopposedtothesingleprogram,single-executingthreadapproachessuchasAvida [83].Second,unlike-state-basedapproachessuchasstatemachines(FSMs)[21,73]or cellularautomata[98],thecomputationalentitieswithintheDZandDDZmodelsdonot containstatesbutrathermaintainafully-functioning,virtualCPUcapableof executinginstructionsfromaTuring-Completeprogramminglanguage.Assuch,anagent's stateinourmodelsisdynamicandconstantlybyinteractionswithinternalcom- putingstructuresandtheenvironment.Third,eachprograminbothourDZandDDZ modelisstoredinacirculartapeformatthatisdynamic,extendable,andbasedoninstruc- tions,ratherthanrules,thatreducethenumberofelementsnecessarytoencodeaparticular 73 functionandsupportkeyfeaturesfoundinmodernsoftware,suchasbranchingandlooping operations.Finally,toaddressthechallengeoftraceabilityofevolvedsolutionlogicwith encodings,suchasartineuralnetworks(ANNs)[111,112],theevolvedcontrollogicin bothourDZandDDZmodelsremainsintheformofassembly-likeinstructionsthatare amenabletoautomatedand/orhumananalysis. ThekeyerencethatdistinguishesourDDZmodelfromtheDZmodelistheremoval ofconstraintsontheinternalarchitecture.SimilartopreviousGPapproaches [9,39,72,105],thenumberofprogramsintheDZmodelwasconstrainedaccordingtothe numberofagentsensingcapabilities.Inaddition,thenumberparallel-executingentities, ordigitalenzymes,wasestablishedbasedonthenumberofsensingdirectionsforeach sensor.However,byremovingtheseconstraintsinourDDZmodelandstartingwitha simplesingle-program,single-enzymesolution,wepermittheopen-endedevolutionofthe numberofprograms,threads,andinstructionsthatbestmatchthetaskandfeaturesofthe environment.Whileweobservedthroughanempirical-basedmodelcomparisonthatrelative directionswerethemaincontributortotheincreasedforagingsuccessinourDDZmodel,we observedthatthedynamicvotingandgenomestructureofourDDZmodelwasoftenableto producesolutionsassuccessfulormorewhencomparedtoothervariants.Thisobservation isimportantbecauseitdemonstratesthatournewDDZmodelisabletoevolvecontrollers withequalforagingsuccessastheDZmodelbutusing fewer constraints,thusallowinga largernumberofinternalcontrolstructurestoevolvenaturally. Thisconceptofstartingwithrudimentarystructureandincrementallyaddingcom- plexitytoanevolvedprogramovertime,referredtoas[100]hasbeen implementedinalternativeECapproaches,suchasforGPsandANNs,theseapproaches stillfromseveraldrawbacks.Fortree-basedGPapproaches[71],thereisdebatein theliteratureastowhatshouldconstituteasimplestartingstructure,namely, full trees (i.e.,treeswhosebranchesaretoastartingdepth)and grow trees(i.e.,trees whosebranchessimplycannotexceedastartingdepth).Withoutaclearconsensusforthe 74 startingstructureinthesetree-basedGPapproaches,a rampedhalf-and-half techniqueis oftenadoptedwherethepopulationcontainshalfofeachtreetypethatmayintroducean initialbiasintotheevolutionarysearchprocess.Inaddition,thereisalsoaninherentbias intree-basedGPapproachestoaddcomplexitytoterminalnodes(i.e.,leaves)since50% ofthenodesoftenresideatthislevelwhenselectiontakesplaceduringcrossoverormuta- tion.Asaresult,pruningoperatorsoftenmustmakearbitrarydecisionsastowhatdepth treesshouldberestrictedtoand/orwhichsubtreesshouldberemovedfromasolution,often withdisruptiveanddeleteriousAlternativeGPapproaches,suchasthe2Drepre- sentationsofCartesianGeneticProgramming(CGPs)[77,106,105]andmulti-dimensional representationsofParallelandDistributedGeneticProgramming(PDGP)[89],helpalle- viatetheaforementionedshortcomingsoftraditionalGPs,however,theseapproachesoften requireauser-spvaluefortheirdimensionalityorthenumberofprogramsis predeterminedbythenumberofprogramoutputs.Whilehasbeenimple- mentedwithinANNsusingtechniques,suchasNEAT[100],whereeachsolution'slineage andinheritanceofstructureismaintainedtoguidesearch,evolvedcontrollogicremainsin aformatthatisnotamenabletoanalysis. 4.4Discussion Inthischapter,wehavepresentedtheDDZmodelthatouroriginalDZmodel's designtoaccommodateuncertaintyinthesolutionspacewithrespecttothetraceability ofevolvedsolutionlogicandinternalcontrolstructure.First,toaddressthechallengeof traceabilityofsolutions,theevolvedlogicinboththeDZandDDZmodelsremainsinthe formofassembly-likeinstructionsthatareamenabletoautomatedand/orhumananalysis. Thisdesignstrategyprovidesresearcherswithanopportunitytostudyandcomparethetypes ofstructures(e.g.,simplefunctions,looping,feedback,branching,etc.)thatnaturallyevolve withinadigitalsystemtosolvebiologicallyinspiredproblems.Second,byallowingevolution tofreelymanipulateandselectfor(1)thenumberofuniqueprograms,(2)instructions 75 comprisingeachprogram,and(3)thenumberofthreadsexecutingwithineachcontroller, weareabletosupporttheopen-endedevolutionofasolution'sinternalcontrolstructure. Anextensiveempirical-basedmodelcomparisontosystematicallyiterateacrossvarious alternativecombinationsofkeymodelfeaturesrevealedthattheDDZmodel'suseofa dynamicgenomeandrelativedirectionsnearly doubled theperformanceofpreviouslyevolved strategiesintheDZmodel.EvolvedstrategiesfromtheDDZmodelwereabletomaintain aforagingsuccessrateabove50%inworldsely23 23insize.Moreimportantly, byrelaxingconstraintsfromtheDZmodel,ourimprovedDDZmodelcanmorectively facilitatesearchandaddressuncertaintyinthesolutionspacebyallowingsolutionsto(1) startinalowerdimensionalsearchspaceand(2)dynamicallyaddcomplexitytotheirinternal controlstructureovertime,asnecessary,toconstructandmaintainbialstrategies. 76 Chapter5 UncertaintyintheSearchProcess: Objective-based Inadditiontouncertaintypresentinboththeproblemdomainandsolutionspace, uncertaintycanalsooccurwithinthesearchprocessusedtobridgethegapbetweenthese twocontexts.Whileavarietyoftechniquesareavailablefordingfeasiblesolutions,forthe purposesofthisdissertation,wefocusparticularlyonharnessingthepowerofevolutionary searchtechniquesfortheirabilityto(1)maintain/explorealargenumberofopensearch avenuesinparallel,(2)impartbsolutionsubcomponents,or\buildingblocks,"to (3)avoidbecomingtrappedinsuboptimalregionsusingstochasticity,and(4) constantlyseekglobaloptimathroughtheuseofarelativetnessmeasure. Uncertaintymaypresentitselfinvariousaspectsoftheevolutionarysearchprocesssuch astheenvironmentwherethesystemisevaluatedorexecuted,theobjectivesorgoalsthat guidesearchinthedirectionofoptimalsolutions,theconstraintsthatimposerestrictionsthat mustbemetforasolutiontobeconsideredvalid,andalsothechoiceofevolutionarysearch operatorsusedtofacilitatethediscoveryofdesiredsolutions. Objective-baseduncertainty isoneformofuncertaintyduringsearchpertainingtothedimensionsusedforevaluating, measuring,andultimately,comparingevolvedsolutions.Amultitudeoffactorscan thelevelofobjective-baseduncertaintysuchasthedesign/typesofobjectivesused(e.g., continuousversusdiscrete),thetypeofinteractions(e.g.,complementary,competing,non- 77 interacting,etc.)amongobjectives,thestrengthoftheseinteractionsandthebiasesthey mayproduce,theprioritizationofobjectivesovertime,aswellaswheresolution lieintheobjectivespace. InSection5.1,weoverviewremotedatamirroring(RDM)systems,necessitatetheuse ofdynamicallyadaptivesystems/controllerswithinthisdomain,anddescribethekeychal- lengesintheirdesign.Next,wediscusstheoriginal Plato dynamicntool[91] andtheutilityofgeneticalgorithmsfornavigatingthevastsolutionspaceofourindustrial application.InSection5.3,weleverage Plato todynamicallygenerateplans forRDMnetworks.Duringthisprocess,weobservedthatinteractionsamongtheprob- lem'scompetingobjectivestlyimpacted Plato 'sabilitytoandreturnsolutions throughoutalargeportionoftheoverallobjectivespace.Tomitigatetheseinteractions,we presentanalternative,target-basedapproachinSection5.4thatexpandstheevolutionary algorithm'scoverageofthesolutionspaceandprovidesdomainexpertswithamoreintuitive methodforguidingsearchtowardsregionsofdesiredsolutions. 5.1RemoteDataMirroringSystems Remotedatamirroring(RDM)systems[65]arewidelydeployedtosynchro- nizationandreliabilityforcriticaldataitemsdistributedacrossanetworkinthepresence ofsite/linkfailures[64,108].Inordertoaccomplishtheseobjectives,RDMsystems copy criticaldataresidingatprimarysitesand remotelystore (mirror)thisdataacrosssecondary siteswithinthenetwork.Intheeventofafailure,anRDMsystemcanrecovereithervia adatareconstructionfromasecondarysiteoracompletefailover.Sincedesigningandde- ployinganRDMsystemcanincurtoverheadandisacomplextask,these systemsshouldonlybeconsideredwhenthecostoflosingdataexceedsthecostofprotect- ingit[64].ThedesignofanRDMsolution,referredtoasan overlaynetwork [5],centers aroundtwocriticaldecisions:(1)thesubsetofnetworklinkstoincludefromtheunderlying basenetworkand(2)thetypeofRDMnetworkingprotocolutilizedoneachactivelink. 78 Twonetworkingprotocoltypes, synchronous and asynchronous ,existtobalancethe associatedwithimprovingoverallnetworkbandwidth(resourceconsumption) whilemitigatingtheriskforgreaterpotentialdataloss(dataatrisk).A synchronous pro- tocolensuresthateachwriteoperationofacriticaldataitemissuccessfullyappliedand storedatthesecondarysitebeforesubsequentwriteoperationscanproceedattheprimary site.Incontrast, asynchronous protocolscoalescewriteoperationsattheprimarysiteover asplengthoftime.Afterthislengthoftimehaselapsed,writeoperationsaresent inbatchformoverthenetworktosecondarysitesandappliedatomically.InTable5.1,we presenttheelapsedtimebetweeneachbatch,theamountofpotentialdataatrisk(inGB), aswellasthepercentageofconsumednetworkbandwidthforbothsynchronous(P1)and asynchronous(P2-P7)protocols.` Protocol Type ID Interval Length Dataat Risk(GB) Bandwidth Synchronous P1 0minutes 0.0 1.0 Asynchronous P2 1minute 0.35 0.9098 P3 5minutes 0.6989 0.8623 P4 1hour 1.7782 0.7271 P5 4hours 2.3802 0.5732 P6 12hours 2.8573 0.4380 P7 24hours 3.1584 0.3967 Table5.1:PropertiesofRDMnetworkingprotocols[65]. Whileasynchronousbatchedprotocolsareabletoconservemorebandwidthandthere- foreachievehighernetworkperformance,theyalsocorrespondtohigherpotentialdataloss shouldtheoverlaynetworkexperienceanetworklinkorsitefailure.Synchronousprotocols areabletoachievezeropotentialdataloss,butdoingsoisattheexpenseofconsuming largeamountsofnetworkbandwidth.TheRDMapplicationcontainsmultiplecompeting objectiveswheretrademustbemadeamongsolutions'operationalcost,resourceand bandwidthconsumption,anddataatriskinthefaceoffailure.Inadditiontoitsinherent DASproperties(e.g.,self-*properties),theRDMproblemencompassesavastsolutionspace wherethesetofallpossiblenetworkdesignsistoolargetomanuallyenumerate.Forafully- 79 connectednetwork,theRDMproblem'sorderofcomplexitycomprises2 n ( n 1) = 2 network constructions,where n isthenumberofmirrorsites. 5.2Plato Plato [91]isatoolpreviouslydevelopedtosupportan autonomiccomputingsystem [67,107]bymanaginghigh-level,user-spobjectivesfordynamic,run-time ration.Atypicalautonomiccomputingsystemcomprisesthreeelements:(1)a monitoring element[49]todetectenvironmentalconditionsthatsuggestpossiblerec(2)a decision-making elementtodiscernconditionsthatwarrantanactualresponse,and(3)a recation elementtoperformsystemadaptationinordertosystemrequirements. Plato 'sresponsibilityliesinthelatter,evolvinginresponsetochangingenvi- ronmentalconditionsand/oradministratorobjectivesatruntimefortheRDMapplication. TodynamicallyanRDMnetworkatruntime, Plato reliesonasingle- objective,geneticalgorithmtocontinuallyevolveasetofcandidateoverlaynetworksusing two-pointcrossoverandpointmutation.Within Plato ,anevolvedoverlaynetworksolution isencodedasavectorwhereeachelementmapstoaspconnection(link)inabase network,asshowninFigure5.1.Eachelementinthegenomestores(1)abooleanfor whethertheconnectionisusedinthesolution,and(2)thespRDMprotocolutilized bytheactiveconnection. Figure5.1:Twosampleoverlayencodingsindicatingactivelinksandtheircorresponding RDMprotocols. 80 Threeobjectivesaretargetedduringoptimization: Cost ( f cost ), ResourceConsumption ( f resource ),and DataatRisk ( f risk ).Theformulasfordeterminingtheseobjectivevaluesare giveninEquations(5.1)-(5.6)andwerederivedfromstudiesforoptimizingdatarecov- erysystems[65].TherearenoadditionalconstraintsfortheRDMapplication.Inthese equations,acandidatesolutionvector( x )contains N totallinksfromtheunderlyingbase network.Foreachlink( x i ), x flag i storeswhetherthelinkisactive(1)orinactive(0)and x risk i and x band i correspondtothedataatriskandbandwidthconsumedbythelink'sRDM protocol,respectively.Theoperationalexpenseofanunderlyingnetworklinkisdenoted as C i whilepropertiesofaparticularRDMprotocol,suchasthebandwidthconsumed(ex. P 1 band ),refertothevaluesinTable5.1.Toavoidbiasingsearchalongobjectiveswithlarger rangesofvalues,eachobjectiveisnormalizedbetween0.0and1.0. f cost ( x )= P N i =0 C i x flag i P N i =0 C i (5.1) f resource ( x )= f resource 1 ( x ) P 1 band P 1 band P 7 band (5.2) f resource 1 ( x )= P N i =0 x band i x flag i P N i =0 P 1 band x flag i (5.3) f risk ( x )=0 : 5 f risk 1 ( x )+0 : 5 f risk 2 ( x ) (5.4) f risk 1 ( x )=1 : 0 P N i =0 x flag i N (5.5) f risk 2 ( x )= P N i =0 x risk i x flag i P N i =0 P 7 risk x flag i (5.6) Tomeasure Cost ,theoperationalexpensesofactiveoverlaylinksaretotaledandnormal- izedbytheworstcostscenario(i.e.,allnetworklinksactivated).Likewise,overlay Resource Consumption ismeasuredbasedontotalebandwidthafterdatahasbeencoalesced ( f resource )normalizedbytheworstbandwidthscenario(i.e.,synchronous-onlyoverlay).Op- timizingalongthe ResourceConsumption dimensionresultsinthereductionoftotaldata sentandanincreaseinavailablebandwidthduetocoalescingwriteoperations.Themea- sureofacandidateoverlay's DataatRisk iscalculatedaccordingtotwometrics,thelevel 81 ofconnectivity( f risk 1 )andthelevelofunprotecteddata( f risk 2 ).Connectivitymeasures thenumberofoverlaylinksnormalizedbythemaximumnumberoflinksavailableinthe underlyingbasenetworksinceaddingredundantlinkscanallowanetworktotoleratelink failures.Thesecondmetric, f risk 2 ,measuresthetotaldataatriskduetowritecoalescing normalizedbytheworstriskscenario(i.e.,maximally-asynchronousoverlay). Intheoriginal Plato tool,auser'shighlevelgoalswereincorporatedintoalinear- weightedsumwhereeachdimensionwasassignedaweightingcottoprioritizeand guidesearchtowardsparticularoverlaysolutions,asshowninEquation(5.7).Forexam- ple,ifanRDMadministratorwantedtoevolvenetworksthatsolelyprioritized Resource Consumption ,aweightingschemeof cost =0.0, resource =1.0,and risk =0.0couldbe used.Asenvironmentalconditionsand/orrequirementschangeatruntime,developerscan introducecodetoautomaticallyrespondbyupdatingthecotsofeachdimensionin theappropriatemanner. Minimize cost f cost ( x )+ resource f resource ( x )+ risk f risk ( x ) subjectto cost + resource + risk =1 : 0 (5.7) 5.3LinearWeightedFitness While Plato [91]demonstratedthesuccessful generation ofRDMplans atrun-time,severalissuesremainedforfurtherinvestigation.First,theweightingco cientsusedin Plato didnotdirectlyspecifydesiredevolvedsolutioncharacteristics.Instead, thesecotsspthe prioritization thatonedimensionshouldbegivenduringthe evolutionaryprocess.However,thisprioritizationrequiresadomainexperttoeither(1)un- derstandhowdimensionprioritizationcombinationstheunderlyingsearchdynamics or(2)relyonatrial-and-errororbruteforceapproachusingvariousweightingcombinations toreachdesiredsolutions.Inaddition,anequivalencerelationmayexistwheresimilarco- tcombinationsdriveevolutionarysearchtothesameareaofthesolutionspacethus 82 makingittogeneratenew,uniquesolutions.Second,althoughseveralcoet settingsweredemonstratedusing Plato [91],anopenissueremainsastowhetherthechar- acteristicsoftheevolvedoverlaynetworksolutionsaccuratelytheweightschosento producethesesolutionsonabroaderscale.Ifnot,howshouldweightsbechosenand/or alteredtobestcapturethenetworkpropertiesspbytheenduser? Toexploretheseissues,weperformedanempiricalstudytosystematicallyiterateacross arepresentativesetofcoientcombinationsinordertocomparetheirrelationtothe qualityofevolvedoverlayswithrespecttothreedimensions: Cost , ResourceConsumption , and DataatRisk .Usingtheexperimentalparametersfromtheoriginal Plato casestudy [91],thegoalwastoevolvetargetnetworkforafully-connectedunderlying networkcontaining26remotedatamirrors.Thecomplexityofthisoptimizationproblem encompasses2 n ( n 1) = 2 networkconstructions.Fora26-nodeproblemwith7possibleprotocol optionsforeachnetworklink,thetotalnumberofpossibleis7 2 325 . Byusinganinitialstartingvalueof0.0,anincrementsizeof0.10,andarequirement thattheweightingcotvaluessumto1.0,wewereabletogenerateatotalof62unique cotcombinations.Foreachofthesecombinations,weappliedthe Plato tiontooltodynamicallygenerateanoverlaynetworkoptimizedforthegivenprioritization ofdimensionsspEachevolutionaryruncontainedapopulationof500candidateso- lutionsevolvedoveratotalof1000generations,equatingtoroughly2minutesofwall-clock timewhenexecutedonaMacbookProwitha2.53GHzIntelCore2DuoProcessorand 4GBofRAM.Toprovideadequatestatisticaleachcotcombinationwas evaluatedusing30replicaterunsusingauniquerandomseedforeachrun. Toassesswhetherevolvedoverlaynetworksolutionsaccuratelytheweightschosen toproducethem,eachsolution'snetworkmeasures(i.e., Cost , ResourceConsumption ,and DataatRisk )wereusedtoplotathree-dimensionalsolutionpointshowninFigure5.2.An evolvedoverlaynetworkisassignedaspcolorbasedonthecotsettingsusedto evolveit.Eachnormalizedweightcotmapstoanintensitylevelforacomponentof 83 Figure5.2:Thetop5%solutionsofall Plato runsplottedwithinthe3Dobjectivespace. theRed-Green-Blue(RGB)colormodel{Redfor Cost ,Greenfor ResourceConsumption , andBluefor DataatRisk . InFigure5.2,weobservethatthesolutionsetobtainedfromallcotcombina- tionsproducesa\pictureframe"withintheobjectivespace.Thisistheresult ofsolutionsresidingonlyonthe extremes ofoneormoreparticulardimensions.Evolved 84 solutionsappeartobetrulyoptimizedwithrespecttoonlyonedimensionatatimeindi- catingthataparticulardimensionappearstotakepriorityoverallotherdimensionsduring search.Byinspectingeachborderofthe\pictureframe"artifact,wevisuallyobservethat apredominantcoloremergesamongmostpointsalongthegivenborder(e.g.,shadesofred attheoptimalendofthe Cost dimension). Thisartifactproducedby Plato istroublingforseveralimportantreasons.First,de- spiteperformingasystematicsweepofcotcombinations,theresultingsolutionsonly liewithinalimitedregionoftheoverallobjectivespace.Asweincreasethegranularity (incrementsize)ofthecocients,wewouldexpectmorecotcombinationstocon- vergetothesameregions,indicatingahighlevelofredundancyinmappingcotsto evolvednetworkcharacteristics.Second, Plato isunabletoreachtheinteriorofthesolution spacewhereareknowntoexistamongtheproblemdimensions(e.g.,amoderate networkcostwithmoderateresourceconsumption).Bynotreachingthisinteriorregion, Plato isrestrictedtoevolvingsolutionsthatexhibitpoorqualityinoneormoredimensions. Third,andmostimportantly,themeasuredpropertiesofevolvedsolutionsmaynot theprioritizationofdimensionsspbythecots.Therefore,the\optimal"solu- tionforagivencocientcombinationmayinfactbedetrimentaltotheRDMapplication. Forexample,inFigure5.2,wenoticethatcotcombinationsthatprioritized Dataat Risk (blueshade)over Cost and ResourceConsumption mostlylieontheleastoptimalendof the Cost dimensionindicatingthat Plato didnotattempttooptimizethisdimensionwithin networksolutions.Thesemisleadinganddeceptivecombinationsplaceanadditionalburden onthedomainexpertinformulatingcotsthatwillreturncorrect,desiredsolutions inthefaceofdynamicenvironmentalconditions. Inordertoexplaintheartifact'spresencewithinthesolutionspace,weobservehow solutionsaremeasuredalongtheRDMapplication'sdimensionsandtheirtontheun- derlyingsearchdynamicswhenimplementedasalinear-weightedsum.First,itisimportant topointoutthatthelinear-weightedsumapproachusedby Plato sparelative prior- 85 itization ofthedimensionsandonlyrewardssolutionsforevolvingintheproper direction alongagivendimension.Asaresult,duringevolutionarysearch,theonlystoppingcriterion alongaparticulardimensioniseither(1)thedimension'sboundaryhasbeenreachedor(2) furtherprogressalongthedimensiondegradesthesolution'squalityalonganotherdimension withhigherprioritization. Wehighlighttheissuethatthisweighted-sumimplementationposesusingtwoofthe RDMapplication'sdimensions, Cost and ResourceConsumption .InEquation(5.1),the Cost submeasure( f cost )rewardsmoreoptimalvaluesforthecontinuousremovaloflinks fromtheoverlaynetworksolution.However,withinalinear-weightedsum,the Cost di- mensioncanbeconsidereda\runaway"dimensionsinceitremainslargelyuncheckedby interactionswithotherdimensions.Forexample,network Cost hasnointer- actionswith ResourceConsumption ( f resource )meaningthatboththesedimensionscanbe optimizedsimultaneously.Withrespecttooverallnetwork DataatRisk ,only one ofthe submeasures( f risk 1 )withthe Cost dimensionbyrewardingfortheadditionoflinks intotheoverlaynetwork,leadingtoapartialbetweenthesedimensions.Without thepresenceofainteraction,evolutionarysearchwillcontinuetoremovelinks fromtheoverlaynetworkssincethisleadstomoreoptimalvalues(seeFigure5.3).A similar\runaway"existswithinthe ResourceConsumption dimension( f resource )since itisalsoonlyindirectwithoneofthe DataatRisk submeasures( f risk 2 ). Aconsequenceofthisectisthatsolutionsareoftenunabletoremainatintermediate valueswithinadimensionandinsteadareonlyrewardedforreachingtheextremeboundaries, asdemonstratedinFigures5.2and5.3.Inaddition,tocounteractthistheend usermustdeterminewherethesedimensioninteractionsoccurandre-weightappropriately. However,theseinteractionscanleadtoentangleddimensionsornon-intuitivecot assignments.Forexample,tocounteractthecontinuousremovaloflinks,anenduserwould berequiredtoaltertheweightingofthe DataatRisk dimensionthatmaydirectly withtheir ResourceConsumption needs. 86 Figure5.3:Theaveragemeasuredvaluewithinaparticulardimensionofthetop5%of evolved Plato networkscomparedagainsttheweightingcotsettingduringtheevolu- tionaryrun. Acrossmanydomains,solutionsareoftenmeasuredalongmultipledomain-spedi- mensions(objectives)thathavebeenarbitrarilychosenbytheresearchertoassesssolution quality.Thepresenceofinteractionswithinthesedimensionshasatimpacton thequality,aswellasthecorrectnessofsolutionsthatarereturned.Determining where theseinteractionsoccuramongdimensions,the type ofinteractionthatisoccurring(e.g., complementary,both,neither,etc.),andthe amount ofinteractioninorderto properlyassignweightsforguidingevolutionarysearchcanbeanimpracticalexpectation foradeveloperordomainexpert.Weclassifytheinabilitytoacquirethislevelofdomain knowledgeas objective-baseduncertainty . 5.4TargetGoal-basedFitness Inthissection,wepresentanalternativeapproachtogenerateRDMoverlaynetworks thatmitigatestheformofobjective-baseduncertaintypreviouslyfoundusing Plato 'slinear- weightedsumimplementation.Wefocusonaddressingtwocriticalshortcomingsof Plato : (1)expandingtheevolutionaryalgorithm'scoverageoftheobjectivespaceand(2)providing thedomainexpertwithamoreintuitivemethodforguidingsearchtowardsregionsofdesired andcorrectoverlaynetworksolutions. Torealizethesegoals,weretainedtheoriginaldimensionmeasuresoutlinedinEqua- 87 tion(5.1)andinsteadredesigned Plato 'sfunctionthatoriginallyrelieduponalinear- weightedsum.Toremovethepossibilityof\runaway"dimensionsandtheresulting\picture frame"artifactinthesolutionspace,wereplacedtheprioritizationofdimensions(coef- ts)withthetruetargetcharacteristicsthattheRDMdomainexpertdesireswithin evolvedsolutions.Werefertoournewapproachthatreliesupontargetvaluesasinputas TargetingPlato .AsshowninEquation(5.8),thedomainexpertprovidesthree targetvalues foreachofthethreerespectivedimensions.Forexample,toevolveoverlaynetworksthat weremoderately-pricedbutwhoselinks'synchronizationprotocolwereoptimizedentirely forresourceconsumption,thedomainexpertmightspecifyatargetof ˝ cost = 0.5, ˝ resource =0.0,and ˝ risk =1.0. Minimize j ˝ cost f cost ( x ) j + j ˝ resource f resource ( x ) j + j ˝ risk f risk ( x ) j subjectto0 : 0 ˝ cost ;˝ resource ;˝ risk 1 : 0 (5.8) Inordertoensurethat TargetingPlato convergedonregionsofthesolutionspaceas closetothetargetonaspossible,anoverlaynetwork'sisdeterminedbyits proximitytothepointspbythetargetvalues.Overlaynetworksolutionsthatreduce thedistancebetweenthetargetpoint(i.e., ˝ cost , ˝ resource ,and ˝ risk )andtheoverlay'smeasure withineachdimension(i.e., f cost ( x ), f resource ( x ),and f risk ( x ))achievehighervalues andaremorelikelytobeselectedduringevolutionarysearch.Toprovideenduserstheability toprioritizeparticulardimensions,additionalweightingcotscouldbeassociatedto eachtargetvaluetoenablethemtocontributemoretotheoverlay'stotalvalue. Toevaluateournewapproach,wesystematicallyiterateacrossvarioustarget urationsbystartingeachtargetmeasureat0.0withanincrementsizeof0.10untilthe maximumboundaryof1.0wasreachedwithineachdimension.Asbefore,eachtargetcon- wasevaluatedacross30replicaterunswitheachrunusingauniquerandomseed. Inordertoassesswhetherevolvedoverlaynetworksolutionsaccuratelythetarget valueschosentoproducethem,weusedeachsolution'snetworkmeasurestoonceagain 88 Figure5.4:Thetop5%solutionsofall TargetingPlato runsplottedwithinthe3Dobjective space. plotathree-dimensionalsolutionpointasshowninFigure5.4.Weusedthenormalized targetvalueofadimensiontogenerateanintensitylevelforeachcolorcomponentofthe Red-Green-Blue(RGB)colormodel{Redfor Cost ,Greenfor ResourceConsumption ,and Bluefor DataatRisk . AsshowninFigure5.4,our TargetingPlato approachprovidestlybettercover- ageofthesolutionspacebyreturningsolutionsintheregionspreviously unexplored by Plato aswellasregionspreviouslyreached.Thisresultdemonstratesthat TargetingPlato alessredundantmappingbetweenhigh-level,user-spobjectivesandtheexpressed propertiesofevolvedsolutions.Asaresult,weareabletoachieveincreased searchiencyfromourgeneticalgorithmandprovidemoreassurancethatuserinputs leadtotheirexpectedoutcomes. ThisimprovedmappingabilityisfurtherillustratedinFigure5.5wherewehaveplot- 89 Figure5.5:Theaveragemeasuredvaluewithinaparticulardimensionofthetop5%of evolvednetworkscomparedagainstthetargetvaluesettingduringtheevolutionaryrun. tedeachdimension'stargetsettingandtheaveragemeasuredvalueofreturnedsolutions. Asdemonstrated,ahighlytmappingexistsparticularlyinthe Cost and Resource Consumption dimensionsasreturnedsolutionsexpresstheuser'sdesiredlevelof Cost within 0.018( 0.034)and ResourceConsumption within0.006( 0.009).Sincethe DataatRisk di- mension( f risk 2 )ispartiallyrestrictedbythetargetvaluespfor ResourceConsumption ( ˝ resource ),welimitedourtargetsettingsforthisdimensionto1.0- ˝ resource .Whilethereis highervariabilitywithinthe DataatRisk dimension,thisvarianceisduetothe Cost dimen- sionthesecond DataatRisk submeasure( f risk 1 ).Bytargetinghighercostnetworks, additionalredundantlinksareaddedtothenetworktherebyincreasingthemeasuredvalue of f risk 1 withinevolvednetworks.Thisexplanationisalsosupportedbythenumberofdata points(10)withineachtarget DataatRisk setting,correspondingtothe10costsettings (0.0,0.1,0.2,0.3,etc.)usedduringouranalysis.Despitereturningsolutionswithmeasured DataatRisk valueswithin0.165( 0.127)ofthetargetsetting,itisimportanttonotethat ourapproachwasstillabletoreturnsolutionswhosemeasuredvaluematchedthatofthe targetsetting. 90 5.5RelatedWork Thissectionpresentsworkrelatedtobothevolutionaryandnon-evolutionarysearch- basedtechniquesforthedesignandreconofoverlaynetworks. 5.5.1Non-EvolutionarySearch-BasedTechniques. Oneapproachforsupportingself-rewithinanautonomiccomputingsystem istoincorporate utilityfunctions thatmapsystemcomponentstatesintorealscalarvalues. Thesescalarvaluesexpressthedegreeofdesirabilitywithrespecttouserpreferencesand canbeusedtodeterminethemostoptimalstatewithintheautonomicsystem. Walsh etal. [107]proposeabi-levelarchitecturewhereglobalsystemoptimizationis distributedamonginteractingautonomicentities.Eachautonomicentityreliesonaresource DemandForecasterandUtilityfunctionCalculatortocomputeeachpossible overallutilityandthemeansnecessaryforWhileutilityfunctionsare similartothetnessfunctionsusedwithingeneticalgorithms,evolutionarysearchuses stochasticity(mutation)andmaintainsadiversesetofsolutionsinordertoescapelocal optimathatoftentrap\greedy"approaches. Provisioningtools,suchasMinerva[4],areapopularalternativethatareusefulinthe designandmanagementofstorageareanetworksandRDMoverlays.Duetothesolution spacesize,thesetoolsoftenrelyon(1)decomposingdesignautomationintosuccessive, grainedevaluationphasesofheuristic-basedsearchand(2)functionsthatquantifydesign variables'onsystempropertiestobeusedbymathematicalsolverssuchasmixed integerprogramming.However,theseanalyticalmodelscanbeexpensivetocalculateand areoften static ,basedonexpectedenvironmentalconditions(i.e.,\grescenarios). Theseautomatedtechniques[64,65]maynotprovidevalidnstrategiesat runtimewhendynamicenvironmentalconditionsdeviatefromthosemodeledduringthe system'sdesign. 91 5.5.2EvolutionarySearch-BasedTechniques. Geneticalgorithmsareacommontoolinareasrelatedtoremotedatamirrorssuchas networkengineering,demand-baseddatareplication[74],andthedesignofoverlay multicastnetworks[43,75,110].In[74],Loukopoulos etal. useageneticalgorithmtodecide whichandtargetdistributionsitestousefordatareplicationinordertominimizeauser's experienceddelay.Whiletheirapproachtothisconstraint-basedoptimizationproblemwas notexecutedatruntime,itincorporatedpotentialdynamicchangestonetworkattributes intothedistribution'sdesign. Forthedynamicgenerationofoverlaynetworks,geneticalgorithmshavebeenapplied [43,70]toproblemscharacterizedbymultipleobjectivessuchasminimizingcost,maxi- mizingthroughput,andbalancingamongcompetingdimensionssuchasresource consumptionanddataatrisk.However,acommonapproachforassessingsolutionquality istocollapsethesemultipleobjectivesintoasingleobjectivevalueusingalinear-weighted combination[74,75,79,91,110].Asdemonstratedinthispaper,unlessknowledgeofthe solutionlandscape(e.g.,non-convexity)isgiven apriori ,theseweightedsumtechniquesmay onlyreturnalimitedsetofallpossiblesolutionsand\optimal"solutionsmaybefor user-spinputs.Asthenumberofobjectivessurpassthecapabilitiesofvisualization tools,theseundesirableinteractionsandbecomehardertodetect. Fornetwork,includingbothtopologyandlinkcapacities,Montana etal. [79]appliedgeneticalgorithmstoadaptinresponsetochangingoperatingconditions.For networkscomprising20orfewernodesand5orfewerchannels,thisapproachsupported onlineoptimization.However,relianceonacomputationallyexpensivenetworksimulator, ns2,restrictsthisapproachfromscalingtolargernetworksforaccurateevaluationofcan- didatetopologies. Plato [91],andsimilarlyour TargetingPlato approach,supporttheuseof monitoringinformationandcomputationallyetevaluationfunctionsinordertoremain responsiveatruntime. 92 5.6Discussion Inthischapter,weperformedanempiricalstudytoinvestigatethethatprior- itizing(weighting)problemdimensionshasongeneratingvalidstrategies withinaremotedatamirroringapplication.Duringthisprocess,wemadeseveralcritical observations.First,alinear-weightedsumapproachproducesahighlyredundantmapping thatrestrictstheoverallsetofreturnedsolutionsandsubsequently,adynamicallyadaptive system'sabilitytourecorrectlyatruntime.Second,linear-weightedtechniques areshowntobe incapable ofdiscoveringoverlaysolutionseatbalancing andreturningsolutionsrepresentativeofuserinputsandfortheapplication.Theseob- servationsweretheresultofobjective-baseduncertaintywithregardstothestrengthof competinginteractionstakingplaceamongtheproblem'sobjectivesthatwerepreventing largeregionsoftheobjectivespacefrombeingdiscovered. Tomitigatetheseissues,weproposedournew TargetingPlato approachthatwasable toreturnsolutionsinregionspreviouslyunreachableby Plato wheredesirable amongthecompetingobjectivesoccur.Duringourvisualanalysis,wediscoveredthatthe \surface"containingvalidoverlaynetworksolutionswasnon-convex(i.e.bulgingdownward) thatsolutionsthatlieinthisregion cannot bedetected[31]usingalinearweighted sumapproach.Thisobservationwarrantingconcernfortechniquessuchas Plato wasonly noticeableduetothelimitednumberofexploreddimensionsandwouldbeexceedingly todetectandmitigateasthedimensionalityoftheRDMapplicationincreased. Alternativeapproachessuchasnon-linearversionsoftheweightedmetricmethoddiscussed inSection2.2.4, TargetingPlato ,ormulti-objectiveoptimizationtechniques(e.g.,MOEAs) arerequiredinordertoreachtheseinteriorregionsofthesolutionspace.Our Targeting Plato approachprovidesamoretandpredictablemappingbetweenuserinputsand evolvednetworkpropertiesover Plato ,therebyincreasingtheenessofevolutionary searchanddecreasingthelevelofobjective-baseduncertaintypresentduringsearch. Inadditiontoimprovedcoverageoftheobjectivespace,our TargetingPlato approach 93 doesnotaddadditionalcomputationalcomplexitywhencomparedtotheoriginal Plato algorithm.Inourexperiments,theaverageruninlessthan3minuteswithsearch oftenconvergingtotheoptimalsolutioninlessthan1minute.Thisaveragerunlengthiswell withintheacceptablerangeforaremotedatamirroringapplicationsincebothour Targeting Plato approachand Plato relyoninexpensivecalculationsbasedonreal-worldmetricsrather thancostlysimulationsfoundinotherapproaches. Forendusers,our TargetingPlato approachdoesnotrequirestrategies tobeprescribedatdesigntimeinanticipationforconditionsthatmightariseafterdeploy- ment.Instead,ourapproachcontinuestosupportthecapabilityofdynamicallyadaptingto newuserrequirements(spashigh-levelobjectives)oradverseenvironmentalcondi- tions.Thiscapabilityisachievedbyembeddingtheactualsearchtechniquethatgenerates strategieswithinthesystemasopposedtothestrategies themselves. Lastly,webelievethatbyspecifyingthedesiredqualitylevelsalongtheRDMappli- cation'sdimensionsinsteadoftherelativeprioritizationofdimensions,wehaveprovideda moreintuitiveinterfaceforendusers.Theoriginal Plato approachaddsalevelofindirection forgeneratingtionsolutionsinordertoimproveupontheexistingoverlaynet- work'smeasuredqualities.Forexample,ifthecurrentoverlaynetworkexhibitsamoderate levelofrisk(e.g.,0.6)andadverseconditionswarrantloweringthelevelofriskinthenetwork (e.g.,0.4),determiningtheappropriateweightingschemetogeneratesuchachangeisquite challengingusing Plato .Theendusermusttakeintoaccounttheweightsettingsusedto generatethecurrentnetworkcharacteristicsanddeterminetherelativemagnitudethateach dimension'scotmustbealteredinordertoproperlycoercesearchintoa new region oftheobjectivespace.Incontrast,producingthissamewithinour TargetingPlato is quitesimplesincetheuserdirectlyspsthetargetvaluesthatevolvedsolutionsshould strivetoexhibitthatcorrespondstoadesiredregionofthesolutionspace. Onepotentialdrawbacktoour TargetingPlato approachisthattoensuretrulyoptimal 94 solutionsarebeingtargetedduringsearch,thisapproachrequiresthatthetargetpointbe placedeitheronorbeneaththesolutionsurface.However, apriori knowledgeofwherethis solutionsurfaceliesisnotalwaysavailableoreasytoderivewhichmaycauseadomainexpert torelyonatrial-and-errorapproachwithvarioustargetcombinationsusingthistechnique. Inthefollowingchapter,weturntomulti-objectiveoptimizationtoaddressthischallenge andcontinuetoreduceuncertaintypresentduringsearch. 95 Chapter6 UncertaintyintheSearchProcess: Operator-based Duetoobjective-baseduncertaintyduringsearch,tworecurringobservationswithpre- viousPlato-basedstudiesweremade(1)theobjectiveswereoftencompetingagainst,or insomecasesnegating,theofotherobjectives,or(2)completeknowledgeofthe landscapewasnecessarytoavoidsuboptimalsolutions.However,domainexpertsof- tenseektooptimizemultiplecompeting(orthogonal)objectivessimultaneouslyinorderto assesswhereexistamongtheproblemdimensions.Multi-objectiveevolutionary algorithms(MOEAs)fromtraditionalgeneticalgorithmsinthatcompetingobjec- tives/dimensionsarenotcollapsedintoasingleobjectivefunctionbutinsteadareoptimized simultaneously,asshowninEquation(6.1),inordertoa diverse setofsolutionsthat areoptimalwithrespecttotheirachievedreferredtoas Pareto-optimal solutions. Thesealgorithmsalsodonotrequiredomainexpertstospecifydesiredsolutionqualitiesor toprioritizeobjectivestodeterminewheresolutionoccur. Minimize( f cost ;f resource ;f risk ) (6.1) Evolutionarysearchalgorithms,includingMOEAs,canincorporateanumberof entoperatorssuchasacrossoveroperatortorecombineor\mix"solutionsubcomponents fromparentsolutions,amutationoperatortointroducenewgeneticinformationintothe 96 population,anelitismoperatortodecidewhichsolutionsshouldpersistintothenextgenera- tion,aselectionoperatortothelevelofexplorationversusexploitationofthesearch space,oradiversity-preservingoperatortomaximizethenoveltyofreturnedsolutions.As aresult, operator-baseduncertainty duringsearchpertainstothechoiceofoperatorstobe usedforaspproblembutmoreimportantly,thehidden interactions thatmayexist duetoanoperator'suseaswellasitsunintendedconsequencesonsearch. Inthischapter,wedetectedthepresenceofahiddenfeatureinteraction[16]involvinga keysearchoperatorwithinapopularMOEA.Thishiddeninteractionresultedinevolutionary searchabandoningitsprimaryroleofdiscoveringadiverse,Pareto-optimalsolutionsetand instead,resultedinsearchbiasedtoaseverelylimitedregionoftheoverallsearchspace. 6.1DiscoveringaHiddenFeatureInteraction Toleveragemulti-objectiveevolutionarysearchforthedynamicgenerationofRDM plans,wechosetheNon-DominatedSortingGeneticAlgorithm(NSGA- II)[37]whosedesignisparticularlywell-suitedtomitigatethedrawbacksofboth Plato and TargetingPlato throughtheincorporationoftwomainoperators:(1) non-dominated sorting and(2)a crowding-distance operator.Non-dominatedsortingmitigatestheconcern ofsuboptimalsolutionsandensuresthatsolutionsapproachtruePareto-optimalitybygiving prioritytosolutionswhoseobjectivemeasuresdominate(i.e.,improveupon)theobjective measuresofothersolutionsinthepopulation.NSGA-II'suseofacrowdingdistanceoperator mitigatesthelackofdiversityproblembygivingprioritytonon-dominatedsolutionslocated inlesscrowded(i.e.,novel)regionsoftheobjectivespace. UsingtheoriginalimplementationofNSGA-II[37],weperformedaseriesofrunsto assessitsabilitytoevolveoverlaynetworksolutionscomparabletotheexperimentalsolutions foundinpreviouswork[91].Eachruncontainedapopulationof500candidatesolutions employingtournamentselection( k =5),two-pointcrossover,anda5%mutationratefor atotalof1,000generations,equatingtoroughly3minutesofwall-clocktime.Toprovide 97 adequatestatistical30replicaterunswereevaluatedwitheachrunusinga uniquerandomseed. Usingthethreeobjectivemeasures( Cost , ResourceConsumption ,and DataatRisk ),we plottedathree-dimensionalpointforeachsolutionreturnedbyNSGA-II(coloredredin Figure6.1).Weobservedthatsolutionswereclusteredaroundthreedistinctextremainthe objectivespaceandthat,despitetheuseofNSGA-II'scrowding-distanceoperator,solutions werepredominantlylocatednearoneanother.Moreover,ahigh Cost measurecorrelatesto moreactivenetworklinksandtherefore,abroaderrangeofevolvable ResourceConsumption and DataatRisk levelsshouldexistsinceeachlinkcansupportoneofseventRDM protocols.AsshowninFigure6.1,however,NSGA-IIwasunabletoreturnsolutionswitha diversesetof ResourceConsumption measuresasthemajorityofnetworkswithhigh Cost only havea ResourceConsumption levelnear0.70.TheseobservationssuggestedthatNSGA-II wasnotreturningasolutionsetrepresentativeoftheentirePareto-optimalsurface. Figure6.1:OriginalNSGA-IIsolutions(red)comparedagainstsolutionsonParetosurface (grey)returnedbyepsilon-constrainedNSGA-II 98 6.2ParetoSurfaceDetection ToassessthetrueshapeoftheunderlyingPareto-optimalsurface,weperformedaseries ofadditionalrunsusingtheepsilon-constraintmethodforNSGA-II.Usingthismethod, searchcontinuestoseekPareto-optimalsolutionsthatminimizeallthreeobjectivevalues describedinEquation(6.1),however,subjecttotheconstraintthattheyarelocatedwithin asetofuser-spdboundaries.Byperforminganexhaustivesweepoftheobjectivespace usingintervalsizesof0.01alongboththe Cost and ResourceConsumption dimensions,we obtainedagrainedsamplingof10,000regionsacrossthePareto-optimalsurface. InFigure6.1,weplottedsolutions(coloredgrey)returnedbyepsilon-constrainedNSGA- IIandthattheoriginalNSGA-IIreturnedonlyalimitedsubsetofthesolutions onthetruePareto-optimalsurface.Thisobservationwastroublingforseveralreasons. First,NSGA-IIwasunabletoreturnsolutionsfromalargeregionofthesearchspacewhere Pareto-optimalsolutionsweredemonstratedtoexist,suggestingthathiddenfactorsmaybe hinderingsearch.Second,despiteNSGA-II'suseofacrowding-distanceoperatordesignedto coercesolutionsintounoccupied,novelregionsoftheobjectivespace,thereturnedsolutions areclusteredcloselytogether.Third,theoverallshapeofthereturnedsolutionsettapers towardsthreedistinctregionswithintheobjectivespace,indicatingthepotentialpresence ofanselectivepressurebiasingsolutionstowardtheextremesofeachobjective. Next,wedescribeaseriesofexperimentsthatwereperformedtodeterminetheleading causesof(i)basins-of-attractionthatsolutionsevolvetowards,(ii)highsolution crowding/clustering,and(iii)largeregionsofundiscoverednon-dominatedsolutions.We beginbyexamininghownoveltyiscalculatedforeachsolutionusingtheoriginalNSGA-II crowding-distanceoperator.Next,weinvestigatetwokeyevolutionarysearchoperators, crossoverandmutation,andtheirimpactonsolutions'objectivevaluesandexplorefactors ofboththeapplicationandencodingschemethatpreventsearchfromexpandingintomore novelregionsoftheobjectivespace.Finally,wedeterminetherootcauseofanunwanted, hiddenfeatureinteractionbiasingsearchandvalidateitsimpactonsearchcoverage.Eachof 99 theexperimentaltreatmentsbelowcomprised30replicaterunsusingthesameexperimental parametersintheoriginal Plato work,unlessstatedotherwise. 6.3BasinsofAttractionRemoval Problem/Motivation: UponanalyzingthenumberofuniqueParetofrontsmain- tainedforeachgeneration,weobservedthattheoriginalNSGA-IIrapidlyconvergedtoa single Paretofront.Consequently,thedistinguishingselectionfactoramongsolutionsbe- comesthecrowdingdistanceoperator.IntheoriginalNSGA-II[37],crowdingdistanceis assignedbysortingeachParetofrontbyanobjectivemeasureandeither(1)awardingpos- itiveyto\boundarysolutions"possessingtheminimum/maximumobjectivevalues or(2)summingthedistancebetweenadjacentsolutions'objectivevaluesfornon-boundary solutions. Whilepriorityisgiventosolutionsmaximizingtheircrowdingdistance,thisimplemen- tationmaybecomenoisyandoverestimatehowcrowdedasolutiontrulyisintheobjective space.Adjacentsolutionswithina single objectivemaybequitedistantwhentheir ad- ditional objectivevaluesaretakenintoconsideration.Asaresult,theoriginalcrowding distanceoperatordoesnotstorethedistancetothenearestindividualsolutionbutrather storestheshortestdistancesto any solutionwithineachobjective.Inaddition,boundary solutionsreceivethemaximumachievablecrowdingdistancetherebyproducing highlyadvantageousregionsoftheobjectivespace. Hypothesis1: Byassigningacrowdingdistancevalueofpositiveytoboundary solutions,basinsofattractionarecreatedthatbiassearchintheoriginalNSGA-II. Methods: Toprovideamoreaccuratedistancemeasureandavoidproducingfalse optima,anewimplementation( NSGA-II-MinEuc )wasusedtoreplacetheoriginalcrowding distancewiththeminimumEuclideandistancebetweensolutionsasadiversity-preserving mechanism.Thisimplementationuses every objectivevalueofasolutionduringitsdistance calculationwhilealsoremovingthepositiveyassignmentbias. 100 Results: InFigure6.2,weobservedthatthebasins-of-attractionanomaly isnolongerpresentwiththeremovalofthepositiveyassignment,andthereturned solutionsetismoreevenlydistributedintheobjectivespace.Despitesimilarhighlevels ofsolutionclusteringwitnessedpreviously, NSGA-II-MinEuc isableto dynamically respond toboundarysolutionsinnovelareaswithoutanexplicitreward/bias.Therefore,inour remainingexperiments,weleveragetheminimumEuclideancrowdingdistanceoperatoras weaddressNSGA-II'srestrictedsearchcoverage. Figure6.2: NSGA-II-MinEuc solutions(green)comparedagainstsolutionsonParetosurface (grey) 6.4NearestNeighborDistanceAnalysis Problem/Motivation: Despiteamoreevenlydistributedsolutionsetreturnedby NSGA-II-MinEuc ,wecontinuedtoobserve(i)large,unreachedregionsoftheParetosurface and(ii)highsolutioncrowding/clusteringintheobjectivespaceasshowninFigure6.2. Similarly, NSGA-II-MinEuc quicklyconvergedtoasingleParetofrontcausingasolution's crowdingdistancetobecomethedistinguishingfactorforitspersistingintosub- 101 sequentgenerations.Asaresult,webeganbydeterminingwhethertheregionreturnedby NSGA-II-MinEuc wasassociatedwithlarge(good)nearestneighbordistancesaswellanalyz- ingtheoveralldistributionofsolutionsintheobjectivespace. Hypothesis2: Thelimitedregionreturnedby NSGA-II-MinEuc isassociatedwith largecrowdingdistancesthatpreventsearchfromexpandingintonovelregionsandalso leadstohighsolutioncrowding. Methods: Using NSGA-II-MinEuc ,werecordedeachsolution'sobjectivemeasuresas wellasitsnearest-neighborEuclideandistanceattheendofeverygeneration.InFigure 6.3,weplottedasolution's Cost and ResourceConsumption valuealongtheXandZaxes, respectively,andallowedtheverticalY-axistorepresentthesolution'snearest-neighbor distance.Inaddition,wealsousedacolorgradienttodepictthefrequencyatwhichsolutions withthesame Cost and ResourceConsumption measuresweregeneratedthroughoutarun withredrepresentinghighfrequencyandbluerepresentinglowfrequency.Thiscolorgradient wasderivedfromtheoverallfrequencydistributionofsolutionsshowninFigure6.4. Results: BasedontheresultsshowninFigure6.4,wefoundthatthemajorityof solutionsdiscoveredby NSGA-II-MinEuc followedabell-shapeddistributionlocalizedaround acenterwith Cost =0.3and ResourceConsumption =0.5.Moreimportantly,Figure6.3 revealsthatboundarysolutions(bluecolor)foundinmorenovelregionsoftheobjectivespace wereattributedwithlargercrowding-distancevalues.However,theseboundarysolutions werenotabletopersistduringevolutionarysearchandappearedtobeselected against by NSGA-II-MinEuc infavorofsolutionsinmorecrowdedregionsoftheobjectivespace.This resultcontradictsbothourhypothesisandthepurposeofthecrowding-distanceoperator thatprioritizessolutionswithlargercrowdingdistancevalues.Thisresultsuggestedthat hiddenfactorsofeithertheevolutionarysearchoperators(e.g.,crossover,mutation,etc.) werehinderingesearch. 102 Figure6.3:TheaverageEuclideandis- tancetothenearestneighboringsolu- tionusing NSGA-II-MinEuc Figure6.4:Theoverallfrequencydis- tributionofsolutionsusing NSGA-II- MinEuc 6.5CrossoverImpactAnalysis Problem/Motivation: InthefrequencydistributionshowninFigure6.4,weobserved thatfewgeneratedsolutionsborderedtheregionexploredby NSGA-II-MinEuc .Aclaim couldbemadethattherestrictedsearchcoverageandhighsolutionclusteringwasdueto aneand/ordisruptive crossover operator. Asweobserved,themajorityofsolutionswerehighlyclusteredintheobjectivespace andlikelyexhibitedstrongsimilaritiesatthegenomelevel.Thislackofdiversityinparent genomesmayhaverenderedcrossover ctive astheproducedwouldnotcontain tfromtheirparents.Asaresult,evolutionarysearchmighthavestalled andwasunabletoreachfarther,morenovelregions.Asecond,orthogonalexplanationfor NSGA-II-MinEuc 'srestrictedsearchcoverageisthatthecrossoverwastoo disruptive asa searchoperatorandquicklydestroyeddiversityinthepopulation.Boundarysolutionsnear novelregionsoftheobjectivespacewithlargercrowdingdistancevaluesweremorelikely tobeselectedtoproducegandtherefore,thesesolutionsweremorelikelytobe disruptedbycrossover. Hypothesis3A: Lackofdiversityinthepopulationrendersthecrossoveroperator 103 ecausinghighsolutionclusteringandpreventingsearchfromexpandingintonovel regions. Hypothesis3B: Crossoverisdisruptiveasanevolutionaryoperatorcausinghighso- lutionclusteringandpreventingsearchfromexpandingintonovelregions. Methods: Inthisexperiment,wechosetoconstructtheoptimalconditionsfordeter- miningwhethercrossoverwasectiveordisruptivebyenforcinga(1)well-mixedpopu- lationof(2)Pareto-optimalsolutions(3)uniformlydistributedacrosstheobjectivespace. Theseoptimalconditionsallowedustotestwhethercrossoverwas ctive byensuring thatthepopulationcontainedahighlevelofdiversitybeforecrossoverwaspermittedto occur.Similarly,theseconditionsallowedustotestwhethercrossoverwas disruptive by measuringthelevelofdiversityintheobjectivespaceaftercrossoverwaspermittedtooc- cur.Moreover,ifcrossoverwasfoundtobedisruptive,allowingonlymutationtoguide NSGA-IIsearchwouldvalidateifotherhiddenfactorswereconstrictingevolutionarysearch. Togenerateawell-mixed,diverse,anduniformlydistributedpoolofcandidatesolutions todrawfrom,weperformedanexhaustivesearchacrosstheobjectivespaceinincrementsof 0.01usingepsilon-constrainedNSGA-II.Ateachincrement,westored100Pareto-optimal solutionswhose Cost and ResourceConsumption measureswerecontainedwithintheincre- ment'sboundaries.Forauser-spenumberofgenerations,arandomcoordinateinthe objectivespacewouldbeselectedtodrawarandomPareto-optimalsolutionfrominorder togenerateanratherthanundergotraditionaltwo-pointcrossover.Duringthese generations,therandomlyselectedsolutionswouldstillbebymutation beforebeingplacedintothenextgeneration'spopulation. Oncetheuser-spnumberofgenerationshadelapsed,twoexperimentaltreatments wereexploredfortheremaininggenerations.Inthetreatment,referredtoas NSGA-II- XOver ,thetraditionaltwo-pointcrossoveroperatorreplacedourprocessofrandomlyselect- ingfromthewell-mixedcandidatepoolofPareto-optimalsolutions.Inthesecondtreatment, referredtoas NSGA-II-MutOnly ,thisprocessisrestrictedfurtherbyremovingcrossoveralto- 104 getherandonlypermittingmutationtobeappliedforggeneration.Weexperimented withseveralgenerationsettingsforselectingfromtherandomwell-mixedcandidate poolincluding200,400,600,and800generations. Results: Tomeasurethelevelofdiversityinthepopulation,wecalculatedtheper- centageofevolvedsolutionswhose Cost valuewasgreaterthan0.50.Onereasonwechose thisthresholdwasthatitdividedtheobjectivespaceintoequalhalvesthatallowedusto assesswhetherrandomlyselectedsolutionswereuniformlydistributedbeforetheexperimen- taltreatmentwasapplied.Inaddition,thisthresholdallowedustodetectthetreatment's sincethemajorityofsolutionsfromtheoriginalNSGA-IIwereunabletocrossthis threshold. Figure6.5showstheresultsofourtreatmentwhencrossoverwasactivatedafter ensuringawell-mixedpopulationforauser-spnumberofgenerations.Priortoac- tivatingcrossoverateachgeneration,weobservedthatapproximately50%ofthe solutionshad Cost measuresabove0.50.Thisresultwasexpectedgiventhatare randomlyanduniformlydistributedintheobjectivespace.However,despiteahighlevelof initialsolutiondiversity,weobservedthat NSGA-II-XOver 'ssearchcoveragequicklycollapsed aftercrossoverwasactivatedandlikelywoulddeclinefurtherifgivenadditionalgenerations. Whiletheseresultsdisprovedthehypothesisthatsearchwasrestrictedduetoalackofdi- versity,theydidsupportforoursecondhypothesisthatcrossoverisdisruptiveasan evolutionaryoperator. InFigure6.6,weshowtheresultsofoursecondtreatmentwherecrossoverisremoved andonlymutationisusedtoproduceIfcrossoverweretherootcauseoflimited searchcoverageanddisruptivetomaintainingnovelsolutions,thenwewouldexpectthat theremovalofthisoperatorin NSGA-II-MutOnly wouldallowsearchtobettermaintain itsinitialhighlevelofdiversity.However,inFigure6.6,weobservedthatremovingthe crossoveroperatorresultedinahigherrateofdeclineandloweroverallsearchcoveragethan wewitnessedwhencrossoverwasincluded.Withtheseresults,weareabletoconcludethat 105 lackofdiversityduringcrossoveris not acontributingfactortotheobserved,limitedsearch coverage.Instead,crossoverstavesthetofahiddensearchfactorthatispreventing searchfromexpandingintonewregionsofthesolutionspace. Figure6.5:Thenumberofsolutions (with Cost > 0.50)usingtwo-point crossoverfromawell-mixedpopulation Figure6.6:Thenumberofsolutions (with Cost > 0.50)usingonlymutation fromawell-mixedpopulation 6.6MutationDistanceAnalysis Problem/Motivation: BasedontheresultsfromourCrossoverImpactAnalysis,we wereabletoconcludethatthehiddenfactorconstrictingsearch(1)wasmostpronounced whenstrictlymutationwasusedtogeneratesolutions,(2)thecrowding distancevaluesofsolutionssinceNSGA-IIquicklyconvergedtoasingleParetofront,and(3) placedanegativeselectivepressureonlargenetworksbyremovingthemfromthepopulation. Takentogether,theseresultssuggestedthatthesizeofanevolvedoverlaynetworksolution (i.e.numberofactivelinks)mighthaveantonthecrowdingdistancevaluesthatits areabletoattain. AlthoughtheobjectivefunctionslistedinEquations(5.1)wereformulatedasratios andnormalized,anormalprocedureformanyoptimizationproblems,wenoticedthatthis designhowobjectivemeasureswereabletochangedependingonthenumberof activenetworklinkswithinaparentsolution.Forexample,ifmutationalterstheRDM 106 protocolof3networklinksina small networkcontaining10activelinks,thisproduces alargechange(30%)inthenetwork's ResourceConsumption and DataatRisk measures. Incontrast,ifmutationalterstheRDMprotocolof3networklinksina large network containing100activelinks,thisproducesatlysmallerchange(3%)inthenetwork's ResourceConsumption and DataatRisk measures.Asaresultoftheirlargersize,theratiosof thesenetworkswouldexperiencegreater\inertia,"or resistancetochange ,intheirobjective measuresduringmutationandreceiveworsecrowding-distancevaluesthannetworkswith feweractivelinks. Hypothesis4: Thenumberofactivenetworkslinksofanevolvedsolutionproducesa intheparent-tocrowdingdistancevaluesacrosstheobjectivespace. Methods: Todeterminewhetherthisntialexisted,weusedepsilon-constrained NSGA-IItoperformanexhaustivesearchacrosstheobjectivespaceinincrementsof0.01 andmeasuredtheaveragecrowdingdistancebetweenparentandsolutions.Inthis experiment,weremovedthecrossoveroperatorfromepsilon-constrainedNSGA-IIsincethe hiddenfactorrestrictingsearchhadthemostpronouncedwhenstrictlymutationwas usedforgeneration.Despitetheremovalofthecrossoveroperator,thisimplementa- tionallowsustomeasuretwoimportantaspectsofsearch:(1)theaverageparent-to- distanceand(2)theaveragedistancesolutionswillmutateawayfromwherethecrossover operatorinitiallyplacesthemintheobjectivespace.Therefore,theseresultscanserveas aproxytoindirectlymeasurehowevolvedsolutionswouldbetedhadcrossoverbeen included. Foreachevolvedsolutionwhoseobjectivemeasureswerecontainedwithinanincrement's boundaries,wegenerated50solutionsandrecordedtheaverageEuclideancrowding distance.Werequired100parentsolutionstobeusedateachincrementtoallowsearchto potentiallydiscovertsolutionswithsimilar Cost and ResourceConsumption values. Using30replicateruns,wecalculatedtheoverallaverageEuclideandistancebetweenparent andsolutionsateach Cost and ResourceConsumption coordinateandplottedthe 107 resultsinFigures6.7and6.8. Results: Theresultsfromthisexperimentprovidedseveralkeyobservationstowards determiningtherootcauserestrictingsearchcoverage.InFigure6.7,weour hypothesisthatsmallernetworkswithfeweractivelinksare,onaverage,abletomutate farther fromtheirparentsthannetworkswithmoreactivelinks,providingbettercrowding distancevalues.Thisresultmatchedourexpectationssincesmallernetworksby mutationexperiencegreaterchangeintheirobjectivemeasuresthanlargernetworks.After applyingacolorgradient,wedeterminedthatmedium-sizednetworkswithbalancedlevelsof ResourceConsumption and DataatRisk mutatetheshortestdistanceintheobjectivespace. Althoughwewilladdress why thisregionistheminimuminalatersection,itisimportantto pointoutthatthemajorityofsolutionsin NSGA-II-MinEuc (Figure6.4)evolved away from thisdeleteriousregionandtowardsregionsassociatedwithlargercrowding-distancevalues. Figure6.7:Averageparent-to-o Euclideancrowdingdistance Figure6.8:Locationswhere NSGA-II- MinEuc solutionswerereturned 6.7EdgeConnectivityAnalysis Problem/Motivation: Oneremainingitemlefttoaddressis,ifNSGA-IIisselecting forregionsassociatedwithlargecrowdingdistancesbetweenparentandsolutions, whydoesNSGA-II'ssearchnotexpandintosurroundingregionswhereevenlargercrowding- distancevalueswereshowntoexist?Forexample,inFigure6.8,weobservethatnetworks 108 withlower Cost measures(e.g.,size)providegreaterparencrowdingdistance valuesthanthosereturnedbytheoriginalNSGA-II(coloredred). WhensearchingforPareto-optimalsolutionsforourRDMapplication,itiscriticalthat evolvednetworksare connected meaningthat,minimally,asinglepathexistsfromanydata mirrortoallotherdatamirrorsinthenetwork.Thisnetworkpropertyensuresthatcopiesof criticaldataitemscanbedistributedamongalldatamirrorsforbothbackupandrestoration purposesshouldasitefailureoccur.Ifanevolvedoverlaynetworkisdisconnecteddueto crossoverand/ormutation,itisconsidereddominatedbyanyconnectedsolutioninthe population,regardlessofitsobjectivemeasures.Onereasonwhysearchmaynotexpand intotheselow Cost regionsassociatedwithlargerparencrowdingdistancevalues isduetotheincreasedriskoftheirgsolutionsbecomingdisconnected. Hypothesis5: Anincreasedriskofbecomingdisconnectedpreventssearch fromexpandingintoregionswithhigherparencrowdingdistances. Methods: Toexplorethishypothesis,weusedepsilon-constrainedNSGA-IItoperform anexhaustivesweepusingincrementsof0.01alongthe Cost and ResourceConsumption dimensionsoftheobjectivespace.Foreachevolvedsolutionwhoseobjectivemeasures werewithinthespeciboundaries,wegenerated50solutionsandrecordedthe averageedgeconnectivityusingtheBoostGraphLibrary[1].Theedgeconnectivitymetric measurestheminimumnumberofedgesthatmustberemovedtocauseanetworktobecome disconnected.Werequired100solutionstobefoundwithineachincrementsothatNSGA- IIcoulddiscovertsolutionswithsimilar Cost and ResourceConsumption measures. Using30replicateruns,wecalculatedtheaveragepercentageofactivenetworklinksrequired todisconnecteachnetworkandplottedtheresultsinFigure6.9. Results: InFigure6.9,weobservethatthepercentageofactivelinksrequiredto disconnectanetworkdecreaseswithrespecttonetwork Cost .Thisresultmatchesourex- pectationssincefeweractivenetworkslinksincreasesthelikelihoodthatacriticallinkis removedduringmutationthatdisconnectsthenetwork.Inaddition,weobservedasudden 109 dropinedgeconnectivityalongthe Cost dimensioncorrespondingtonetworksthataremin- imumspanningtreesthathaveachievedthelowestpossible Cost sincetheremovalof any networklinkresultsinadisconnectednetwork.ThepointscoloredredinFigure6.9indicate wherethe NSGA-II-MinEuc wasabletoandreturnsolutions.Inthisweobserve thatthe NSGA-II-MinEuc wasabletoreturnsolutionsupuntilthisboundarywasreachedat whichpointevolvedsolutionswithlower Cost representdisconnectedsolutionsthatwould beguaranteedtobedominatedinthepopulation.Thiskeyinsightsupportsourhypothesis andoneexplanationforwhy NSGA-II-MinEuc didnotexpandintoregionsassociated withhigherparencrowdingdistancespreviouslydiscussed. Figure6.9:Percentageofactivelinkstoremoveanddisconnectnetworks. 6.8MutationAnalysis Problem/Motivation: Theriskofbecomingdisconnectedanexplanationfor whynetworkswereunabletoevolvefurtheralongthe Cost dimension.However,wealso found additional regionsalongthe ResourceConsumption dimensionthatwereassociated withhighercrowdingdistancesthantheregionswheresolutionswerereturnedby NSGA- 110 II-MinEuc .Sincetheseadditionalregionsarefoundalongtheextremesofthe Resource Consumption dimension,anevolvednetworkwouldberequiredtoadoptthesameRDM protocolacrossanincreasingnumberofitsactivelinksinordertoapproachtheseextremes. WithsevenRDMprotocols,theprobabilityofmutationaloneproducingidentical- protocolnetworkswith N activelinksis(1 = 7) N .Inourexperiments,eachRDMnetwork contained26datamirrorsandrequired minimally 25activelinkstoensureaconnectednet- work,correspondingtoaprobabilityof(1 = 7) 25 .Asnetworksize(e.g., Cost )increases,the probabilityofevolvingthesetypesofnetworksdecreasesfurtherandmatchesourprevious (Figure6.8)where NSGA-II-MinEuc 'sreturnedsolutionsetisshowntotaperalong the Cost dimension. Althoughselectionandthecrowding-distanceoperatorworktomaintainsolutionsdis- coveredintheseregions,twofactorspreventsearchfromexpandingfurtheralongthe Resource Consumption dimension.First,ifasolutionwithanincreasednumberofidenticallinksis selectedtoproduceanthenitisunlikelythatthewouldgainadditional identicallinksduetothedisruptiveofbothcrossoverandmutation.Second,each timeanovelsolutionisselectedtoproduceanthereisanincreasedlikelihoodthat itsgwillmutateashorterdistancethanitscurrentnearestneighboror Whilebeinganon-dominatedsolutionwithalargecrowdingdistanceisadvantageousfor survivingthecurrentgeneration,theincreasedlikelihoodofproducingmaybecome disadvantageousinsubsequentgenerationsasthesolutionbecomesmorecrowded. Hypothesis6: Thenetofmutationonanevolvedsolution'sobjectivesopposes searchfromexpandingintonovelregionsoftheobjectivespace. Methods: Inthisexperiment,weexploredmutation'snetoneachobjective measurewhenthe Cost and ResourceConsumption ofanevolvednetworkwerecontrolled. Usingepsilon-constrainedNSGA-II,weperformedanexhaustivesweepusingincrementsof 0.01alongthe Cost and ResourceConsumption dimensions.Foreachevolvedsolutionwhose objectivemeasureswerewithinthespedboundaries,wegenerated50solutions 111 andrecordedmutation'sneton Cost , ResourceConsumption ,and DataatRisk . Results: Wethatmutationopposestheexpansionofsearchintonovelregions alongallthreedimensions: Cost (Figure6.10), ResourceConsumption (Figure6.11),and Data atRisk (Figure6.12).Solutionswithlowobjectivevalueswithineachdimensionexperience anet increase aftermutationisappliedandsimilarly,solutionswithhighobjectivevalues experienceanet decrease .Inthe Cost dimension,theobservedeisconsistentasmutation workstoincreasethenumberofactivatedlinkswhenlessthan50%ofthenetwork'slinks areactiveanddecreasethenumberofactivatedlinkswhenmorethan50%ofthenetwork's linksareactive.Whilethisisalsoobservedinboththe ResourceConsumption and DataatRisk dimensionstoreturnnetworksto50%levelof ResourceConsumption and Data atRisk ,respectively,wealsothatthestrength(i.e.,slope)ofthisonthese objectivevaluesweakensasthe Cost ,orsize,ofthenetworkincreases.Asaresult,these evolutionaryoperatorsproducea\funneling"astheyworktoreturnsolutionstoa zeronetpointwherethereisequalprobabilityofactivating/deactivatinganetwork linkandsubstitutingamongRDMprotocols.Thesepointsalsocorrespondtothelocationin theobjectivespacewheretheaverageparencrowdingdistancewaspreviously observedtobethelowest(worst). 6.9IncreasedMutationProbabilityAnalysis Problem/Motivation: Fromourpreviousexperiments,wedeterminedthatthesize ofanetwork(1)thedistancethatareabletomutatefromtheirparents aswellas(2)thedistancesimilarnetworksareabletomutatefromoneanother.While theoriginalNSGA-IIappearstohaverespondedtothistialbyreturningsolutions inregionsassociatedwithgreatermutationdistances,wehavenotformallytestedwhether NSGA-IIsearchisbythisfactor. Hypothesis7: NSGA-II'ssearchforgoesexpandingintonovelregionsoftheobjective spaceinfavorofregionsassociatedwithgreatermutationdistances 112 Figure6.10:Thenetofmutationonthe Cost objectiveofsolutionsreturnedthroughout theobjectivespace Methods: Totestourhypothesis,wedividedtheobjectivespaceintotwoequalhalves referredtoasthe Control region(Cost 0.50)andthe Treatment region(Cost > 0.50). IntheControlregionwherethemajorityofsolutionswerereturnedbytheoriginalNSGA- II,wemaintainedtheoriginalmutationrateof5%duringgeneration.Inthe Treatmentregion,however,wevariedthemutationratethatsolutionswereexposedto usingthefollowingrates:10%,20%,30%,40%,50%,60%,and70%.Anetworklocated intheTreatmentregionismore likely (notguaranteed)toexperienceagreaternumberof mutationstotheirnetworklinks,andthereforeagreateroverallchangeintheirobjectives andcrowdingdistance,thannetworksfoundintheControlregion.Ifourhypothesisis correctthatNSGA-IIfavorsregionsassociatedwithgreatercrowdingdistancesovernovel regionswherenon-dominatedsolutionsexist,weexpectamajorityofsolutionsreturned byNSGA-IItoresidewithintheTreatmentregionattheendofarun.Weperformed30 replicaterunsforeachofthemutationratesettingsandplottedthepercentageofsolutions inthepopulationfoundintheTreatmentregioninFigure6.13. Results: ByobservingthepercentageofsolutionsintheTreatmentregionwitha5% 113 Figure6.11:Thenetofmutationonthe ResourceConsumption objectiveofsolutions returnedthroughouttheobjectivespace mutationrate,weobtainabaselinefortheoriginalNSGA-IIwherethemutationratesfor bothregionsareequalandthusnoispresent.Withnotreatmentappliedatthe 5%mutationrate,only5.94%( 1.33%)ofsolutionswereobservedwithintheTreatment region.However,asthemutationrateincreased,weobservedatincrease(p ˝ 0.01)inthepercentageofsolutionsreturnedwithintheTreatmentregion.Theincreased likelihoodofsolutionsmutatingfartherintheTreatmentregionproducedapowerful onsearchasthenumberofsolutionsfoundwithintheControlregiondroppedfrom94.06% intheoriginalNSGA-IItoaslowas17.24%.Theseresultsconourhypothesisthat NSGA-IIforgoesexpandingsearchintonovelregionsoftheobjectivespaceinfavorofregions wherehighercrowdingdistancesareachievable. 6.10RelatedWork Despitenearly20yearsofalgorithmdevelopmentalstudiesinevolutionarymulti- objectivesearch,thisnewlydiscoveredinteractionofvariable-lengthgenomesandthecrowd- ingdistanceoperatoraswellasitsonsearchcoveragehasnotbeendocumentedin 114 Figure6.12:Thenetofmutationonthe DataatRisk objectiveofsolutionsreturned throughouttheobjectivespace theliterature.Ishibuchietal.[62,63]examinedhowdiscreteobjectivefunctionswithtwo t granularities (widthofintervalswithinanobjective)searchwhenusing popularmulti-objectiveoptimizationalgorithmsincluding,NSGA-II,SPEA2,MOEA/D, andSMS-EMOA.Atwo-objective0/1knapsackproblem[115]withintegerpvaluesfor eachknapsackitemwasusedintheirexperiments.Byapplyingroundingfactorsoft sizes(e.g.,roundby10,100,etc.)toeachobjective,theyexploredtheofdt granularitycombinationsonsearch.Theirresultsdemonstratedthatwhenthegranularities oftheproblem'sdimensionsvary,searchisbiasedtowardsparticularregionsoftheobjective space. Whiletheseresultsstronglycorroborateourandexploreasimilarproblem, severalkeydistinguishourwork.First,thegranularitiesofeachobjectivewere establishedbyapplying adhoc roundingfactorsandwerenotattributesoftheoriginal application.Asaresult,bothoftheirobjectiveshad uniformgranularity wherebythe intervalwidthwasconstantwithineachobjective.Second,thegranularityofeachobjective in[62,63]was static duringsearchmeaningthattheintervalwidthdidnotchangefrom 115 Figure6.13:ThepercentageofsolutionsfoundintheTreatmentregionacrossvariousmu- tationratesettings. onegenerationtothenext.Incontrast,thegranularitiesoftheobjectivesinourworkwere notestablishedbutratherthey emerged fromourapplicationthusconcealingthehidden interactionandmakingitmoretodetect.Third,thegranularityofobjectives was non-uniform sincetheintervalwidthwasdependentonthenumberoflinkswithinan evolvedsolution.Smallernetworksexperiencedlargergranularitiesduringmutationand largernetworksexperiencedsmallergranularities.Lastly,thegranularityofobjectiveswas dynamic andevolvedwithrespecttonetworksizeovertime.Forexample,twonetworks (networkA=10expensivelinks,networkB=30inexpensivelinks)withthe same Cost valueof0.30willexperiencetgranularitiesintheir Cost objective. Thesekeybetweenourtwoproblemsalsoleadtoorthogonalresultsand conclusions.Ishibuchietal.[62,63]observedthatsearchwasbiasedtowardsobjectiveswith granularitywhereasinthispaper,solutionsarebiasedtowardsthecoarsegranularity regionofeachobjective.Also,thisstudyfoundthatdiscreteobjectiveswithcoarsegranu- laritiesimprovethesearchabilityofNSGA-IIwithmanydimensions(objectives),whereas thecoarsegranularityregionsoftheobjectivespaceinourworkhindersNSGA-II'ssearch coverage. 116 6.11Discussion Theexperimentsinthissectionhavedemonstratedthepresenceofahiddeninteraction betweentheunderlyinggenomerepresentationandthecrowdingdistanceoperatorfoundin MOEAapproachessuchasNSGA-II.Twofactorsofourapplicationcausedthisinteraction tooccur,namely,(1)a variable-lengthgenome and(2)objectivefunctionsformulatedas ratios .Byallowingthenumberofsolutionelementstoevolvefreely,generated fromsolutionswithfewerelementsaremorelikelytoexperiencealargerchangetotheir objectivemeasures.Asaresult,boththeparentsolutionanditsaremorelikelyto belocatedfartherfromoneanotherintheobjectivespace.Sincelargervaluesareprioritized bythecrowdingdistanceoperator,NSGA-II'ssearchisunabletoexplorenovelregionswhere additionalPareto-optimalsolutionscanbefoundsincethesesolutionscannoteasilyachieve similarcrowdingdistancevalues. Theimplicationsofthishiddeninteractionaretsince,dependingonthe strengthofthisinteraction,thesetofPareto-optimalsolutionsreturnedbyNSGA-IImay onlyencompassanextremelylimitedregionoftheoverallParetosurfaceinagivenappli- cation.Moreimportantly,withoutknowledgeoftheunderlyingParetosurface,thishidden interactionwouldbetodetectandtheoriginalreturnedsolutionsetmighteasily havebeenacceptedast.Invariousapplicationdomains,thenumberofsolutionele- mentsisoftenafreevariableevolvedinordertoexploretdesignsandtheirassociated Similarly,acommonandoftennecessarytaskwhennormalizinganobjectiveis toformulatetheobjectiveasaratio.Asaresult,thesefactorscanappearquiteeasilyina givenapplicationwithouttheresearcherbeingawareoftheirconsequences.Thisinteraction becomesmoretodetectandalsomorelikelytooccurasthedimensionalityofthe problemincreases. 117 Chapter7 MitigatingOperator-based UncertaintyintheSearchProcess Inordertoincreaseaccesstosolutionsthroughouttheobjectivespace,theprevious chaptershavedescribedaseriesofGA-basedtoolsthathavebeenprogressivelydeveloped, eachofwhichrequiredtlevelsofdomainexpertise: Plato , TargetingPlato ,and NSGA- IIPlato thatsupportdynamicforanindustrialdatamirroringapplication. Whiletheevolvedsolutionsoftheseapproacheswerebetterthansolutionsgeneratedman- ually,furtherinspectionrevealedthatsolutionswerefortheirintendedenvironment, regionsoftheobjectivespacewereunreachable,oranexhaustive,trial-and-error-process wouldbenecessarytoyielddesiredsolutions.Moreover,operator-baseduncertaintywasob- servedinthehiddeninteractionsbetweenavariable-lengthgenomedesignandthediversity- preservingsearchoperatorofapopularmulti-objectiveevolutionaryalgorithm,NSGA-II, thatcantlyrestrictedsearchcoverageintheobjectivespace.AswerecallinFigure 6.7, NSGA-IIPlato 'ssearchwasbiasedtowardsregionsassociatedwithlow Cost valuesas thesesolutionscontainfewnetworklinksandthustheirobjectivevaluesexperiencegreater changesduringmutation.SinceNSGA-II'scrowding-distanceoperatorprioritizessolutions locatedinsparsely-populatedregionsoftheobjectivespace,solutionswhoseobjectivevalues experiencegreaterchangearefavoredsincetheyarelesslikelytobecomemorecrowdedover time.Asaresult,candidatesolutionsofvaryingsizeareunableto globally competewith 118 oneanotherinthesamepopulation. Inthischapter,tosupportadiversesetofoptimalsolutionswheresolutioncomplexity isakeyvariablebeingexplored,weproposethat niching beleveragedtomitigatetheun- wantedinteractionsstemmingfrom operator-baseduncertainty duringsearch.Nichingisan evolutionarysearchoperatorthatiscapableofexplicitlycreatingandmaintainingfavorable regionstodrawsearchtowardsintheobjectivespaceinordertopromotefaircompetition amongsimilarmembersofapopulation.Whilethisnichingoperatorwasintendedtocoun- teracttheCurseofDimensionalityProblem[7]forhigh-dimensionalapplications,wepropose analternativeuseforthisoperatoranddemonstrateitsabilitytosuccessfullymitigatethe hiddensearchinteractionspresentinNSGA-IIandreturndiversesetsofPareto-optimal throughouttheobjectivespace. 7.1DesiredSearchProperties GiventheobservedweaknessesofpreviousPlatoapproaches,wehighlightthreehigh- levelabilitiesneededforsearchtechniquesusedinthedynamicofadaptive systems:(1)theabilitytoreturna diverse solutionset,(2)theabilitytoreturn non- dominated,Pareto-optimal solutions,and(3)theabilityto managenon-uniformmutational cts tosolutionobjectives.Foreachoftheseabilities,weprovideaworkingition, describeitsimportanceforadaptivesystemguration,andsummarizewhetherthe abilitywassupportedinpreviousPlatoapproaches. 7.1.1DiverseSolutionSet Solutionsetdiversity,or\spread,"representsthedegreeofcoverageasearchtechnique isabletoachieveintheobjectivespace.Maintainingadiversepopulationpreservesavari- etyofopen,parallelsearchavenuestoexplore,thusloweringthebarrierofprobabilistically discoveringaglobaloptima,ifmultiplepathstosuchoptimaexist.Whileadiversepopula- tionmayslowconvergenceonnewlydiscoveredoptimaduetoitsspread,thispropertyalso 119 reducesthelikelihoodofsearchbecomingtrappedinlocaloptima.Forapplications,suchas RDM,thatrequireadynamicallyadaptivesystemtorespondtoavarietyofenvironmental andsystemuncertainties,ahighlydiversesolutionset(1)arangeofforboth domainusersandautomatedtoolstoconsideraswellas(2)amethodtoindirectlyprobe therangeofachievableobjectivevaluesgivencurrentconditions. Inboththeoriginal Plato and TargetingPlato ,thequalityofanevolvedsolutionwas collapsedintoasinglevalue,and,asaresult,searchoftenconvergedupon one partic- ularsolutiontypethatoptimizedthisvalue.Thereturnedsolutionsetsoftheseapproaches oftenlackeddiversity,andgoodcoveragecouldonlybeachievedbyexhaustivelyvarying searchparametersovermanysearchiterations.Inaddition,non-convexParetosurfacespre- vent Plato fromreturningalargenumberofsolutions.Whilethecrowding-distanceoperator of NSGA-IIPlato isnormallycapableofdrivingsearchtowardssparsely-populatedareasof theobjectivespace,hiddeninteractionswithsolutionswhoseobjectivevaluesareunequally bymutationwereobservedtodisruptthismechanism.Therefore,NSGA-IIonly supportssolutionsetdiversitywhentheseinteractionsarenotpresentintheoptimization problem. 7.1.2Non-Dominated,Pareto-OptimalSolutions Forapplicationsbymultipleorthogonalobjectives,asolutionis Pareto-optimal ifnosingleobjectivecanbeimprovedfurtherwithoutitsquality alonganotherobjective.WhileParetooptimalitycanbeassessedforasolutioninisola- tion,non-dominationisassessedrelativetoothermembersofthe aggregate solutionset, orpopulation.Asolution B issaidto\dominate"anothersolution C whensolution B is noworsethansolution C withineachrespectiveobjectiveandsolution B improvesuponat leastoneofsolution C 'sobjectivevalues.Theabilitytoreturnanincreasingmajorityof non-dominatedsolutionsisadesirablesearchpropertysincethesesolutionsareirreplaceable byotherpopulationmembersthushelpingtominimizesearch\waste"(i.e.,dominatedsolu- 120 tions)andimprovesearch.However,sinceminorchangesmayeasilyproducenew, non-dominatedsolutions,thisabilityalonedoesnotguaranteeabroadrangeoft thusunderscoringtheimportanceofsolutionsetdiversity. Linear-weightedsumtechniques,suchas Plato ,canbeusedtoseekPareto-optimal solutions,however,non-convexregionsoftheobjectivespaceremainundetectableand,as demonstrated,returnedsolutionsmaybemisalignedwiththeuser'sgoalsandtherefore fortheirintendedenvironment.While TargetingPlato overcametheseweaknesses, apriori knowledgeoftheParetosurface'slocationisnecessarytoavoidreturningsuboptimal solutionscausingadomainexperttooftenrelyonatrial-and-errorapproachusingvarious targetcombinations.Byconstantlyprioritizingsolutionsthatimproveupontheobjective valuesofotherpopulationmembers, NSGA-IIPlato isabletoseekandreturnnon-dominated, Paretooptimalsolutions,however,thesesolutionswerenotrepresentativeoftheoverall objectivespace. 7.1.3ManageNon-UniformMutational Finally,inordertohandlediscrete/combinatorialoptimizationproblems,suchasour RDMapplication,weseekevolutionarysearchtechniquesthatcansuccessfullymitigatethe non-uniformofmutationonsolutionobjectivesasadirectresultofhiddeninterac- tionsrecentlyobserved.Inourempiricalstudy,avariable-lengthgenomecausedsolutions' objectivevaluestobedisproportionatelybymutationandasaresult,solutionswith fewerelementsexperiencedgreaterchangestotheirobjectivevaluesduringmutationthus conferringanadvantageforescapingcrowdedregions.Thesehiddeninteractionsbetween NSGA-II'scrowding-distanceoperatorandmutationpreventedfaircompetitionamongsolu- tionsandbiasedsearchtowardsregionscontainingsmallersolutions.Invariousapplication domains,thenumberofsolutionelementsisoftenafreevariableevolvedtoexplore entdesignsandtheirassociatedTherefore,properlymanagingthisinteractionis criticalforsearchtechniquesusedforadaptivesystems.Moreover,avariable-lengthgenome 121 designisbutonespexamplebywhichobjectivevaluesmayvarydisproportionately duringsearch. Both Plato and TargetingPlato approachesdonotcontainamechanism,suchasthe crowding-distanceoperator,thatexplicitlyrewardssolutionsbasedontheirlocationrelative tooneanother.Asaresult,theseapproachesarenotsusceptibletonon-uniformmutational 7.2LeveragingReference-basedNiching Inbiology,anecologicalniche[87]oftenreferstoasprole,function,orareathatan organisminhabitswithinanecosystemasaresultofthedistributionofresources,predators, and/orcompetitors.Whenspacewithinapopulationofcompetingindividualsislimited, evolutionvianaturalselectionoftendrivesorganismstoenteruniquenichesinordertomin- imizecompetitionthusallowingamorediverseoverallpopulationtoco-exist.Similarly,in evolutionarysearch,anichingoperator creates regionswhereindividualscanlocallycompete bysegmentingthepopulationintodistinctsubpopulationsandisusefulwhen simultaneously targetingmultipleoptimaand/orwhensolutionsetdiversityistoachievedueto convergence. Inmany-objective(fourormoreobjectives)optimizationproblems,twocriticalissues arise:(1)thesearchspacevolumeincreasesexponentially,duetotheCurseofDimensionality problem[7],makingittoelyexplorenewregions,and(2)themajorityofthe population'sopenslotsbecomeoccupiedwithnon-dominatedsolutionscausingevolutionary searchtoslowdowndramatically[35].Toaddresstheseissues,DebandJainrecently developedanewMOEAnamedNSGA-III[35]thatincorporatedtheconceptof niching duringsearchbyreplacingNSGA-II'scrowding-distanceoperatorwitha referencepoint- basedniching operator. Weproposeanewalternativerole[17]forNSGA-III'snichingoperator,namely,toman- agenon-uniformmutationalchangestosolutionobjectives.Inapplicationswherevariable- 122 lengthgenomesareused,solutionscannotgloballycompetewithoneanotherduetoinequity createdbysolutionsizes.Nichingpromotesfaircompetitionamongsolutionsbyen- suringthatsolutions locally competewithothersbasedonsimilarobjectivevaluesthereby buildingequitybetweensolutionsbackintotheoptimizationalgorithm.Inaddition,the abilitytoexplicitlynichelocationsintheobjectivespaceallowsNSGA-IIItoproduce aselectivepressureforsearchtoenterregionspreviouslytoreachbyNSGA-II. Weassesswhethernichingcanprovidethethreehigh-leveldesiredpropertiesforDAS byusingNSGA-IIIforthedynamicofanindustrialRDMapplication.Using thesameexperimentalparametersaspreviousPlato-basedstudies,NSGA-IIImustevolve overlaynetworksolutionsforfully-connectedRDMnetworkscontaining26datamirrors. Eachevolutionaryruncontainedapopulationof500candidatesolutionsthatemployed tournamentselection( k =5),two-pointcrossover,anda5%mutationrateforatotalof 1,000generations,equatingtoroughly4minutesofwall-clocktime.Toprovideadequate statisticalweused30replicaterunswithauniquerandomseedassignedtoeach run. Toeachniche'slocation,weusedDasandDennis's[30]systematicapproach inordertogenerateauniformlydistributedgridofreferencepointsintheobjectivespace onanormalizedhyperplanein N 1dimensions.Thegranularityofthisreferencegrid's resolutioncanbespbythedomainexpertbasedonthenumberofintervals( p )along eachofthehyperplane'sedges.Thetotalnumberofreferencepoints( H )foran M -objective problemisgivenbyEquation(7.1).InourRDMapplicationwheresolutionsweretobe optimizedalongthreeobjectives( M =3),eachofthe2Dhyperplane'sedgeswasdivided into20intervals( p =20),producingatotalof231uniqueuniformly-distributedreference points. H = M + p 1 p (7.1) Toassesssolutionsetdiversityduetoniching,wevisuallyinspectedthesearchcoverage 123 foreachreplicaterunusing NSGA-IIIPlato .Inordertodemonstratethateachrunconsis- tentlyachievedthesamelevelofcoverage,solutionsfromanindividualrunwereassigned the same ,uniquecoloralongared-bluegradient(i.e.,Run 1 =Red ::: Run 30 =Blue).Using niching,weobservedthatatlylargeregionoftheParetosurfacewasconsistently foundandreturnedbyeachexperimentalrunwhencomparedtotheachievedcoverageof previousPlatoapproaches(Figure6.7).Assuch,theevendistributionofeachrunacross thefullobjectivespacehasyieldedanoverallpurplecoloringofthecombinedresults.More importantly,solutionsofvaryingsizesandcomplexitieswereevolved,maintained,andre- turned.Thisresultdemonstratesthatnichingwasabletoovercomeandmitigatethehidden searchbiascausedbynon-uniformchangestosolutionobjectives,acriticalpropertyfor maximizingthenumberoftRDMdesignsaswellastheirassociated Figure7.1:Thereturnedsolutionsfor NSGA-IIIPlato plottedwithinthree-dimensionalob- jectivespace. ToquantifyandcomparethesearchvolumeforeachofthePlatoapproaches,weusedthe hypervolumeindicator [116]tomeasurethevolumedominatedbyPareto-optimalsolutions 124 inthepopulation.Thepercentageoftheobjectivespace'stotalhypervolumethatis dominatedbya single runacrossthetPlatoapproachesissummarizedinFigure7.2. Figure7.2:AveragepercentageofthehypervolumedominatedbyeachPlatoapproach's solutions Byleveragingniching,NSGA-IIIachievedatincrease(p ˝ 0.01)inaverage searchcoveragethatwas1.6-1.7timesgreaterthantheaverage Plato run,2.9-3.0times greaterthantheaverage TargetingPlato run,and1.4timesgreaterthantheaverage NSGA-II Plato run.However,duetothenon-convexParetosurface, Plato couldnotachieveequivalent searchcoverage,evenwithmultipleruns,sincetheinteriorofthissurfaceisunreachable bylinear-weightedapproaches.Usingnumeroustargetvaluecombinations, TargetingPlato couldachievecomparablesearchcoverage,however,thisiscomputationallyexpensiveand requires complete knowledgeoftheParetosurface'slocationtoensuresub-optimalsolutions arenotreturned.Similarto Plato ,the NSGA-IIPlato approachcouldnotachieveequivalent searchcoverageduetothenon-uniformchangestosolutionobjectivesduringmutationthat restrictssearchtoalimitedregionoftheParetosurface. 125 7.3RelatedWork Asapreviouslyundiscoveredhiddensearchbiascausedbynon-uniformchangesto solutions'objectivevalues,theuseofreferencepoint-basednichingtomitigatethisissuehas notbeenpreviouslypresentedintheliterature.Thekeyfactorthatenabledreferencepoint- basednichingtoovercomethishiddensearchbiaswasthatnicheswere explicitlyd andmaintainedduringsearch.Alternativenichingstrategies[97]oftenrelyonnichesto dynamicallyemerge intheobjectivespacebasedonsolutionproperties. In sharing and clearing strategies[53,57,96],aresource(e.g.,objectivevalueor isapportionedtoindividualswithinauser-nicheradius(threshold)ineither theobjectiveorsolutionspace.Inthesestrategies,nichesemergeassolutionsaredriven towardssparsely-populatedregionstoavoidsharingandcompetingfortheirniche'sresource withmorepopulationmembers.However,thesestrategiesmaybebiasedagainstsolutions whoseobjectivevaluesexperiencelittlevariationasthesesolutionsmorerapidlyacquire nichemembers. Clustering operators[97],suchas k -means,canbeusedinplaceofa nicheradiusforallocatingindividualsinto k nichesbasedontheirproximitytoacentroid, however,analysisofthisapproachdemonstratedthatthisapproachwasunsuccessful atmitigatingthesearchbias. In crowding strategies[32,37],competitiontakesplacebetweenparentsand forinclusioninthenextgeneration'spopulation,wherecrowdoutthemostsimilar individualfromarandomlyselectedsubsetofuser-specsize,oftenreferredtoasthe crowdingfactor.Inthesestrategies,nichesemergeassolutionsaredrivenawayfromother memberstolowertheprobabilityofbeingselectedforreplacement.UsingNSGA-II,weob- servedthatcrowdingstrategiesremainsusceptibletosearchbiasasparentswhoseobjectives experiencehighvariationarelikelytobemoredissimilartotheirandthereforemay beprioritizedduringsearch. Similarly,the -dominance [36]strategyexpandstherangeofobjectivevaluesconsid- eredtobe dominated byaparticularsolutionbyaddingasmallvalue( )toeachobjective 126 measure.Nichesemergeassolutionsaredrivenawayfromothermemberstolowerthe probabilityofbeingplacedintoadominatedfront.However,thisstrategyisvulnerableto similarhiddeninteractionssinceitrequiresnichestobedynamicallycreatedbysolutionsas opposedtoexplicitlybeingOnceasolutionbecomestrulyPareto-optimal,neigh- boringsolutionsmustbeabletomutateoutsidetherangeofobjectivevaluesconsideredto bedominatedwhichmaybeinregionswherethesevaluesexperiencelessvariation, thusbiasingsearchagainsttheseregions. Referencegrid nichingstrategiestypicallydividetheobjectivespaceintosubspaces eitherthroughanexplicitdistributionofniches(e.g.,NSGA-III)orbyallowingnichesto emergefromsolutionproperties.TheParetoArchivedEvolutionaryStrategy(PAES)[69] performsthelatterbyrecursivelybisectingtherangeofcurrentobjectivevaluestodetermine whethertoarchiveasolution.Onepotentialshortcomingofthisstrategy,however,isthat thedegreetowhichasolutioniscrowdedthearchivalofsolutions.Sincearchived solutionswhoseobjectivevaluesexperiencelessvariationbecomecrowdedmorerapidly, thesesolutionsmaybefrequentlyselectedbyPAESforreplacementandbiasedagainst.In contrast,referencegridstrategiesthatexplicitlyniches,suchasNSGA-III,arenot susceptibletothelevelofcrowdingwithinaniche,andthereforethenichesarepreservedby keepingatleastoneassociatedmemberinsubsequentgenerationsofsearch. 7.4Discussion Theexperimentsinthischapterhavedemonstratedthevalueof referencepoint-based niching forapplicationsbytwokeyfeatures:(1)solutionsetdiversityisapriorityand (2)objectivevaluesofsolutionsareunequallybymutation.Multi-objectivegenetic algorithms,suchasNSGA-II,oftenseektoreturna diverse setofPareto-optimalsolutions andmayincorporatesearchoperators(e.g.,crowding-distance)thatareresponsivetothe distancesthatsolutionsmutateintheobjectivespace.Whensolutions'objectivevalues aredisproportionatelybymutation,however,theseoperatorsarebiasedtowards 127 solutionswhoseobjectivevaluesexperiencegreaterchangesduetotheirabilitytoescape intolesscrowded,novelregionsoftheobjectivespace. Referencepoint-basednichingmitigatesthisissuebyperformingtwokeyfunctions. First,nichesare explicitly createdandmaintaineduniformlythroughouttheobjectivespace inregionsforsearchtoreach.Thesolutionsintheseregionsmayeitherbetoo toconstructbyrandommutationaloneorbiasedagainstduetosmallerchanges totheirobjectivevalues.Nichingproducesastrongselectivepressureforsolutionsto sparselypopulatednichesinordertominimizecompetitionandincreasetheirchancesof survivalintothenextgeneration.Asaresult,solutionsareconstantlydriventoequally spreadacrosstheobjectivespaceresultinginthetobservedincreaseinsearch coverage(i.e.diversity)whencomparedwithpreviousapproaches.Second,referencepoint- basednichingensuresthatonlysolutionswithsimilarproperties(i.e.solutionsizeor Cost ) arelocalizedwithinthesamenichepromotingfaircompetitionamongsolutions. Althoughthevariable-lengthgenomedesignintheRDMapplicationcausednon-uniform changestosolutionobjectives,thisscenarioisonlyoneofmanytwaysthatthishid- densearchbiasmaymanifestitselfinanapplication.Forexample,ifthemappingbetween solutionelementsandproblemobjectiveschangesovertime,thensolutionswhoseobjectives aremappedtofewerelementswillexperiencegreaterchangestotheirobjectives,and,as aresult,thesesolutionsmaybepreferredduringsearch.Alternatively,ifanobjective's granularityisnon-uniform,thenasearchbiasmayexistforsolutionsinmorecoarse-grained regionsoftheobjectivethatexperiencemorevariation.Moreover,ifthegranularitiesbe- tweenobjectivesaret,thensolutionsabletooptimizealongthecoarserobjective moreeasilymaybeprioritized.Objectivefunctiongranularityhasbeenrecentlyhighlighted [76]asanimportantfutureresearchareaforitsonsearchdynamicsandperformance. Theseissuesareexacerbatedfurtherindynamicoptimizationproblems(DOPs)[12]asboth theParetosurfaceandgranularityofobjectiveschangeovertimethusunderscoringthe importanceofniching.Ourresultsprovideakeyinsightintonichingfeaturesusefulforover- 128 comingthishiddenbiastoaidresearchersexploringmulti-objectiveoptimizationindomains sharingsimilarqualities. 129 Chapter8 ConclusionsandFutureWork Inthischapter,weconcludebysummarizingthecontributionsofthisdissertationand outlinefutureavenuesofresearchinthisarea. 8.1SummaryofContributions Assoftwaresystemsbecomemoreubiquitousbytakingonnewcomplexrolesandap- plications,thereisanincreasingdemandforsystemscapableofself-adaptinginresponse tochangesintheirenvironmentandsystemrequirements.Ashumandevelopers,itisoften infeasibletoidentifyoranticipatethepossiblecombinationsofsystemand/orenvironmental conditionsthatmightbeencounteredoncethesystemhasbeendeployed.Whilesearchtech- niques,suchasevolutionarycomputation,arecapableofdynamicallygeneratingdesignsor foradaptivesystemsatruntime,achallengingconcernforthesetechniques isoperatingwithinthecontextofuncertainty.Assuch,modelsandtechniquesthatcan successfullymanageormitigateuncertaintyarevitaltothedesignofourfutureadaptive embeddedcontrollers.Thisdissertationhasaddressedthreecontextsofuncertaintywhile harnessingevolutionarysearchforthegenerationofadaptivecontrollers,namely,(1)inthe problemdomain,(2)inthesolutionspace,and(3)duringtheevolutionarysearchprocess. First,uncertaintyisinherentwhenapplyingevolutionarysearchtonewproblem domains,particularlyassystemcapabilitiesand/ortheenvironmentundergot 130 changesthatoftenleadtounwieldyinstructionsetscontainingunrealizableorhighly- customizedinstructions.Toaddressuncertaintyinthe problemdomain relatedtothese issues,weintroducedthe DigitalEnzyme(DZ) computationalmodelinspiredbytherole ofsignaltransductionandenzymesfoundinbiologicalcells.Thismodel'sdesignencodes aspectsoftheenvironmentandsystemintoamanipulablebitstringformat,ratherthanthe instructionset,allowinginformationtobeassembledandrepurposedduringsearch.Asa result,ourDZmodelcanmoreivelymanageuncertaintywithintheproblemdomain byusingasetof compact , realizable ,and problem-independent instructions.Inaddition,our modelavoidstimingdependencieswiththeenvironmentthatoftenleadtobrittlecontroller designsbyensuringthemostrecentstateoftheenvironmentisavailablethroughoutits execution. Second,uncertaintycanalsoarisewithinthe solutionspace withrespecttounder- standingandverifyingevolvedsolutionlogicaswellastheinternaldecisionprocesstobe usedtotranslateinformationfromtheenvironmentintomeaningful,robustbehaviors.To accommodateuncertaintyinthesolutionspace,wepresentedthe DynamicDigitalEnzyme (DDZ) computationalmodelthatextendedourDZmodel'sdesigntoincorporateadynamic genomeandrunqueuestructures.Thisdesignstrategysupportstheopen-endedevolution ofkeyinternalcontrolcomponents,suchasthenumberofexecutingprogramsandthreads, andfacilitatessearchbyallowingsolutionstostartinalowerdimensionalsearchspace anddynamicallyaddcomplexityovertime,asnecessary,toconstructbsolutions. Moreover,inboththeDZandDDZmodels,evolvedsolutionlogicremainsintheformof assembly-likeinstructionsthatareamenabletoautomatedorhumananalysis. Third,uncertaintycanbeintroducedinavarietyoftways duringevolution- arysearch thatconnectsboththeproblemdomainandthesolutionspace.Inthiswork, weinvestigateuncertaintyduringsearchasitrelatestothecompetinginteractionsamong thesearch objectives andevolutionary operators .Tomitigatetheofobjective-based uncertaintythatpreventedlargeregionsoftheobjectivespacefrombeingdiscovered,we 131 presentedatargetgoal-basedapproachthatrewardssolutionswhosecharacteristicsmore closelyresembletheuser's\ideal"solution.Thisapproachwasshowntoexpandsearchcov- erageintothesepreviouslyundiscoveredregionsandprovidesamoreintuitivespcation methodfordomainexperts.Finally,throughanempiricalstudy,wedetectedthepresenceof ahiddenfeatureinteractioninpopulationswhosesolutionsexperiencenon-uniformchanges totheirobjectivevaluesduetomutation.Wedemonstratedthatakeysearchoperatorin multi-objectiveevolutionaryalgorithmsrespondstothesechangesbyprioritizingsolutions whoseobjectivevaluesexperiencedgreatervariationovertimeandbiasingsearchtowardsa tlylimitedregionoftheobjectivespace.Tomitigatethisunwantedsearchbiasdue tooperator-baseduncertainty,weproposedanalternativeroleforreferencepoint-basednich- ingtoexplicitlycreateandmaintainfavorableregionsintheobjectivespacethatpromoted faircompetitionamongsolutions. 8.2FutureWork Asresearcherscontinuetouseevolutionarysearchforuncoveringoptimalsolutions withintheirrespectiveproblemdomains,itwillbecomeincreasinglymoreimportantthat wecontinuetodevelopmethodsandapproachestoaccommodate,reduce,ormitigatethe uncertaintyinherentwithinthethreecontextsoutlinedinthiswork.Inthissection,we overviewfollow-onareasofinvestigationtoaddressuncertaintywithintheproblemdomain, solutionspace,andduringthesearchprocess. 8.2.1UncertaintyintheProblemDomain. First,tostudyandcomparethetypesofstructures(e.g.,simplefunctions,looping, feedback,branching,etc.)andenvironmentalfactorsthatnaturallyevolveanddrivethe internalcontrollogicwithincontrollers,ourcomputationalmodelscouldbeappliedtonew biologically-inspiredproblemssuchasthepredator-prey,colonymigration,andtracking problems.Bydiscoveringandunderstandingcommon\designpatterns"withincontrollers 132 evolvedacrossmultipledomains,high-levelinstructionscanbedevisedtoencapsulatethese controlpatternsinordertofacilitatesearchandthusbetteraccommodateuncertaintyinthe problemdomain.Inadditiontothesenewapplicationdomains,ourcomputationalmodel canbeusedtoevolvebehaviorformorecomplex,simulatedagents,suchasthee-Puck, quadruped,orquadrotorrobots,tostudyinstructionsandcontrolstructuresthatb thetransferabilityofevolvedsolutionsontoreal-worlddeployedsystems.Finally,similarto howweaccommodateduncertaintyinthesolutionspacebystartingsolutionsinalower- dimensionalsearchspaceandincrementallyaddingcomplexityovertime,anotherinteresting topicistostudyhowfeaturesoftheproblemdomaincanbeallowedto\complexify"over timeinordertoaccommodateuncertaintyintheproblemdomain.Oneapproachwouldbe toincorporatedynamicbitstringsintoourcomputationalmodelwhosesizecanevolveand adapttomatchthelevelofprecisionnecessarytoconstructoptimalstrategies. 8.2.2UncertaintyintheSolutionSpace. InourDDZmodel,thedynamicgenomeandrunqueue'ssupportfortheopen-ended evolutionofkeycontrolcomponentsdemonstratedatperformanceimprovement overourstaticDZmodelwherethenumberoftheseelementswased.Moreover,analysis ofevolvedcontrollers'internalcompositionrevealedthatourDDZmodelsupportedawide varietyofdesignsrangingfromsingle-program,single-enzymecontrollerstomany-program, many-enzymecontrollers.However,achallengetoelystudyandcomparethetypes ofevolvedcontrolstructuresisdeterminingwhichstructuresofasolutionarenecessaryfor implementingitsbehavior.Inordertoreduceuncertaintythatsurroundsdeterminingwhich solutioncontrolelementsareessential,afutureinvestigationcanexplorehowtoincorpo- rateanenergymodelwhereeachinstructionexecutedbyacontrollerisassociatedwithan energycost,asistrueofmanybiologicalsystems.Byrequiringsolutionstoexpendenergy (e.g.,theprograms,executingthreads,andinstructionsthatarenon-essentialwill beselectedagainstandremovedduringsearchinordertopromoteterse,optimalsolutions 133 containingonlyessentialelements.Moreimportantly,byassociatingcostsattheinstruc- tionlevel,wearestillabletosupportopen-endedevolutionwithrespecttothenumberof programs(i.e.genes)andthreads(i.e.enzymes). Toaccommodateuncertaintyinthesolutionspaceregardingtheinter-processsharing andexchangeofinformation,ourDDZmodelcanpotentiallybeextendedwithtwoadditional controlstructures.Inbiologicalcells,akeyfunctionalunitisthegel-likesubstancethat isenclosedandwsthroughoutthecell,therebymovingandtransferringmolecules(e.g., information)betweentcellentities.Similarly,withinanembeddedcontroller,shared memoryallowsinformationtobeexchangedbetweentexecutingprocesses.One possibleextensiontoourDDZmodelistoaddasharedmemoryregionaddressableby digitalmoleculesandusefulforstoringand/orretrievingmoleculesto/fromtheregisters ofexecutingenzymes.Asecondphenomenoninbiologicalcellsisreferredtoasprotein moonlightingwherebygenes(i.e.programs)canbesharedandtakeonalternativerolesin tproteinssuchasenzymes.Withinsoftwaresystems,suchasembeddedcontrollers, proteinmoonlightingisanalogoustocallingasharedlibraryfunctionorprocedure.The secondextensiontoourDDZmodelisasharedinstructionregionformaintainingalibraryof \functions"thatcanbeaddressedandexecutedbyanyexecutingenzyme.Byincorporating thisfeatureintoourmodel,commonfunctionalityorcontrolstructuresthatnormallywould berequiredtoevolve separately withineachprogram(i.e.,gene)couldbemaintainedinone sharedregion,thushelpingreducetheoverallsolutionspaceandfacilitatingthet discoveryofoptimalsolutions. 8.2.3UncertaintyduringSearch. Whilewehavedetectedandsuccessfullymitigatedtwoformsofuncertaintyduring search,namely,objective-baseduncertaintyandoperator-baseduncertainty,twoadditional sourcesarecandidatesforourfutureworkincludingenvironmentalandconstraint-basedun- certainty. Environmentaluncertainty occursattheinterfacebetweentheevolvedadaptive 134 system(e.g.,sensorsandinputs)andtheenvironment(e.g.,featuresandconditions).At thisinterface,systemsensorsdictatetheenvironmentalfeaturesthatarecapableofbeing monitoredandtherefore,thatareavailableduringthedecision-makingprocess.Uncertainty atthisinterfaceincludesdeterminingwhichfeaturesareimportant(oravailable)froma potentiallyhigh-dimensionalsetofenvironmentalfeaturesandforthosefeaturesthatare important,whetherasensor'srangeisknown,whetherasensorisnoisyversusreliable,and whichcombinationsofenvironmentalfeaturesarenecessarytoprovideresiliencyintheface offailure.Moreover,evaluatinganevolvedsystemforallpossiblecombinationsofenviron- mentalfeatures,orevenalargesetofsuchfeatures,isoftentoocostlytoconstructortoo computationallyexpensivetoenumerate.Asaresult,uncertaintyexistsduetotheabsence ofenvironmentalinformationorpresenceofincompleteorimperfectenvironmentalinfor- mation. Constraint-baseduncertainty pertainstorestrictionsthatgoverntheevolutionary searchprocessthatmustbeinorderforanevolvedsolutiontobeconsideredvalid. Theseconstraintsoftenappearasminimumormaximumboundsonfreedesignvariables (e.g.,alimitonanavailableresource)butmayalsorepresentapropertythatmust bemaintainedbytheoverallsolution(e.g.,aconnectionpathmustexistbetweenallsystem components).Similartotheproblemobjectives,theconstraintsthatgovernsearchareoften moadded,aswellasremovedovertime,therebymakingtheirdynamicnatureasource ofuncertaintyduringsearch. Thediscoveryofthishiddeninteractionintheofmulti-objectiveoptimizationun- derscorestheimportanceofdevelopingformaltestproblemsthatcapturethekeyproblem featuresdisruptingsearchandallowresearcherstoadjustthedegreetowhichthefeatures mayvaryinordertodeveloptechniquestomitigatetheirunwantedTheindustry- providedRDMproblemusedinthisworkisoneexampleofabroadofproblems, referredtoasdiscrete/combinatorialoptimizationproblems,thatarelikelytobeimpacted bythishiddenfeatureinteractionwhencoupledwithevolutionaryoperatorsresponsiveto thenon-uniformchangesinsolutions'objectivevalues.Asimpleexampleofaformaltest 135 problemthatcapturesthekeyfeaturesofthisinteractionisaDynamicKnapsackProblem wherethegoalistooptimizethetotalvalueofitemsplacedintoknapsackswithvaryingstor- agecapacities.SimilartoourRDMproblem,evolutionarysearchwouldbebiasedtowards knapsackswithsmallerstoragecapacitiesastheaddition/removalofitemsintheseknap- sackscausesagreaterchangetoobjectivevaluesthanlargeknapsacksandwouldthereby beprioritizedbyadiversity-preservingoperator. Finally,objectivefunctiongranularityhasbeenrecentlyhighlighted[76]asanimpor- tantfutureresearchareaforitsonsearchdynamicsandperformance.Whilereference point-basednichinghasbeenshowntosuccessfullymitigatetheadverseofthishid- deninteraction,avarietyofalternativenichingstrategiesexistandhavebeentraditionally usedtopromotediversitywithinpopulations.Oneareaoffutureworktowardsdeveloping techniquesformitigatinguncertaintyduringsearchistoassesstheperformanceofthese alternativestrategiesanddeterminethekeypropertiesthatleadtotheirsuccess. 136 BIBLIOGRAPHY 137 BIBLIOGRAPHY [1] TheBoostGraphLibrary:UserGuideandReferenceManual .Addison-WesleyLong- manPublishingCo.,Inc.,Boston,MA,USA,2002. [2] Modistancecalculationingenerationaldistanceandinvertedgenerationaldis- tance.In EvolutionaryMulti-CriterionOptimization ,volume9019,pages110{125. Springer,2015. [3] LeeAltenberg.Theevolutionofevolvabilityingeneticprogramming.InKennethE. Kinnear,Jr.,editor, Advancesingeneticprogramming ,pages47{74.MITPress,Cam- bridge,MA,USA,1994. [4] GuillermoA.Alvarez,ElizabethBorowsky,SusieGo,TheodoreH.Romer,Ralph Becker-Szendy,RichardGolding,ArifMerchant,MirjanaSpasojevic,AlistairVeitch, andJohnWilkes.Minerva:Anautomatedresourceprovisioningtoolforlarge-scale storagesystems. ACMTransactionsonComputingSystems ,19(4):483{518,November 2001. [5] DavidAndersen,HariBalakrishnan,FransKaashoek,andRobertMorris.Resilient overlaynetworks. SOSPProceedingsoftheEighteenthACMSymposiumonOperating SystemsPrinciples ,35(5):131{145,October2001. [6] Thomasack. EvolutionaryAlgorithmsinTheoryandPractice:EvolutionStrategies, EvolutionaryProgramming,GeneticAlgorithms .OxfordUniversityPress,Oxford,UK, 1996. [7] RichardBellman. DynamicProgramming .PrincetonUniversityPress,Princeton,NJ, USA,1stedition,1957. [8] MiroslavBenda,VasudevanJagannathan,andRajendraDodhiawala.Onoptimal cooperationofknowledgesources-anempiricalinvestigation.TechnicalReportBCS{ G2010{28,BoeingAdvancedTechnologyCenter,BoeingComputingServices,1986. [9] ForrestH.BennettIII.Automaticcreationofantmulti-agentarchitecture usinggeneticprogrammingwitharchitecture-alteringoperations.In Proceedingsof the1stAnnualConferenceonGeneticProgramming ,pages30{38.MITPress,1996. [10] FrancescoBernardini,MarianGheorghe,andNatalioKrasnogor.QuorumsensingP systems. TheoreticalComputerScience ,371:20{33,February2007. [11] NicolaBeume,BorisNaujoks,andMichaelEmmerich.SMS-EMOA:Multiobjective selectionbasedondominatedhypervolume. EuropeanJournalofOperationalResearch , 181(3):1653{1669,September2007. 138 [12] JurgenBranke,ThomasKaubler,ChristianSchmidt,andHartmutSchmeck.Amulti- populationapproachtodynamicoptimizationproblems.In AdaptiveComputingin DesignandManufacturing ,pages299{308.Springer,2000. [13] JurgenBrankeandHartmutSchmeck.Designingevolutionaryalgorithmsfordy- namicoptimizationproblems.In AdvancesinEvolutionaryComputing ,pages239{262. Springer,NewYork,NY,USA,2003. [14] AlanBrown. NerveCellsandNervousSystems:AnIntroductiontoNeuroscience . Springer,1991. [15] ThomasBrunl. EmbeddedRobotics:MobileRobotDesignandApplicationswithEm- beddedSystems .Springer,3rdedition,2008. [16] ChadByers,BettyH.C.Cheng,andKalyanmoyDeb.Unwantedfeatureinteractions betweentheproblemandsearchoperatorsinevolutionarymulti-objectiveoptimiza- tion.In EvolutionaryMulti-CriterionOptimization ,volume9018of LectureNotesin ComputerScience ,pages19{33.Springer,2015. [17] ChadByersandBettyH.C.Cheng.Anapproachtomitigatingunwantedinteractions betweensearchoperatorsinmulti-objectiveoptimization.In Proceedingsofthe17th AnnualConferenceCompaniononGeneticandEvolutionaryComputation ,GECCO '15,pages655{662,NewYork,NY,USA,2015.ACM. [18] ChadByersandBettyH.C.Cheng.Digitalenzymes:Cooperativeagentsofreaction forroboticcontrollers(draftunderrevision). ALife ,2015. [19] ChadByers,BettyH.C.Cheng,andPhilipMcKinley.Exploringtheevolutionofin- ternalcontrolstructureusingdigitalenzymes.In Proceedingsofthe14thInternational ConferenceonGeneticandEvolutionaryComputationConferenceCompanion ,pages 1407{1408,NewYork,NY,USA,2012.ACM. [20] ChadByers,BettyH.C.Cheng,andPhilipK.McKinley.Digitalenzymes:Agents ofreactioninsideroboticcontrollersfortheforagingproblem.In Proceedingsofthe 13thInternationalConferenceonGeneticandEvolutionaryComputationConference , pages243{250,NewYork,NY,USA,2011.ACM. [21] AlexandreCampoandMarcoDorigo.tmulti-foraginginswarmrobotics.In Proceedingsofthe9thEuropeanConferenceonAdvancesinALife ,ECAL'07, pages696{705,Lisbon,Portugal,2007.Springer. [22] ViraChankongandYacovHaimes. MultiobjectiveDecisionMakingTheoryand Methodology .ElsevierScience,NewYork,1983. [23] SinManCheang,KwongSakLeung,andKinHongLee.Geneticparallelprogram- ming:Designandimplementation. IEEETransactionsonEvolutionaryComputation , 14:129{156,June2006. 139 [24] CarlosCoelloCoello,GaryLamont,andDavidvanVeldhuizen. EvolutionaryAlgo- rithmsforSolvingMulti-ObjectiveProblems(GeneticandEvolutionaryComputation) . Springer,Secaucus,NJ,USA,2006. [25] JaredCohon. MultiobjectiveProgrammingandPlanning ,volume140.CourierDover Publications,2004. [26] ThomasCormen,CharlesLeiserson,RonaldRivest,andClStein. Introduction toAlgorithms,ThirdEdition .TheMITPress,3rdedition,2009. [27] DavidCorne,JoshuaKnowles,andMartinOates.Theparetoenvelope-basedselec- tionalgorithmformultiobjectiveoptimization.In ProceedingsoftheParallelProblem SolvingfromNatureVIConference ,pages839{848.Springer,2000. [28] IainCouzin,JensKrause,NigelFranks,andSimonLevin.eleadershipand decision-makinginanimalgroupsonthemove. Nature ,433(7025):513{516,2005. [29] CharlesDarwin. Ontheoriginofspecies .NewYork:D.AppletonandCompany,1871. [30] IndraneelDasandJ.E.Dennis.Normal-boundaryintersection:Anewmethodfor generatingtheparetosurfaceinnonlinearmulticriteriaoptimizationproblems. SIAM JournalonOptimization ,8(3):631{657,March1998. [31] IndraneelDasandJohnDennis.Acloserlookatdrawbacksofminimizingweighted sumsofobjectivesforparetosetgenerationinmulticriteriaoptimizationproblems. Structuraloptimization ,14(1):63{69,1997. [32] KennethDeJong. AnAnalysisoftheBehaviorofaClassofGeneticAdaptiveSystems. PhDthesis,AnnArbor,MI,USA,1975.AAI7609381. [33] KennethDeJong.EvolutionaryComputation:AApproach.In Proceedingsof the10thInternationalConferenceonGeneticandEvolutionaryComputationConfer- ence ,pages2245{2258,NewYork,NY,USA,2008.ACM. [34] KalyanmoyDeb. Multi-ObjectiveOptimizationUsingEvolutionaryAlgorithms .John Wiley&Sons,Inc.,NewYork,NY,USA,2001. [35] KalyanmoyDebandHimanshuJain.Anevolutionarymany-objectiveoptimization algorithmusingreference-point-basednondominatedsortingapproach,parti:Solving problemswithboxconstraints. IEEETransactionsonEvolutionaryComputation , 18(4):577{601,Aug2014. [36] KalyanmoyDeb,ManikanthMohan,andShikharMishra.Evaluatingtheepsilon- dominationbasedmulti-objectiveevolutionaryalgorithmforaquickcomputation ofpareto-optimalsolutions. IEEETransactionsonEvolutionaryComputation , 13(4):501{525,December2005. [37] KalyanmoyDeb,AmritPratap,SameerAgarwal,andTMeyarivan.Afastandeli- tistmultiobjectivegeneticalgorithm:Nsga-ii. IEEETransactionsonEvolutionary Computation ,6(2):182{197,April2002. 140 [38] PatrikD'haeseleer.Contextpreservingcrossoveringeneticprogramming.In Interna- tionalConferenceonEvolutionaryComputation ,pages256{261,1994. [39] CeciliaDiChioandPaoloDiChio.Group-foragingwithparticleswarmsandgenetic programming.In Proceedingsofthe10thEuropeanConferenceonGeneticProgram- ming ,EuroGP'07,pages331{340,Valencia,Spain,2007.Springer. [40] MarcoDorigoandLucaMariaGambardella.Antcolonysystem:Acooperativelearn- ingapproachtothetravelingsalesmanproblem. IEEETransactionsonEvolutionary Computation ,1(1):53{66,1997. [41] FrancisYsidroEdgeworth.Mathematicalpsychics:Anessayontheapplicationof mathematicstothemoralsciences.london:Keganpaul,1881. [42] A.E.EibenandC.A.Schippers.Onevolutionaryexplorationandexploitation. Fun- damentaInformaticae ,35(1-4):35{50,January1998. [43] RamonFabregat,YezidDonoso,BenjamBaran,FernandoSolano,andJoseMarzo. Multi-objectiveoptimizationschemeformulticastws:Asurvey,amodelanda moeasolution.In Proceedingsofthe3rdInternationalIFIP/ACMLatinAmerican ConferenceonNetworking ,LANC'05,pages73{86,NewYork,NY,USA,2005.ACM. [44] DoyneFarmer,NormanPackard,andAlanPerelson.Theimmunesystem,adaptation, andmachinelearning. PhysicaD:NonlinearPhenomena ,2(1-3):187{204,October 1986. [45] MarkFleischer.Themeasureofparetooptimaapplicationstomulti-objectivemeta- heuristics.In Proceedingsofthe2ndInternationalConferenceonEvolutionaryMulti- criterionOptimization ,EMO'03,pages519{533,Berlin,Heidelberg,2003.Springer. [46] LawrenceFogel,AlvinOwens,andMichaelWalsh. Aintelligencethroughsim- ulatedevolution .Wiley,Chichester,WS,UK,1966. [47] CarlosFonsecaandPeterFleming.Geneticalgorithmsformultiobjectiveoptimization: Formulationdiscussionandgeneralization.In Proceedingsofthe5thInternationalCon- ferenceonGeneticAlgorithms ,pages416{423,SanFrancisco,CA,USA,1993.Morgan Kaufmann. [48] ChristianGagnandMarcParizeau.Genericityinevolutionarycomputationsoftware tools:Principlesandcase-study. InternationalJournalonAIntelligenceTools , 15(2):173{194,2006. [49] DavidGarlan,Shang-WenCheng,An-ChengHuang,BradleySchmerl,andPeter Steenkiste.Rainbow:Architecture-basedself-adaptationwithreusableinfrastructure. Computer ,37(10):46{54,October2004. [50] MarianGheorghe,CarlosMartVictorMitrana,andMarioJ.PerezJimenez. Anagentbasedapproachofcollectiveforaging.In ProceedingsoftheAand NaturalNeuralNetworks7thInternationalConferenceonComputationalMethodsin 141 NeuralModeling-Volume1 ,IWANN'03,pages638{645,o,Menorca,Spain,2003. Springer. [51] Chi-KeongGohandKayChenTan. EvolutionaryMulti-objectiveOptimizationin UncertainEnvironments:IssuesandAlgorithms .Springer,1stedition,2009. [52] DavidGoldberg. GeneticAlgorithmsinSearch,OptimizationandMachineLearning . Addison-Wesley,Boston,MA,USA,1stedition,1989. [53] DavidGoldbergandJonRichardson.Geneticalgorithmswithsharingformultimodal functionoptimization.In Proceedingsofthe2ndInternationalConferenceonGenetic AlgorithmsonGeneticAlgorithmsandTheirApplication ,pages41{49,Hillsdale,NJ, USA,1987.L.ErlbaumAssociates. [54] PrabhatHajelaandChyi-YeuLin.Geneticsearchstrategiesinmulticriterionoptimal design. Structuraloptimization ,4(2):99{107,1992. [55] MichaelHansenandAndrzejJaszkiewicz.Evaluatingthequalityofapproximationsto thenon-dominatedset.TechnicalReportIMM-REP-1998-7,1998. [56] JohnHolland. AdaptationinNaturalandASystems:AnIntroductoryAnalysis withApplicationstoBiology,ControlandAIntelligence .MITPress,Cam- bridge,MA,USA,1992. [57] Horn,NicholasNafpliotis,andDavidE.Goldberg.Anichedparetogenetic algorithmformultiobjectiveoptimization.In Proceedingsofthe1stIEEEConference onEvolutionaryComputation,WorldCongressonComputationalIntelligence ,pages 82{87vol.1,Jun1994. [58] DeanHougen,SaifallahBenjaafar,JordanBonney,JohnBudenske,MarkDvorak, MariaGini,HowardFrench,DonaldKrantz,PerryLi,FredMalver,BradleyNelson, NikolaosPapanikolopoulos,PaulRybski,SaschaStoeter,RichardVoyles,andKe- malBerkYesin.Aminiatureroboticsystemforreconnaissanceandsurveillance.In IEEEInternationalConferenceonRoboticsandAutomation ,pages501{507.IEEE, 2000. [59] EvanHughes.Multiplesingleobjectiveparetosampling.In ProceedingsoftheCongress onEvolutionaryComputation ,pages2678{2684,Canberra,Australia,2003.IEEE. [60] EvanHughes.Msops-ii:Ageneral-purposemany-objectiveoptimiser.In IEEE CongressonEvolutionaryComputation ,pages3944{3951,Sept2007. [61] HisaoIshibuchiandTadahikoMurata.Multi-objectivegeneticlocalsearchalgorithm. In ProceedingsoftheIEEEInternationalConferenceonEvolutionaryComputation , pages119{124,May1996. [62] HisaoIshibuchi,MasakazuYamane,andYusukeNojima.tsofdiscreteobjective functionswithtgranularitiesonthesearchbehaviorofemoalgorithms.In Proceedingsofthe14thAnnualConferenceCompaniononGeneticandEvolutionary Computation ,GECCO'12,pages481{488,2012. 142 [63] HisaoIshibuchi,MasakazuYamane,andYusukeNojima.yinevolutionary multiobjectiveoptimizationofdiscreteobjectivefunctionswithtgranularities. In EvolutionaryMulti-CriterionOptimization ,pages230{245,2013. [64] MinwenJi,AlistairVeitch,andJohnWilkes.Seneca:Remotemirroringdonewrite. In USENIXAnnualTechnicalConference ,pages253{268.USENIX,2003. [65] KimberleyKeeton,CiprianoSantos,DirkBeyer,Chase,andJohnWilkes. Designingfordisasters.In Proceedingsofthe3rdUSENIXConferenceonFileand StorageTechnologies ,pages59{62,Berkeley,CA,USA,2004. [66] JamesKennedyandRussellEberhart.Particleswarmoptimization.In Proceedingsof theIEEEInternationalConferenceonNeuralNetworks ,pages1942{1948,Perth,WA, Australia,November1995. [67] JeKephartandDavidChess.Thevisionofautonomiccomputing. Computer , 36(1):41{50,January2003. [68] ScottKirkpatrick,C.D.Gelatt,andM.P.Vecchi.OptimizationbySimulatedAn- nealing. Science ,220,4598(4598):671{680,1983. [69] JoshuaKnowlesandDavidCorne.Approximatingthenon-dominatedfrontusingthe paretoarchivedevolutionstrategy. EvolutionaryComputation ,8(2):149{172,June 2000. [70] King-TimKo,Kit-SangTang,Cheung-YauChan,Kim-FungMan,andSamKwong. Usinggeneticalgorithmstodesignmeshnetworks. Computer ,30(8):56{61,Aug1997. [71] JohnKoza. GeneticProgramming:OntheProgrammingofComputersbyMeansof NaturalSelection .MITPress,Cambridge,MA,USA,1992. [72] JohnKoza,JonathanRoughgarden,andJamesRice.Evolutionoffood-foragingstrate- giesforthecaribbeananolislizardusinggeneticprogramming. AdaptiveBehavior , 1:171{199,October1992. [73] WenguoLiuandAlanModelingandoptimizationofadaptiveforagingin swarmroboticsystems. InternationalJournalofRoboticsResearch ,29:1743{1760, December2010. [74] ThanasisLoukopoulosandIshfaqAhmad.Staticandadaptivedistributeddatareplica- tionusinggeneticalgorithms. JournalonParallelDistributedComputing ,64(11):1270{ 1285,November2004. [75] JunLuandWengangCheng.Agenetic-algorithm-basedroutingoptimizationscheme foroverlaynetwork. 2013InternationalConferenceonComputing,Networkingand Communications(ICNC) ,4:421{425,2007. 143 [76] KentMcClymont.Recentadvancesinproblemunderstanding:Changesintheland- scapeayearon.In Proceedingsofthe15thAnnualConferenceCompaniononGenetic andEvolutionaryComputation ,GECCO'13Companion,pages1071{1078,NewYork, NY,USA,2013.ACM. [77] JulianMiller. CartesianGeneticProgramming .NaturalComputing.Springer,2011. [78] MarvinMinsky. TheSocietyofMind .Simon&Schuster,March1988. [79] DavidMontanaandTalibHussain.Adaptivenofdatanetworksusing geneticalgorithms. AppliedSoftComputing ,4(4):433{444,2004. [80] R.R.Murphy,S.Tadokoro,D.Nardi,A.JaP.Fiorini,H.Choset,andA.M. Erkmen.Searchandrescuerobotics.In SpringerHandbookofRobotics ,pages1151{ 1173.Springer,2008. [81] ShigeruObayashi,KalyanmoyDeb,CarloPoloni,TomoyukiHiroyasu,andTadahiko Murata,editors. Proceedingsofthe4thInternationalConferenceonEvolutionary Multi-CriterionOptimization,EMO2007,Matsushima,Japan,March5-8,2007,Pro- ceedings ,volume4403of LectureNotesinComputerScience .Springer,2007. [82] CharlesOfria,C.TitusBrown,andChrisAdami. TheAvidaUser'sManual .1998. [83] CharlesOfriaandClausO.Wilke.Avida:asoftwareplatformforresearchincompu- tationalevolutionarybiology. ALife ,10(2):191{229,March2004. [84] VilfredoPareto. Coursd'EconomiePolitique .Droz,Geneve,1896. [85] LynneE.Parker.Alliance:Anarchitectureforfaulttolerantmulti-robotcooperation. IEEETransactionsonRoboticsandAutomation ,14:220{240,1998. [86] ElizabethPennisi.Jumpinggeneshopintotheevolutionarylimelight. Science , 317(5840):894{895,2007. [87] A.TownsendPeterson,JorgeSoberon,RichardG.Pearson,RobertP.Anderson,En- riqueMartinez-Meyer,MiguelNakamura,andMiguelBastosAraujo. EcologicalNiches andGeographicDistributions(MPB-49) .MonographsinPopulationBiology.Princeton UniversityPress,2011. [88] D.T.Pham,A.Ghanbarzadeh,E.Koc,S.Otri,S.Rahim,andM.Zaidi.TheBees Algorithm,ANovelToolforComplexOptimisationProblems.In Proceedingsofthe 2ndInternationalVirtualConferenceonIntelligentProductionMachinesandSystems (IPROMS2006) ,pages454{459.Elsevier,2006. [89] RiccardoPoli.Evolutionofgraph-likeprogramswithparalleldistributedgeneticpro- gramming.In Proceedingsofthe7thInternationalConferenceonGeneticAlgorithms , pages346{353,EastLansing,Michigan,1997.MorganKaufmann. 144 [90] GheorgheaunandFranciscoJoseRomero-Campero.Membranecomputingasamod- elingframework:cellularsystemscasestudies.In ProceedingsoftheFormalMethods fortheDesignofComputer,Communication,andSoftwareSystems ,SFM'08,pages 168{214,Bertinoro,Italy,2008.Springer. [91] AndresJ.Ramirez,DavidB.Knoester,BettyH.C.Cheng,andPhilipK.McKinley. Plato:ageneticalgorithmapproachtorun-timeinautonomiccom- putingsystems. ClusterComputing ,14(3):229{244,2011. [92] I.Rechenberg. Evolutionsstrategie:optimierungtechnischersystemenachprinzipien derbiologischenevolution .Frommann-Holzboog,1973. [93] R.Rojas. Neuralnetworks:asystematicintroduction .Springer,1996. [94] P.G.andM.Delbruck.Brownianmotioninbiologicalmembranes. Proceedings oftheNationalAcademyofSciencesoftheUnitedStatesofAmerica ,72(8):3111{3113, August1975. [95] J.DavidScMultipleobjectiveoptimizationwithvectorevaluatedgenetical- gorithms.In Proceedingsofthe1stInternationalConferenceonGeneticAlgorithms , pages93{100,Hillsdale,NJ,USA,1985.L.ErlbaumAssociatesInc. [96] V.SeydiGhomsheh,M.A.Khanehsar,andM.Teshnehlab.Improvingthenon- dominatesortinggeneticalgorithmformulti-objectiveoptimization.In Computational IntelligenceandSecurityWorkshops,2007.CISW2007.InternationalConferenceon , pages89{92,Dec2007. [97] OferM.Shir.Nichinginevolutionaryalgorithms.In HandbookofNaturalComputing , pages1035{1069.SpringerBerlinHeidelberg,2012. [98] M.Sipper.Theevolutionofparallelcellularmachines:towardevolware. Biosystems , 42(1):29{43,March1997. [99] N.SrinivasandKalyanmoyDeb.Muiltiobjectiveoptimizationusingnondominated sortingingeneticalgorithms. IEEETransactionsonEvolutionaryComputation , 2(3):221{248,September1994. [100] KennethStanleyandRistoMiikkulainen.Evolvingneuralnetworksthroughaugment- ingtopologies. IEEETransactionsonEvolutionaryComputation ,10(2):99{127,June 2002. [101] J.H.SuddandN.R.Franks. Thebehavioralecologyofants .NewYork,NewYork, USA,1987. [102] AdrianTrenaman.Concurrentgeneticprogramming,tartarusanddancingagents.In Proceedingsofthe2ndEuropeanWorkshoponGeneticProgramming ,pages270{282, London,UK,1999.Springer. 145 [103] DavidAllenVanVeldhuizen. MultiobjectiveEvolutionaryAlgorithms:ations, Analyses,andNewInnovations .PhDthesis,WrightPattersonAFB,OH,USA,1999. AAI9928483. [104] DavidA.VanVeldhuizenandGaryB.Lamont.Multiobjectiveevolutionaryalgorithm research:Ahistoryandanalysis,1998. [105] JamesAlfredWalker,JulianFrancisMiller,andRachelCavill.Amulti-chromosome approachtostandardandembeddedcartesiangeneticprogramming.In Proceedingsof the8thAnnualConferenceonGeneticandEvolutionaryComputation ,GECCO'06, pages903{910,NewYork,NY,USA,2006.ACM. [106] JamesAlfredWalker,KatharinaVolk,StephenL.Smith,andJulianFrancisMiller. Parallelevolutionusingmulti-chromosomecartesiangeneticprogramming. Genetic ProgrammingandEvolvableMachines ,10:417{445,December2009. [107] W.E.Walsh,G.Tesauro,J.O.Kephart,andR.Das.UtilityFunctionsinAutonomic Systems.pages70{77,2004. [108] R.WittyandD.Scott.Disasterrecoveryplansandsystemsareessential.Technical ReportFT-14-5021,GartnerResearch,September2001. [109] StephenWolfram. CellularAutomataandComplexity .PerseusBooksGroup. [110] F.Xiang,L.Junzhou,W.Jieyi,andG.Guanqun.Qosroutingbasedongenetic algorithm. ComputerCommunications ,22(1516):1392{1399,1999. [111] XinYao.EvolvingNeuralNetworks. ProceedingsoftheIEEE ,87:1423{1447, 1999. [112] B.Yegnanarayana. ANeuralNetworks .Prentice-HallofIndiaPvt.Ltd,2004. [113] QingfuZhangandHuiLi.Moea/d:Amultiobjectiveevolutionaryalgorithmbasedon decomposition. IEEETransactionsonEvolutionaryComputation ,11(6):712{731,Dec 2007. [114] E.Zitzler,M.Laumanns,andL.Thiele.SPEA2:Improvingthestrengthpareto evolutionaryalgorithmformultiobjectiveoptimization.In EvolutionaryMethodsfor DesignOptimizationandControlwithApplicationstoIndustrialProblems ,pages95{ 100,Athens,Greece,2001.InternationalCenterforNumericalMethodsinEngineering. [115] E.ZitzlerandL.Thiele.Multiobjectiveevolutionaryalgorithms:Acomparativecase studyandthestrengthparetoapproach. IEEETransactionsonEvolutionaryCompu- tation ,3(4):257{271,November1999. [116] E.Zitzler,L.Thiele,M.Laumanns,C.M.Fonseca,andV.G.daFonseca.Performance assessmentofmultiobjectiveoptimizers:ananalysisandreview. IEEETransactions onEvolutionaryComputation ,7(2):117{132,April2003. 146 [117] EckartZitzlerandSimonKnzli.Indicator-basedselectioninmultiobjectivesearch. In Proceedingsofthe8thInternationalConferenceonParallelProblemSolvingfrom Nature(PPSN ,pages832{842.Springer,2004. [118] JesseZydallis,DavidvanVeldhuizen,andGaryLamont.Astatisticalcomparisonof multiobjectiveevolutionaryalgorithmsincludingthemomga-ii.In EMO ,volume1993 of LectureNotesinComputerScience ,pages226{240.Springer,2001. 147