Mutation Protection method- in voting

[jknilinux]

Hi Everyone!

This thread is continued from a thread in the DB3 forum. If you are unfamiliar with the discussion, you can see it [a href=\'index.php?showtopic=2908\']here![/a]

Basically, the problem is that whenever someone tries to run a DB evosim, the bots end up "evolving" until they are filled with random crud and are unable to eat, because necessary genes have been overwritten. Eric first noticed that real-life evolution almost never modifies necessary metabolic pathways, even though these genes make up the bulk of our genome. Instead, less necessary genes, such as those controlling the number of fingers, are mutated much more often. So, something must be protecting those necessary genes from mutation, and the reason that evolution rarely works in DB is probably because it lacks this feature.

So, I'll try to see which algorithm is most popular, and then maybe we should implement that one first.

So far, there are four options: (I'm trying to make it objective, but some of my bias may show through. Let me know if I forgot a pro/con)



Number 1: Make metadata (Mutation-Rate data) instructions that attach to the DNA but are not DNA instructions, like [x10] ... [/x10]

Pros:
The mutation rate data is "glued" to it's assigned exon.
Evolution cannot delete/move a codule
Mutation protection cannot be overwritten if used more than once, since the mutation protection is Metadata.

Cons:
Fragile (it's more than one instruction long, so evolution and new coders could break it more easily)
Evolution cannot delete/move a codule



Number 2: Make a new instruction, such as x .protect25 store, to protect the next x bases by giving them a mutation rate of 25%.

Pros:
Easy for new coders and evolution to use.
Robust, since it can be put anywhere in a genome, or have x changed, etc..., and it will still function.
Easy to add to the next version of DB, since less work is required.
Evolution can delete/move it, since it is DNA.

Cons:
The mutation rate data is not "glued" to it's assigned exon.
Evolution can delete/move it, since it is DNA.
Mutation protection may be overwritten if used more than once, since the mutation protection is not Metadata.



Number 3: Make mutation immunity have a cost. If a bot is unable to pay the cost, immunity is lost. Immunity also degrades over time. Basically it would work like this:

Step 1-make enzyme. This will act the same way as slime does, decaying over time, more enzyme provides more protection eg reduce chance of mutatoins
Step 2-use X .protect store; if X is negative, it will protect X bps before the command, if positive, the next X bps after the command. The bigger the size of code protected, the faster enzymes wear off.

Note that Bacillus later changed Step 2 to tagging with metadata, which allows multiple protects in one cycle (not sure about logic though), and the distribution of substances.

Pros:
Time- and cost-dependent
Easy for new coders and evolution to use.
Robust, since it can be put anywhere in a genome, or have x changed, etc..., and it will still function.
Easy to add to the next version of DB, since less work is required.
Evolution can delete/move it, since it is DNA.

Cons:
Mutation protection may be overwritten if used more than once, since the mutation protection is not Metadata.
The mutation rate data is not "glued" to it's assigned exon.
Evolution can delete/move it, since it is DNA.



Number 4: Make a hybrid algorithm that combines the best features of different ideas. For example, a mutation control instruction that IS glued to it's assigned exon and applies the mutation rate it encodes to itself.

These Pros and Cons will look at an implementation of the MPPI instruction.

Pros:
Easy for new coders and evolution to use.
Robust, since it can be put anywhere in a genome, or have x changed, etc..., and it will still function.
Easy to add to the next version of DB, since less work is required than idea 1, but there's more than 2.
Evolution can delete/move it or not, it's up to the coder. Put x .protect0 store to make itself and the following x lines of code unchangeable.
The mutation rate data is "glued" to it's assigned exon.

Cons:
Mutation protection may be overwritten if used more than once, since the mutation protection is not Metadata.



Number 5: Bacillus' Idea: A hybrid of 1 and 3, where mutation immunity for an exon is governed by metadata attached to the DNA (as a codule), but can be lost if the bot is not able to pay the immunity costs and/or if the bot gets too old.

Pros:
The mutation rate data is "glued" to it's assigned exon.
Evolution cannot delete/move a codule
Mutation protection cannot be overwritten if used more than once, since the mutation protection is Metadata.

Cons:
Fragile (it's more than one instruction long, so evolution and new coders could break it more easily)
Evolution cannot delete/move a codule



Number 6: Ikkes' DNA comparison Idea: Make one or more copies of the genome, and if one copy is mutated, replace the mutated code with the equivalent code from another copy. Checking for mutation is done by comparing the genomes' DNA line-by-line.

EDITED!

Pros:
Allows evolution to make the genes from the two copies interact to create a novel outcome.
The required instructions could be used for other uses by evolution, since they are general-purpose.
Because the instructions are more flexible, a bot could have conditional mutation protection.


Cons:
If damage needs to be repaired, then it may slow down the sim if twice the amount of DNA is executed each cycle, since there will need to be a copy of the bots' genome.



Number 7: Ikkes' Hash comparison Idea: Make one or more copies of the genome, and if one copy is mutated, replace the mutated code with the equivalent code from another copy. Checking for mutation is done by comparing the genomes' Hashes.

EDITED!

Pros:
Allows evolution to make the genes from the two copies interact to create a novel outcome.
The required instructions could be used for other uses by evolution, since they are general-purpose.
Because the instructions are more flexible, a bot could have conditional mutation protection.

Cons:
If damage needs to be repaired, then it may slow down the sim if twice the amount of DNA is executed each cycle, since there will need to be a copy of the bots' genome.




  Thanks for voting!  

Note: I moved the hybrid option back up because someone voted for it, but after I added the other ideas it was moved down and Bacillus' second idea got the vote.

[bacillus]

In reply to 3.), it simple represents an effective 'mutation-immunity' system becoming ineffective over time, and needing refreshing. The major issue (note that this is not the only suggestion that has this issue) is that it relies on the data being stored in a memory location; multiple attempts at protecting DNA will override previous attempts, therefore the way to go will eventually be in the form of metadata. Based on that, I'd change my suggestion to combine the metatag suggestion with the protective enzyme protection system, which also gives a way to control the costs of protecting DNA. (in nrg per unit produced, evenly distributed within the tags, or perhaps allocated by a variable)
EDIT=>Don't forget that most people invloved in this discussion put forward an idea themselves, so I'd be surprised if there is a clear winner

[jknilinux]

In reply to 3.), it simple represents an effective 'mutation-immunity' system becoming ineffective over time, and needing refreshing. The major issue (note that this is not the only suggestion that has this issue) is that it relies on the data being stored in a memory location; multiple attempts at protecting DNA will override previous attempts, therefore the way to go will eventually be in the form of metadata. Based on that, I'd change my suggestion to combine the metatag suggestion with the protective enzyme protection system, which also gives a way to control the costs of protecting DNA. (in nrg per unit produced, evenly distributed within the tags, or perhaps allocated by a variable)
EDIT=>Don't forget that most people invloved in this discussion put forward an idea themselves, so I'd be surprised if there is a clear winner

Could you explain how trying to protect the DNA more than once would cause the Mutation protection instructions to be overwritten? Also, how would you combine enzymatic protection with metadata?

EDIT=> There probably won't be overwhelming support for one of the suggestions, but if there is a significant majority then we'd have to go with that. I'll also add ideas to the poll as they come up.

I'll need to leave your original suggestion on the poll, since some people have already voted in favor of it.

NUMSGIL, ERICL & IKKE: Did I summarize your ideas so they reflect your original opinions? Let me know!

[ikke]

Actually I gave two different suggestions, both located within the gene and based on some compare function
1) compare different copies of the same gene (not necessarily two)
2) compare an actual hash value of a section of the genome with the stored one (stored in the genome)

