FREE TAPATALK APP

Mitchell314 · 4th February 2009, 06:32 PM

I've been doing a little studying into genetic algorithms (GA) computer simulations. And yet I haven't seen the "information" of members within a tested population to be interpreted as computer instructions. Why? Well, why not have an open ended system where new "traits" (more like the image of traits) may appear, existing "traits" may change their own interpretations, etc.?

Now, being an eternally curious computer geek, I tried to make my own instruction based GA systems. The actual interpreter function (yes, I put this into this forum* on purpose) was fairly simply to make. But the problem that arises is that there is much more burden put onto the specific application to make things "connect." My current schedule hasn't been very forgiving, so I haven't had much progress this semester (I started working on GAs last semester).

Your thoughts?

*I thought about putting this in the computer forum, but I changed my mind since this is a cross-disciple topic.

INRM · 4th February 2009, 06:50 PM

What's a Genetic Algorithm simulation?

INRM

NewtonTrino · 4th February 2009, 07:00 PM

There is plenty of opportunity for this kind of stuff. I have put some thought into it but it's not exactly on my life schedule to work on it anytime soon.

If you take a look at something like corewars it might give you some ideas though.

Mitchell314 · 4th February 2009, 07:10 PM

A genetic algorithm is a way to simulate natural selection to solve a problem. I'm going informal, because it is a little hard to define.

Lets say you want the computer to make an efficient engine design. You could create a bunch of different random models, which would mostly be inefficient. You do a simulation on the different models, and rank which does best (most power output per fuel consumed or something). Then "sexually" or "asexually" reproduce the ones that did comparatively better, and "kill" the worst. Maybe mutate one. So some part represented by bit pattern 0111 becomes 0110 if mutated, which'll do something like move it or make it bigger. Repeat, and you should get a good engine design.

That's sort of like genetic algorithms, but it can be applied to many other problems. I might have explained it poorely, but the point is:
a) You have a problem
b) You create a population of randomly seeded members
c) The members represent a way to solve the problem
d) Evaluate the members (test 'em)
e) do natural selection stuff on population
f) Loop back to d until convergence is detected (all the engines become roughly the same)

So the engine example:
a) make an efficient engine
b) simulate a bunch of engines
c) an engine member is composed of varying parts. Like one may have a large shaft, and another could have a smaller one
d) Run physical simulations, find most efficient
e) stuff
f) Run until all the engines look the same and/or operate sufficiently efficient.

roger · 4th February 2009, 08:04 PM

I may have misunderstood your question, but instruction based genetic algorithms are called genetic programming. John Koza has written several books on the subject, and there is of course lots of papers in the literature.

Dr. Trintignant · 4th February 2009, 08:21 PM

I've written an instruction-based GA simulator to evolve little creatures that run around and eat. I think the key is to create a "robust" instruction set that works even when the instructions are mutated or arbitrarily reordered. I used a stack-based memory, for example, which is fairly robust in this way, since it doesn't matter where on the stack you are to begin with. In fact, none of my instructions had arguments: "mul" just popped off the top two stack elements and pushed the result, "dup" duplicated the top element, "skipifnv" skipped the next instruction if the top element was non-zero, etc. Every possible sequence of instructions was a valid program. The stack was circular as well, which meant that superfluous instructions were often harmless.

- Dr. Trintignant

Dr Adequate · 4th February 2009, 08:49 PM

Originally Posted by Mitchell314

I've been doing a little studying into genetic algorithms (GA) computer simulations. And yet I haven't seen the "information" of members within a tested population to be interpreted as computer instructions.

You mean stuff like Tierra.

INRM · 5th February 2009, 09:19 AM

This stuff,

How detailed is the simulation? Do the creatures have their own brains and think for themselves?

If so there are some ethical issues you should consider

INRM

Dymanic · 5th February 2009, 09:26 AM

Originally Posted by INRM

How detailed is the simulation? Do the creatures have their own brains and think for themselves?

