Lecture Notes in Artificial Intelligence 5778 EditedbyR.Goebel,J.Siekmann,andW.Wahlster Subseries of Lecture Notes in Computer Science George Kampis István Karsai Eörs Szathmáry (Eds.) Advances in Artificial Life Darwin Meets von Neumann 10th European Conference, ECAL 2009 Budapest, Hungary, September 13-16, 2009 Revised Selected Papers, Part II 1 3 SeriesEditors RandyGoebel,UniversityofAlberta,Edmonton,Canada JörgSiekmann,UniversityofSaarland,Saarbrücken,Germany WolfgangWahlster,DFKIandUniversityofSaarland,Saarbrücken,Germany VolumeEditors GeorgeKampis EötvösUniversity DepartmentofHistoryandPhilosophyofScience PázmányP.s.1/C,1117Budapest,Hungary E-mail:[email protected] IstvánKarsai EastTennesseeStateUnviversity DepartmentofBiologicalSciences JohnsonCity,TN37614-1710,USA E-mail:[email protected] EörsSzathmáry CollegiumBudapest,Szentháromságu.2 1014Budapest,Hungary E-mail:[email protected] ISSN0302-9743 e-ISSN1611-3349 ISBN978-3-642-21313-7 e-ISBN978-3-642-21314-4 DOI10.1007/978-3-642-21314-4 SpringerHeidelbergDordrechtLondonNewYork LibraryofCongressControlNumber:2011927893 CRSubjectClassification(1998):I.2,J.3,F.1.1-2,G.2,H.5,I.5,J.6 LNCSSublibrary:SL7–ArtificialIntelligence ©Springer-VerlagBerlinHeidelberg2011 Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsareliable toprosecutionundertheGermanCopyrightLaw. Theuseofgeneraldescriptivenames,registerednames,trademarks,etc.inthispublicationdoesnotimply, evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevantprotectivelaws andregulationsandthereforefreeforgeneraluse. Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) Preface Artificial Life, unlike artifical intelligence, had humble beginnings. In the case of the latter, when the word itself was born, the first breathtaking results were alreadyout,suchasTheLogicTheorist,acomputerprogramdevelopedbyAllen Newell,HerbertSimonandCliffShawin1955–56.Inartificallife,foralongwhile, amibition seems to have dominated over the results, and this was certainly true forthefirst,formativeyears.Itwasabitunclearwhatexactly ArtificialLifeis.As notuncommoninscience,thefirstdefinitionwasattemptedinthenegativeform, justlikewhenpsychology(thestudyofthemental)wasfirstdefinedas“anything not physics”(meaning, not naturalscience) in the nineteenth century. A tempt- ingearlydefinionofArtificialLife wasonethatdistinguisheditfromtheoretical and mathematical biology, modeling, evolution theory, and all the rest of what consituted“an old kind of science”about life. This was not without grounds, perhaps, and the parallel with artificial intelligence comes up again. Artificial intelligence was conceptually based on“machine functionalism,”the philosophi- cal idea that all operations,such as the mental operations of humans, are to be captured as“mere functions,”or, in other words, as independent of their actual physicalrealizations.Functionalismhasputcomputersandalgorithmsinthefo- cus of interest in all dealings with human intelligence, and artificial intelligence was a computerized approach to the mind that was designed to capture human mental operations in the functional sense. Now it was simply the case that the functionalism of life was not yet born, and Artificial Life looked like the candi- datethatwasneededforexactlythat—todiscoverhowcomputerscanbeusedto uncoverthesecretsoflife.Therewerecellularautomata,thatJohnvonNeumann discoveredback around 1950,that are capable of self-reproduction.Perhaps life wasjustastepaway.This andanew fascinationwithfunctionalisminArtificial Life put computer scientists (who could technically master cellular automata and computer math) into a central position—in Artificial Life as it could be. But Artificial Life became different. Incidentally, the slogan“life as it could be” was coined as a motto for Artificial Life, but now the same conditionals apply to Artificial Life itself. The reason is that functionalism turned out to be just one part of the story. There is a well-known and much used (maybe over-used) phrase in biology, called“Dobzhansky’s dictum,”which says that“nothing in biology makes sense exceptinthe lightofevolution.”Evolutionis,asrightlycapturedinthe dictum, centraltotheunderstandingofallthingsalive,andhenceitis,andthishadtobe discovered,centraltothestudiesofArtificialLifeaswell.Andsoonitalsoturned out that evolution cannot be readily reduced to algorithmic problems, or and leastnotinthatpure,detachedsenseasitwasattemptedinfunctionalism.Evo- lutioniscomplex inasenserecentlyacknowledgedinthesciencesofcomplexity: there is no single principle, no simple set of rules,and no transparency.Instead, VI Preface evolutionisacombinationofmanyheterogeneous,andsometimescontingentfac- tors,manyofwhichhavetodowiththecomplexwaysofexistenceoforganisms: theirbody,theirinteraction,theirdevelopment,theirgeo-spatialrelations,their temporal history, and so on. This brought biology and biologists back into the equation, and Artificial Life has greatly benefited from that. Evo-devo (the in- terplaybetweenevolutionaryanddevelopmentalbiology),evolutionaryrobotics, or systems biology are examples of fields where mathematical and algorithmic thinking combined with “wet” reality started to produce new and fascinating results. (Those who kept an eye on cognitive science and artificial intelligence found that over all those years a similar process has taken place there as well. Embodiment, or situated physical realization,has permeated and changed these fields to the same extent, or even more, as it did Artificial Life). Today,asaresultoftheseprocesses,ArtificialLifeisaprolificfieldthatcom- bines the best of computer science with the best of theoretical biology, math- ematical modeling, and simulation. One way to express this is to say“Darwin meets von Neumann”at last—where“real”biology and“pure”function are no longerseenascontradicting,orevencomplementary.Rather,theypermeateand fertilize each other in a number of fascinating ways. ECAL2009wasthe 10thEuropanConferenceofArtificialLife,whichmeans 20 years of history. It was an occasion to celebrate the 20 years of develop- ment of the field and also the new symbiosis referred to in the title. Famously, 2009 was also“Darwin year,”celebrating his 200th birthday and the 150 years of the Origin of Species. Thus it was highly appropriate to dedicate the meet- ing to Darwin—and von Neumann together. Five keynote lectures were deliv- ered by eminent invited speakers, in the order of appearance they were: Peter Hammerstein(HumboldtUniversity,Berlin),HodLipson(Cornell),NickBarton (FRS,Edinburgh),RichardWatson(Southampton)andEvaJablonka(Tel-Aviv University)—their choice reflected the spirit of convergence alluded to above. The conference featured 161 submissions, out of which 54 were accepted as talks and 87 as posters (making up a total of 141 presentations). Adopting the recent practice of many science meetings, submissions could be based either on full papers or extended abstracts. The meeting was organized in a single track overthreedays,withparallel(whole-day)postersections,togivebestvisibilityto everyone’swork.We decidedtopublishallpapersofthe acceptedpresentations, notmakinganydifferencebetweenpostersandtalks.Thisresultedfromdifferent factors:manyexcellentsubmissionshadtobeputintothepostersectiontokeep reasonabletimelimitsforthetalks,andoftenthisincludedsecondorthirdpapers ofsomeofthekeyspeakers.Posterortalkwasthereforenotnecessarilyaquality issue. But also, we decided to publish all poster papers because we wanted to showtheheterogeneityandthefullspectrumofactivitiesinthefield,inorderto provide an authentic overview. The result is this volume in 2 parts, containing 116 full papers. The conference was sponsored by the Hungarian Academy of Science in dif- ferent ways,one of them the special rates we enjoyed when using the wonderful historical building of the Academy in the very center of Budapest, just across Preface VII the castle and the Chain Bridge. It is a building with a unique historical atmo- sphereandone that hasseenmany majorscientific events.Theconference talks wereheldintheGreatLectureHall,whichaddedtotheimpressionthatArtificial Life—andECAL—arecomingofage.TheothersponsorwasAitiaInternational, Inc., whose support is gratefully acknowledged. Aitia is the maker of MEME, or Model ExplorationModulE, a platform for DoE (design of experiments) and parameter sweeping, running on a cloud (https://modelexploration.aitia.ai/). The publication process experienced several unexpected difficulties and de- lays. The proceedings could never have been published without a final push by MarkJelasity,ofSzegedUniversity,a memberofthe LocalOrganizingCommit- tee. It was his support and his offer for a hands-on contribution and equally his expertise of LATEX and prior experience with Springer LNCS publications that made the essential difference that helped cross the line. Mark was offered but declined to be an Editor,lacking a scientific contributionto this conference and bearing a responsibility for the selection process, and this is a decision we had to respect. Nevertheless, here is a“big thank you,”Mark. Several other people providedimportanthelpintheproductionofthevolume,ofwhomBalazsBalint (Collegium Budapest) and Chrisantha Fernando (Sussex) need special mention. WethanktheTenSiCongressLtd.fortheseamlesstechnicalorganizationofthe meeting. In the evaluation phase, importanthelp was given by severalmembers of the Program Committee and also by additional reviewers, listed separately, whose contribution is highly appreciated. The conference and the proceedings havebeentheworkofseveralpeople,andwethankallofthemformakingithap- pen. Finally, we thank Anna Kramer of Springer for her support and patience. February 2011 George Kampis Istv´an Karsai E¨ors Szathma´ry (Editors) Organization Organizing Committee George Kampis and E¨ors Szathma´ry (Chairs) Chrisantha Fernando, Ma´rk Jelasity, Ferenc Jord´an, Andra´s L˝orincz, and Istv´an Scheuring Program Committee Wolfgang Banzhaf Takashi Ikegami Alexandra Penn Xabier Barandiaran Istvan Karsai Daniel Polani Zoltan Barta Jozef Kelemen Luis Rocha Mark Bedau Simon Kirby Matthias Scheutz Randall Beer Doron Lancet Thomas Schmickl Seth Bullock Robert Lowe Peter Stadler Philippe Capdepuy John McCaskill Elio Tuci Peter Cariani Bruce MacLennan Andreas Wegner Andy Clark Federico Moran Franjo Weissing Tam´as Cz´ara´n Alvaro Moreno Larry Yaeger Ezequiel Di Paolo Chrystopher Nehaniv Klaus-Peter Zauner Dario Floreano Stefano Nolfi Inman Harvey Charles Ofria Additional Reviewers Rose Canino-Koning Heather Goldsby Bess Walker Arthur Covert Laura Grabowski Luis Zaman Tomassino Ferrauto David Knoester Sherri Goings Anuraag Pakanati Table of Contents – Part II Group Selection Investigations of Wilson’s and Traulsen’s Group Selection Models in Evolutionary Computation ........................................ 1 Shelly X. Wu and Wolfgang Banzhaf The Evolution of Division of Labor................................. 10 Heather J. Goldsby, David B. Knoester, Jeff Clune, Philip K. McKinley, and Charles Ofria A Sequence-to-Function Map for Ribozyme-Catalyzed Metabolisms..... 19 Alexander Ullrich and Christoph Flamm Can Selfish Symbioses Effect Higher-Level Selection? ................. 27 Richard A. Watson, Niclas Palmius, Rob Mills, Simon T. Powers, and Alexandra Penn The Effect of Group Size and Frequency-of-Encounteron the Evolution of Cooperation .................................................. 37 Steve Phelps, Gabriel Nevarez, and Andrew Howes Moderate Contact between Sub-populations Promotes Evolved Assortativity Enabling Group Selection ............................. 45 James R. Snowdon, Simon T. Powers, and Richard A. Watson Evolution of Individual Group Size Preference Can Increase Group-LevelSelection and Cooperation............................. 53 Simon T. Powers and Richard A. Watson Ecosystems and Evolution Implications of the Social Brain Hypothesis for Evolving Human-Like Cognition in Digital Organisms .................................... 61 Suzanne Sadedin and Greg Paperin Embodiment of Honeybee’s Thermotaxis in a Mobile Robot Swarm .... 69 Daniela Kengyel, Thomas Schmickl, Heiko Hamann, Ronald Thenius, and Karl Crailsheim Positively versus Negatively Frequency-Dependent Selection ........... 77 Robert Morris and Tim Watson XII Table of Contents– Part II Origins of Scaling in Genetic Code ................................. 85 Oliver Obst, Daniel Polani, and Mikhail Prokopenko Adaptive Walk on Fitness Soundscape.............................. 94 Reiji Suzuki and Takaya Arita Breaking Waves in PopulationFlows ............................... 102 George Kampis and Istvan Karsai Symbiosis Enables the Evolution of Rare Complexes in Structured Environments ................................................... 110 Rob Mills and Richard A. Watson Growth of Structured Artificial Neural Networks by Virtual Embryogenesis................................................... 118 Ronald Thenius, Michael Bodi, Thomas Schmickl, and Karl Crailsheim Algorithms and Evolutionary Computation The Microbial Genetic Algorithm .................................. 126 Inman Harvey HybrID: A Hybridization of Indirect and Direct Encodings for Evolutionary Computation ........................................ 134 Jeff Clune, Benjamin E. Beckmann, Robert T. Pennock, and Charles Ofria An Analysis of LamarckianLearning in Changing Environments ....... 142 Dara Curran and Barry O’Sullivan Linguistic Selection of Language Strategies: A Case Study for Colour ... 150 Joris Bleys and Luc Steels Robots That Say ‘No’ ............................................ 158 Frank F¨orster, Chrystopher L. Nehaniv, and Joe Saunders A Genetic Programming Approach to an Appropriation Common Pool Game .......................................................... 167 Alan Cunningham and Colm O’Riordan Using Pareto Front for a Consensus Building, Human Based, Genetic Algorithm....................................................... 175 Pietro Speroni di Fenizio and Chris Anderson The Universal Constructor in the DigiHive Environment .............. 183 Rafa(cid:3)l Sienkiewicz and Wojciech Jedruch (cid:2) Table of Contents– Part II XIII A Local Behavior Identification Algorithm for Generative Network Automata Configurations ......................................... 191 Burak O¨zdemir and Hu¨revren Kılıc¸ Solving a Heterogeneous Fleet Vehicle Routing Problem with Time Windows through the Asynchronous Situated Coevolution Algorithm... 200 Abraham Prieto, Francisco Bellas, Pilar Caaman˜o, and Richard J. Duro Philosophy and Arts Modeling Living Systems ......................................... 208 Peter Andras Facing N-P Problems via Artificial Life: A Philosophical Appraisal ..... 216 Carlos E. Maldonado and Nelson G´omez Observer Based Emergence of Local Endo-time in Living Systems: Theoretical and Mathematical Reasoning ........................... 222 Igor Balaz and Dragutin T. Mihailovic Life and Its Close Relatives ....................................... 230 Simon McGregor and Nathaniel Virgo A Loosely Symmetric Model of Cognition ........................... 238 Tatsuji Takahashi, Kuratomo Oyo, and Shuji Shinohara Algorithmic Feasibility of Entity Recognition in Artificial Life ......... 246 Janardan Misra Creative Agency: A Clearer Goal for Artificial Life in the Arts......... 254 Oliver Bown and Jon McCormack Optimization, Action, and Agent Connectivity Agent-BasedToyModelingforComparingDistributiveandCompetitive Free Market..................................................... 262 Hugues Bersini Swarm Cognition and Artificial Life ................................ 270 Vito Trianni and Elio Tuci Life Engine - Creating Artificial Life for Scientific and Entertainment Purposes........................................................ 278 Gonc¸alo M. Marques, Anto´nio Lorena, Jo˜ao Magalh˜aes, Taˆnia Sousa, S.A.L.M. Kooijman, and Tiago Domingos