Additionally I suggested some repair/ kill function to follow the compare function. This might not be needed though: genes can already be deleted, so one programming option would be to delete the reproductive gene if a mutation has been detected.

A simple form of mutation protection would be something like:
if  gene1 !=gene2 delgene reproduce
or
if hash (gene1)!=1234 delgene reproduce

combined:
if hash(gene1) != hash(gene2).....

BTW: some bots already have a level of mutation protection by means of attacking mutants.

The main things I want to get out of this are the following:
1) mutation protection is located within the genome
2) mutation protection is done by combining generic instructions which also have other possible applications, for instance virus protection, conspec. Preferrably also functions only evolution thinks of. I like to be surprised
I think properly implemented mutation protection should expand bot genomes, not limit them. Therefor evolution should be able to break it, or reuse it in some other way.

[jknilinux]

Ikke- Does it adequately present your viewpoint now?

Also, how difficult do you think your idea would be to implement? It might be difficult for me, since I'm not in CS, but maybe there's an easy way to do it that I'm not seeing.

[Peter]

I'm going with EricL idea. Possible together wih some costs, but not necesarily.

Oh, and I like some command that would decrease mutation-rates overall, like the propopal of storing a negative number in .mrepro that Numsgil did. Or maybe creating some kind of dna-fixing substance. Something that uses itself by undoing mutations. Atleast that the bots could gain a possibility to survive in high mutation enviroments.