I've done a bit of the same sort of thing. My virtual creatures do not merely have their own brains; they have souls.

Well, you can't prove that they don't.

drkitten · 5th February 2009, 09:37 AM

Originally Posted by INRM

If so there are some ethical issues you should consider

... starting with the ethics of spewing complete horse manure on the JREF forum, INRM?

Dymanic · 5th February 2009, 10:05 AM

Originally Posted by Mitchell314

Well, why not have an open ended system where new "traits" (more like the image of traits) may appear, existing "traits" may change their own interpretations, etc.?

Uh... well, how about because doing that would basically involve creating an entire virtual world, with astronomical numbers of elements interacting more or less simultaneously; and in which everything happened implicitly, as natural consequences of those interactions; and even if you had the time and the system resources to dedicate to the effort, the complexity of all that would render most of the activity incomprehensible anyway?

Mitchell314 · 5th February 2009, 03:25 PM

Originally Posted by roger

I may have misunderstood your question, but instruction based genetic algorithms are called genetic programming. John Koza has written several books on the subject, and there is of course lots of papers in the literature.

I've hear of that term before, but I just assumed it to be a synonym for GA. Now that I know..

Originally Posted by Dr. Trintignant

I've written an instruction-based GA simulator to evolve little creatures that run around and eat. I think the key is to create a "robust" instruction set that works even when the instructions are mutated or arbitrarily reordered. I used a stack-based memory, for example, which is fairly robust in this way, since it doesn't matter where on the stack you are to begin with. In fact, none of my instructions had arguments: "mul" just popped off the top two stack elements and pushed the result, "dup" duplicated the top element, "skipifnv" skipped the next instruction if the top element was non-zero, etc. Every possible sequence of instructions was a valid program. The stack was circular as well, which meant that superfluous instructions were often harmless.

That's what I was talking about, although each "cell" was given 16 addressable 2-byte variables, because my current system is 12 bit (4 bit instruction, 4 bit argument1, 4 bit argument2).

Originally Posted by Dr Adequate

You mean stuff like Tierra.

Neat find

Originally Posted by INRM

This stuff,

How detailed is the simulation? Do the creatures have their own brains and think for themselves?

If so there are some ethical issues you should consider

But their ribs are most succulent! But seriously, no brains. By creature/cell, we mean more or less an interpretation of segments of memory. For me, it's a string of a couple instructions and some variables.

Originally Posted by Dynamic

...the complexity of all that would render most of the activity incomprehensible anyway?

Who said anything had to be comprehensible?

Dymanic · 5th February 2009, 05:04 PM

Originally Posted by Mitchell314

Who said anything had to be comprehensible?

Well, if incomprehensible complexity does it for you, that's easy enough to obtain. I've seen some nice little programs that achieved it with just a few lines of code. I've done it myself, without even trying (in fact, even when I was trying not to. You could always just head out to the garden with a magnifying glass (or maybe pick up a book on postmodernism). But if the point of the exercise is to learn (or be entertained) by creating a model, it's nice to have results that can be interpreted, or visualized, or something. Plus, it makes it a lot easier to debug.

Mitchell314 · 5th February 2009, 05:30 PM

Originally Posted by Dymanic

Well, if incomprehensible complexity does it for you, that's easy enough to obtain. I've seen some nice little programs that achieved it with just a few lines of code. I've done it myself, without even trying (in fact, even when I was trying not to. You could always just head out to the garden with a magnifying glass (or maybe pick up a book on postmodernism). But if the point of the exercise is to learn (or be entertained) by creating a model, it's nice to have results that can be interpreted, or visualized, or something. Plus, it makes it a lot easier to debug.

I was just joking. I did a simple GA path finding test where you could watch the little bugs run about and eventually learn to get to the objects very quickly. I've got the results on an Excel worksheet somewhere. Surprisingly, the 'learning curve' was modeled to a 5th degree polynomial with an R² value around .6 .

