|
|
Evolving
Dynamical Systems Simulation of
Biology Final Project Ken Camann
Idea The idea
for this project comes from the paper "Interactive Evolution of
Dynamical Systems" by Karl Sims.
In it, he suggests that visually interesting dynamical systems can be evolved
more effectively than they can be designed.
He defines his systems using four scalar functions of two variables, two
giving the initial conditions of quantities A and B, and two giving their
time derivatives. These equations
represent the genotype of a dynamical system, with the phenotype being the system
generated from time integrating the differential equations. A user picks a phenotype that he or she thinks
is visually interesting and the system copies its equations. During copying, several different types of
mutations can change the functions slightly, creating a different genotype. A typical session is similar to a Blind Watchmaker
simulation: the user is presented with multiple systems, and after time
integrating them the user picks the most visually interesting. This is copied 4 times, possibly with
mutations. The user again picks the
favorite as it evolves. Programming Challenges In Karl
Sims’ implementation of this program, Lisp expressions were used to encode
the functions in prefix form. A
typical function might be (+ A x), which would
correspond to f(x, y) = A(x, y) + x, where A is the name of the first
variable in the system. The original
version was also implemented on a Connection Machine, a massively parallel super
computer from the 1980s, in order to run at interactive speed. To achieve an acceptable balance between
ease of development and execution time, my implementation was written using Microsoft
Visual C# Express Edition. This is
because I needed the rapid application development properties of modern
language (like the ability to build a quick user interface) but also needed
direct memory access (software bit-block transfers are used to actually draw
the image, for speed reasons). Despite
this, the program is still very slow, although it is much faster than my
Processing reaction-diffusion code. Because
I did not use Lisp, I represented functions as expression trees. My program is able to parse and output the
Lisp expressions corresponding to the internal expression tree
representation, however. Function Set
Unary Functions abs,
round, negate, sqrt, square, exp (e^x), sin, cos, sign Binary Functions +, -, *,
/, ^ (power), log, mod, atan2, min, max Ternary Functions ifpos, ifneg, noise Neighborhood Functions (functions
which operate on neighborhoods in one image) xgrad, ygrad, gradmag, graddir, gradmagsquared, gradindir, laplacian, nhmin, nhmax, nhave, conv5, conv9 The
function noise is special: it
generates Perlin noise and has three parameters: frequency,
persistence, and number of octaves. For
each octave, the frequency doubles and the amplitude weighted by the product
of the existing weight and the persistence factor as in fBm noise. Randomly Generated Expressions Certain
types of mutations, as well as the initial 4 systems, require a mechanism for
generating random expressions. A
random expression can be of 3 different types: constant, variable, or
function. A constant is just a
constant scalar value. A variable is
either A, B, x, or y. A function is
one of the above functions types, which requires additional random expressions
for its arguments. Many special rules
apply to avoid generating mathematically uninteresting arguments for certain functions,
for example the Lisp expression (laplacian 3). Because random function expressions are
generated recursively, a “maximum height” is specified in the random
generation call. The procedure will be
forced to generate a variable or constant expression after the tree reaches
this depth. Noise functions cannot be
generated in differential equations, only in initial conditions. Mutations The
probability of a mutation while recursively copying an expression tree is
inversely proportional to the number of nodes in the tree, multiplied with
some constant. This ensures that
longer expressions do not change too drastically when they are copied. There are several different types of
mutations: Random Expression – A node is replaced with a
random expression tree Type Preserving – A node is mutated to another
expression of the same type. I.e., constants
become different constants, variables become different variables, and
functions become different functions. The
old function arguments are used in the new function. If the number of arguments changes, existing
arguments are either omitted or new ones are generated. Function Argument – An existing node becomes an
argument to a new random function Function Deletion – If
the type of this node is a function, the function is deleted and its argument
becomes the new expression. The
frequency with which these occur must be tweaked to ensure that the
differential equations usually do something interesting. For example, inappropriate mutation settings
might create too many constant scalar values, resulting in uninteresting
behavior because the function does not have enough dependency on variables. This often results in a harmful mutation; completely
visually uninteresting systems are never selected by the user, and some
genetic mutations will cause the screen to be all white (or all black) if the
system is unstable or always evaluates to a constant value. Differential Equations & Ensuring Interesting Behavior Because
of technological limitations at the time, the original program used Euler
time integration. I had wanted to implement the classic 4th
order Runge-Kutta method instead to ensure greater
stability, but I did not have time to do so.
Because of the sensitivity of differential equations I had expected
not to get much interesting behavior without starting from equations known to
be interesting, but I was able to get many interesting results just using the
random expression generator. The first
two of these pictures were taken at a time when the program output was not
working so the corresponding functions do not appear. All 16 functions appear for the second
screenshot. Some interesting initial conditions
Some interesting systems after 500 Euler steps
Top Left A0 = (gradmagsquared (noise 0.0932686469744745
0.00121141318288232 4)) B0 = (neg (noise 0.00638372166193264 0.583485082529245 1)) dA/dt =
(square (sin B)) dB/dt = (sqrt (atan2 A (round B))) Top Right A0 = (gradmagsquared (noise 0.0932686469744745 0.00121141318288232
4)) B0 = (neg (noise 0.00638372166193264 0.583485082529245 1)) dA/dt = (nhmin (sin B)) dB/dt = (nhave A) Bottom Left A0 = (gradmagsquared (noise 0.0932686469744745
0.00121141318288232 4)) B0 = (neg (noise 0.00638372166193264 0.583485082529245 1)) dA/dt =
(square (sin B)) dB/dt = (nhave A) Bottom Right A0 = (gradmagsquared (min (noise 0.0932686469744745
0.00121141318288232 4) (nhave (noise
0.0783055754617348 0.0433988650531503 1)))) B0 = (neg (noise 0.00638372166193264 0.583485082529245 1)) dA/dt =
(square (sin B)) dB/dt = (nhave (conv9 A (nhmin x))) Using the Program Initially
the screen will be black. Right click
anywhere on the black screen and a dialog will pop up with a proposed set of
4 functions for a random system.
Either accept this by clicking Update, click “CopyM” to copy a given function until it mutates, or
enter in your own function in Lisp form.
Clicking Update will generate 4 random genotypes and display their
initial condition. Pressing the “TI
Start” button starts the time integration.
Pressing the “TI Stop” button stops this integration. Left clicking a system shows the other
variable (B if A is currently shown, A if B is
currently shown), and middle clicking at any time selects that system for
reproduction. All 4 system windows
will automatically be populated with copied (and possibly mutated) children
from the selected system. The program requires
the Microsoft .Net framework 2.0 to run.
There is a known bug in the software: the dialog that pops up when
right clicking a system cannot be closed by hitting the “X” button. You must either click Update or Cancel. Closing it with “X” will cause a runtime
exception.
The
source code and binaries are located here References
|
