Emergence, Complexity and Computation ECC Susan Stepney Andrew Adamatzky E ditors Inspired by Nature Essays Presented to Julian F. Miller on the Occasion of his 60th Birthday Emergence, Complexity and Computation Volume 28 Series editors Ivan Zelinka, Technical University of Ostrava, Ostrava, Czech Republic e-mail: [email protected] Andrew Adamatzky, University of the West of England, Bristol, UK e-mail: [email protected] Guanrong Chen, City University of Hong Kong, Hong Kong, China e-mail: [email protected] Editorial Board Ajith Abraham, MirLabs, USA Ana Lucia C. Bazzan, Universidade Federal do Rio Grande do Sul, Porto Alegre, RS, Brazil Juan C. Burguillo, University of Vigo, Spain Sergej Čelikovský, Academy of Sciences of the Czech Republic, Czech Republic Mohammed Chadli, University of Jules Verne, France Emilio Corchado, University of Salamanca, Spain Donald Davendra, Technical University of Ostrava, Czech Republic Andrew Ilachinski, Center for Naval Analyses, USA Jouni Lampinen, University of Vaasa, Finland Martin Middendorf, University of Leipzig, Germany Edward Ott, University of Maryland, USA Linqiang Pan, Huazhong University of Science and Technology, Wuhan, China Gheorghe Păun, Romanian Academy, Bucharest, Romania Hendrik Richter, HTWK Leipzig University of Applied Sciences, Germany Juan A. Rodriguez-Aguilar, IIIA-CSIC, Spain Otto Rössler, Institute of Physical and Theoretical Chemistry, Tübingen, Germany Vaclav Snasel, Technical University of Ostrava, Czech Republic Ivo Vondrák, Technical University of Ostrava, Czech Republic Hector Zenil, Karolinska Institute, Sweden The Emergence, Complexity and Computation (ECC) series publishes new developments, advancements and selected topics in the fields of complexity, computation and emergence. The series focuses on all aspects of reality-based computation approaches from an interdisciplinary point of view especially from applied sciences, biology, physics, or chemistry. It presents new ideas and interdisciplinary insight on the mutual intersection of subareas of computation, complexity and emergence and its impact and limits to any computing based on physical limits (thermodynamic and quantum limits, Bremermann’s limit, Seth Lloyd limits…) as well as algorithmic limits (Gödel’s proof and its impact on calculation,algorithmiccomplexity,theChaitin’sOmeganumberandKolmogorov complexity, non-traditional calculations like Turing machine process and its consequences,…) and limitations arising in artificial intelligence field. The topics are (but not limited to) membrane computing, DNA computing, immune computing, quantum computing, swarm computing, analogic computing, chaos computingandcomputingontheedgeofchaos,computationalaspectsofdynamics of complex systems (systems with self-organization, multiagent systems, cellular automata, artificial life,…), emergence of complex systems and its computational aspects,and agent based computation. The main aim ofthis series it todiscussthe above mentioned topics from an interdisciplinary point of view and present new ideas coming from mutual intersection of classical as well as modern methods of computation.Withinthescopeoftheseriesaremonographs,lecturenotes,selected contributions from specialized conferences and workshops, special contribution from international experts. More information about this series at http://www.springer.com/series/10624 ⋅ Susan Stepney Andrew Adamatzky Editors Inspired by Nature Essays Presented to Julian F. Miller on the Occasion of his 60th Birthday 123 Editors SusanStepney AndrewAdamatzky Department ofComputer Science Unconventional Computing Centre University of York University of the West of England York Bristol UK UK ISSN 2194-7287 ISSN 2194-7295 (electronic) Emergence, Complexity andComputation ISBN978-3-319-67996-9 ISBN978-3-319-67997-6 (eBook) https://doi.org/10.1007/978-3-319-67997-6 LibraryofCongressControlNumber:2017952894 ©SpringerInternationalPublishingAG2018 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpart of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission orinformationstorageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilar methodologynowknownorhereafterdeveloped. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publicationdoesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfrom therelevantprotectivelawsandregulationsandthereforefreeforgeneraluse. The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authorsortheeditorsgiveawarranty,expressorimplied,withrespecttothematerialcontainedhereinor for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictionalclaimsinpublishedmapsandinstitutionalaffiliations. Printedonacid-freepaper ThisSpringerimprintispublishedbySpringerNature TheregisteredcompanyisSpringerInternationalPublishingAG Theregisteredcompanyaddressis:Gewerbestrasse11,6330Cham,Switzerland Preface Julian Francis Miller ThisbookisatributetoJulianFrancisMiller’sbreadthofideasandachievementsin computer science, evolutionary algorithms and genetic programming, electronics, unconventionalcomputing,artificialchemistry,andtheoreticalbiology.Well-known forbothCartesianGeneticProgrammingandevolutioninmaterio,Julianhasfurther interestsfromquantumcomputingtoartificialchemistries.Hehasover200refereed publications (http://www.cartesiangp.co.uk/jfm-publications.html); here, we high- lightjustafewofhismajoraccomplishments. Julian started his life in science as mathematical physicist working on the interactionofsolitonsinvariousnonlinearpartialdifferential equationssuchasthe sine-Gordonequation[3,5],andthemodifiedKorteweg-de Vries equation [4].He entered classical computer science with his paper on synthesis and optimisation of networksimplementedwithuniversallogicmodules[1,16,30].Julian’sinterestin optimisation ledhimtogenetic algorithms,whichheemployed foroptimisation of field-programmable arrays [26], Reed-Muller logical functions [15], finite-state machines [2], and evolving combinatorial logic circuits [18, 22, 23] and non-uniform cellular automata [27, 28]. v vi Preface Julian combined his interests in physics and computer science in work on constant complexity algorithm for solving Boolean satisfiability problems on quantum computers, and quantum algorithm for finding multiple matches [31]. Julian’s ideas in optimisation of circuits and quantum computing are reflected in Younes’ Chapter “Using Reed-Muller Expansions in the Synthesis and Optimization of Boolean Quantum Circuits”. Julian’sinterestincombiningnaturalprocessesandcomputationexpandedfrom physicstoincludetheexcitingworldofbiologicalprocesses,suchasevolutionand morphogenesis. He used principles ofmorphogenesisto evolve computing circuits andprograms[14,17,19].TheseaspectsofJulian’sworkarereflectedinChapters “EvolvableHardwareChallenges:Past,PresentandthePathtoaPromisingFuture” by Haddow and Tyrell, “Artificial Development” by Kuyucu et al., and Banzhaf’s “Some Remarks on Code Evolution with Genetic Programming”. In 2000, Julian, together with Peter Thomson, presented a fully developed concept of Cartesian Genetic Programming (CGP) [24]. There, a program is genetically represented as a directed graph, including automatically defined func- tions [29] and self-modifying operators [10]. This approach has become very popular,becauseitallowsthediscoveryofefficientsolutionsacrossawiderangeof mathematical problems and algorithms. Several chapters of the book manifest the success of CGP in diverse application areas: “Designing Digital Systems Using Cartesian Genetic Programming and VHDL” by Henson et al.; “Breaking the Stereotypical Dogma of Artificial Neural Networks with Cartesian Genetic Programming” by Khan and Ahmad; “Approximate Computing: An Old Job for CartesianGeneticProgramming?”bySekanina;“MedicalApplicationsofCartesian GeneticProgramming”bySmith andLones;“Multi-stepAheadForecastingUsing Cartesian Genetic Programming” by Dzalbs and Kalganova; “Cartesian Genetic Programming for Control Engineering” by Clarke; “Bridging the Gap Between Evolvable Hardware and Industry Using Cartesian Genetic Programming” by Vasicek; “Combining Local and Global Search: A Multi-objective Evolutionary Algorithm for Cartesian Genetic Programming” by Kaufmann and Platzner. In2001,MillerandHartmanpublished“Untidyevolution:Evolvingmessygates for fault tolerance” [21]. Their ideas of exploiting of “messiness” to achieve “optimality”—“natural evolution is, par excellence, an algorithm that exploits the physical properties of materials”—gave birth to a new field of unconventional computing:evolutioninmaterio[7,12,20].Theevolutioninmaterioapproachhas proved very successful in discovering logical circuits in liquid crystals [11–13], disordered ensembles of carbon nanotubes [6, 7, 25] (and Chapter “Evolution in Nanomaterio: The NASCENCE Project” by Broersma), slime mould (Chapter “Discovering Boolean Gates in Slime Mould” by Harding et al.), living plants (Chapter “Computers from Plants We Never Made: Speculations” by Adamatzky et al.), and reaction-diffusion chemical systems (“Chemical Computing Through Simulated Evolution” by Bull et al.). Julian’sinspirationfromnaturehasnotneglectedtherealmofchemistry:hehas exploitedchemicalideasinthedevelopmentofanovelformofartificialchemistry, Preface vii used to explore emergent complexity [8, 9]. Chapter “Sub-Symbolic Artificial Chemistries” by Faulkner et al. formalises this approach. The book will be a pleasure to explore for readers from all walks of life, from undergraduate students to university professors, from mathematicians, computers scientists, and engineers to chemists and biologists. York, UK Susan Stepney Bristol, UK Andrew Adamatzky June 2017 References 1. Almaini,A.E.A.,Miller,J.F.,Xu,L.:Automatedsynthesisofdigitalmultiplexernetworks.IEE Proc.E(Comput.Dig.Tech.)139(4),329–334(1992) 2. Almaini,A.E.A.,Miller,J.F.,Thomson,P.,Billina,S.:Stateassignmentoffinitestatemachines usingageneticalgorithm.IEEProc.Comp.Dig.Tech.142(4),279–286(1995) 3. Bryan, A.C., Miller, J.F., Stuart, A.E.G.: A linear superposition formula for the sine-Gordon multisolitonsolutions.J.Phys.Soc.Japan56(3),905–911(1987) 4. Bryan, A.C., Miller, J.F., Stuart, A.E.G.: Superposition formulae for multisolitons. II.—The modifiedKorteweg-deVriesequation.IlNuovoCimentoB101(6),715–720(1988) 5. Bryan,A.C.,Miller,J.F.,Stuart,A.E.G.:Superpositionformulaeforsine-Gordonmultisolitons. IlNuovoCimentoB101(6),637–652(1988) 6. Dale,M.,Miller,J.F.,Stepney,S.:Reservoircomputingasamodelforinmateriocomputing. In:AdvancesinUnconventionalComputing,pp.533–571.Springer,Berlin(2017) 7. Dale, M., Miller, J.F., Stepney, S., Trefzer, M.A.: Evolving carbon nanotube reservoir com- puters. In: International Conference on Unconventional Computation and Natural Computa- tion,pp.49–61.Springer,Berlin(2016) 8. Faulconbridge,A.,Stepney,S.,Miller,J.F.,Caves,L.:RBN-world:ThehuntforarichAChem. In:ALifeXII,Odense,Denmark,August2010,pp.261–268.MITPress,Cambridge(2010) 9. Faulconbridge, A., Stepney, S., Miller, J.F., Caves, L.S.D.: RBN-World: A sub-symbolic artificialchemistry.In:ECAL2009,Budapest,Hungary,September2009,vol.5777ofLNCS, pp.377–384.Springer,Berlin(2011) 10. Harding, S., Miller, J.F., Banzhaf, W.: Developments in Cartesian Genetic Programming: Self-modifyingCGP.Genet.Program.EvolvableMach.11(3/4),397–439(2010) 11. Harding,S.,Miller,J.:Evolutioninmaterio:Initialexperimentswithliquidcrystal.In:Pro- ceedings of NASA/DoD Conference on Evolvable Hardware, 2004, pp. 298–305. IEEE (2004) 12. Harding,S.,Miller,J.F.:Ascalableplatformforintrinsichardwareandinmaterioevolution. In:ProceedingsofNASA/DoDConferenceonEvolvableHardware,2003,pp.221–224.IEEE (2003) 13. Harding,S.,Miller,J.F.:Evolutioninmaterio:Evolvinglogicgatesinliquidcrystal.In:Proc. Eur.Conf.Artif.Life(ECAL2005),WorkshoponUnconventionalComputing:FromCellular AutomatatoWetware,pp.133–149.Beckington,UK(2005) 14. Liu,H.,Miller,J.F.,Tyrrell,A.M.:Abiologicaldevelopmentmodelforthedesignofrobust multiplier. In: Workshops on Applications of Evolutionary Computation, pp. 195–204. Springer,Berlin,Heidelberg(2005) 15. Miller, J.,Thomson,P.,Bradbeer,P.:Ternarydecisiondiagramoptimisationofreed-muller logic functions using a genetic algorithm for variable and simplification rule ordering. In: EvolutionaryComputing,pp.181–190(1995) viii Preface 16. Miller, J.F., Thomson, P.: Highly efficient exhaustive search algorithm for optimizing canonicalReed-Mullerexpansionsofbooleanfunctions.Int.J.Electr.76(1),37–56(1994) 17. Miller, J.: Evolving a self-repairing, self-regulating, french flag organism. In: Genetic and EvolutionaryComputation—GECCO2004,pp.129–139.Springer,Berlin,Heidelberg(2004) 18. Miller, J., Thomson, P.: Restricted evaluation genetic algorithms with tabu search for opti- mising boolean functions as multi-level and-exor networks. In: Evolutionary Computing, pp.85–101(1996) 19. Miller,J.F.:Evolvingdevelopmentalprogramsforadaptation,morphogenesis,andself-repair. In:EuropeanConferenceonArtificialLife,pp.256–265.Springer,Berlin,Heidelberg(2003) 20. Miller, J.F., Downing, K.: Evolution in materio: looking beyond the silicon box. In: Pro- ceedingsofNASA/DoDConferenceonEvolvableHardware,pp.167–176.IEEE(2002) 21. Miller, J.F., Hartmann, M.: Untidy evolution: evolving messy gates for fault tolerance. In: International Conference on Evolvable Systems, pp. 14–25. Springer, Berlin, Heidelberg (2001) 22. Miller, J.F.,Job, D.,Vassilev,V.:Principles intheevolutionary designofdigital circuits— partI.GeneticProg.EvolvableMach.1(1–2),7–35(2000) 23. Miller, J.F., Thomson, P.: Combinational and sequential logic optimisation using genetic algorithms. In: GALESIA. First International Conference on Genetic Algorithms in Engi- neeringSystems:InnovationsandApplications,1995(Conf.Publ.No.414),pp.34–38.IET (1995) 24. Miller, J.F., Thomson, P.: Cartesian genetic programming. In: European Conference on GeneticProgramming,pp.121–132.Springer,BerlinHeidelberg(2000) 25. Mohid, M., Miller, J.F., Harding, S.L., Tufte, G., Massey, M.K., Petty, M.C.: Evolution-in-materio: solving computational problems using carbon nanotube–polymer composites.SoftComput.20(8),3007–3022(2016) 26. Thomson, P., Miller, J.F.: Optimisation techniques based on the use of genetic algorithms (gas)forlogicimplementationonfpgas.In:IEEColloquiumonSoftwareSupportandCAD TechniquesforFPGAs,pp.4–1.IET(1994) 27. Vassilev, V., Miller, J.,Fogarty, T.:Theevolution ofcomputation in co-evolvingdemes of non-uniform cellular automata for global synchronisation. In: Advances in Artificial Life, pp.159–169(1999) 28. Vassilev, V.K., Miller, J.F., Fogarty, T.C.: Co-evolving demes of non-uniform cellular automata for synchronisation. In: Proceedings of the First NASA/DoD Workshop on EvolvableHardware,1999,pp.111–119.IEEE(1999) 29. Walker, J.A., Miller, J.F.: The automatic acquisition, evolution and re-use of modules in Cartesiangeneticprogramming.IEEETrans.Evol.Comput.12,397–417(2008) 30. Xu, L., Almaini, A.E.A., Miller, J.F., McKenzie, L.: Reed-Muller universal logic module networks.IEEProc.E-ComputersDig.Tech.140(2),105–108(1993) 31. Younes,A.,Rowe,J.,Miller,J.:Ahybridquantumsearchengine:Afastquantumalgorithm formultiplematches.arXivpreprintquant-ph/0311171(2003) Contents Part I Evolution and Hardware Evolvable Hardware Challenges: Past, Present and the Path to a Promising Future . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Pauline C. Haddow and Andy M. Tyrrell Bridging the Gap Between Evolvable Hardware and Industry Using Cartesian Genetic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 Zdenek Vasicek DesigningDigitalSystemsUsingCartesianGeneticProgrammingand VHDL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 Benjamin Henson, James Alfred Walker, Martin A. Trefzer and Andy M. Tyrrell Evolution in Nanomaterio: The NASCENCE Project. . . . . . . . . . . . . . . 87 Hajo Broersma Using Reed-Muller Expansions in the Synthesis and Optimization of Boolean Quantum Circuits. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 Ahmed Younes Part II Cartesian Genetic Programming Applications Some Remarks on Code Evolution with Genetic Programming . . . . . . . 145 Wolfgang Banzhaf Cartesian Genetic Programming for Control Engineering . . . . . . . . . . . 157 Tim Clarke Combining Local and Global Search: A Multi-objective Evolutionary Algorithm for Cartesian Genetic Programming . . . . . . . . . . . . . . . . . . . 175 Paul Kaufmann and Marco Platzner ix