Evolution of Parallel Cellular Machines The Cellular Programming Approach Moshe Sipper c Moshe Sipper 2004 (cid:13) (originally published by Springer, 1997) To see a world in a grain of sand And a heaven in a wild (cid:13)ower, Hold in(cid:12)nity in the palm of your hand And eternity in an hour. William Blake, Auguries of Innocence vii Preface There is grandeur in this view of life, with its several powers, having been originallybreathedintoafewformsorintoone; andthat,whilstthisplanet has gone cycling on according to the (cid:12)xed law of gravity, from so simple a beginning endless forms most beautiful and most wonderful have been, and are being, evolved. Charles Darwin, The Origin of Species Naturalevolutionhas\created"amultitudeofsystemsinwhichtheactionsof simple,locally-interactingcomponentsgiverisetocoordinatedglobalinformation processing. Insect colonies, cellular assemblies, the retina, and the immune sys- tem, have all been cited as examples of systems in which emergent computation occurs. Thistermreferstotheappearanceofglobalinformation-processingcapa- bilitiesthat are not explicitlyrepresentedin the system’selementarycomponents or in their interconnections. The parallel cellular machines \designed" by nature exhibit striking problem- solving capacities, while functioning within a dynamic environment. The central question posed in this volume is whether we can mimic nature’s achievement, creating arti(cid:12)cial machines that exhibit characteristics such as those manifest by their natural counterparts. Clearly, this ambitious goal is yet far o(cid:11), however, our intent is to take a small step toward it. The(cid:12)rstissuethatmustbeaddressedconcernsthebasicdesignofoursystem, namely, we must choose a viable machine model. We shall present a number of systems in this work, which are essentially generalizations of the well-known cel- lularautomata (CA)model. CAsaredynamical systemsinwhichspaceand time are discrete. A cellular automaton consists of an array of cells, each of which can be in one of a (cid:12)nite number of possible states, updated synchronously in discrete time steps, according to a local, identical interaction rule. CAs exhibit three no- table features, namely, massive parallelism, locality of cellular interactions, and simplicity of basic components (cells). Thus, they present an excellent point of departure for our forays into parallel cellular machines. Havingchosenthemachinemodel,weimmediatelyencounteramajorproblem common to such local, parallel systems, namely, the painstaking task one is faced withindesigningthemtoexhibitaspeci(cid:12)cbehaviororsolveaparticularproblem. This results from the local dynamics of the system, which renders the design of local interaction rules to perform global computational tasks extremely arduous. Aiming to learn how to design such parallel cellular machines, we turn to nature, seekinginspirationintheprocessofevolution. Theideaofapplyingthebiological principle of natural evolution to arti(cid:12)cial systems, introduced more than three decades ago, has seen impressive growth in the past decade. Usually grouped under the term evolutionary algorithms or evolutionary computation, we (cid:12)nd the domains of genetic algorithms, evolution strategies, evolutionary programming, viii andgeneticprogramming. Inthisvolumeweemployarti(cid:12)cialevolution,basedon the genetic-algorithms approach, to evolve (\design") parallel cellular machines. The book consists of three parts. After presenting the overall framework in Chapter 1, including introductory expositions of cellular automata and genetic algorithms, we move on to Chapter 2, the (cid:12)rst part of this volume. We focus on non-uniform cellular automata, the machine model which serves as a basis for the succeeding parts. Such automata function in the same way as uniform ones, the only di(cid:11)erence being in the local cellular interaction rules that need not be identical for all cells. In Chapter 2 we investigate the issue of universal computation, namely, the construction of machines, embedded in cellular space, whose computational power is equivalent to that of a universal Turing machine. This is carried out in the context of 2-dimensional, 2-state, 5-neighbor cellular space, that is not computation universal in the uniform case. We show that non- uniform CAs can attain universal computation using systems that are simpler than previous ones and are quasi-uniform, meaning that the number of distinct rules is extremely small with respect to rule-space size, distributed such that a subset of dominant rules occupies most of the grid. The (cid:12)nal system presented is minimal, with but two distinct rules. Thus, we demonstrate that simple, non- uniform CAs comprise viable parallel cellular machines. Chapter 3, the second part of this volume, investigates issues pertaining to arti(cid:12)cial life (ALife). We present a modi(cid:12)ed non-uniform CA model, with which questions of evolution, adaptation, and multicellularity are addressed. Our ALife systemconsistsofa2-dimensionalgridofinteracting\organisms"thatmayevolve over time. We (cid:12)rst present designed multicellular organisms that display several interesting behaviors, including reproduction, growth, and mobility. We then turn our attention to evolution in various environments, including an environ- ment where competition for space occurs, an IPD (Iterated Prisoner’s Dilemma) environment, a spatial-niches environment, and a temporal-niches one. Several measuresofinterestareintroduced,enablingustogleantheevolutionaryprocess’ inner workings. This latter point is a prime advantage of ALife models, namely, our enhanced investigative power in comparison to natural systems. Our main conclusion from this part is that non-uniform CAs and their exten- sions comprise austere yet versatile models for studying ALife phenomena. It is hoped that the development of such ALife models will serve the two-fold goal of: (1) increasing our understanding of biological phenomena, and (2) enhancing our insight into arti(cid:12)cial systems, thereby enabling us to improve their performance. ALife research opens new doors, providing us with novel opportunities to explore issues such as adaptation, evolution, and emergence, that are central both in natural environments as well as man-made ones. In thethirdandmain partof thisvolume, consistingof Chapters4 through 8, we focus on the evolution of parallel cellular machines that solve complex, global computational tasks. In Chapter 4 we introduce the basic approach, denoted cel- lular programming, whereby a non-uniform CA locally coevolves to solve a given ix task. Our approach di(cid:11)ers from the standard genetic algorithm, where a pop- ulation of independent problem solutions globally evolves. We demonstrate the viability of our methodology by conducting an in-depth study of two global com- putational problems, density and synchronization, which are successfully solved by coevolved machines. In Chapter 5 we describe a number of additional com- putational tasks, motivated by real-world problems, for which parallel cellular machines were evolved via cellular programming. These tasks include counting, ordering, boundary computation, thinning, and random number generation, sug- gesting possible application domains for our systems. Though most of the results described in this volume have been obtained through software simulation, a prime motivation of our work is the attainment of \evolving ware," evolware, with current implementations centering on hard- ware, while raising the possibility of using other forms in the future, such as bioware. This idea, whose origins can be traced to the cybernetics movement of the 1940s and the 1950s, has recently resurged in the form of the nascent (cid:12)eld of bio-inspired systems and evolvable hardware. The (cid:12)eld draws on ideas from evolutionarycomputationaswellasonrecenthardwaredevelopments. Chapter6 presents the \(cid:12)re(cid:13)y" machine, an evolving, online, autonomous hardware system that implements the cellular programming algorithm, thus demonstrating that evolware can indeed be attained. Mostclassicalsoftwareandhardwaresystems,especiallyparallelones,exhibit a very low level of fault tolerance, i.e., they are not resilient in the face of errors; indeed, where software is concerned, even a single error can often bring an entire program to a grinding halt. Futurecomputing systemsmay contain thousands or even millions of computing elements. For such large numbers of components, the issue of resilience can no longer be ignored since faults will be likely to occur with high probability. Chapter 7 looks into the issue of fault tolerance, examining the resilienceofourevolvedsystemswhenoperatingunderfaultyconditions. We(cid:12)nd that they exhibit graceful degradation in performance, able to tolerate a certain level of faults. A fundamental property of the original CA model is its standard, homoge- neous connectivity, meaning that the cellular array is a regular grid, all cells connected in exactly the same manner to their neighbors. In Chapter 8 we study non-standard connectivity architectures, showing that these entail de(cid:12)nite per- formance gains, and that, moreover, one can evolve the architecture through a two-level evolutionary process, in which the local cellular interaction rules evolve concomitantly with the cellular connections. Our main conclusion from the third part is that parallel cellular machines can attain high performance on complex computational tasks, and that, moreover, such systems can be evolved rather than designed. Chapter 9 concludes the volume, presenting several possible avenues of future research. Parallel cellular machines hold potential both scienti(cid:12)cally, as vehicles for studying phenomena of interest in areas such as complex adaptive systems and x arti(cid:12)cial life, as well as practically, showing a range of potential future applica- tions, ensuing the construction of systems endowed with evolutionary, reproduc- tive, regenerative, and learning capabilities. We hope this volume sheds light on the behavior of such machines, the complex computation they exhibit, and the application of arti(cid:12)cial evolution to attain such systems. Acknowledgments I thank you for your voices: thank you: Your most sweet voices. William Shakespeare, Coriolanus It is a pleasure to acknowledge the assistance of several people with whom I collaborated. Daniel Mange, Eduardo Sanchez, and Marco Tomassini, from the Logic Systems Laboratory at the Swiss Federal Institute of Technology in Lausanne, were (and still are!) a major source of inspiration and energy. Our animated discussions, the stimulating brainstorming sessions we held, and their penetrating insights, have seeded many a fruit, disseminated throughout this volume. I thank Eytan Ruppin from Tel Aviv University, with whom it has always been a joy to work, for having in(cid:13)uenced me in more ways than one, and for his steadfast encouragement during the waning hours of my research. Pierre Marchal from the Centre Suisse d’Electronique et de Microtechnique was a constant crucible of ideas, conveyed in his homely, jovial manner, and I have always been delighted at the opportunity to collaborate with him. The Logic Systems Laboratory has provided an ideal environment for research, combining both keen minds and lively spirits. I thank each and every one of its members, andamespeciallygratefultoMaximeGoeke,Andr(cid:19)esP(cid:19)erez-Uribe,Andr(cid:19)eStau(cid:11)er, Mathieu Capcarrere, and Olivier Beuret. I am grateful to Melanie Mitchell from the Santa Fe Institute for her many valuable comments and suggestions. I thank Hezy Yeshurun from Tel Aviv University for his indispensable help at a critical point in my research. I am grateful to Hans-Paul Schwefel from the University of Dortmundforreviewingthismanuscript,o(cid:11)eringhelpfulremarksandsuggestions for improvements. I thank Alfred Hofmann and his team at Springer-Verlag, without whom this brainchild of mine would have remained just that { a pipe dream. Finally, last but not least, I am grateful to my parents, Shoshana and Daniel, for bequeathing and believing. Lausanne, December 1996 Moshe Sipper Contents Preface vii 1 Introduction 1 1.1 Prologue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Cellular automata . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.1 An informal introduction . . . . . . . . . . . . . . . . . . . 3 1.2.2 Formal de(cid:12)nitions . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.3 Non-uniform CAs. . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.4 Historical notes . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3 Genetic algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2 Universal Computation in Quasi-Uniform Cellular Automata 15 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2 A universal 2-state, 5-neighbor non-uniform CA . . . . . . . . . . . 16 2.2.1 Signals and wires . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2.2 Logic gates . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2.3 Clock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2.4 Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.3 Reducing the number of rules . . . . . . . . . . . . . . . . . . . . . 22 2.4 Implementing a universal machine using a (cid:12)nite con(cid:12)guration . . . 23 2.5 A quasi-uniform cellular space . . . . . . . . . . . . . . . . . . . . . 25 2.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3 Studying Arti(cid:12)cial Life Using a Simple, General Cellular Model 31 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.2 The ALife model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.3 Multicellularity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.3.1 A self-reproducing loop . . . . . . . . . . . . . . . . . . . . 35 3.3.2 Reproduction by copier cells. . . . . . . . . . . . . . . . . . 39 3.3.3 Mobility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.3.4 Growth and replication . . . . . . . . . . . . . . . . . . . . 43 3.4 Evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.4.1 Evolution in rule space . . . . . . . . . . . . . . . . . . . . . 44 xii Contents 3.4.2 Initial results . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.4.3 Fitness in an IPD environment . . . . . . . . . . . . . . . . 49 3.4.4 Energy in an environment of niches . . . . . . . . . . . . . . 56 3.4.5 The genescape . . . . . . . . . . . . . . . . . . . . . . . . . 61 3.4.6 Synchrony versus asynchrony . . . . . . . . . . . . . . . . . 66 3.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 4 Cellular Programming: Coevolving Cellular Computation 73 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.2 Previous work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.3 The cellular programming algorithm . . . . . . . . . . . . . . . . . 79 4.4 Results using one-dimensional, r = 3 grids . . . . . . . . . . . . . . 82 4.5 Results using one-dimensional, r = 1 grids . . . . . . . . . . . . . . 83 4.5.1 The density task . . . . . . . . . . . . . . . . . . . . . . . . 85 4.5.2 The synchronization task . . . . . . . . . . . . . . . . . . . 91 4.6 Results using two-dimensional, 5-neighbor grids . . . . . . . . . . . 94 4.7 Scaling evolved CAs . . . . . . . . . . . . . . . . . . . . . . . . . . 96 4.8 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 5 Toward Applications of Cellular Programming 101 5.1 The synchronization task revisited: Constructing counters . . . . . 102 5.2 The ordering task . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 5.3 The rectangle-boundary task . . . . . . . . . . . . . . . . . . . . . 105 5.4 The thinning task . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5.5 Random number generation . . . . . . . . . . . . . . . . . . . . . . 111 5.6 Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . . . 117 6 Online Autonomous Evolware: The Fire(cid:13)y Machine 119 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 6.2 Large-scale programmable circuits . . . . . . . . . . . . . . . . . . 121 6.3 Implementing evolware . . . . . . . . . . . . . . . . . . . . . . . . . 122 6.4 Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . . . 126 7 Studying Fault Tolerance in Evolved Cellular Machines 129 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 7.2 Faults and damage in lattice models . . . . . . . . . . . . . . . . . 130 7.3 Probabilistic faults in cellular automata . . . . . . . . . . . . . . . 131 7.4 Results. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 7.5 Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . . . 139 8 Coevolving Architectures for Cellular Machines 141 8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 8.2 Architecture considerations . . . . . . . . . . . . . . . . . . . . . . 142 8.3 Fixed architectures . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 Contents xiii 8.4 Evolving architectures . . . . . . . . . . . . . . . . . . . . . . . . . 148 8.5 Evolving low-cost architectures . . . . . . . . . . . . . . . . . . . . 153 8.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 9 Concluding Remarks and Future Research 159 A Growth and Replication: Speci(cid:12)cation of Rules 165 B A Two-state, r=1 CA that Classi(cid:12)es Density 169 C Speci(cid:12)cation of Evolved CAs 173 D Speci(cid:12)cation of an Evolved Architecture 175 E Computing acd and equivalent d 177 0 Bibliography 179 Index 196 xiv Contents