Fixation of genetics - program

I've written a quick proof-of-concept program (not a true GA) which demonstrates how beneficial mutations can fixate into a population, even though they don't even come close to assuring the organism that has them with success, and each beneficial change has only a small chance of making it into the population, and given that most mutations are harmful.I recommend at least reading the headers at the top of the program before you respond; they explain what it does and does not show.http://www.daughtersoftiresias.org/progs/ev.cHere's the first 100 generations of outputhttp://www.daughtersoftiresias.org/progs/ev_output.txtI strongly invite comments. Again, I just threw this together in 2 hours, so don't expect too much from it, it's just barebones. Also, changing the parameters can really help someone get a handle on what is being discussed here. If you increase the mutation rate too much, you'll find that the species actually advances slower, because the organisms are becoming damaged almost as fast as they're advancing. You can see how important parallelism is to the population by changing the number of organisms - if you have a very small population, unless you have a very low mutation rate the population is likely to get devastated by a bad mutation. With a large population, it is effectively impossible. Etc.------------------
"Illuminant light,
illuminate me."[This message has been edited by Rei, 09-26-2003]

Hi, Rei!Nice job! I especially liked the random element you tossed in before comparing the fitness of competing offspring. Even with such a huge crowbar jammed in the works, fitness increased anyway. And the economy of combining the gene with the gene's expression and fitness into a single number was a shrewd move.I wrote a Ring Counter Evolution program last year that you might want to look at. It's a bit more obscure than yours because its based upon a PLA structure, but it has a fixed goal of producing ring counter behavior. Even this simple goal makes well apparent the difficulty of properly formulating the selection algorithm. Just ask yourself whether 1-1-1-2 is closer to ring counter behavior than 0-1-1-0 and you see the problem.We might not quite agree on the definition of GA. For me, if the program has genes, reproduction and selection then it's GA. That your program has no fixed goal doesn't matter to me.I've been toying in the back of my mind with the idea of writing my own "world" simulation with organisms that evolve, but I've always stopped myself from moving forward once I realized the time-consuming nature of some of the issues, particularly of the interfaces necessary to providing insight into what is happening in the simulated world. A couple weeks ago I took a quick peek around the web to see if there was any shareware already out there, and I came across something called FramSticks. I downloaded it and took a quick peek, but it's use model was sufficiently obscure that I didn't go beyond that. Are you aware of any good shareware evolution packages out there?--Percy

Well, I'm always careful to qualify a "true" GA in case Fred stops by, because he expects all GAs to emulate all major characteristics of a normal biological system, and has it in his head that no GAs do it just because there are some that don't. And he also has it in his head that the ones that don't emulate all major characteristics don't show anything. While that's akin to saying that a computer that doesn't have a printer or speakers doesn't demonstrate that computers can work, I'm being explicit because of that.Framsticks is pretty neat looking, although I've never run it myself. I wouldn't doubt that it's complex - modelling physics isn't easy. What types of GAs are you into running? A "virtual machine" GA, an evolving art GA, a physics-based GA like framsticks, etc?I agree about writing GAs being hard work mostly due to writing code that lets you monitor what they're doing realtime - to be able to "take a peak", so to speak. If you write a commercial-style GA, in which there is just a "fitness algorithm" run on each creature and the ones that perform the worst are tossed, it's pretty easy - you can just grab any result at any time, and it's guaranteed to be good. Of course, then they lack most of the parallelism, the different approaches different organisms take to getting around challenges.I actually started writing a piece of software called "libevolve" a year or two ago, which is designed to make GAs simpler to code (it contains generalized, customizable mutation, breeding algorithms, output, and competition algorithms; it wouldn't be useful for an "abiogenesis" modelling GA, but could be used for anything where you want to assume the basics of life already exist). For commercial-style GAs, it is even easier to use - you just simply need to input the fitness-calculation function. Perhaps I'll be tempted to finish it now. ------------------
"Illuminant light,
illuminate me."

I'm not really interested in GA's per se. My goal is to simulate organisms competing and evolving in a simulated world, with my strongest interest in observing how the evolutionary process produces innovation. To that end I'll employ whatever software techniques are necessary, so to me GA's are just a tool, and I'm actually not sufficiently well versed on GA's to have a clear idea of the distinctions you were drawing, such as art versus physics-based, though I think I have some informed guesses.What would my simulated world be like? I would definitely start way after abiogenesis. But would it have two or three dimensions? What would be the properties of the organism? Of the environment? Could the organisms effect change on the environment? Would I start at the cellular level, or assume higher level components in the manner of FramSticks? Though I've thought and considered issues like this, I really can't say I have any answers.I assume your libevolve library could be utilized by a "world" simulation program - do you have anything that describes it? It would give me some more to think about.--Percy

quote:

---

I've written a quick proof-of-concept program (not a true GA)...

---

This "GA" is also showing up in other topics.What is a "GA"? The unabreviated term should appear in the message, at least in the topic opening message.I think this would be a good practice for any abreviated term, even one such as the generally widely known ToE. Use a form such as "The theory of evolution (ToE) is such that...".AM

