Sign in to follow this  
shadowisadog

Genetics

Recommended Posts

Hi, I wanted to start a bit of a discussion on the application/approach behind modeling DNA mutation based on simple physical law. IE What would happen if you had a random set of DNA, mutated it randomly and applied the process of natural selection to it? I think I would go about this by starting with a random set of numbers (most likely an array), and have a mutate/live methods. In the mutate method a strand would get altered and in the live method it would basically get subjected to some simple physical laws (constraints to determine evolution). Then based on some formulas the information contained in the DNA would get drawn to the screen (IE two of the numbers could be used for something like the color of the creatures skin)... I want to see how other people would start to approach this situtation :). Atleast it could make for an intresting screensaver heh.

Share this post


Link to post
Share on other sites
I had to read your post two times before I understood what you really meant. You could have said it in a simpler way, methinks... like this:

"How would you design a screensaver-ish program to display natural selection & evolution based on completely random numbers?"

This is pretty much what I'm trying to do myself as a hobby project. I haven't gotten it to work yet - I just started two weeks ago. Got a few more days to go.

Anyway, my basic approach is:
Give the creatures some abilities, such as biting and depositing scent traces, turn left and so on. On the map there's minerals and water and so on. The creatures die if left without energy, and collecting minerals allow new creatures to be spawned by their hive.
Six different DNA's are randomized. A colony of 10 creatures are spawned for each type of DNA. Thus there's six colonies on the map.
Initially their behaviour is completely random;

"If monster to the right and dead body behind and i'm hungry then turn left."

Since I know what is needed to be successful, I hand out points to the DNA which accomplishes that.

"If (collected_water) then score += 100;"

After a period of time, I freeze the action. The 2 DNA's with the most score get saved, the rest get deleted. These two are cross-bred and randomized to create four new ones. Thus they are six again, and a new contest can start.

Share this post


Link to post
Share on other sites
I seperated this into two posts to clearly define the difference.

This is how I think a more interesting solution would be:

2 stages of evolution taking place at the same time. Two seperate simulations.
The first is a simulation where different random parts are joined together and given random guides on how to move around. It tries to evolve the best way to move around.
The second is a simulation where the developed moving technique is strapped to a creature. The creature is given random bodyparts with random usage-guides. It tries to evolve the best way to survive (there's food lying about).

To make it more interesting, have several of these threads running at the same time - each with different random seeds. Then pit them in the same valley and see what they figure out to do with eachother.


Oh crap... I got way too ambitious. This would be quite a big undertaking. I'll came back to you when I figured out something actually DO-ABLE.
Latersssss.......!

Share this post


Link to post
Share on other sites
I think the most interesting (yet do-able) way would be to evolve ways of accomplishing a single, yet very complex task.

Another guy on this forum made a program which evolved ways for an arm to move in order to throw a ball as far as possible. A more interesting program would be to join random legs- & feet-type extremites together in a physics enviroment, with a random way to move them.

Award score by how far they managed to move in a given time period, and evolve with the system I'm currently using (described above). This could very easily be presented on the screen, and also be interesting.

I've seen programs which do this before, but they have a vital point which is flawed.
- The creatures have no senses. Their movement are based on timers ONLY.

Thus their movement would not work with a different gravity setting, or in real life at all.

In order for interesting (and WORKING) ways of movement to be evolved, the creature need to be strapped with senses. A sense of balance, a acceleration-sense and a body-sense. The body-sense tells the AI where it can feel it's limbs are at the moment (my left leg is bent really far).

THAT should make for an interesting simulation. I feel like constructing it myelf.

Share this post


Link to post
Share on other sites
I actually just started working on a little system for genetic algorithms on neural nets yesterday. Right now I'm running a very simple survival test where blocks fall from the top of the screen and the ai can move only left and right. When one of the ai blocks is hit it dies instantly and its slot is replaced by a breeding of the 2 oldest ai on the board with a small mutation. I would like to really put my AI system to the test, but I can't seem to think of any good enviroment for it either.

What would be nice would be to combine trial and error learning with genetic algorithms so the AI can learn while they are alive and pass there knowledge to their descendents. AI that run in colonies and compete would be good too, but what system could be done where the AI try to do something interesting and actually succeed sometimes?

I think you were all talking about more statistics on creatures than AI, but I think AI that evolves is just more interesting to watch.

Share this post


Link to post
Share on other sites
Well my system I am more intrested in evolving how a character looks then how smart it is.

I was thinking of making a creature composed of many simple cell units each with it's own DNA, any mutations would get passed on through cell division.

I still haven't worked it all out yet though...

About your system, a friend of mine once applied a neruel network to a simple problem which was trying to get a little dot to stay on the screen for the longest possible time. The neruel network could alter the x or y axis (It made curved lines heh). I believe it used a combination of genetics with neruel networks to train the network, it would use the last longest time neruel network configuration and pass it to the offspring but it would be mutated slightly. If the mutation resulted in a longer time on the screen, then the new neruel configuration would be passed to the next generation. Otherwise the last longest time would be passed on and mutated again :). Eventually this would result in a smarter and smarter dot that could stay on screen for a very long time ;).

