Sign in to follow this  
polyfrag

self-reproduction

Recommended Posts

I made a program where there's a bunch of flying orbs linked with lines to other orbs: http://i90.photobucket.com/albums/k276/krims2006/orbs.gif http://i90.photobucket.com/albums/k276/krims2006/orbs.gif http://i90.photobucket.com/albums/k276/krims2006/orbs.gif What I'm going to do with these orbs is to make them into a 3-dimensional representation of an algorithm. I will assign a certain function to each orb and its relation to other functions will be determined by its links. For example, here's a simple algorithm represented in C++:
a = 3 + 4;
In my 3d system I will break each of these pieces into orbs and link them in a tree form:
 
   (a)
    |
   (+)
  /   \
(3)   (4)
Once I've done this, I want to create a 3d algorithm that reproduces itself, so that the end result is like a biological cell reproducing itself. The problem is that I can't think of a way for how to implement this self-reproduction. I could make a function-orb that takes all the orbs nearby and reproduces them exactly, but that ruins the whole point of what I'm trying to do. And what I'm trying to do is to create a 3d evolving system where even the means by which the "organisms" reproduce can be mutated and evolved. So what I need is to break down self-reproduction into little steps that I will represent with orbs. I could store all the information on how to reconstruct an organism in some orbs, but then that is not really self-reproduction but having a really complex organism make smaller organisms... Is that understandable? It's very abstract, but I happen to have become interested in this sort of thing because I have a lot of free time to waste. :D So any ideas on how I can use very simple rules to create a self-reproducing organism in this 3d system?

Share this post


Link to post
Share on other sites
Here is a way that I've thought about how to do the self-reproduction:

There will be a section of the organism called the "reader" that will traverse through all the orbs in the organism, and send a command to a "copier" section to copy each orb with a link attached to the original (like an umbilical cord). The next phase is to copy all the links in the copied orbs the same way as they are linked in the original organism. The final step is to cut the "umbilical cords" and animate the new organism.

The problem with this is that it is too complicated. I tried for a long time to try to do a schematic of this organism on paper, but it was just mind-boggling trying to figure how to put it on paper.

Share this post


Link to post
Share on other sites
Reminds me of L-systems and Conway's Game of Life. Perhaps those can give you some inspiration. Both have a simple ruleset and especially the latter can result in very interesting situations.

Share this post


Link to post
Share on other sites
I'm a little confused about what exactly your problem is.

Are you asking:
"how do I create a copy of an arbitrary graph (collection of nodes and vertices)"; or,
"how do I make new functions from old functions that are still valid functions (given your constraints on your initial function space)"; or,
"what kinds of functions are functions of themselves"?

I'll try rereading your post a few more times to see if it helps... but perhaps you could give us a little more detail about the specific problem you have.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
You are evolving a genetic algorithm.
Quote:

The problem is that I can't think of a way for how to implement this self-reproduction. I could make a function-orb that takes all the orbs nearby and reproduces them exactly, but that ruins the whole point of what I'm trying to do. And what I'm trying to do is to create a 3d evolving system where even the means by which the "organisms" reproduce can be mutated and evolved.


You could specify a fitness function with orbs, then your orb tree will mutate until one of acceptable fitness is created.
Using this method you could mutate the mutators and the mutator mutator mutators, etc :)

Share this post


Link to post
Share on other sites
I'm not sure if I agree with the 3D space and orb methodology, but it is an interesting idea. I think you'll end up spending as much or more time managing the 3D simulation and lose computational power on the real question at hand. I'd be interested in the results, regardless.

You may get some good information from the following papers.


http://www.sq3.org.uk/papers/evselfreps.pdf

Hutton, T. J. (2002). "Evolvable self-replicating molecules in an artificial chemistry." Artificial Life 8: 341-356.




http://citeseer.comp.nus.edu.sg/cache/papers/cs/27414/http:zSzzSzcogprints.ecs.soton.ac.ukzSzarchivezSz00002888zSz01zSzNRC-44969.pdf/smith03selfreplicating.pdf