Genetic Algorithm (GA). You may be able to figure out roughly what it is from that. FAQ: comp.ai.genetic part 2/6 (A Guide to Frequently Asked Questions)

Ah, so you want to do more of a world-sim. Do you want physics in it or not? If you want physics, you'll either have to spend a lot of time coding a physics sim (better dig out that college physics text, and go to the pages about solid and fluid mechanics!), or find one that you can already make use of. An easier option would be to do something like Polyworld - a simple 2d environment without any mechanics, just the ability of organisms to "move". Once you have the sort of world you'd like in mind, you need to come up with their "genetics". Of course you can have bulk, physical traits in there; that's the easy part. However, unless you're starting with a sort of abiogenesis sim, you're going to need to have a way to have stimulus-response in there. One possible way is to use a neural net - like physics, you'll either need to code your own neural net sim, or find one that you can use. While that will probably get you the best behavior, you can also use a variety of simpler jury-rigged mecnahisms, such as the ability of each sensor simply do a time-delay activation of a response organ or of another sensor.libevolve, the way it is designed, creates a "ring" of organisms - it's a 1d world. The standard usage (although any part can be replaced) is to compete each organism with one "near" it - the highest odds being to compete with its immediate neighbors, then next highest odds being to compete with the organisms 2 away, then 3 away, etc, until the odds are almost nonexistant of a competition. This adds "regionalism", allowing for some parallel paths to the same goal to evolve. Again, using the default functions, it then takes whatever fitness algorithm you give to compete them, and the initiates the default mutation and breeding algorithms to fill in the places of organisms that die. The way I had started on it, however, it was designed so that any major function call in the library could be replaced; you could use custom mutation or breeding algorithms if you chose, or even make it so that the 1d ring is really representative of a multi-dimensional world which used its own competition algorithm (all you'd really end up getting out of the library, in such a case, would be statistics printing functions, save/restore functions, etc). However, it was being written to be optimal for developing things which are most fit toward a specified goal.------------------
"Illuminant light,
illuminate me."

Hi Percy,
If a simulation of organisms competing and evolving is something you are interested in here is a recent reference on just this topic..Nature. 2003 May 8;423(6936):139-44. Related Articles, LinksThe evolutionary origin of complex features.Lenski RE, Ofria C, Pennock RT, Adami C.Department of Microbiology & Molecular Genetics, Michigan State University, East Lansing, Michigan 48824, USA. lenski@msu.eduA long-standing challenge to evolutionary theory has been whether it can explain the origin of complex organismal features. We examined this issue using digital organisms--computer programs that self-replicate, mutate, compete and evolve. Populations of digital organisms often evolved the ability to perform complex logic functions requiring the coordinated execution of many genomic instructions. Complex functions evolved by building on simpler functions that had evolved earlier, provided that these were also selectively favoured. However, no particular intermediate stage was essential for evolving complex functions. The first genotypes able to perform complex functions differed from their non-performing parents by only one or two mutations, but differed from the ancestor by many mutations that were also crucial to the new functions. In some cases, mutations that were deleterious when they appeared served as stepping-stones in the evolution of complex features. These findings show how complex functions can originate by random mutation and natural selection.

Hi Rei,Thanks for the info!After looking up Tierra, I'm wondering if I'm using an incorrect definition of GA. Tierra was mentioned in a book I'm reading called Artificial Life, and this book seemed to believe that the algorithm had to be self-replicating in order to be considered GA. Perhaps I haven't read far enough yet, though.--Percy

Hi, Mammuthus!Found one of their papers online - thanks for the reference.--Percy

quote:

---

the algorithm had to be self-replicating to be considered GA

---

You see, that's the problem with the term "genetic algorithm" - it has a wide range of definitions, and people like Fred take advantage of that to try and pigeonhole all of the different GAs out there into being the exact same thing, when there's such a huge variety of them. "Artificial life" and "Artificial evolution" aren't much better terms, they're still fairly vague.I sometimes use the terms "commercial GA" and "research GA" to incidate ones which are given a "goal to evolve towards" (i.e., a preset fitness algorithm, "truncation selection", etc) versus ones which exist and compete in the same fashion as normal life, typically used to study genetic spread in organisms. And there's still no clear boundary between types...------------------
"Illuminant light,
illuminate me."

Rei's Fantasyland refuted here:http://EvC Forum: Fred Williams' Mutation Rate Article Obsolete -->EvC Forum: Fred Williams' Mutation Rate Article ObsoleteMsg 26

Response made. All you need is a larger population, and it still works The larger the population, the worse the ratio of good to bad mutations can be.Try again, Fred!!!------------------
"Illuminant light,
illuminate me."

Baloney!!! I know it is mathematically impossible for your program to produce increasing overall fitness if you set the advantageous rate to 1 in 1000 while leaving your other paramters alone. Also, DID YOU FIX THE BUG where the top 4% always fall in the 10% advantageous bracket? If you did not, then your program will likely still produce your fantasyland results (since 1 in 25 will be advantageous at a whopping 10%) as I stated in my prior post, a post which appears you did not read carefully.