Anyway my two cents. I'll gues I make the confusion bigger.  

There isn't really a winner.

[jknilinux]

I'm going with EricL idea. Possible together wih some costs, but not necesarily.

Oh, and I like some command that would decrease mutation-rates overall, like the propopal of storing a negative number in .mrepro that Numsgil did. Or maybe creating some kind of dna-fixing substance. Something that uses itself by undoing mutations. Atleast that the bots could gain a possibility to survive in high mutation enviroments.

Anyway my two cents. I'll gues I make the confusion bigger.  

There isn't really a winner.

Thanks for the 2 cents! We need as many comments as possible to see what everyone wants. And as many votes as possible, too!
Feel free to vote for your own idea, too, if you think it's the best.

Well, anyway, you could decrease mutation rate for the entire bot by making the mutation protection instruction apply for the entire genome. For example, if a bots' DNA is 100 bps long then putting

"100 .protect50 store"

 at the top of the genome would halve the mutation rate for the entire bot. So, maybe I'm just not understanding your argument.

---

And no, there isn't a winner yet. I'm planning on leaving the poll going for a week, and next Saturday the idea voted for most, even if it wins by only one vote, will be submitted as the final suggestion to be implemented.

  So, everyone, be sure to vote! It does count!  

[Peter]

... at the top of the genome would halve the mutation rate for the entire bot. So, maybe I'm just not understanding your argument.

I had three different suggestions. Maybe not formulated perfectly in the earlier post. The second one could be implented anyway, it isn't too difficult, I think  .

 
1. What Eric said.

2. Decrease mutations during reproduction by storing a negative number in .mrepro.(Original Numsgil idea)

3. Or maybe creating some kind of dna-fixing substance. Something that uses itself by undoing mutations. Atleast that the bots could gain a possibility to survive in high mutation enviroments.(I copy/paste it from my original post )

[ikke]

Let me rephrase the hash idea, because this is the one best fleshed out to me
- Allow genome alteration evaluation by means of a hashing function
- allow hash results to be stored in the genome
- allow a genome copying function in the genome
With these commands mutation protection can be built. The bonus is that the functions can also be used for other things.
The con for the level of genome mutation protection is wrong. Given adequate programming any level of protection can be estabished, and this can be done without duplicates. A duplicate is only needed if damage needs to be repaired. Furthermore it can be used to programme (conditional) increase mutation occurrence, and is therefor more flexible.

[jknilinux]

K, thanks ikke. Changed it in the original post. Is it alright now? Also, would you like for me to remove the original DNA-comparison idea from the poll?

Everyone, be sure to read the edited summaries to get a better idea of the proposals!

[bacillus]

Could you explain how trying to protect the DNA more than once would cause the Mutation protection instructions to be overwritten? Also, how would you combine enzymatic protection with metadata?

Step One-Select code to be protected, and amount to be allocated to protected gene(as a ratio of total allocated protection), mutations to protect against (not necessary, just thought some mutations should be harder to prevent than others.)
[protect rate=60, type=delta]
...
[/protect]

Step Two-Protect, amount is spread in a ratio between all genes protected
100 .mkenzyme store

an alternative way to go is to share evenly, and define a threshold after which a gene will stop being protected. Enzymes will not stop mutations, but *for example) 50 units stop 50%, 100 units 70%, 200 units 80% etc.

[Cyberduke]

Unfortunately I know very little about biology and I am new to darwinbots itself, but that’s never stopped me putting my 0.02 cents in before.

What is this feature trying to achieve? Is it protecting sub sets of hand coded DNA from changing in an otherwise mutating bot?

Or is it indented to allow a bot to evolve protection for vital areas of code mutating too often without needing to lower the simulation wide mutation rate?

If it’s the second, you might not want a bot to be able to evolve cost free protection since; it may appear to be slightly beneficial in the short term, stabilising a population by creating a larger proportion of fully functioning bots, especially if the simulation wide mutation rate is high, but might be damaging to the species in the long term, by drastically slowing its evolution.
Correct me if I am wrong but it feels like something that could accumulate and might not show its true detriment until many generations later by which time (by its very nature) would then be very hard for the bot to undo. If it had a cost from the start then each step would have to show real and immediate benefits in order for it to persist; only I am not sure that with costs attached it would show any tangible benefits in the short term, the benefits of this kind of targeted protection sound like long-term ones? Not forgetting that changes to things like feeding and reproduction will most likely become evolutionary dead-ends in very short order anyway.

[jknilinux]

