ACloserLookattheEvolutionaryDynamicsofSelf仔細(xì)看看自己的進(jìn)化動力學(xué)課件

CreditsThisprojectispartofthesisworkleadingtotheMasterofSciencedegreeinComputationalScience.ResearchissupervisedbyDr.HirokiSayamaUniversityofElectro-Communications,Tokyo,JapanProjecttobecompletedbytheendofthisyear.11/19/20221SectionComputationalScience,UniversiteitvanAmsterdamCreditsThisprojectispartofLecturePlanStatementofProblemFormerworksANewDynamicEnvironmentIdentificationandClassificationGenealogyLarge-scaleSimulationsConclusions11/19/20222SectionComputationalScience,UniversiteitvanAmsterdamLecturePlanStatementofProbl1.StatementofProblemGoal:Tostudytheemergenceofcomplexevolutionaryphenomenathroughasimple,abstractmodel.Method:“…abstractfromthenaturalself-reproductionproblemitslogicalform.”(Neumann)Synthesizeusingcellularautomata(CA).11/19/20223SectionComputationalScience,UniversiteitvanAmsterdam1.StatementofProblemGoal:112.FormerWorks11/19/20224SectionComputationalScience,UniversiteitvanAmsterdam2.FormerWorks11/9/20224SectiTimelinerelatingcurrentworkVonNeumann’sUniversalConstructor19531970GameofLife(Conway)1994Tierra(Ray)1984SRLoop(Langton)1998Evoloop(Sayama)11/19/20225SectionComputationalScience,UniversiteitvanAmsterdamTimelinerelatingcurrentworkTheSelf-ReproducingLoopSheath:Outershellhousinggenesequence.Genes:7s(straightgrowth)and4s(turning).Tube:2swithinsheath.Arm:Extensibleloopstructureforreplication.sheathgenestubearm11/19/20226SectionComputationalScience,UniversiteitvanAmsterdamTheSelf-ReproducingLoopSheatState-transitionRulesLTCBRIRulestaketheformCTRLB>I.Localanddeterministic.11/19/20227SectionComputationalScience,UniversiteitvanAmsterdamState-transitionRulesLTCBRIRuLangton’sSRLoop8states5-cellneighbourhoodProgramforself-replicationcontainedingenesequence(genotype)Deathoccursviafunctionalfailure(limitedinfinitespace)11/19/20228SectionComputationalScience,UniversiteitvanAmsterdamLangton’sSRLoop8states11/9/TheEvoloop9states(SRruleset+dissolvingstate)5-cellneighbourhoodModificationstoSRrulesetintroduceadaptivityleadingtoevolution.Deathoccursviastructuraldissolution.11/19/20229SectionComputationalScience,UniversiteitvanAmsterdamTheEvoloop9states(SRrulesEvoloopCAStatesStateNameFunction0[Black]Background1[Blue]CoreFillstubeofloop2[Red]SheathExternalstructure3[Purple]Structureofarm4[Green]GeneInfoforturningarm5[LightBlue]Messenger6[Yellow]Messenger/Guide/Finisher7[White]GeneInfoforstraightgrowth8[Grey]DissolverDissolvesloopstructure11/19/202210SectionComputationalScience,UniversiteitvanAmsterdamEvoloopCAStatesStateNameFuncPropertiesoftheDissolvingStateAppearsfromundefinedconfigurations.Travelsalongtubetodissolveneighbouringstates.Anycontiguousstructureisextinguished,creatingfreespacefornewloops.11/19/202211SectionComputationalScience,UniversiteitvanAmsterdamPropertiesoftheDissolvingSQualitiesoftheEvoloopCASimpleandscalable:Smallruleset(95=59049rules)NocentraloperatingsystemPurelydeterministic(nostochasticoperationsinruleset).Adaptable.Realizesanemergentevolutionaryprocess.11/19/202212SectionComputationalScience,UniversiteitvanAmsterdamQualitiesoftheEvoloopCASimPredictabilityoftheEvoloopContinuousself-reproductionleadstohigh-densitylooppopulations(nofreespace).Interactionofphenotypesfavourssmall-sizedloops.Evolutionendswithahomogeneoussingle-speciespopulation.Nodiversity,nospeciation,noevolution.11/19/202213SectionComputationalScience,UniversiteitvanAmsterdamPredictabilityoftheEvoloopCConclusion:modifytheenvironment.EvolutioninaPeriodicDomain11/19/202214SectionComputationalScience,UniversiteitvanAmsterdamConclusion:modifytheenviron3.ANewDynamicEnvironment11/19/202215SectionComputationalScience,UniversiteitvanAmsterdam3.ANewDynamicEnvironment11TenthstateaddedtoEvoloopCA.Rulesnearlyidenticaltodissolvingstate,butpersistsintimeforafiniteperiodN(persistenceorlifetime).Purelypartoftheenvironment:loopswillneverproduceitontheirown.ThePersistentDissolvingState11/19/202216SectionComputationalScience,UniversiteitvanAmsterdamTenthstateaddedtoEvoloopCTheMemoryLayerMemorylayeractsascounter,decrementinglifetimeeachiterationifdissolvercellisabove.Whenlifetimereacheszero,counterisresetanddissolvercellisremoved.Doesnotdirectlyinteractwithneighbouringlooplayerstates.CTBLRILoopLayerMNMemoryLayer11/19/202217SectionComputationalScience,UniversiteitvanAmsterdamTheMemoryLayerMemorylayeraPersistenceandScaleThechoiceofthepersistenceNimposesafixedscaleonthesystem.Asdomainisexpanded(gridsize),Ncanbeusedto“scale”thepopulationclustersize.11/19/202218SectionComputationalScience,UniversiteitvanAmsterdamPersistenceandScaleThechoicPersistenceandScaleSignsofcomplexevolutionaryphenomena.Speciationandlong-termdiversity(phenotype).Conclusion:tounderstandwhat’shappening,weneedbetteranalysis…11/19/202219SectionComputationalScience,UniversiteitvanAmsterdamPersistenceandScaleSignsof4.IdentificationandClassification17d55555/13x1311/19/202220SectionComputationalScience,UniversiteitvanAmsterdam4.IdentificationandClassifiNewDefinitionsGenotype:sequenceofstates‘0’,‘1’,‘4’,and‘7’insidealoop’stubestructure.Phenotype:sizeofinnersheath.Birth:appearanceofstate‘6’(umbilicalcorddissolver).Death:dissolutionofanyinnersheathstate.11/19/202221SectionComputationalScience,UniversiteitvanAmsterdamNewDefinitionsGenotype:sequePropertiesofLoopSpecies“Stationary”(identification):GenotypePhenotype“Reproductive”(classification):Existenceandidentityoffirst-bornoffspringinfreespace.11/19/202222SectionComputationalScience,UniversiteitvanAmsterdamPropertiesofLoopSpecies“StaIdentificationofLoopSpecies17d5555513x13Identifier:17d55555/13x13LoopReplicationGenotypePhenotype11/19/202223SectionComputationalScience,UniversiteitvanAmsterdamIdentificationofLoopSpeciesGenotype-basedCharacteristics41f55/6x613e95/6x65f541/6x6Speciesofthesamephenotypebutdifferentgenotypeexhibitdistinctdynamics:11/19/202224SectionComputationalScience,UniversiteitvanAmsterdamGenotype-basedCharacteristicsClassificationofLoopSpeciesStable:First-bornchildinfreespaceisidenticaltoparent.Transitional:First-bornchildinfreespaceisdifferentfromparent.Terminal:Speciesdoesnotreproduce.11/19/202225SectionComputationalScience,UniversiteitvanAmsterdamClassificationofLoopSpecies5.Genealogy11/19/202226SectionComputationalScience,UniversiteitvanAmsterdam5.Genealogy11/9/202226SectionGenealogyasaTreeTotrackgenealogy,ancestralinformationrecordedinparent/childform.Onlargegrids,resultsinhugegenealogytrees.Informationmissing:multipleparents(ancestors)forasinglechild(descendant).Conclusion:genealogynottree-based?11/19/202227SectionComputationalScience,UniversiteitvanAmsterdamGenealogyasaTreeTotrackgeGenealogyasaGraphLoopspeciesrepresentedbygraphnodes(vertices).Links(edges)representancestralrelations.Linktraversalfrequenciesbothtimeandspace-dependent.Graph-spacesizeon3Kx3Krun:5Knodes10Klinks11/19/202228SectionComputationalScience,UniversiteitvanAmsterdamGenealogyasaGraphLoopspeciClassificationinGraph-spaceStable:nodewithfree-spaceself-link(“buckle”).Transitional:nodewithfree-spacetoanothernode.Terminal:nodewithnofree-spacelinks.Free-spacelink:graph-spacelinktraversedinfreespace.11/19/202229SectionComputationalScience,UniversiteitvanAmsterdamClassificationinGraph-spaceSExampleofGraph-basedGenealogyA:5f541/6x6B:47d51/6x6C:27d5/5x5D:87d5/5x5E:9f5/4x4F:41f55/6x611/19/202230SectionComputationalScience,UniversiteitvanAmsterdamExampleofGraph-basedGenealoStatisticsfromGraph-BasedGenealogyRankSpeciesInLinksFrequency141f55/6x66542151927d/4x4642174437d/3x3621482RankSpeciesOutLinksFrequency120fa55/7x7855807878241f55/6x68214449632317d55555/13x1335155423(3Kx3Krun-compiledafter940Kiterations)11/19/202231SectionComputationalScience,UniversiteitvanAmsterdamStatisticsfromGraph-BasedGe6.Large-scaleExperiments11/19/202232SectionComputationalScience,UniversiteitvanAmsterdam6.Large-scaleExperiments11/9Method3000x3000gridPersistence(N)=20,000timesteps.Initiatedwiththreeloopsofspecies17d55555/13x13.Blockofdissolvercellsbegininupper-rightcorner.Runfor29daysonDASII.11/19/202233SectionComputationalScience,UniversiteitvanAmsterdamMethod3000x3000grid11/9/202“Bottlenecked”LifeCyclePeriodicdomainisdynamicallypartitionedbydissolver.Onespecies(5f541/6x6)narrowlyescapesextinction.Thisspeciesistheexclusiveancestorforallfuturegenerations.Predictingthiseventnearlyimpossible.11/19/202234SectionComputationalScience,UniversiteitvanAmsterdam“Bottlenecked”LifeCyclePerio“Bottlenecked”LifeCycle11/19/202235SectionComputationalScience,UniversiteitvanAmsterdam“Bottlenecked”LifeCycle11/9/EvolutionaryStasisBetween400Kand1Miterations,twospecies(41f55/6x6,20fa55/7x7)dominateexclusively.11/19/202236SectionComputationalScience,UniversiteitvanAmsterdamEvolutionaryStasisBetween400EvolutionaryCoupling?Cycleingraph-spaceconnectsdominantspecies(41f55/6x6,20fa55/7x7).Systemsettlesingraph-space“potentialminimum”.A:41f55/6x6B:20fa55/7x7C:107d255/8x811/19/202237SectionComputationalScience,UniversiteitvanAmsterdamEvolutionaryCoupling?CycleinReturnoftheGiantsStasisabruptlyendsat940Kiterations.Large-sizedloops(size9,10,11,12,13)makeabriefreturn.Highdiversityforveryshortperiod(roughly80K).Punctuatedequilibrium(Tierra)?11/19/202238SectionComputationalScience,UniversiteitvanAmsterdamReturnoftheGiantsStasisabrReturnoftheGiants11/19/202239SectionComputationalScience,UniversiteitvanAmsterdamReturnoftheGiants11/9/202237.ConclusionsDiversitycanbesynthesizedinaCAspace.Genealogycanbeviewedasagraph.ComplexevolutionaryphenomenacanemergefromadeterministicCAmodel:Evolutionary“bottlenecking”PunctuatedEquilibriumDescribingthepastiseasierthanprescribingthefuture.11/19/202240SectionComputationalScience,UniversiteitvanAmsterdam7.ConclusionsDiversitycanbeReferencesHirokiSayama,Anewstructurallydissolvableself-reproducingloopevolvinginasimplecellularautomataspace,ArtificialLife,vol.5,no.4,pp.343-365,1999.HirokiSayama:ConstructingEvolutionarySystemsonaSimpleDeterministicCellularAutomataSpace,Ph.D.Dissertation,DepartmentofInformationScience,GraduateSchoolofScience,UniversityofTokyo,December1998.Langton,C.G.:Self-reproductionincellularautomata,PhysicaD,10pp.135-144,1984WolframS.:ANewkindofscience,WolframMedia,2002.VonNeumann,J.editedbyBurks:TheoryofSelf-ReproducingAutomata,1966.Workinprogress:.11/19/202241SectionComputationalScience,UniversiteitvanAmsterdamReferencesHirokiSayama,AnewThanks!J11/19/202242SectionComputationalScience,UniversiteitvanAmsterdamThanks!J11/9/202242SectionComCreditsThisprojectispartofthesisworkleadingtotheMasterofSciencedegreeinComputationalScience.ResearchissupervisedbyDr.HirokiSayamaUniversityofElectro-Communications,Tokyo,JapanProjecttobecompletedbytheendofthisyear.11/19/202243SectionComputationalScience,UniversiteitvanAmsterdamCreditsThisprojectispartofLecturePlanStatementofProblemFormerworksANewDynamicEnvironmentIdentificationandClassificationGenealogyLarge-scaleSimulationsConclusions11/19/202244SectionComputationalScience,UniversiteitvanAmsterdamLecturePlanStatementofProbl1.StatementofProblemGoal:Tostudytheemergenceofcomplexevolutionaryphenomenathroughasimple,abstractmodel.Method:“…abstractfromthenaturalself-reproductionproblemitslogicalform.”(Neumann)Synthesizeusingcellularautomata(CA).11/19/202245SectionComputationalScience,UniversiteitvanAmsterdam1.StatementofProblemGoal:112.FormerWorks11/19/202246SectionComputationalScience,UniversiteitvanAmsterdam2.FormerWorks11/9/20224SectiTimelinerelatingcurrentworkVonNeumann’sUniversalConstructor19531970GameofLife(Conway)1994Tierra(Ray)1984SRLoop(Langton)1998Evoloop(Sayama)11/19/202247SectionComputationalScience,UniversiteitvanAmsterdamTimelinerelatingcurrentworkTheSelf-ReproducingLoopSheath:Outershellhousinggenesequence.Genes:7s(straightgrowth)and4s(turning).Tube:2swithinsheath.Arm:Extensibleloopstructureforreplication.sheathgenestubearm11/19/202248SectionComputationalScience,UniversiteitvanAmsterdamTheSelf-ReproducingLoopSheatState-transitionRulesLTCBRIRulestaketheformCTRLB>I.Localanddeterministic.11/19/202249SectionComputationalScience,UniversiteitvanAmsterdamState-transitionRulesLTCBRIRuLangton’sSRLoop8states5-cellneighbourhoodProgramforself-replicationcontainedingenesequence(genotype)Deathoccursviafunctionalfailure(limitedinfinitespace)11/19/202250SectionComputationalScience,UniversiteitvanAmsterdamLangton’sSRLoop8states11/9/TheEvoloop9states(SRruleset+dissolvingstate)5-cellneighbourhoodModificationstoSRrulesetintroduceadaptivityleadingtoevolution.Deathoccursviastructuraldissolution.11/19/202251SectionComputationalScience,UniversiteitvanAmsterdamTheEvoloop9states(SRrulesEvoloopCAStatesStateNameFunction0[Black]Background1[Blue]CoreFillstubeofloop2[Red]SheathExternalstructure3[Purple]Structureofarm4[Green]GeneInfoforturningarm5[LightBlue]Messenger6[Yellow]Messenger/Guide/Finisher7[White]GeneInfoforstraightgrowth8[Grey]DissolverDissolvesloopstructure11/19/202252SectionComputationalScience,UniversiteitvanAmsterdamEvoloopCAStatesStateNameFuncPropertiesoftheDissolvingStateAppearsfromundefinedconfigurations.Travelsalongtubetodissolveneighbouringstates.Anycontiguousstructureisextinguished,creatingfreespacefornewloops.11/19/202253SectionComputationalScience,UniversiteitvanAmsterdamPropertiesoftheDissolvingSQualitiesoftheEvoloopCASimpleandscalable:Smallruleset(95=59049rules)NocentraloperatingsystemPurelydeterministic(nostochasticoperationsinruleset).Adaptable.Realizesanemergentevolutionaryprocess.11/19/202254SectionComputationalScience,UniversiteitvanAmsterdamQualitiesoftheEvoloopCASimPredictabilityoftheEvoloopContinuousself-reproductionleadstohigh-densitylooppopulations(nofreespace).Interactionofphenotypesfavourssmall-sizedloops.Evolutionendswithahomogeneoussingle-speciespopulation.Nodiversity,nospeciation,noevolution.11/19/202255SectionComputationalScience,UniversiteitvanAmsterdamPredictabilityoftheEvoloopCConclusion:modifytheenvironment.EvolutioninaPeriodicDomain11/19/202256SectionComputationalScience,UniversiteitvanAmsterdamConclusion:modifytheenviron3.ANewDynamicEnvironment11/19/202257SectionComputationalScience,UniversiteitvanAmsterdam3.ANewDynamicEnvironment11TenthstateaddedtoEvoloopCA.Rulesnearlyidenticaltodissolvingstate,butpersistsintimeforafiniteperiodN(persistenceorlifetime).Purelypartoftheenvironment:loopswillneverproduceitontheirown.ThePersistentDissolvingState11/19/202258SectionComputationalScience,UniversiteitvanAmsterdamTenthstateaddedtoEvoloopCTheMemoryLayerMemorylayeractsascounter,decrementinglifetimeeachiterationifdissolvercellisabove.Whenlifetimereacheszero,counterisresetanddissolvercellisremoved.Doesnotdirectlyinteractwithneighbouringlooplayerstates.CTBLRILoopLayerMNMemoryLayer11/19/202259SectionComputationalScience,UniversiteitvanAmsterdamTheMemoryLayerMemorylayeraPersistenceandScaleThechoiceofthepersistenceNimposesafixedscaleonthesystem.Asdomainisexpanded(gridsize),Ncanbeusedto“scale”thepopulationclustersize.11/19/202260SectionComputationalScience,UniversiteitvanAmsterdamPersistenceandScaleThechoicPersistenceandScaleSignsofcomplexevolutionaryphenomena.Speciationandlong-termdiversity(phenotype).Conclusion:tounderstandwhat’shappening,weneedbetteranalysis…11/19/202261SectionComputationalScience,UniversiteitvanAmsterdamPersistenceandScaleSignsof4.IdentificationandClassification17d55555/13x1311/19/202262SectionComputationalScience,UniversiteitvanAmsterdam4.IdentificationandClassifiNewDefinitionsGenotype:sequenceofstates‘0’,‘1’,‘4’,and‘7’insidealoop’stubestructure.Phenotype:sizeofinnersheath.Birth:appearanceofstate‘6’(umbilicalcorddissolver).Death:dissolutionofanyinnersheathstate.11/19/202263SectionComputationalScience,UniversiteitvanAmsterdamNewDefinitionsGenotype:sequePropertiesofLoopSpecies“Stationary”(identification):GenotypePhenotype“Reproductive”(classification):Existenceandidentityoffirst-bornoffspringinfreespace.11/19/202264SectionComputationalScience,UniversiteitvanAmsterdamPropertiesofLoopSpecies“StaIdentificationofLoopSpecies17d5555513x13Identifier:17d55555/13x13LoopReplicationGenotypePhenotype11/19/202265SectionComputationalScience,UniversiteitvanAmsterdamIdentificationofLoopSpeciesGenotype-basedCharacteristics41f55/6x613e95/6x65f541/6x6Speciesofthesamephenotypebutdifferentgenotypeexhibitdistinctdynamics:11/19/202266SectionComputationalScience,UniversiteitvanAmsterdamGenotype-basedCharacteristicsClassificationofLoopSpeciesStable:First-bornchildinfreespaceisidenticaltoparent.Transitional:First-bornchildinfreespaceisdifferentfromparent.Terminal:Speciesdoesnotreproduce.11/19/202267SectionComputationalScience,UniversiteitvanAmsterdamClassificationofLoopSpecies5.Genealogy11/19/202268SectionComputationalScience,UniversiteitvanAmsterdam5.Genealogy11/9/202226SectionGenealogyasaTreeTotrackgenealogy,ancestralinformationrecordedinparent/childform.Onlargegrids,resultsinhugegenealogytrees.Informationmissing:multipleparents(ancestors)forasinglechild(descendant).Conclusion:genealogynottree-based?11/19/202269SectionComputationalScience,UniversiteitvanAmsterdamGenealogyasaTreeTotrackgeGenealogyasaGraphLoopspeciesrepresentedbygraphnodes(vertices).Links(edges)representancestralrelations.Linktraversalfrequenciesbothtimeandspace-dependent.Graph-spacesizeon3Kx3Krun:5Knodes10Klinks11/19/202270SectionComputationalScience,UniversiteitvanAmsterdamGenealogyasaGraphLoopspeciClassificationinGraph-spaceStable:nodewithfree-spaceself-link(“buckle”).Transitional:nodewithfree-spacetoanothernode.Terminal:nodewithnofree-spacelinks.Free-spacelink:graph-spacelinktraversedinfreespace.11/19/202271SectionComputationalScience,UniversiteitvanAmsterdamClassificationinGraph-spaceSExampleofGraph-basedGenealogyA:5f541/6x6B:47d51/6x6C:27d5/5x5D:87d5/5x5E:9f5/4x4F:41f55/6x611/19/202272SectionComputationalScience,UniversiteitvanAmsterdamExampleofGraph-basedGenealoStatisticsfromGraph-BasedGenealogyRankSpeciesInLinksFrequency141f55/6x66542151927d/4x4642174437d/3x3621482RankSpeciesOutLinksFrequency120fa55/7x7855807878241f55/6x68214449632317d55555/13x1335155423(3Kx3Krun-compiledafter940Kiterations)11/19/202273SectionComputationalScience,UniversiteitvanAmsterdamStatisticsfromGraph-BasedGe6.Large-scaleExperiments11/19/202274SectionComputationalScience,UniversiteitvanAmsterdam6.Large-scaleExperiments11/9Method3000x3000gridPersistence(N)=20,000timesteps.Initiatedwiththreeloopsofspecies17d55555/13x13.Blockofdissolvercellsbegininupper-rightcorner.Runfor29daysonDASII.11/19/202275SectionComputationalScience,UniversiteitvanAmsterdamMethod3000x3000grid11/9/202“Bottlenecked”LifeCyclePeriodicdomainisdynamicallypartitionedbydissolver.Onespecies(5f541/6x6)narrowlyescapesextinction.Thisspeciesistheexclusiveancestorforallfuturegenerations.Predictingthiseventnearlyimpossible.11/19/202276SectionComputational