Cellular Programming

Evolution of Parallel Cellular Machines

Romanian translation of this page

Overview

Natural evolution has "created" many 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 system, have all been cited as examples of systems in which emergent computation occurs. This term refers to the appearance of global information processing capabilities that are not explicitly represented in the system's elementary components or in their interconnections.

The parallel cellular machines "designed" by nature display an impressive capacity to successfully confront extremely difficult computational problems. In recent years we are witness to a rapidly growing interest in such complex adaptive systems. Under this heading we find researchers from different fields, studying diverse systems, natural- as well as human-made, with the underlying two-fold goal of: (1) enhancing our understanding of the functionings of natural systems, as well as of the ways by which they might have evolved, and (2) mimicking nature's achievement, creating artificial systems based on these principles, matching the problem-solving capacities of their natural counterparts. The goal of our work is to explore these issues, basing our studies on the cellular automata (CA) model. CAs exhibit three notable 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. The model investigated in our work is an extension of the CA model, termed non-uniform cellular automata.

A major problem common to such local, parallel systems is 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. Toward this end we turn to nature, seeking inspiration in the process of evolution, that has given rise to the field of evolutionary computation. We apply our cellular programming approach to evolve parallel cellular machines to perform computational tasks. Cellular programming involves a local, coevolutionary algorithm, thus differing from the standard, global genetic algorithm.

Evolving 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 applications, ensuing the construction of adaptive systems, and in particular evolving ware, evolware (see below). We hope our work sheds light on the behavior of parallel cellular machines, the complex computation they exhibit, and the application of artificial evolution to attain such systems.

(To get an idea about the enabling methodologies, see the online introduction to cellular automata, and the online introduction to genetic algorithms.)

Group members

Principal researchers:

Collaborators: Students (present and former):

Work carried out to date

Annotated version is given below.
M. Sipper, Machine Nature: The Coming Age of Bio-Inspired Computing, McGraw-Hill, New York, 2002.
See Moshe Sipper's publications page for more recent papers, paper abstracts, and (some) online versions.

Other groups doing research on cellular programming


Last updated: Dec 8, 2003