... at the top of the genome would halve the mutation rate for the entire bot. So, maybe I'm just not understanding your argument.

I had three different suggestions. Maybe not formulated perfectly in the earlier post. The second one could be implented anyway, it isn't too difficult, I think  .

 
1. What Eric said.

2. Decrease mutations during reproduction by storing a negative number in .mrepro.(Original Numsgil idea)

3. Or maybe creating some kind of dna-fixing substance. Something that uses itself by undoing mutations. Atleast that the bots could gain a possibility to survive in high mutation enviroments.(I copy/paste it from my original post )

Ok, now I see what you mean. I should've known that being tired would make me miss something you said!

Anyway, putting a negative number in .mrepro would just decrease the entire bots' mutation rate. What we were suggesting is finer-grained control, so that a bot can protect it's most important and fragile DNA (like living organisms do- when was the last time you heard of a dog that was born with a broken Krebs cycle? And, when was the last time you heard of a dog with an extra toe? One's much more common than the other, implying specific mutation protection for the important genes.)

Also, by having something that uses itself by undoing mutations, do you mean bacillus' idea of an enzyme that has a cost associated with it? You don't actually mean deleting the instruction from the offspring when used by the parent, do you?

And correct me if I'm wrong, but numsgil wanted codules, not negative .mrepro instructions. In fact, he thinks there shouldn't be any metadata in the DNA at all. Look at the link to the DB3 topic in the first post above.

---

Cyberduke:
Both are reasons for the Mutation Protection. We know living organisms protect their DNA. For example, when was the last time you heard of a dog that was born with a broken Krebs cycle? And, when was the last time you heard of a dog with an extra toe? One's much more common than the other, implying specific mutation protection for the important genes.

If a bot is in a difficult environment, then it would be better for it to have a good chance of mutating, so it can evolve. But once it has reached a local maxima, where most further mutations will harm it rather than help it, then it should protect it's DNA from further mutation, instead of constantly breaking itself. Once the environment changes, it would be best for it to re-allow mutation, to find the local maxima once more.
So, I don't think that cost-free mutation protection would slow evolution, since the bots with no-mutations-allowed will die out in a new environment, while the ones that allow mutations will probably survive.
So, I'm thinking mutating does have a short-term benefit.

However, I am starting to like the cost idea too. Maybe free mutation protection will be a problem.
So, anyway, I'm guessing you voted for bacillus' original idea?

[Numsgil]

Both are reasons for the Mutation Protection. We know living organisms protect their DNA. For example, when was the last time you heard of a dog that was born with a broken Krebs cycle? And, when was the last time you heard of a dog with an extra toe? One's much more common than the other, implying specific mutation protection for the important genes.

This is not because core metabolic pathways are protected.  It's because almost all mutations in them break the organism so bad that they never get born in the first place.  Or at least, that's the central theory to modern evolutionary thought.  Since about the mid 80s there's been some thought about organisms directing their own mutations somewhat in response to evolutionary pressure.  So this feature lives only to please whoever wants it, not to satisfy realism.

[Peter]

Anyway, putting a negative number in .mrepro would just decrease the entire bots' mutation rate. What we were suggesting is finer-grained control, so that a bot can protect it's most important and fragile...

Yes, I was putting in a more global suggestion inside it. If bots are save and sound they can lower the whole mutation rate. If they are endangered they can higher the mutation by making it a positive number. That together with some protected genes can come to steared mutation of parts.

DNA (like living organisms do- when was the last time you heard of a dog that was born with a broken Krebs cycle? And, when was the last time you heard of a dog with an extra toe? One's much more common than the other, implying specific mutation protection for the important genes.)

Cyberduke:
Both are reasons for the Mutation Protection. We know living organisms protect their DNA. For example, when was the last time you heard of a dog that was born with a broken Krebs cycle? And, when was the last time you heard of a dog with an extra toe? One's much more common than the other, implying specific mutation protection for the important genes.

Used copy/paste huh.

Also, by having something that uses itself by undoing mutations, do you mean bacillus' idea of an enzyme that has a cost associated with it? You don't actually mean deleting the instruction from the offspring when used by the parent, do you?

Yes, that could be. Some ''enzyme'' that undoes mutations. I could have missed it, but I thought bacillus idea wasn't really the same. I'd go for Eric idea for this one anyway.

And correct me if I'm wrong, but numsgil wanted codules, not negative .mrepro instructions. In fact, he thinks there shouldn't be any metadata in the DNA at all. Look at the link to the DB3 topic in the first post above.

Well in the other topic he made a quick notion of it. So that is how it became Numsgil idea.