Some problems with this though are that the dot can not be allowed to really directly alter the speed (my friend tried this and the creature learned to just stand still or go very slowly ;) so he had to correct it).

It was quite cool, I think you would be best to try something like that ;).

Share this post


Link to post
Share on other sites
Quote:
Original post by shadowisadog
Well my system I am more intrested in evolving how a character looks then how smart it is.

I was thinking of making a creature composed of many simple cell units each with it's own DNA, any mutations would get passed on through cell division.

I still haven't worked it all out yet though...

About your system, a friend of mine once applied a neruel network to a simple problem which was trying to get a little dot to stay on the screen for the longest possible time. The neruel network could alter the x or y axis (It made curved lines heh). I believe it used a combination of genetics with neruel networks to train the network, it would use the last longest time neruel network configuration and pass it to the offspring but it would be mutated slightly. If the mutation resulted in a longer time on the screen, then the new neruel configuration would be passed to the next generation. Otherwise the last longest time would be passed on and mutated again :). Eventually this would result in a smarter and smarter dot that could stay on screen for a very long time ;).

Some problems with this though are that the dot can not be allowed to really directly alter the speed (my friend tried this and the creature learned to just stand still or go very slowly ;) so he had to correct it).

It was quite cool, I think you would be best to try something like that ;).


How exactly was he training the dot to do that? Did it just have a set of consecutive instructions to carry out, like "move x 5", "move x 5 y 10" and so on, and carry them out like that? Or what? That sounds like something I'd like to try. I'm interested in this kind of AI (genetic algorithms and NNs) just because I like the concept and the subject fascinates me, not neccessarily because they are very useful in most games. Let me know, thanks!

Share this post


Link to post
Share on other sites
Well I can't say I know what he did, but if I were trying to make a neural net for that scenerio I would have 2 input nodes to give the current x and y and 1 output node for the angle to travel at. Then I would create a lot of ai objects say 50 or 200 at random and let them each run until they went off the screen(aka died). Then I would replace the newly emptied slots with ai breeded from the oldest ai left on the screen. As you repreat the process the ai will get better and better. A similar process could be used on non ai based systems too, but usually atleast some type of ai(not necessarily learning) would be needed.

More on the initial topic: The first program I ever wrote with genetic algorithms was a simple A-life type program. I had a bunch of ai entities that all had 8 chromozones(8 seemed like a good number at the time). Each chromozone had a number for its effect on stats. The stats were speed, (closeness to detect food), (closeness to detect mates), and (closeness to detect predators). The ai could die from old age, starving, or being cuaght by a predator. The ai was very simple, run away from predator, run to food, run to mate if over certain size and age, and if no stimuli move at random. If 2 ai that were both over certain age and size(based on food eaten) collided then a new ai was created where each chromozone was selected at random from either parent. My final program was not very interesting to watch becuase it was drawn in a bunch of colored squares and it was very hard to tell what was going on at any given time. If my experiment were redone with fancier graphics and possibly some enviromental factors other than predators and food it might make quite a nice screensaver.

Share this post


