Darwinbots Forum
Code center => Bugs and fixes => Topic started by: Botsareus on May 30, 2012, 05:14:52 PM
-
I just realized that genetic distance and generational distance charts where never programmed. I would like to take a crack at it, but, not really sure how to code it. I did some experiments where I figure out the most unique robot but this is a little different. Also, should I code this cross-species or not? (My personal preference is to code this cross-species but it is your call to make)
I guess I can do (my number from the unique robot calculator / total robots) for genetic distance.
But, what about generational distance?
-
I think I can use "reclev" from the "Score" function to get max generational distance right?
-
Genetic distance is sort of tricky. You need to match up lengths of DNA based on similarity, and then count the number of differences. That makes the algorithm robust to insertions and deletions. I think the sexrepro code already has a cross-over matching algorithm I helped Eric write a few years ago. You could probably leverage that. That would give you the genetic difference between any two bots. I'm not sure how you'd turn that in to a sim-wide graph. Either you'd do genetic distance from common ancestor, or some sort of median or average of genetic distance of all members of a species.
Generational distance is much simpler. You can just do either the average/median generation number since the common ancestor or do the relative spread of the living members.
...
If you're going to be doing some non-trivial programming, do you want to try and clean up the trunk while you're at it? I'll set you up with priveleges. It's in a mucky state; too much development got tried all at the same time and it sort of imploded. I tried to salvage it by separating out easy fixes from more systemic changes, but it turns out merging UI code is basically impossible so I failed at even that and gave up to go back to DB3 development :/ So the few patches you've submitted I haven't merged in yet, for instance.
I think the best bet is to rollback the trunk to changelist 61. That's basically 2.45.01 with my shflav fix added in and some file reorgnization. You could then go from there and add in the few patches you've done so far and then do the graph work. We'd lose the veggy work, but I don't have the energy to salvage it so meh :/
-
On the genetic distance:
See the Crossover function in robots.bas. It does more work than you'd need to do, though. The algorithm basically is recursive and looks something like:
Find largest matching sequence in current two DNA strands, or terminate if the sequences don't match.
For the DNA on either end of the matching sequence (the ones that don't match), feed them in to the algorithm again.
So you keep subdividing the DNA in to a matching middle and unmatching sides. Eventually you terminate and you have a bunch of matched regions in between areas of genetic difference.
Then to get a genetic distance you could do 1 - the total sum of the matching sequence lengths divided by the total DNA length (or average of them or something like that if they're different).
0 would mean the DNA is exactly matching. 1 would mean they're basically totally different.
-
Here's an article about the problem (http://www.ics.uci.edu/~eppstein/161/960229.html) of finding the longest common sequence.
-
If you're going to be doing some non-trivial programming, do you want to try and clean up the trunk while you're at it?
I'll clean up the Trunk but I am afraid Pandas chloroplast code will get lost. I have a bunch of new fixes since you added the fix that includes in/out 5 trough 9 pears. Just pm me a password/username.
For genetic distance I already had an algorithm implemented (it is a little different then what you want though. It works more like windiff) , see attachment:
-
Each letter is equivalent to a dna command. The only thing I don't know is how much 'points' should I charge for a 'change' and how much points should I charge for a 'move'
I kinda get why we have divide the whole thing by average DNA length though. This way the system won't favor robots with more DNA.
-
Your diffing algorithm is a little too simplistic. You should read the link I linked to, it explains the ideas pretty well.
-
I've set you up with a password and username (check your PMs).
I've moved the chloroplast stuff to a different branch. Someone, at some point, can go back and salvage it. But having the program in limbo isn't good for anyone, so it sucks but it just sort of needs to happen this way.
-
We'd lose the veggy work, but I don't have the energy to salvage it so meh :/
I have a few concepts I'll add from Pandas patches, once I finish all the non-trivial programming. For one, I like Pandas approach of using flags for chart types.
-
I think that was Shasta, actually, but yeah, go for it.
-
All post CL 61 revisions are me btw
I have a typo on DNA help, I'll fix that later.
-
62-68 were me, actually. Those are the garbage commits I said you'd probably have to revert.
-
I think the best bet is to rollback the trunk to changelist 61. That's basically 2.45.01 with my shflav fix added in and some file reorgnization. You could then go from there and add in the few patches you've done so far and then do the graph work. We'd lose the veggy work, but I don't have the energy to salvage it so meh :/
that's exactly what I did. Do you see my changes to the trunk?
I've moved the chloroplast stuff to a different branch.
I think you might have forgot you already did that.
-
I think the best bet is to rollback the trunk to changelist 61. That's basically 2.45.01 with my shflav fix added in and some file reorgnization. You could then go from there and add in the few patches you've done so far and then do the graph work. We'd lose the veggy work, but I don't have the energy to salvage it so meh :/
that's exactly what I did. Do you see my changes to the trunk?
Is that your "some updates" commit (69)? Can you make the commit message more descriptive? (Right click on the transaction in SmartSVN and change commit message).
I've moved the chloroplast stuff to a different branch.
I think you might have forgot you already did that.
Yes, this is entirely possible :P
-
Sorry Numsgil I don't have pro. (see picky) I should of been less lazy when committing that revision. But I will list my updates here:
Updates to icons
array out of bounds bug fixes (sometimes code never finds "end")
subtraction overflow protection
rotate robot on placment (has to do with vegs and manually inserted robots)
skin fix (when skin was trasfeared to robot the first element was always zero)
A debug button to the console window (did not code it yet, should replace RobDebug form)
Else genes where not being displayed properly in the gene activation window fix
maybe a couple more minor once that I don't remember and are not worth mentionaning
-
Bleh okay. (You might want to grab a command line SVN client then. For example, SlikSVN (http://www.sliksvn.com/en/download). Just because there are a number of tasks that you might want to be able to do that SmartSVN won't let you do without a license).
I'll update the commit message. Are the changes you're describing in addition to the revision to CL 61?
-
Are the changes you're describing in addition to the revision to CL 61?
Yes
You might want to grab a command line SVN client then.
Hate command line, I will just be careful to add proper comments next time. Is there any other components that I may need that are not in unlicensed SmartSVN ?
-
If you have to do much branching work I'm not sure how much unlicensed SmartSVN will let you do. Possibly also generating or integrating patches, if you need to do that (rare but possible). For day-to-day work it should be fine.
-
8)
-
For commit messages, a sentence or two is usually fine, but be as precise as you can. You don't know when you might leave the program to work on other stuff, and you want whoever looks at it next (yourself included) to have an idea of where you left off. For instance, a bad message would be: "physics stuff". What physics stuff? GUI work or engine work? Is it in a finished state? A better message would be: "Fixing bounciness issue when bots collide. Updating physics options form with a new slider to control bounciness.".
-
I don't think the crossover code works correctly at all:
I set up this test:
Private Sub MDIForm_Load()
'debug
Randomize
Do
Dim dna1(9) As block
Dim dna2(11) As block
ReDim rob(1)
dna1(0).value = 100
dna1(1).value = 200
dna1(2).value = 300
dna1(3).value = 400
dna1(4).value = 500
dna1(5).value = 600
dna1(6).value = 700
dna1(7).value = 800
dna1(8).value = 900
'
dna1(9).value = 1
dna1(9).tipo = 10
dna2(0).value = 111
dna2(1).value = 2
dna2(2).value = 3
dna2(3).value = 4
dna2(4).value = 400
dna2(5).value = 500
dna2(6).value = 600
dna2(7).value = 8
dna2(8).value = 9
dna2(9).value = 10
dna2(10).value = 11
'
dna2(11).value = 1
dna2(11).tipo = 10
rob(0).DNA = dna1
rob(0).DnaLen = DnaLen(rob(0).DNA)
rob(0).spermDNA = dna2
rob(0).spermDNAlen = DnaLen(rob(0).spermDNA)
Crossover 0, 1
Dim i As Integer
For i = 0 To UBound(rob(1).DNA)
MsgBox rob(1).DNA(i).value
Next
MsgBox "reset"
Loop
'debug
and it is ether returning the DNA or the SpermDNA
it should be returning one of the four below:
111,2,3,4,400,500,600,700,800,900,1
100,200,300,400,500,600,8,9,10,11,1
it is only returning:
100,200,300,400,500,600,700,800,900,1
or
111,2,3,4,400,500,600,8,9,10,11,1
is this output wrong or am I missing a step?
-
I think it has a threshold where if the DNA is dissimilar enough, it doesn't do the crossover at all.
-
surely this has to be similer enough (same result :():
'debug
Randomize
Do
Dim dna1(100) As block
Dim dna2(100) As block
ReDim rob(1)
Dim i As Integer
For i = 0 To 99
dna1(i).value = i
dna2(i).value = i
Next
dna1(0).tipo = 1
dna1(1).tipo = 1
dna1(2).tipo = 1
dna1(99).tipo = 1
dna1(98).tipo = 1
dna1(97).tipo = 1
dna1(100).value = 1
dna1(100).tipo = 10
dna2(100).value = 1
dna2(100).tipo = 10
rob(0).DNA = dna1
rob(0).DnaLen = DnaLen(rob(0).DNA)
rob(0).spermDNA = dna2
rob(0).spermDNAlen = DnaLen(rob(0).spermDNA)
Crossover 0, 1
Dim k As String
k = ""
For i = 0 To 99
k = k & " " & rob(1).DNA(i).tipo
Next
MsgBox k
Loop
'debug
btw, what is the threshold % anyway? because I found no code at all that looks like it is checking for dissimilarity
-
It smells like it's just plain broken then. You should probably attempt to fix it or check out a previous version and see if you can isolate which release it broke (and figure out what the change was).
I don't remember the threshhold percent. I think it was supposed to be like 50%. This is the relevant thread (http://forum.darwinbots.com/index.php/topic,2486.0.html) where Eric was discussing what he was trying to do.
-
I'll make it 52%. I have an idea about how to fix this, I'll try my best. If the robots is 52% or less similer I won't let them reproduce sexually at all, the system I am thinking of will also give me direct access to genetic distance.
edit: Changed my mind about 40%; I want an eco-system to develop...
-
I have to stay off DB for a while and try to get my summer homework done. I also have a soccer AI project I am writing a revision on for school. I can not concentrate on more then two things at a time. For the soccer AI I will only have access to 16 cores server until the end of Fall, so I have to get my prioritys straight. I got about 7 chapters in MCPD so I hope I start working on DB crossover fix by the end of August. If Shasta wants to resume work on his version of the chloroplast code, please coordinate with Numsgil because he moved it to a different revision. For now, good luck to all.
-
I am going to resume work soon. After thinking about it at length I have decided to go with 40% after all. The main reason being is that amplification (when implemented) will drastically change the DNA on each mutation.
-
They gave me a new 30 day trial with the smartsvn update, so I went in an added a proper commit message instead of "some updates"
-
[small bump]
Definitely starting work in August
-
[bump]
Re-implemented Shastas idea to tag graph ids with names (although had to get rid of internet mode specks since we are most likely going p2p)
Added the max generational distance graph
Added A bug fix to load charting interval from settings