This week's puzzler

[Tom Carter]

All -

   First a quick introduction -- I'm Tom Carter, long time resident  
faculty for the SFI Complex Systems Summer School, encouraged into  
FriAM by Owen and Steve . . .  I did make it to one FriAM session  
this summer -- here's hoping I'll be back next summer!

   Anyway, after spending too much time recently under my brother's  
"new" Datsun Roadster, struggling to extract the cracked exhaust  
manifold (we got it out and discovered that it needed extensive  
welding, so he ended up putting the car on a trailer to take back to  
Flagstaff, Az. with him), I figured I should have some other fun, and  
play with NetLogo for a while.

   So, this week's puzzler --   The basic idea is this:  there are a  
bunch of agents, each with a "genome" (a string of bits).  At each  
time step, each agent looks at its (nearby) neighbors and selects one  
to mate with.  The selection algorithm is to choose the neighbor who  
is most *different* (hamming distance of genomes) from you.  
Reproduction is replacement of self by a single offspring, whose  
genome is the result of a crossover with the mate (a crossover point  
is selected; the new genome results from one parent up to the  
crossover point, and the other parent from there on -- which parent  
selected at random).  The crossover point is selected from a normal  
distribution with mean = genome-size / 2, and standard deviation =  
genome-size / 6.  There is also the possibility of mutation of a  
"gene" (a bit in the genome).


   The question:  starting with a uniform distribution of genomes,  
what will the typical histogram of the long term distribution look  
like (after, say, a couple of hundred generations)?  For extra  
credit, why does it look that way?  Also, what is the range of likely  
long term distributions?

   The NetLogo is here:

   http://csustan.csustan.edu/~tom/SFI-CSSS/2005/NetLogo/genomes/ 
MostDifferent.html

tom

p.s.  For more extra credit, what will the typical histogram look  
like if the crossover point is uniformly distributed across the  
genome instead of normally distributed?

And, for extra extra credit, what if the crossover is always at bit  
two (i.e., the first 2 bits are from one parent, the rest from the  
other, chosen randomly)?  If you could anticipate this one, my hat is  
definitely off to you ! !! !   Now, having developed an explanation  
for yourself for this behavior, how does your explanation hold up for  
fixed crossover at bit 1 or bit 3?

p.p.s.  Does any of this have any relevance for actual biology?   (I  
find myself thinking about genders, autoimmune systems, and incest  
taboos . . .)

[Stephen Guerin]

Wow, a nice simple problem statement that yields cool effects!

Selection pressure for "most-different" genomes introduces an interesting
dynamic -- I wonder if there's a relationship to self-avoiding random walks. It
certainly is a nice technique to avoid premature convergence.

I ran the applet out to 1000 time steps and saw what roughly looked liked two
Boltzmann distributions symmetrically flipped about the middle. Thinking back to
your CSSS lectures and the idea that diffusion against a wall is a simple
mechanism that yields a Boltzmann distribution, is there an equivalent dynamic
going on here? Does the normal distribution for crossover somehow introduce a
"wall" in the middle?

Or maybe the "wall" comes from the fact that high-entropy genomes in the middle
(equal mixtures of 1's and 0's) have a difficult time surving as they would on
average match at least some bits with random neighbors and thus not have maximum
hamming distances. Similarly, I can see low-entropy genomes (ie nearly all 1's
or 0's) on the edges having a difficult time as they would maintain small
hamming distances with other low entropy offspring after crossover. ah...kind of
muddled thinking...

I'm in crunch mode on a couple of projects now but look forward to some time to
return to play with this some more...anyone else have some insights on this one?

Cool problem, Tom!

-Steve

[Owen Densmore]

Hi Tom, good to see you here amongst folks of like mind.

Stephen, Mike and I have been puzzling about drugs.  Er .. strictly  
in a modeling sort of way.  So we were thinking about a Tomonomics  
sort of drug supply/economy.  Here's what our first cut looks like:
     http://backspaces.net/models/drugsupply.html

What's up in your neck of the world?  Tilting any new and interesting  
windmills?

     -- Owen

Owen Densmore - http://backspaces.net - http://redfish.com - http://
friam.org


On Aug 22, 2005, at 5:11 PM, Tom Carter wrote:

> All -
>
>   First a quick introduction -- I'm Tom Carter, long time resident  
> faculty for the SFI Complex Systems Summer School, encouraged into  
> FriAM by Owen and Steve . . .  I did make it to one FriAM session  
> this summer -- here's hoping I'll be back next summer!
>
>   Anyway, after spending too much time recently under my brother's  
> "new" Datsun Roadster, struggling to extract the cracked exhaust  
> manifold (we got it out and discovered that it needed extensive  
> welding, so he ended up putting the car on a trailer to take back  
> to Flagstaff, Az. with him), I figured I should have some other  
> fun, and play with NetLogo for a while.
>
>   So, this week's puzzler --   The basic idea is this:  there are a  
> bunch of agents, each with a "genome" (a string of bits).  At each  
> time step, each agent looks at its (nearby) neighbors and selects  
> one to mate with.  The selection algorithm is to choose the  
> neighbor who is most *different* (hamming distance of genomes) from  
> you.  Reproduction is replacement of self by a single offspring,  
> whose genome is the result of a crossover with the mate (a  
> crossover point is selected; the new genome results from one parent  
> up to the crossover point, and the other parent from there on --  
> which parent selected at random).  The crossover point is selected  
> from a normal distribution with mean = genome-size / 2, and  
> standard deviation = genome-size / 6.  There is also the  
> possibility of mutation of a "gene" (a bit in the genome).
>
>
>   The question:  starting with a uniform distribution of genomes,  
> what will the typical histogram of the long term distribution look  
> like (after, say, a couple of hundred generations)?  For extra  
> credit, why does it look that way?  Also, what is the range of  
> likely long term distributions?
>
>   The NetLogo is here:
>
>   http://csustan.csustan.edu/~tom/SFI-CSSS/2005/NetLogo/genomes/ 
> MostDifferent.html
>
> tom
>
> p.s.  For more extra credit, what will the typical histogram look  
> like if the crossover point is uniformly distributed across the  
> genome instead of normally distributed?
>
> And, for extra extra credit, what if the crossover is always at bit  
> two (i.e., the first 2 bits are from one parent, the rest from the  
> other, chosen randomly)?  If you could anticipate this one, my hat  
> is definitely off to you ! !! !   Now, having developed an  
> explanation for yourself for this behavior, how does your  
> explanation hold up for fixed crossover at bit 1 or bit 3?
>
> p.p.s.  Does any of this have any relevance for actual biology?    
> (I find myself thinking about genders, autoimmune systems, and  
> incest taboos . . .)
>
> ============================================================
> FRIAM Applied Complexity Group listserv
> Meets Fridays 9:30a-11:30 at ad hoc locations
> Lecture schedule, archives, unsubscribe, etc.:
> http://www.friam.org
>