Link to post
Share on other sites
Quote:
Original post by Alrecenk
Well I can't say I know what he did, but if I were trying to make a neural net for that scenerio I would have 2 input nodes to give the current x and y and 1 output node for the angle to travel at. Then I would create a lot of ai objects say 50 or 200 at random and let them each run until they went off the screen(aka died). Then I would replace the newly emptied slots with ai breeded from the oldest ai left on the screen. As you repreat the process the ai will get better and better. A similar process could be used on non ai based systems too, but usually atleast some type of ai(not necessarily learning) would be needed.


Sorry for derailing the thread, but I just wanted to know what kind of a process would go on internally to make it determine the angle. It seems like you would have to hardcode the formula used to determine the angle, and just have the inputs change the result of the formula, while allowing some numerical parameters to "evolve".

Share this post


Link to post
Share on other sites
I wanted to make sure I knew what I was talking about before I explained this more so I wrote the program. The neural determines the angle and handles the formula. When you evolve the neural net you are effectivly evolving the formula. And here are some specifics of my program for those who might want to know: inputs (x,y,current age), outputs (angle). There are 150 networks of 12 nodes running at a time.

This was a pretty cool test, but it seems a little too easy. Just in the time of me writing this post I got an ai to survive for 132544 frames. The record on my dodging test so far has only been 35000.

Share this post


Link to post
Share on other sites
Quote:
Original post by Alrecenk
I wanted to make sure I knew what I was talking about before I explained this more so I wrote the program. The neural determines the angle and handles the formula. When you evolve the neural net you are effectivly evolving the formula. And here are some specifics of my program for those who might want to know: inputs (x,y,current age), outputs (angle). There are 150 networks of 12 nodes running at a time.

This was a pretty cool test, but it seems a little too easy. Just in the time of me writing this post I got an ai to survive for 132544 frames. The record on my dodging test so far has only been 35000.


I actually did something similar last night, but in a much more simplified way. It was just a simple genetic algorithm, where fitness was determined by how long it stayed on the screen and the factor that "evolved" was the angle that the dots launched from. It worked =) However, I'm going to check out your app so I can see what yours looks like visually. Thanks.

EDIT: Let's move this discussion to another thread if we're going to continue it =) Your program is a lot more interesting than mine. That's what always mystifies me... how you prevent yourself from having to hardcode the formula. I would be curious to know what you did. It might help my understanding. Thanks for the app.

Share this post


Link to post
Share on other sites
Don't have time to write much, but a 'classic' AI problem to try out genetics/neural nets is the many variants of the pole balancing idea. The idea is that you have a pole on a cart - the AI component can move the cart backwards and forwards (1D) and sense the poles angle and angular velocity - the net has to see how long it can keep the pole balanced. More advanced versions include limits on the amount of space avaliable to the cart, multiple poles to balance and no velocity information. If you google ('pole balancing problem' works.) it you will find the precise definitions of the problem. Needless to say AI researchers arn't concerned with solving the problem - they can keep it going for as long as they want, there concerned with how quickly they can evolve a solution...

Share this post


Link to post
Share on other sites
Hi,

You might be interested in checking out an old program called DancerDNA, which was released many years ago by an old company (now out of business) I used to work for.

You can find some info and demo versions here dancerDNA, and i'm sure with some more searching you could find more info.

Its been a long time since i looked at it, but i'm pretty sure you can read the 'dna' files of each 'creature' and that might give you some idea how to approach programming a similar application.

Another area you might want to investigate first is L-Systems, which have been used extensively for modelling reallife elements such as plants but can create interesting geometrical shapes as well.

Finally some of the work by Richard Dawkins, (the Blind Watchmaker) and his Biomorph software might also be of interest.


Overall from your first post I would say that you'd want to move away from using simple DNA blocks/random set of numbers (similar to how L-systems work - where a character represents a function) towards actual code blocks for functions. This allows you to mutate that actual code blocks or more precisly the variables/elements within a code block. As this gives far greater scope for mutations. Check out the dancerDNA creature code to see what I mean (open them in wordpad or notepad)

Of course for starting out an L-system method might be the perfect introduction, certainly it could achieve the aims of your first post.

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