Interactive Evolution of Cellular Automata

Software	Language with good GUI facilities (OO or functional)
Covers	Programming, evolutionary computing, simple graphics
Skills Required	Programming, willingness to understand some simple maths, preferably interest in art or graphic design.
Challenge	Conceptual ???? Technical ??? Programming ?????

Brief Description

A cellular automaton is a simple computational machine, that has a state, and on each cycle computes its next state according to the states of its neighbours. Arrays of cellular automata (with different transition functions or all with the same transition function) can exhibit interesting collective behaviour. They are often used to study evolutionary processes and the behaviour of ecosystems.

The behaviour of arrays of cellular automata can be displayed as colour patterns. A bitmap picture can be used to show either a single state of a two dimensional array of automata, or a sequence of states of a one dimensional array (a line) of automata. Thus cellular automata can be used to produce pretty pictures that could be used as textile patterns or in other types of graphic design (an idea suggested by Yoshiyuki Shiroma at ICED 99).

Interactive evolution has been used as a method for creating artworks and designs: at each stage the user is presented with a range of alternative designs, and picks one for further development; the chosen design is then modified in various different ways and the new designs are then presented to the user for the next cycle of development.

In this project, your task is: (1) To develop a user interface for displaying the successive states of several one dimensional arrays of cellular automata as colour bitmaps, with a mechanism for choosing one of these interactively. (2) To develop a way of describing the transition functions of cellular automata such that this description can be randomly modified in a variety of different ways, plus a mechanism that randomly modifies the transition functions of cellular automata. (3) A mechanism for running arrays of cellular automata, recording a succession of states and translating these state sequences into colour bitmaps. (4) To use these components to build an interactive system for guided evolution of cellular automaton transition functions.

Extensions

Implement a mechanism for creating new transition functions by mating two existing transition functions by creating one or a set of (legal) random combinations of parts of them. Implement a way to do this interactively as part of the graphical user interface.

Implement a way to display the transition function itself in some symbolic form, and a mechanism that allows the users to edit it interactively.

Implement a way to apply the same approach to evolving transition functions for two dimensional arrays of cellular automata. How do you find the particular state in a time sequence that you want (if what you want is a pretty pattern)?

The above presupposes that all the automata in an array are the same. Think about how to extend all this to arrays containing more than one type of cellular automaton.

Cross-Reference

My project Interactive System for Automatic Design of Textile Patterns is about doing essentially the same thing using rewrite rules for constructing shapes.

Variants

If you're intrigued by cellular automata, but aren't interested in pretty patterns, we can talk about what else you might do....

Back to