I'll re-post the post here:Try again, Fred!Yes, there was that bug; the 10% rate was supposed to be 0.2, not 4.2 as it effectively was - and I've corrected it. However, let's use your rates, shall we?The overall mutation rate is one in 50 per gene (or trait), not one in 50 per organism. If you think this should be changed, fine, but I don't see why one would think that it should be changed.Also:

quote:

---

The lowest deleterious rate Ive seen from the scientific community is 1.6 per organism/generation (after selection), yet yours is roughly 0.3 per organism.

---

Nope. My mutation rate was 1 in 50; 100 genes; that's 2 mutations average per organism; 50% had no effect, that's 1% mutations total. Even with the bug, there were .84 bad mutations per organism. Also note that my mutations are actually much more dramatic than most. In reality, a "harmful" mutation would have to be pretty severe to be a -10% selection rate, let alone a -90%. And yet, I had one in 7 bad mutations be -90%! And check out what rates I'm going to use below...Do you honestly believe that 0.84 * 6% (the old number) or 0.84 * 14.27% (the new number) - that is, 5% or even more preposterously 12% of the people who make it to reproductive maturity have a brand-new minus 90% mutation to fitness??? We're not even talking about the sum of bad mutations, or bad mutations inherited from parents - we're talking about *brand new*, -90% fitness mutations.Fatal-mutation rates are irrelevant; a fatal rate to offspring born is basically the same thing as having more offspring, so if you want to account for fatals, just account for them in the offspring number.Now, moving on:Your rates: 1/1000 (0.1%) beneficial at all. In my opinion, that is *WAY* too low - example, a polar bear growing longer fur in an ice age is an advantageous mutation, and it has about the same probability of it happening as growing shorter hair. The assumption of the vast majority of mutations being disadvantageous only holds when species are under the same selective pressure that they've been under for a long period of time, and have already become optimized to it; when put under new selective pressures, change is typically a good thing. But, we'll go with your numbers, just to prove the point.Let's do the beneficials as 0.05% +1%, 0.025% +2%, 0.015% +5%, and 0.01% +10% to be nice and favorable to you - in short, we're making that the vast majority of favorable mutations are only a *tiny* bit beneficial, one-upping you. The "+10%" mutations on a gene occur only once every ten thousand replications. Let's adjust the negatives correspondingly to 14.27% -90%, 14.27% -50%, 14.27% -20%, 14.27% -10%, 14.27% -5%, 14.27% -2%, 14.28 -1% - i.e., making it so that all bad levels of mutation are equally likely, and they range all the way down to -90%. These are astoundingly pessimistic assumptions, and astoundingly bad mutations (again, minus 90% is almost unheard of in how bad it is, in the real world; and note again how the beneficial mutations only go up to +10%, with an incredibly rare rate. In short, a bad mutation 10% or worse (far worse!) is 5708 times more likely than a good one of 10% or better (and there is no better).)Let's take out all of the mutations that do nothing, because you're using them to try and skew the interpretation of the results. Mutations with no effects are now set to 0. They can just be factored in by the mutation rate itself - in fact, I'll just go ahead and do that.However, we're only dealing with a population of 1,000 organisms. In reality, we're often dealing with trillions. Lets be nice, and only increase it to 100,000 organisms. Again, all we're doing is changing the population size here to make it *more like real life*.What are our results?http://www.daughtersoftiresias.org/progs/ev_output2.txt(Note: I didn't run it as long, because it runs a *lot* slower with this many organisms; if I want to do much more with it, I may need to give it a faster competition algorithm, instead of the "easy to understand" one that I've got now. Also, to get the program to work with this many organisms, I had to change double variables to floats, and to redo the memory allocation structure. I also put in some more debugging print statements.)As you can see, *any* bad rate can be handled and good genes will fixate, so long as there's a large enough population. Likewise, another option for a population is to have the mutation rate drop (mutation rates can be controlled by genetics as well - want me to add in natural selection for mutation rates?). With a low enough mutation rate, even a population of 2 organisms (plus one generation of children) will evolve. Also, unlike the real world, my sim is pessimistic and assumes that organisms have no ability to assess the fitness of their mates before reproducing, so that's no advantage to selection instead of the positive advantage to selection that exists in the real world.I've jury-rigged this as far as I can in your favor, Fred, and evolution still occurs. Want to make the already preposterously unreasonable mutation rate numbers even worse? I'll just make the population even larger, or let them evolve their own optimal mutation rate like in real life.I should work out the formula for this... since it's working on probabilities, I'm not sure how I'd do it mathematically, but I could probably do it statistically. Of course, someone may have already done this work, which would save me a lot of time. The results, however, follow the same trend: if the population is large enough OR the mutation rate is low enough (or any combination), evolution occurs. The average population starts a downward trend, while a few individuals begin an upward trend. Those inviduals genotypes steadily fixate into the population. Eventually, the entire population follows these upward trends.------------------
"Illuminant light,
illuminate me."[This message has been edited by Rei, 10-24-2003]