As for the genetic programming, I'm having ... technical issues (memory leak, but I wasn't allocating anything

). But it's looking promising, especially when the program was learning to cut off most of it's traveling. Instead of the usual randomize the cells, I put in a very inefficient (When dealing with hex code, it's not my fault I couldn't optimize. F03443A55 is hard to transcribe) method for the same path finding problem: Go down the whole screen, go right a pixel, go up the whole screen, go right a pixel, go down, etc until all three objectives were touched. Success was touching all three objectives (100*100 squares) first. When I tested it, first, every few generations would clip off a couple of iterations to complete. Then it got clever and decided to "bar code" the map; taking out a quarter of the iterations to complete. Then every few generations took out large chunks of iterations (my method was around 1,001,000 iterations). Eventually it got to 500,000 iteration, then the memory leak pretty much drained the computer to the point where I had to quite.

But it was really fun to watch when it did work. I changed the code around so that it wouldn't leak (I think it was an issue with strings being used in UDTs, this was in a BASIC variant). But now it won't work at all (it doesn't move or turn). The GP implementation was much superior to the simpler model that just had two important genes specified by me: jump how many pixels and turn how often (random mostly). To those who never have seen a genetic algorithm or genetic program in action, it is something to watch. I may be biased since I'm a geek, but there is some entertainment - and awe - of watching an AI start from a low "dumb" level and learn over time then become intelligent, and even creative!

Dymanic · 5th February 2009, 09:35 PM

I did a sort of expanded version of the classic game "snake", where the critters (I called them "worms") went around looking for food, getting longer if they found it, and shorter (and eventually dying) if they didn't, and breeding only when they reached a certain maximum length (one of about twenty "genetic" characteristics). Each one had a list of colors it could eat, and though there was a population of virtual plants to provide food, they could also eat other worms, as long as the color was on their list.

One of the things I was interested in at the time was r/K selection. (In biology, elephants, and humans, are K-selected; they produce few offspring and invest a lot in each one -- whereas oysters are r-selected; a single one can produce millions of offspring each year, but only a few survive.)

In my little simulation, everything came at a cost. Offspring with, say, good vision, required a longer developmental time, expressed as a longer max length. Short-tails could breed fast, but they also died off quicker when food got scarce, and since they were at a disadvantage when it came to finding food in the first place, they could really thrive only when it was especially plentiful. So that worked. A lot of times, the whole population would die, usually after the worms had gobbled up all the plants. I took that as a sign that I had created a decent model.

Thing is, early on, I would check in after an all-night run and find that the whole sim had somehow bogged down. There would be these big globs of mostly a single color, or maybe two, and nothing else. It kept happening on run after run, and for a while, I thought it was a bug. I was quite tickled when I figured it out: I had neglected to outlaw cannibalism. What I was looking at was clusters of symbiotic worms, feeding off of each other and their own offspring.

They figured that out before I did.

4th February 2009, 06:32 PM	#1
Mitchell314 Critical Thinker Join Date: Jun 2008 Location: NC, US Posts: 299	An inqury into the matters of Genetic Algorithms I've been doing a little studying into genetic algorithms (GA) computer simulations. And yet I haven't seen the "information" of members within a tested population to be interpreted as computer instructions. Why? Well, why not have an open ended system where new "traits" (more like the image of traits) may appear, existing "traits" may change their own interpretations, etc.? Now, being an eternally curious computer geek, I tried to make my own instruction based GA systems. The actual interpreter function (yes, I put this into this forum* on purpose) was fairly simply to make. But the problem that arises is that there is much more burden put onto the specific application to make things "connect." My current schedule hasn't been very forgiving, so I haven't had much progress this semester (I started working on GAs last semester). Your thoughts? *I thought about putting this in the computer forum, but I changed my mind since this is a cross-disciple topic.
	__________________ - "It's pronounced 'pea-can', man." Lapis Sells . . . But Who's Buying?

4th February 2009, 06:50 PM	#2
INRM Philosopher Join Date: Jul 2002 Posts: 5,490	What's a Genetic Algorithm simulation? INRM
INRM Philosopher Join Date: Jul 2002 Posts: 5,490

4th February 2009, 07:10 PM	#4
Mitchell314 Critical Thinker Join Date: Jun 2008 Location: NC, US Posts: 299	A genetic algorithm is a way to simulate natural selection to solve a problem. I'm going informal, because it is a little hard to define. Lets say you want the computer to make an efficient engine design. You could create a bunch of different random models, which would mostly be inefficient. You do a simulation on the different models, and rank which does best (most power output per fuel consumed or something). Then "sexually" or "asexually" reproduce the ones that did comparatively better, and "kill" the worst. Maybe mutate one. So some part represented by bit pattern 0111 becomes 0110 if mutated, which'll do something like move it or make it bigger. Repeat, and you should get a good engine design. That's sort of like genetic algorithms, but it can be applied to many other problems. I might have explained it poorely, but the point is: a) You have a problem b) You create a population of randomly seeded members c) The members represent a way to solve the problem d) Evaluate the members (test 'em) e) do natural selection stuff on population f) Loop back to d until convergence is detected (all the engines become roughly the same) So the engine example: a) make an efficient engine b) simulate a bunch of engines c) an engine member is composed of varying parts. Like one may have a large shaft, and another could have a smaller one d) Run physical simulations, find most efficient e) stuff f) Run until all the engines look the same and/or operate sufficiently efficient.
	__________________ - "It's pronounced 'pea-can', man." Lapis Sells . . . But Who's Buying?

