Moshe Sipper Evolution of Parallel Cellular Machines ehT Cellular gnimmargorP hcaorppA Springer Lecture Notes in Computer Science 1194 Edited by G. Goos, J. Hartmanis and J. van Leeuwen Advisory Board: W. Brauer D. Gries J. Stoer Series Editors Gerhard Goos, Karlsruhe University, Germany Juris Hartmanis, Cornell University, NY, USA Jan van Leeuwen, Utrecht University, The Netherlands Author Moshe Sipper Swiss Federal Institute of Technology Logic Systems Laboratory, IN-Ecublens CH-1015 Lausanne, Switzerland E-mail: Moshe.Sipper @ di.epfl.ch Cataloging-in-Publication data applied for Die Deutsche Bibliothek - CIP-Einheitsaufnahme Sipper, Moshe: Evolution of parallel cellular machines : the cellular programming approach / Moshe Sipper. - Berlin ; Heidelberg ; New York ; Barcelona ; Budapest ; Hong Kong ; London ; Milan ; Paris ; Santa Clara ; Singapore ; Tokyo : Springer, 1997 (Lecture notes in computer science ; )4911 ISBN 3-540-62613-1 NE: GT CR Subject Classification (1991): F.1, C.1.2, F.2.2, D.1.3, 1.2.6, J.3 ISSN 0302-9743 ISBN 3-540-62613-1 Springer-Verlag Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer -Verlag. Violations are liable for prosecution under the German Copyright Law. (cid:14)9 Springer-Verlag Berlin Heidelberg 1997 Printed in Germany Typesetting: Camera-ready by author SPIN 10549006 06/3142 - 5 4 3 2 1 0 Printed on acid-free paper To see a world in a grain of sand And a heaven in a wild flower, ttold infinity in the palm of your hand And eternity in an hour. William Blake, Auguries of Innocence Preface There is grandeur in this view of life, with its several powers, having been originally breathed into a few forms or into one; and that, whilst this planet has gone cycling on according to the fixed 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 Natural evolution has "created" a multitude of systems in which the actions of simple, locally-interacting components give rise to coordinated global information 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. This term refers to the appearance of global information-processing capa- bilities that are not explicitly represented in the system's elementary components 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 artificial machines that exhibit characteristics such as those manifest by their natural counterparts. Clearly, this ambitious goal is yet far off, however, our intent is to take a small step toward it. The first issue that must be addressed concerns the basic design of our system, 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- lular automata (CA) model. CAs are dynamical systems in which space and time are discrete. A cellular automaton consists of an array of cells, each of which can be in one of a finite 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. Having chosen the machine model, we immediately encounter a major problem common to such local, parallel systems, namely, the painstaking task one is faced with in designing them to exhibit a specific behavior or solve a particular problem. 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, seeking inspiration in the process of evolution. The idea of applying the biological principle of natural evolution to artificial 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 find the domains of genetic algorithms, evolution strategies, evolutionary programming, iiiv and genetic programming. In this volume we employ artificial evolution, based on 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 first 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 difference 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 final 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 artificial life (ALife). We present a modified non-uniform CA model, with which questions of evolution, adaptation, and multicellularity are addressed. Our ALife system consists of a 2-dimensional grid of interacting "organisms" that may evolve over time. We first present designed multicellutar 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 measures of interest are introduced, enabling us to glean the evolutionary process' 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 artificial 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 the third and main part of this volume, consisting of Chapters 4 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 task. Our approach differs from the standard genetic algorithm, where a pop- ulation of independent problem solutions globMly 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," ,eracvlove with current implementations centering on hard- ware, while raising the possibility of using other forms in the future, such as .erawoib 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 field of bio-inspired systems and evolvable hardware. The field draws on ideas from evolutionary computation as well as on recent hardware developments. Chapter 6 presents the "firefly" machine, an evolving, online, autonomous hardware system that implements the cellular programming algorithm, thus demonstrating that evolware can indeed be attained. Most classical software and hardware systems, especially parallel ones, 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. Future computing systems may 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 resilience of our evolved systems when operating under faulty conditions. We find 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 definite 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 scientifically, as vehicles for studying phenomena of interest in areas such as complex adaptive systems and artificial 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 artificial 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 influenced 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, and am especially grateful to Maxime Goeke, AndrOs P~rez-Uribe, Andr~ Stauffer, 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 Dortmund for reviewing this manuscript, offering helpful remarks and suggestions 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 tIv Introduction 1 1.1 Prologue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Cellular automata . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.1 An informal introduction . . . . . . . . . . . . . . . . . . . 3 1.2.2 Formal definitions . . . . . . . . . . . . . . . . . . . . . . . 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 finite configuration . . . 23 2.5 A quasi-uniform cellular space . . . . . . . . . . . . . . . . . . . . . 25 2.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3 Studying Artificial 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 (cid:141) Contents 3.4.2 Initial results . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.4.3 Fitness in an IPD environment ................ 49 3.4.4 Energy in an environment of ni(hcs .............. 56 3.4.5 The geuescape ......................... 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 Tlne ~,ynchronization task ................... 91 4.6 Results using two-dimensional, 5-neighbor grids ........... 94 4.7 Scaling evolved CAs . . . . . . . . . . . . . . . . . . . . . . . . . . 96 4.8 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 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 Online Autonomous Evolware: The Firefly Machine 119 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 6.2 Large-scale programmable circuits .................. 121 6.3 Implementing evolware ......................... 122 6.4 Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . . . 126 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 Coevolving Architectures for Cellular Machines 141 8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 8.2 Architecture consideratious ...................... 142 8.3 Fixed architectures . . . . . . . . . . . . . . . . . . . . . . . . . . . 145