Chemical Evolution
Julian Hoch
I've been playing around with the Organic Builder, and yes it's pretty
cool. From the different "levels" I take it the goal is to simulate
the reproduction / evolution of cells (which is a bit strange since
cells in nature aren't just one big molecule, but if it works, why
not).
But what I've seen from the solutions here in the forum to the
different tasks is that what people do is they create a set of rules
to make the cell behave like it should. But this isn't how life works,
is it? It's like the intelligent designer creating the universe and
fine-tuning it to make the cells behave like "they should". Wouldn't
the goal be to develop a more universal set of rules, and develop self-
replication in the framework of these "natural laws"? What I mean is
that in OUR universe the information about how cells divide (for
example) is not encoded in the laws of physics, but in the "DNA". So
when I see solutions where the construction of cellular mouths,
mytosis etc. is encoded in the reaction rules, yes that works, but
shouldn't that be encoded in the "DNA"?
Well perhaps I am asking too much. But if you really want EVOLUTION
you have to encode this kind of information in the organism, so that
it is subject to mutation.
P.S.: I've not analyzed the code yet, but it seems to me the program
is single-threaded, is that true? Makes the program sluggish from time
to time and can screw up the GUI elements.
Tim Hutton
On 7 April 2010 12:02, Julian Hoch <Julia...@web.de> wrote:
> Hi,
>
> I've been playing around with the Organic Builder, and yes it's pretty
> cool.
Excellent - thanks!
> From the different "levels" I take it the goal is to simulate
> the reproduction / evolution of cells (which is a bit strange since
> cells in nature aren't just one big molecule, but if it works, why
> not).
>
> But what I've seen from the solutions here in the forum to the
> different tasks is that what people do is they create a set of rules
> to make the cell behave like it should. But this isn't how life works,
> is it? It's like the intelligent designer creating the universe and
> fine-tuning it to make the cells behave like "they should". Wouldn't
> the goal be to develop a more universal set of rules, and develop self-
> replication in the framework of these "natural laws"? What I mean is
> that in OUR universe the information about how cells divide (for
> example) is not encoded in the laws of physics, but in the "DNA". So
> when I see solutions where the construction of cellular mouths,
> mytosis etc. is encoded in the reaction rules, yes that works, but
> shouldn't that be encoded in the "DNA"?
>
> Well perhaps I am asking too much. But if you really want EVOLUTION
> you have to encode this kind of information in the organism, so that
> it is subject to mutation.
I completely agree with everything you've written. This is the central
problem of the field of Artificial Life; to find a system that we can
leave running and that exhibits the open-ended evolutionary growth of
complexity. (The 'Autoverse' of Greg Egan's book 'Permutation City'
captures this concept perfectly.) Let's call this desired system
"System X".
Organic Builder isn't System X but it *is* an exploration of some of
the properties that we think System X should support (information
replication and physical containment, to name just two). More than
that it's an introduction to artificial chemistries and so I'm
delighted that it's got you asking these questions.
For more thoughts in the direction of System X, have a read of my 2007
paper here:
http://www.sq3.org.uk/wiki.pl?Papers
In that paper I provide rules that allow molecules to make enzymes, so
the letter-sequence of the molecule determines the behaviour of the
cells. I think this is more what you're asking for. I'd love to extend
the Organic Builder in this sort of direction - and then the
challenges might be to design a letter-sequence to solve different
tasks, or you could turn on mutation and leave the system running to
solve them itself.
One problem is that it gets a bit computationally demanding, since the
molecules get very big. Another is that it's hard to know exactly what
to implement since there are so many possibilities.
(In the Organic Builder paper (2009) I mention the possibilitity of
making the search for System X itself into a challenge for the users
to solve. The problem here is knowing how to make that possible
without requiring them to be programmers!)
> P.S.: I've not analyzed the code yet, but it seems to me the program
> is single-threaded, is that true? Makes the program sluggish from time
> to time and can screw up the GUI elements.
Bertrand and I have tried to multi-thread the bottlenecks but I'm sure
it can be improved. It would be great if you could have a look at the
code. I started a port to Flash but never got very far with it:
http://code.google.com/p/ob-flash/
A port to GWT and the Canvas element would work too. Java applets are
pretty much a dead technology I think. (For the work in the paper I
use a C++ implementation and a lattice-based physics for speed.)
Let us know what you think,
Tim
--
Tim Hutton - http://www.sq3.org.uk - http://ferkeltongs.livejournal.com
Bertrand Dechoux
I agree that's pretty cool (and that there is still work to do).
About evolution, it is -generally speaking- broader than just DNA. It
might happens in any environment where there is reproduction,
mutation, selection and a way to store information (like DNA). It
might happen at molecular level (virus), cellular level (gene and so
DNA), cultural level (meme), 'electronic' level (virus) and so on...
Organic Builder is, as you said it rightly, not focused on 'cell
evolution'. It is a simpler world but still with amazing properties.
In his last post, Tim Hutton discussed self-replicating Turing
Machines. I have not had the time to look at it in details but that's
a great step towards 'evolution'. If mutation and selection are
introduced into OB, then with time, luck and horsepower, interesting
patterns might emerge. But finding the best rules to do so is not
trivial. If you want to participate, you are more than welcome.
If you are interested on the subject and have a computer science
background, you could read about evolutionary algorithm. (http://
en.wikipedia.org/wiki/Evolutionary_algorithm) Like life, such
algorithm is basically a blind search to find an optimum.
Last about the 'threading' of the program, there are actually two
threads : one for the engine and one for the gui (that's swing's
paradigm). But I suppose a few fine tunings might be required.
Bertrand Dechoux
You received this message because you are subscribed to the Google Groups "OrganicBuilder" group.
To post to this group, send email to organic...@googlegroups.com.
To unsubscribe from this group, send email to organicbuilde...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/organicbuilder?hl=en.
Julian Hoch
Yes I am a computer scientist (student atm) although I'm more
experienced in image processing, machine learning and robotics. I have
experimented with evolutionary algorithms and find it quite
fascinating.
First a few technical things: Java is a great language. In my opinion
it's way better than C++, and so it's definitely a good option. But
since you mentioned the complexity problem, C++ might perhaps be an
alternative. I was thinking that it should be possible to parallelize
the problem, and an implementation in GPGPU (e.g. in CUDA) might speed
things up enormously. If you really want evolution, you want LOTS of
instances, and a lot of speed.
Now I've got a few questions about the "chemical background" (I will
have to read your papers in detail, but I have a few fundamental
questions):
1. Is the chemistry in your system really chemistry? I though
chemistry describes the reaction of molecules.
But all the rules in your system are on the level of atoms, which
means every interaction of molecules has
to be described on the atomic level. And there is no binding between
molecules (like ionic bindings etc.), so to get complex structures you
need very complex, big molecules, and very complicated rules.
2. It is a 2D chemistry (that posed a problem for me in my playing
around with the problem, since atoms
can wind up on the "wrong side" of a molecule, which in 3D chemistry
is no problem - the atom can "travel" around the third dimension) -
but is life on a cellular basis possible in 2D? Because you can build
no "tubes" without the cell falling into parts. Now I am not sure
about this, but somewhere I've read that this might be a big problem.
3. You (intentionally) did not model energy. Now for so a restricted
setting this will probably not make a big difference. But it is
possibly to model a realistic cell metabolism without energy?
Btw. I find the idea to create a "System X" as you call it very
interesting. You say do not know what properties System X should have.
Well I think it's probably very hard to manually create one (by
specifying a hard set of rules like your chemical reactions). But if
you can design some measure which rates the "quality" of a (physical/
chemical) System in the sense that it permits evolution, then you can
apply optimization methods (such as evolutionary algorithms, in fact).
This would include for example randomly "generating" a System (in the
case of OrganicBuilder, a set of random reaction rules), running the
System for a fixed time and measuring the "evolution-degree" (for
example: are there self- or reciprocal reproducing molecules? can an
increase in complexity of the molecules be observed? does the system
run into a "static" or oszillating state?) and then changing the
parameters as to maximize this measure. Just an idea I had.
My guess is that the biggest problem to design any artificial
evolutionary system on a atom/molecule level is computing power. The
real world is massively parallel in the sense that ALL N atoms
everywhere are subject to some forces and change there state
accordingly instantly. If you want to simulate this behaviour using a
standard CPU, you have to update every atom one after the other and
calculate their respective forces which should be O(N^2). I just
cannot imagine how this complexity can be significantly reduced.
P.S. the "size" and "distance" between the atoms in your molecule
should also influence the outcome. Sometimes atoms just don't "get
through". A possibility to set these parameters (and perhaps also the
other forces) in the GUI might be interesting.
Tim Hutton
> Now I've got a few questions about the "chemical background" (I will
> have to read your papers in detail, but I have a few fundamental
> questions):
> 1. Is the chemistry in your system really chemistry? I though
> chemistry describes the reaction of molecules.
> But all the rules in your system are on the level of atoms, which
> means every interaction of molecules has
> to be described on the atomic level. And there is no binding between
> molecules (like ionic bindings etc.), so to get complex structures you
> need very complex, big molecules, and very complicated rules.
The "atoms" in our artificial chemistry are very roughly analogous to
the proteins and lipids in natural chemistry. If you prefer something
closer to home then you're into the realm of computational chemistry
rather than artificial chemistry: there has been *lots* of work of
making simplified models. Have a look at:
http://en.wikipedia.org/wiki/Dissipative_particle_dynamics
http://en.wikipedia.org/wiki/Molecular_Dynamics
> 2. It is a 2D chemistry (that posed a problem for me in my playing
> around with the problem, since atoms
> can wind up on the "wrong side" of a molecule, which in 3D chemistry
> is no problem - the atom can "travel" around the third dimension) -
> but is life on a cellular basis possible in 2D? Because you can build
> no "tubes" without the cell falling into parts. Now I am not sure
> about this, but somewhere I've read that this might be a big problem.
There's a neat solution to Level 15 (Replicate) where the bonding side
problem is avoided - you can make the molecule symmetric each time so
it doesn't matter which side the atom bonds to.
But that aside, I agree with you that tubes would be nice. Although of
course tubes were a relatively late invention in evolutionary history
- the earlier lifeforms (I'm thinking polyps, stromatolites, medusae,
cnidarians in general) spat out their food the same way it went in. To
make use of a tube you need some way of propelling the contents:
peristalsis or similar. These are high levels of sophistication that
I'd love to see but I don't think we're anywhere near that level yet.
> 3. You (intentionally) did not model energy. Now for so a restricted
> setting this will probably not make a big difference. But it is
> possibly to model a realistic cell metabolism without energy?
Biology textbooks (and biologists) say that energy drives metabolism
but of course they're studying natural chemistry. I would say that our
artificial chemistries do include energy but implicitly: the inbuilt
system reactions only work one way. You can see this because in a
closed system self-replication will stop as everything gets gunked up
into a sticky mess. But with 'floods' there is a constant influx of
energy and replication can keep going forever.
> My guess is that the biggest problem to design any artificial
> evolutionary system on a atom/molecule level is computing power. The
> real world is massively parallel in the sense that ALL N atoms
> everywhere are subject to some forces and change there state
> accordingly instantly. If you want to simulate this behaviour using a
> standard CPU, you have to update every atom one after the other and
> calculate their respective forces which should be O(N^2). I just
> cannot imagine how this complexity can be significantly reduced.
Well there are some approximations that are commonly made. The links
above talk about a few.
Here's a further approximation:
http://people.reed.edu/~mab/publications/papers/bedauEA05.pdf
>
> P.S. the "size" and "distance" between the atoms in your molecule
> should also influence the outcome. Sometimes atoms just don't "get
> through". A possibility to set these parameters (and perhaps also the
> other forces) in the GUI might be interesting.
Yes, atoms could have different sizes and shapes and static charges
between them. It would be nice to have columnar lipids allowing small
molecules to migrate between them. Feel free to experiment!
Thanks for sharing your thoughts,
Tim Hutton
> On 10 April 2010 12:22, Julian Hoch <Julia...@web.de> wrote:
>> 2. It is a 2D chemistry (that posed a problem for me in my playing
>> around with the problem, since atoms
>> can wind up on the "wrong side" of a molecule, which in 3D chemistry
>> is no problem - the atom can "travel" around the third dimension) -
>> but is life on a cellular basis possible in 2D? Because you can build
>> no "tubes" without the cell falling into parts. Now I am not sure
>> about this, but somewhere I've read that this might be a big problem.
>
> There's a neat solution to Level 15 (Replicate) where the bonding side
> problem is avoided - you can make the molecule symmetric each time so
> it doesn't matter which side the atom bonds to.
>
> But that aside, I agree with you that tubes would be nice. Although of
> course tubes were a relatively late invention in evolutionary history
> - the earlier lifeforms (I'm thinking polyps, stromatolites, medusae,
> cnidarians in general) spat out their food the same way it went in. To
> make use of a tube you need some way of propelling the contents:
> peristalsis or similar. These are high levels of sophistication that
> I'd love to see but I don't think we're anywhere near that level yet.
Having had a think about this, I've changed my mind about what I've
written above. Simple tubes in cell membranes are useful without any
form of peristalsis or similar - they just restrict the size of the
particles that can passively flow through. And there's a simple route
to added sophistication by adding a physical door atom or atoms that
can be opened or closed on a chemical signal. None of that is possible
in 2D because of the need to make a complex mouth to allow ingestion
without breaking the cell membrane
Hmmm... So the next version of OB must be 3D, we think?
One nice advantage of 2D, apart from the speed, is that a simple loop
of atoms makes a membrane. In 3D you need a surface, which is much
harder to deal with directly; to stitch together and so on. Of course
in nature the lipids self-organize, so maybe we need that too (see the
static charges experiments on the mailing list).
Or is there something in between 2D loops and 3D lipids that would be
nice to work with? We could have a special atom type that made a 'long
bond' when bonded with another, allowing small particles through. But
it would be a bit of a hack.
Any ideas?
calcyman
> it's way better than C++, and so it's definitely a good option. But
> since you mentioned the complexity problem, C++ might perhaps be an
> alternative. I was thinking that it should be possible to parallelize
> the problem, and an implementation in GPGPU (e.g. in CUDA) might speed
> things up enormously. If you really want evolution, you want LOTS of
> instances, and a lot of speed.
If we plan to elevate Organic Builder to three dimensions, C++ is the
way to go. Otherwise, Java would still be barely adequate.
> And there is no binding between molecules (like ionic bindings etc.),
In 3D OB, it would be possible to have these things:
http://en.wikipedia.org/wiki/Mechanically-interlocked_molecular_architecture
In fact, in two dimensions there is still a way to do this, but it
isn't as
rigid as in three dimensions.
> Biology textbooks (and biologists) say that energy drives metabolism
> but of course they're studying natural chemistry. I would say that our
> artificial chemistries do include energy but implicitly: the inbuilt
> system reactions only work one way. You can see this because in a
> closed system self-replication will stop as everything gets gunked up
> into a sticky mess. But with 'floods' there is a constant influx of
> energy and replication can keep going forever.
There is a constant influx of energy in our biosphere, in the form of
solar rays. Even though the Sun's lifespan is finite, it is
sufficiently
long to appear (in the local scale of time) to be eternal. Indeed, for
life to flourish, we need a constant influx of free energy.
The atom-atom collisions can be evaluated in O(n log n) time. In
general,
everything that naively appears to require O(n²) time can usually be
done
in O(n log n ...) time using superior algorithms. For example, sorting
is
possible in O(n log n) time using von Neumann's merge sort, and
multiplication is possible in O(n log n log log n) time using the
Schonhage-
Strassen algorithm.
As for measuring the forces between atoms in the (simulated) universe,
usually atoms within a certain distance need to be considered, and
those at opposite sides of the universe have more negligable effects
than
floating-point round-off errors.
If you really want to make effects continuous, yet local, choose a
fast-
descending function like F = e^-d, where F is the force and d is the
distance between objects. Most natural phenomena exhibit an inverse-
square law, such as F = (d^-2), but bodies separated by huge distances
can still have significant effects on each other.
> 2. It is a 2D chemistry (that posed a problem for me in my playing
> around with the problem, since atoms
> can wind up on the "wrong side" of a molecule, which in 3D chemistry
> is no problem
I beg to differ. Chirality plays a significant role in (3D) chemistry,
and
cannot be avoided by adding more dimensions. The morning sickness
drug that caused mutations was due to molecules swapping chirality.
> >> but is life on a cellular basis possible in 2D? Because you can build
> >> no "tubes" without the cell falling into parts. Now I am not sure
> >> about this, but somewhere I've read that this might be a big problem.
Molecules can be absorbed and excreted by using a mechanism
similar to an airlock, which means that the cell is never completely
open.
> > There's a neat solution to Level 15 (Replicate) where the bonding side
> > problem is avoided - you can make the molecule symmetric each time so
> > it doesn't matter which side the atom bonds to.
>
> > But that aside, I agree with you that tubes would be nice. Although of
> > course tubes were a relatively late invention in evolutionary history
> > - the earlier lifeforms (I'm thinking polyps, stromatolites, medusae,
> > cnidarians in general) spat out their food the same way it went in. To
> > make use of a tube you need some way of propelling the contents:
> > peristalsis or similar. These are high levels of sophistication that
> > I'd love to see but I don't think we're anywhere near that level yet.
The molecules could be propelled across tubes by conveyor belts,
or villi.
> Having had a think about this, I've changed my mind about what I've
> written above. Simple tubes in cell membranes are useful without any
> form of peristalsis or similar - they just restrict the size of the
> particles that can passively flow through. And there's a simple route
> to added sophistication by adding a physical door atom or atoms that
> can be opened or closed on a chemical signal. None of that is possible
> in 2D because of the need to make a complex mouth to allow ingestion
> without breaking the cell membrane
As long as you have pairs of doors in an airlock system, it is
possible
to have doors open and close. Signals need not be chemical; they
could be electrical pulses travelling through bonded atoms, like in
Dave
Mann's solution to the 'Replicate' challenge.
> Hmmm... So the next version of OB must be 3D, we think?
That would be exciting! Do we have sufficient computational power to
simulate 3D systems yet?
> One nice advantage of 2D, apart from the speed, is that a simple loop
> of atoms makes a membrane.
Yes, that is a nice property, and one of the reasons that I like
Organic
Builder so much.
> In 3D you need a surface, which is much
> harder to deal with directly; to stitch together and so on. Of course
> in nature the lipids self-organize, so maybe we need that too (see the
> static charges experiments on the mailing list).
>
> Or is there something in between 2D loops and 3D lipids that would be
> nice to work with?
Between 2D and 3D you have multi-layer 2D, where there are several
parallel interacting layers. For example, most circuit boards are
double-
layer (one on each side of the PCB) to solve the crossover problem.
> We could have a special atom type that made a 'long
> bond' when bonded with another, allowing small particles through. But
> it would be a bit of a hack.
We don't need a special atom type -- the reactions could be modified
to allow both types of bond in OB. For example:
a1 + a1 => a1--a1
would be a longer bond than the ordinary:
a1 + a1 => a1a1
This shouldn't be too difficult to implement; maybe you could include
it in the next version of Organic Builder.