4th February 2009, 08:04 PM	#5
roger Penultimate Amazing Join Date: May 2002 Location: Mountain View, CA Posts: 11,062	I may have misunderstood your question, but instruction based genetic algorithms are called genetic programming. John Koza has written several books on the subject, and there is of course lots of papers in the literature.
	__________________ May your trails be crooked, winding, lonesome, dangerous, leading to the most amazing view. May your mountains rise into and above the clouds. - Edward Abbey Climb the mountains and get their good tidings. Nature's peace will flow into you as sunshine flows into trees. The winds will blow their own freshness into you, and the storms their energy, while cares will drop off like autumn leaves. - John Muir

4th February 2009, 08:21 PM	#6
Dr. Trintignant Muse Join Date: Mar 2007 Posts: 745	I've written an instruction-based GA simulator to evolve little creatures that run around and eat. I think the key is to create a "robust" instruction set that works even when the instructions are mutated or arbitrarily reordered. I used a stack-based memory, for example, which is fairly robust in this way, since it doesn't matter where on the stack you are to begin with. In fact, none of my instructions had arguments: "mul" just popped off the top two stack elements and pushed the result, "dup" duplicated the top element, "skipifnv" skipped the next instruction if the top element was non-zero, etc. Every possible sequence of instructions was a valid program. The stack was circular as well, which meant that superfluous instructions were often harmless. - Dr. Trintignant
Dr. Trintignant Muse Join Date: Mar 2007 Posts: 745

4th February 2009, 07:00 PM	#3
NewtonTrino Illuminator Join Date: Jul 2007 Location: Bothell, WA Posts: 3,803	There is plenty of opportunity for this kind of stuff. I have put some thought into it but it's not exactly on my life schedule to work on it anytime soon. If you take a look at something like corewars it might give you some ideas though.

4th February 2009, 08:49 PM	#7
Dr Adequate Banned Join Date: Aug 2004 Location: Waiting Long Enough By The River Posts: 17,897	Originally Posted by Mitchell314 I've been doing a little studying into genetic algorithms (GA) computer simulations. And yet I haven't seen the "information" of members within a tested population to be interpreted as computer instructions. You mean stuff like Tierra.

5th February 2009, 09:19 AM	#8
INRM Philosopher Join Date: Jul 2002 Posts: 5,490	This stuff, How detailed is the simulation? Do the creatures have their own brains and think for themselves? If so there are some ethical issues you should consider INRM
INRM Philosopher Join Date: Jul 2002 Posts: 5,490

