Author Topic: Genetic Distance / Generational Distance  (Read 11519 times)

Offline Botsareus

  • Society makes it all backwards - there is a good reason for that
  • Bot God
  • *****
  • Posts: 4483
    • View Profile
Genetic Distance / Generational Distance
« 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?
« Last Edit: May 30, 2012, 06:43:40 PM by Botsareus »

Offline Botsareus

  • Society makes it all backwards - there is a good reason for that
  • Bot God
  • *****
  • Posts: 4483
    • View Profile
Re: Genetic Distance / Generational Distance
« Reply #1 on: May 30, 2012, 07:06:11 PM »
I think I can use "reclev" from the "Score" function to get max generational distance right?

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Re: Genetic Distance / Generational Distance
« Reply #2 on: May 30, 2012, 07:16:17 PM »
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 :/

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Re: Genetic Distance / Generational Distance
« Reply #3 on: May 30, 2012, 08:29:51 PM »
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.

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Re: Genetic Distance / Generational Distance
« Reply #4 on: May 31, 2012, 01:38:48 PM »
Here's an article about the problem of finding the longest common sequence.

Offline Botsareus

  • Society makes it all backwards - there is a good reason for that
  • Bot God
  • *****
  • Posts: 4483
    • View Profile
Re: Genetic Distance / Generational Distance
« Reply #5 on: June 04, 2012, 03:58:46 PM »
Quote
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:

« Last Edit: June 04, 2012, 04:12:58 PM by Botsareus »

Offline Botsareus

  • Society makes it all backwards - there is a good reason for that
  • Bot God
  • *****
  • Posts: 4483
    • View Profile
Re: Genetic Distance / Generational Distance
« Reply #6 on: June 04, 2012, 04:03:54 PM »
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.
« Last Edit: June 04, 2012, 04:54:01 PM by Botsareus »

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Re: Genetic Distance / Generational Distance
« Reply #7 on: June 04, 2012, 05:46:16 PM »
Your diffing algorithm is a little too simplistic.  You should read the link I linked to, it explains the ideas pretty well.

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Re: Genetic Distance / Generational Distance
« Reply #8 on: June 04, 2012, 05:52:42 PM »
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.

Offline Botsareus

  • Society makes it all backwards - there is a good reason for that
  • Bot God
  • *****
  • Posts: 4483
    • View Profile
Re: Genetic Distance / Generational Distance
« Reply #9 on: June 05, 2012, 06:16:20 PM »
Quote
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.

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Re: Genetic Distance / Generational Distance
« Reply #10 on: June 05, 2012, 06:21:17 PM »
I think that was Shasta, actually, but yeah, go for it.

Offline Botsareus

  • Society makes it all backwards - there is a good reason for that
  • Bot God
  • *****
  • Posts: 4483
    • View Profile
Re: Genetic Distance / Generational Distance
« Reply #11 on: June 12, 2012, 06:15:47 PM »
All post CL 61 revisions are me btw

I have a typo on DNA help, I'll fix that later.

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Re: Genetic Distance / Generational Distance
« Reply #12 on: June 12, 2012, 06:56:07 PM »
62-68 were me, actually.  Those are the garbage commits I said you'd probably have to revert.

Offline Botsareus

  • Society makes it all backwards - there is a good reason for that
  • Bot God
  • *****
  • Posts: 4483
    • View Profile
Re: Genetic Distance / Generational Distance
« Reply #13 on: June 12, 2012, 07:09:23 PM »
Quote
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?

Quote
I've moved the chloroplast stuff to a different branch.
I think you might have forgot you already did that.
« Last Edit: June 12, 2012, 08:39:07 PM by Numsgil »

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Re: Genetic Distance / Generational Distance
« Reply #14 on: June 12, 2012, 08:40:20 PM »
Quote
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).

Quote
Quote
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