http://johnnyvon.sourceforge.net/applet/2.0/

Smith, A., P. Turney, et al. (2003). "Self-replicating machines in continuous space with virtual physics." Artif Life 9(1): 21-40.
(Very good paper showing that with the proper enabling environment and rules, you can get self-replication. The applet lets you see it in action.)



http://www.nature.com/nature/journal/v437/n7059/abs/437636a.html
Griffith, S., D. Goldwater, et al. (2005). "Robotics: self-replication from random parts." Nature 437(7059): 636. (Very similar to the work by Hutton, but these folks take it into the real world. Here, instead of simulating the process in a virtual world, they've done it with small robots on an air table. Excellent video under Supplementary info.)

Share this post


Link to post
Share on other sites
Thanks for the links, I'll take a look later.


Here is what is the problem I'm having: I don't know how to make a self-reproducing algorithm in my 3d system.

Before I know what functions I will assign to orbs, I have to know how it will reproduce itself, and then I will figure out what functions I need.

This self-reproducing algorithm has to read itself in 3D SPACE and reconstruct the exact same structure of orbs and links. So try to imagine this - it is an algorithm, represented in 3d network form, that is reproducing a copy of itself, while morphing and shape-shifting because of the things that it's doing.

That's a very complicated task... the concept is actually harder than how DNA reproduces itself because DNA holds information in an essentially straight line (even though it is in 3d space), meanwhile my 3d system is not even a tree but a complicated mesh of orbs and links.


What is the purpose of all this? I am not trying to find a solution to any problem, so I have no criteria for a fitness-evaluator. This project is purely for entertainment and thought-stimulation. I am creating an open-ended evolutionary system. The organisms will reproduce through their own means, and there will not be any system that selects which ones are the most fit, like in real life. Instead the selection of the fittest will emerge itself in the system. There will be a large but limited number of orbs in the system, and as more orbs are being requested through reproduction, older orbs will be removed. What will the results of this? I predict that at first evolution will favour those algorithms that are simpler and reproduce the fastest. And then I predict that there will emerge an algorithm that is more complicated than the first but will be faster at reproducing because it will be construct several copies of itself at once. And then I predict there will be a very simple, parasitic algorithm that will invade other algorithms (in 3d space) "rewire" them in a way so that the host algorithm is tricked into reading and reproducing the parasite algorithm instead of itself. But that's just fantasizing, and the real results will probably be much different from what I've predicted.

Share this post


Link to post
Share on other sites
I just got an idea from DNA - maybe a part of the algorithm will break off from the rest of the organism, and then copy this chunk that it's broken off of?

Mmmm... but then how do I get it to reproduce this piece that's broken off...



I need ANY working idea for how to make a self-reproducing 3d-mesh/algorithm/organism. Once it's working and reproducing, I can introduce random mutations into the system, and eventually it would create other ways of reproducing.... But I need a complete and simple idea. I've been racking my brain trying to figure this out.


I could have just made a text-based evolutionary system based on Core Wars where the algorithms are stored as a sequence of commands, but I don't want to because I want to be able to point to a part of the screen and say "Oh, that's a parasite, and its rewiring that organism there, and that organism over there looks like a mutation of the XZ-Alpha-3 type because it has that unique triangle-shaped array of orbs"...

Share this post


Link to post
Share on other sites
Hmm... this is just an idea that popped into a tired mind, probably inspired by the X-like shape of chromosomes, but why not create a double function, each half of which copies the other half as part of its functionality?

For that matter, why nit start with an algorithm that does nothing but reproduce itself with mutation, and let that evolve - you may find that other functions arise as it evolves.

Share this post


Link to post
Share on other sites
JohnnyVon is a self-reproducing system, but the problem is that once it has created the triangles there is nothing afterwards. And it's randomistic, the sticks just flow together and happen to connect, and this inevitably leads to this one shape. My thing is different because it uses purposeful algorithms to move, fit, and manipulate pieces in very precise ways, and I expect it will create results in the long-term that lead to more and more interesting variation and refinement.



Mmmmm... I think Thaumaturge gave me the right idea. :D I'll think about it some more and come back later.

Share this post


Link to post
Share on other sites
Quote:
Original post by polyfrag

The problem is that I can't think of a way for how to implement this self-reproduction. I could make a function-orb that takes all the orbs nearby and reproduces them exactly, but that ruins the whole point of what I'm trying to do. And what I'm trying to do is to create a 3d evolving system where even the means by which the "organisms" reproduce can be mutated and evolved.


Look into Genetic Algorithms. Also, Stochastic Beam Search may be of some use.

To tell you the truth though, I'm not sure exactly what you're trying to do.

Share this post


Link to post
Share on other sites
I think Thaumaturge's idea is a good one, however, I'm sure you're going to have problems strictly due to the combinatorics of the problem. In a simple case, consider what happens when you have 10 different "commands" or orb types available. The number of possible combinations goes up exponentially: all possible combinations of lenght 1 = 10, length 2 = 100, length 3 = 1000, length 4 = 10000, ... How long would you expect a self-reproducing piece to be? Length 10, which is not too long if you consider the micro-programming pieces, gives you 10^10 possible combinations.

My point is, if you start with something that is capable of self-reproduction that is even of trivial size, the combinatorics create a situation in which random variation through mutation is not tractable. Add to this random variation of the underlying rules by which components interact and you amplify the problem space even further.

As for JohnnyVon, I don't think you looked at the demos. JohnnyVon 1.0 deals with triangles and essentially is related to self-assembly or polymerization. JohnnyVon 2.0 shows a linear self-reproducing structure that does not lead to polymerizing triangles. Also, the other references I pointed you to are linear self-reproducing structures. All of those are within a 2D environment, but the concepts are fully transferable to 3D.

I don't mean to come across negative, but I honestly think you need to re-evaluate the complexity of the problem you're trying to address and simplify your approach.

Share this post


Link to post
Share on other sites
Quote:
Original post by polyfrag
The organisms will reproduce through their own means, and there will not be any system that selects which ones are the most fit, like in real life. Instead the selection of the fittest will emerge itself in the system.


Think about what you just said. There has to be a fitness-factor. Without one, the simulation will be pure chaos and no pattern will emerge.

Now, whether or not the fitness factor is defined implicitly or explicitly is another matter.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
sounds like your question here is:
what is a good function/criteria to let orb networks create copies of themselves, which contains enough hidden factors so that copying favorability would be chaotic yet deterministic, hopefully leading to emergent patterns with the type of orb nets that survive...?

is that kinda what you want?



I would say... first of all, in addition to the orbs that are forming networks, you need some kind of 'resource' for those nets to compete for, how about free-orbs that are unconnected are randomly created and let to drift?
Resource would of course be needed in order for a net to copy itself

you might also allow more direct competition... how about (resource scarcity aside) you let networks steal orbs from each other? youll need factors here to decide success... size? age? number of bonds that would be formed to the stolen orb in one net versus the other?

you'll also need to allow some kind of room for mutation... perhaps network copying is done on a highly local scale with no checksum - each orb in the net grabs a 'resource' copy of himself and tries to inform his neighbors so they can 'get their kids together'
or maybe no neightbor comm. at all, might just bond based on proximity...

and of course you'll need some kind of Order in the system... some kind of rules for type of orb and what they can or cannot bond with...


ohwell, im no expert... but my laymans knowledge tells me that the kind of chaotic emergent behaviour you want needs to come from a balancing of opposing factors...

Share this post


Link to post
Share on other sites
Yes, I meant that the fitness criteria would be IMPLICIT, like in real life. There won't be a magical hand that picks which organisms that are the fittest and allows only those to reproduce. Instead, all older organisms will die away with time, and newer organisms will reproduce as much as they can.




Yes, I know combinatorics can be a problem. I can fit it under 10 pieces since I'm making the functions.




Share this post


Link to post
Share on other sites
I think maybe the problem I'm having is that I've been thinking about this for too long, and I can only focus on details right now without a sense of the whole thing. I need a fresh mind for this...

Share this post


Link to post
Share on other sites
Not an easy topic to consider. It sounds straight forward at first, but then when you dig into the details, it reveals itself to be amazingly complex.

Here's another paper that I read this morning:

http://www.ecal2005.org/workshopsCD/artificialchemistry/Salzberg.pdf
A Graph-based Reflexive Artificial Chemistry. Chris Salzberg 2005

Very interesting concept based upon a finite state machine. Usually we thing of the states of the FSM and the rules of their transitions as being different. Here, the property of reflexivity is introduced such that the transition rules and the states are from the same space. This allows us to modify not only the structures within the space of interest but the rules of their transitions/modifications.

I think this strikes at the essence of your problem. You can define each orb as an independent fuction or value, but how do they affect each other within this space? How do the interact and lead to modifications? More difficult is the question of how do we modify the underlying rules by which they interact with each other? This paper tries to address that very issue. Is it useful? Not sure. I haven't seen the follow up paper in which they do the computational analysis.

Share this post


Link to post
Share on other sites
Quote:
Original post by polyfrag
Yes, I meant that the fitness criteria would be IMPLICIT, like in real life. There won't be a magical hand that picks which organisms that are the fittest and allows only those to reproduce. Instead, all older organisms will die away with time, and newer organisms will reproduce as much as they can.




Yes, I know combinatorics can be a problem. I can fit it under 10 pieces since I'm making the functions.


The answer to your problem is found in the following:

http://en.wikipedia.org/wiki/Stochastic
http://en.wikipedia.org/wiki/Genetic_algorithm
http://en.wikipedia.org/wiki/Simulated_annealing

Share this post


Link to post
Share on other sites
I'm actually having kind of a similar problem.

I have a neural network (NN) that controls a ragdoll. The NN is modified using a genetic algorithm (GA). The fitness function of the GA determins how the ragdoll moves.

For instance, if the fitness function only rewards forwards torso movement without taking any other measures into consideration, the NN evolves so that the ragdoll crawls along the ground. It will more or less use any of it's appendages in any way it can to generate forward movement.

Now, if I add to that fitness function the stipulation that the head be kept above a certain hight, and that the center of the torso be in certainly alignment with the head (so that he's not diving through the air), then somewhat "normal" walking is generated. Although, in most cases, it's seems to turn out as hopping with a controlled fall.

The problem here is, how does one determine the best fitness function? Well, this requires a lot of thought into exactly what one is trying to accomplish. If one's goals are vague, then one will have trouble coming up with a good fitness function. If you are certain on the outcome you are trying to achieve, then a sort of layered fitness function may be best. For example, you have a fitness function


Fitness = (torsoDistance * weightA) + (skullStability * WeightB) - (energyConsumption * weightC); //


We know that we are taking torsoDistance, skullStability, and energyConsumption into consideration. But which one is more important? This is where the weights come in. You can run a GA on top of this one to determine which weight proportions are the best.

Share this post


Link to post
Share on other sites
i didnt read all the replies, so excuse me if I repeat something

but it seems like this is a simple tree structure, just find two nearby orbs, combine the two together in a way that makes your root orb. . .

i.e. the "a" orb is formed by combining (i.e. +) your "3" and "4" orbs together

hope that helps

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Hi, just noticed the post above referencing a paper I wrote (A Graph-based Reflexive Artificial Chemistry). the follow-up (which demonstrates some interesting results), you can find here:

http://sacral.c.u-tokyo.ac.jp/~chris/pubs/alife10.pdf

All other papers I've written are posted here:

http://sacral.c.u-tokyo.ac.jp/~chris/?CV

I won't check this page again, most probably (just stumbled on it). if you have questions just email me (see my webpage above).

Chris

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this