5th February 2009, 09:26 AM	#9
Dymanic Illuminator Join Date: Sep 2002 Posts: 4,809	Originally Posted by INRM How detailed is the simulation? Do the creatures have their own brains and think for themselves? I've done a bit of the same sort of thing. My virtual creatures do not merely have their own brains; they have souls. Well, you can't prove that they don't.
Dymanic Illuminator Join Date: Sep 2002 Posts: 4,809

5th February 2009, 09:37 AM	#10
drkitten Penultimate Amazing Join Date: Mar 2004 Location: Wits' End Posts: 21,647	Originally Posted by INRM If so there are some ethical issues you should consider ... starting with the ethics of spewing complete horse manure on the JREF forum, INRM?

5th February 2009, 10:05 AM	#11
Dymanic Illuminator Join Date: Sep 2002 Posts: 4,809	Originally Posted by Mitchell314 Well, why not have an open ended system where new "traits" (more like the image of traits) may appear, existing "traits" may change their own interpretations, etc.? Uh... well, how about because doing that would basically involve creating an entire virtual world, with astronomical numbers of elements interacting more or less simultaneously; and in which everything happened implicitly, as natural consequences of those interactions; and even if you had the time and the system resources to dedicate to the effort, the complexity of all that would render most of the activity incomprehensible anyway?
Dymanic Illuminator Join Date: Sep 2002 Posts: 4,809

5th February 2009, 03:25 PM	#12
Mitchell314 Critical Thinker Join Date: Jun 2008 Location: NC, US Posts: 299	Originally Posted by roger I may have misunderstood your question, but instruction based genetic algorithms are called genetic programming. John Koza has written several books on the subject, and there is of course lots of papers in the literature. I've hear of that term before, but I just assumed it to be a synonym for GA. Now that I know.. Originally Posted by Dr. Trintignant I've written an instruction-based GA simulator to evolve little creatures that run around and eat. I think the key is to create a "robust" instruction set that works even when the instructions are mutated or arbitrarily reordered. I used a stack-based memory, for example, which is fairly robust in this way, since it doesn't matter where on the stack you are to begin with. In fact, none of my instructions had arguments: "mul" just popped off the top two stack elements and pushed the result, "dup" duplicated the top element, "skipifnv" skipped the next instruction if the top element was non-zero, etc. Every possible sequence of instructions was a valid program. The stack was circular as well, which meant that superfluous instructions were often harmless. That's what I was talking about, although each "cell" was given 16 addressable 2-byte variables, because my current system is 12 bit (4 bit instruction, 4 bit argument1, 4 bit argument2). Originally Posted by Dr Adequate You mean stuff like Tierra. Neat find Originally Posted by INRM This stuff, How detailed is the simulation? Do the creatures have their own brains and think for themselves? If so there are some ethical issues you should consider But their ribs are most succulent! But seriously, no brains. By creature/cell, we mean more or less an interpretation of segments of memory. For me, it's a string of a couple instructions and some variables. Originally Posted by Dynamic ...the complexity of all that would render most of the activity incomprehensible anyway? Who said anything had to be comprehensible?
	__________________ - "It's pronounced 'pea-can', man." Lapis Sells . . . But Who's Buying?

5th February 2009, 05:04 PM	#13
Dymanic Illuminator Join Date: Sep 2002 Posts: 4,809	Originally Posted by Mitchell314 Who said anything had to be comprehensible? Well, if incomprehensible complexity does it for you, that's easy enough to obtain. I've seen some nice little programs that achieved it with just a few lines of code. I've done it myself, without even trying (in fact, even when I was trying not to. You could always just head out to the garden with a magnifying glass (or maybe pick up a book on postmodernism). But if the point of the exercise is to learn (or be entertained) by creating a model, it's nice to have results that can be interpreted, or visualized, or something. Plus, it makes it a lot easier to debug.
Dymanic Illuminator Join Date: Sep 2002 Posts: 4,809

