Lecture Notes in Computer Science 3447 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison LancasterUniversity,UK TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA MoniNaor WeizmannInstituteofScience,Rehovot,Israel OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen UniversityofDortmund,Germany MadhuSudan MassachusettsInstituteofTechnology,MA,USA DemetriTerzopoulos NewYorkUniversity,NY,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA MosheY.Vardi RiceUniversity,Houston,TX,USA GerhardWeikum Max-PlanckInstituteofComputerScience,Saarbruecken,Germany Maarten Keijzer Andrea Tettamanzi Pierre Collet Jano van Hemert Marco Tomassini (Eds.) Genetic Programming 8th European Conference, EuroGP 2005 Lausanne, Switzerland, March 30 –April 1, 2005 Proceedings 1 3 VolumeEditors MaartenKeijzer WL|DelftHydraulics Rotterdamseweg181,Delft,TheNetherlands E-mail:[email protected] AndreaTettamanzi UniversitàdegliStudidiMilano,DipartimentodiTecnologiedell’Informazione c/oPoloDidatticoediRicercadiCrema ViaBramante65,26013Crema,Italy E-mail:[email protected] PierreCollet UniversitéduLittoralCôted’Opale,Laboratoired’InformatiqueduLittoral B.P.719,62100Calaiscedex,France E-mail:[email protected] JanovanHemert NapierUniversity,SchoolofComputing,CentreforEmergentComputing 10ColintonRoad,EdinburghEH105DT,UK E-mail:[email protected] MarcoTomassini UniversityofLausanne,HEC,InformationSystemsDepartment 1015Lausanne,Switzerland E-mail:[email protected] Coverillustration:TriangularUrchin,byChaps(www.cetoine.com).Chapshasob- tained an MSc in Physics at the Swiss Federal Institute of Technology. He is the developeroftheArtiE-FractsoftwarethatwasusedtocreateTriangularUrchin. TriangularUrchin(anIteratedFunctionsSystemof2polarfunctions)emergedfrom anurchinstructureafterafewgenerationsusingArtiE-Fract.Theevolutionaryprocess wasonlybasedonsoftmutations,someofthemdirectlyinducedbytheauthor. LibraryofCongressControlNumber:2005922866 CRSubjectClassification(1998):D.1,F.1,F.2,I.5,I.2,J.3 ISSN 0302-9743 ISBN-10 3-540-25436-6SpringerBerlinHeidelbergNewYork ISBN-13 978-3-540-25436-2SpringerBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsareliable toprosecutionundertheGermanCopyrightLaw. SpringerisapartofSpringerScience+BusinessMedia springeronline.com ©Springer-VerlagBerlinHeidelberg2005 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SPIN:11410591 06/3142 543210 Preface In this volume we present the contributions for the 18th European Conference on Genetic Programming (EuroGP 2005). The conference took place from 30 Marchto1AprilinLausanne,Switzerland.EuroGPisawell-establishedconfer- ence and the only one exclusively devoted to genetic programming. All previous proceedings were published by Springer in the LNCS series. From the outset, EuroGPhasbeenco-locatedwiththeEvoWorkshopsfocusingonapplicationsof evolutionary computation. Since 2004, EvoCOP, the conference on evolutionary combinatorial optimization, has also been co-located with EuroGP, making this year’scombinedeventsoneofthelargestdedicatedtoevolutionarycomputation in Europe. Geneticprogramming(GP)isevolutionarycomputationthatsolvescomplex problemsortasksbyevolvingandadaptingapopulationofcomputerprograms, using Darwinian evolution and Mendelian genetics as its sources of inspiration. Some of the 34 papers included in these proceedings address foundational and theoreticalissuesandthereisalsoawidevarietyofpapersdealingwithdifferent application areas, such as computer science, engineering, language processing, biology and computational design, demonstrating that GP is a powerful and practical problem-solving paradigm. A rigorous, double-blind, peer-review selection mechanism was applied to 64 submitted papers. This resulted in the acceptance of 20 plenary talks and 14 poster presentations. Each paper was reviewed by three or four members of the international Programme Committee who were selected as fairly as possible by matching a reviewer’s particular interests and special expertise to the topics covered by the paper. The results of this process are reflected in the quality of thecontributionspublishedwithinthisvolume.Thisyeartheoverallacceptance rate for talks and poster presentations was 53%. We would like to express our sincere gratitude to the two internationally renowned invited speakers who gave keynote talks at the conference: Prof. Matteo Fischetti of the University of Padova, Italy and Prof. Alberto Piazza from the University of Torino. Thesuccessofanyconferenceresultsfromtheinputofmanypeople,towhom we would like to express our appreciation. Firstly, we would like to thank the membersoftheProgrammeCommitteefortheirattentiveness,perseveranceand willingness to provide high-quality reviews. The local team (Mario Giacobini, Leslie Luthi, Denis Rochat and Leonardo Vanneschi), headed by Prof. Marco Tomassini, must also be thanked: the smooth development of the conference has been their feat. Finally, we would also like to thank VI Preface JenniferWilliesforhercontinuouseffortsandsupport,aswellasforhervaluable andprofessionalhelpwithalltheorganizationalandlogisticaspectsoforganizing the event. April 2005 Maarten Keijzer Andrea Tettamanzi Pierre Collet Jano van Hemert Marco Tomassini Organization EuroGP 2005 was organized by EvoGP, the EvoNet Working Group on Genetic Programming. Organizing Committee Programme Co-chairs: Maarten Keijzer KiQ Ltd., Amsterdam and WL|Delft Hydraulics, Delft, The Netherlands Andrea Tettamanzi Genetica S.r.l. and University of Milan, Italy Publication Chair: Pierre Collet Universit´e du Littoral (Calais), France Local Chair: Marco Tomassini University of Lausanne, Switzerland Publicity Chair: Jano van Hemert Napier University, Edinburgh, UK Programme Committee Abbass, Hussein. University of New South Wales. Australia Araujo, Lourdes. Universidad Complutense de Madrid. Spain Aydin, Mehmet Emin. London South Bank University. UK Azad, R. Muhammad Atif. University of Limerick. Ireland Bailleux, Olivier. Universit´e de Bourgogne. France Banzhaf, Wolfgang. Memorial University of Newfoundland. Canada Borovik, Alexandre. University of Manchester. UK Brabazon, Anthony. University College Dublin. Ireland Burke, Edmund Kieran. University of Nottingham. UK Cagnoni, Stefano. University of Parma. Italy Carbajal, Santiago Garc´ıa. University of Oviedo. Gijon. Spain Cardoso, F. Amilcar. University of Coimbra. Portugal Cheang, Sin Man. Hong Kong Institute of Vocational Education. China Clergue, Manuel. Laboratoire I3S. France Collard, Philippe. Universit´e de Nice–Sophia-Antipolis. France Collet, Pierre. Universit´e du Littoral, Calais. France Costa, Ernesto Jorge. University of Coimbra. Portugal De Jong, Edwin. Utrecht University. The Netherlands Ebner, Marc. Universita¨t Wu¨rzburg. Germany VIII Organization Ekart, Aniko. Computer and Automation Research Institute, Hungarian Academy of Sciences. Hungary Essam, Daryl Leslie. ADFA, UNSW. Australia Fernandez, Francisco. University of Extremadura. Spain Folino, Gianluigi. ICAR-CNR. Italy Fonlupt, Cyril. Universit´e du Littoral, Calais. France Foster, James A. University of Idaho. USA Gustafson, Steven. University of Nottingham. UK Hao, Jin-Kao. University of Angers. France Hemert, van, Jano. Napier University. UK Hirsch, Laurence Benjamin. Royal Holloway University of London. UK Hochreiter, Ronald. University of Vienna. Austria Howard, Daniel. QinetiQ. UK Johnson, Colin. C.G. Johnson. UK Kalganova, Tatiana. Brunel University. UK Kendall, Graham. University of Nottingham. UK Kim, DaeEun. Max Planck Institute for Human Cognitive and Brain Sciences. Germany Kochenderfer, Mykel John. University of Edinburgh. UK Kubalik, Jiri. Czech Technical University in Prague. Czech Republic Kuo, Tzu-Wen. AI-ECON Research Center. Taiwan Langdon, William B. University of Essex. UK Leung, Kwong Sak. Chinese University of Hong Kong. Hong Kong, China Levine, John. University of Strathclyde. UK Lopes, Heitor Silv´erio. CEFET-PR/BIOINFO. Brazil Lucas, Simon Mark. Essex University. UK MacCallum, Bob. Stockholm Bioinformatics Center. Sweden Machado,Penousal.CentreforInformaticsandSystems,UniversityofCoimbra. Portugal Martin, P.N. Naiad Consulting. UK McKay, Robert Ian. University of New South Wales. Australia Mehnen, Jo¨rn. ISF, Department of Machining Technology. Germany Miller, Julian Francis. University of York. UK Monsieurs, Patrick. Expertise Center for Digital Media. Belgium Nicolau, Miguel. University of Limerick. Ireland Nievola, Julio Cesar. PUCPR. Brazil O’Neill, Michael. University of Limerick. Ireland Pizzuti, Clara. ICAR-CNR. Italy Poli, Riccardo. University of Essex. UK Robilliard, Denis. Univ. Littoral, Coˆte d’Opale. France Rodriguez-Vazquez, Katya. UNAM. Mexico Rothkrantz, Leon. Delft University of Technology. The Netherlands Ryan, Conor. University of Limerick. Ireland Saitou, Kazuhiro. University of Michigan. USA Sapin, Emmanuel. LERSIA. France Organization IX Schoenauer, Marc. INRIA. France Sebag, Mich`ele. CNRS, Universit´e Paris-Sud. France Sekanina, Lukas. Brno University of Technology. Czech Republic Skourikhine, Alexei. Los Alamos National Laboratory. USA Spezzano, Giandomenico. Institute of High Performance Computing and Networking (ICAR)-CNR. Italy Streeter, Matthew J. Carnegie Mellon University. USA Tavares, Jorge. University of Coimbra. Portugal Tommassini, Marco. University of Lausanne. Switzerland Vanneschi, Leonardo. University of Milan-Bicocca. Italy V´anyi, Ro´bert. Institute of Informatics, University of Szeged. Hungary Wilson, Garnett Carl. Dalhousie University. Canada Wolff, Krister. Chalmers University of Technology. Sweden Woodward, John Robert William. Birmingham University. UK Sponsoring Institutions EvoNet: The Network of Excellence in Evolutionary Computing, funded by the European Commission’s IST Programme Table of Contents Talks An Algorithmic Chemistry for Genetic Programming Christian W.G. Lasarczyk, Wolfgang Banzhaf ..................... 1 Assessing the Effectiveness of Incorporating Knowledge in an Evolutionary Concept Learner Federico Divina................................................ 13 Automated Re-invention of a Previously Patented Optical Lens System using Genetic Programming Sameer H. Al-Sakran, John R. Koza, Lee W. Jones ................ 25 Bayesian Automatic Programming Evandro Nunes Regolin, Aurora Trindad Ramirez Pozo ............. 38 Dynamic Size Populations in Distributed Genetic Programming Denis Rochat, Marco Tomassini, Leonardo Vanneschi .............. 50 Evolution of Robot Controller Using Cartesian Genetic Programming Simon Harding, Julian F. Miller ................................. 62 Evolving L-Systems to Capture Protein Structure Native Conformations Gabi Escuela, Gabriela Ochoa, Natalio Krasnogor.................. 74 Evolving Rules for Document Classification Laurence Hirsch, Masoud Saeedi, Robin Hirsch .................... 85 Genetic Programming in Wireless Sensor Networks Derek M. Johnson, Ankur M. Teredesai, Robert T. Saltarelli ........ 96 Genetic Transposition in Tree-Adjoining Grammar Guided Genetic Programming: The Duplication Operator Nguyen Xuan Hoai, Robert Ian Bob McKay, Daryl Essam, Hoang Tuan Hao .............................................. 108 GP-EndChess: Using Genetic Programming to Evolve Chess Endgame Players Ami Hauptman, Moshe Sipper ................................... 120 XII Table of Contents GP-Gammon: Using Genetic Programming to Evolve Backgammon Players Yaniv Azaria, Moshe Sipper ..................................... 132 GP-Robocode: Using Genetic Programming to Evolve Robocode Players Yehonatan Shichel, Eran Ziserman, Moshe Sipper.................. 143 Incorporating Learning Probabilistic Context-Sensitive Grammar in Genetic Programming for Efficient Evolution and Adaptation of Snakebot Ivan Tanev ................................................... 155 Multi-logic-Unit Processor: A Combinational Logic Circuit Evaluation Engine for Genetic Parallel Programming Wai Shing Lau, Gang Li, Kin Hong Lee, Kwong Sak Leung, Sin Man Cheang ............................................... 167 Operator-Based Distance for Genetic Programming: Subtree Crossover Distance Steven Gustafson, Leonardo Vanneschi ........................... 178 Repeated Patterns in Tree Genetic Programming William B. Langdon, Wolfgang Banzhaf .......................... 190 Tarpeian Bloat Control and Generalization Accuracy S´ebastien Mahler, Denis Robilliard, Cyril Fonlupt .................. 203 The Tree-String Problem: An Artificial Domain for Structure and Content Search Steven Gustafson, Edmund K. Burke, Natalio Krasnogor............ 215 Using Genetic Programming for Multiclass Classification by Simultaneously Solving Component Binary Classification Problems William Smart, Mengjie Zhang .................................. 227 Posters Context-Based Repeated Sequences in Linear Genetic Programming Garnett Carl Wilson, Malcolm Iain Heywood ...................... 240 Evolution of a Strategy for Ship Guidance Using Two Implementations of Genetic Programming Eva Alfaro-Cid, Euan William McGookin, David James Murray-Smith ..................................... 250