5th February 2009, 05:30 PM	#14
Mitchell314 Critical Thinker Join Date: Jun 2008 Location: NC, US Posts: 299	Originally Posted by Dymanic Well, if incomprehensible complexity does it for you, that's easy enough to obtain. I've seen some nice little programs that achieved it with just a few lines of code. I've done it myself, without even trying (in fact, even when I was trying not to. You could always just head out to the garden with a magnifying glass (or maybe pick up a book on postmodernism). But if the point of the exercise is to learn (or be entertained) by creating a model, it's nice to have results that can be interpreted, or visualized, or something. Plus, it makes it a lot easier to debug. I was just joking. I did a simple GA path finding test where you could watch the little bugs run about and eventually learn to get to the objects very quickly. I've got the results on an Excel worksheet somewhere. Surprisingly, the 'learning curve' was modeled to a 5th degree polynomial with an R² value around .6 . As for the genetic programming, I'm having ... technical issues (memory leak, but I wasn't allocating anything ). But it's looking promising, especially when the program was learning to cut off most of it's traveling. Instead of the usual randomize the cells, I put in a very inefficient (When dealing with hex code, it's not my fault I couldn't optimize. F03443A55 is hard to transcribe) method for the same path finding problem: Go down the whole screen, go right a pixel, go up the whole screen, go right a pixel, go down, etc until all three objectives were touched. Success was touching all three objectives (100*100 squares) first. When I tested it, first, every few generations would clip off a couple of iterations to complete. Then it got clever and decided to "bar code" the map; taking out a quarter of the iterations to complete. Then every few generations took out large chunks of iterations (my method was around 1,001,000 iterations). Eventually it got to 500,000 iteration, then the memory leak pretty much drained the computer to the point where I had to quite. But it was really fun to watch when it did work. I changed the code around so that it wouldn't leak (I think it was an issue with strings being used in UDTs, this was in a BASIC variant). But now it won't work at all (it doesn't move or turn). The GP implementation was much superior to the simpler model that just had two important genes specified by me: jump how many pixels and turn how often (random mostly). To those who never have seen a genetic algorithm or genetic program in action, it is something to watch. I may be biased since I'm a geek, but there is some entertainment - and awe - of watching an AI start from a low "dumb" level and learn over time then become intelligent, and even creative!
	__________________ - "It's pronounced 'pea-can', man." Lapis Sells . . . But Who's Buying?

5th February 2009, 09:35 PM	#15
Dymanic Illuminator Join Date: Sep 2002 Posts: 4,809	I did a sort of expanded version of the classic game "snake", where the critters (I called them "worms") went around looking for food, getting longer if they found it, and shorter (and eventually dying) if they didn't, and breeding only when they reached a certain maximum length (one of about twenty "genetic" characteristics). Each one had a list of colors it could eat, and though there was a population of virtual plants to provide food, they could also eat other worms, as long as the color was on their list. One of the things I was interested in at the time was r/K selection. (In biology, elephants, and humans, are K-selected; they produce few offspring and invest a lot in each one -- whereas oysters are r-selected; a single one can produce millions of offspring each year, but only a few survive.) In my little simulation, everything came at a cost. Offspring with, say, good vision, required a longer developmental time, expressed as a longer max length. Short-tails could breed fast, but they also died off quicker when food got scarce, and since they were at a disadvantage when it came to finding food in the first place, they could really thrive only when it was especially plentiful. So that worked. A lot of times, the whole population would die, usually after the worms had gobbled up all the plants. I took that as a sign that I had created a decent model. Thing is, early on, I would check in after an all-night run and find that the whole sim had somehow bogged down. There would be these big globs of mostly a single color, or maybe two, and nothing else. It kept happening on run after run, and for a while, I thought it was a bug. I was quite tickled when I figured it out: I had neglected to outlaw cannibalism. What I was looking at was clusters of symbiotic worms, feeding off of each other and their own offspring. They figured that out before I did.
Dymanic Illuminator Join Date: Sep 2002 Posts: 4,809