DPRG List  

[DPRG] Hello from sawtooth

Subject: [DPRG] Hello from sawtooth
From: Francisco Jose Ayala ze at neuroblast.net
Date: Wed Nov 26 09:20:16 CST 2008

> Hi im Jacob and I was the other guy on the sawtooth team. I got an  
> email from the list forwarded to me regarding the two 3pi's using AI  
> and I have a few questions for those two gentlement:

Hi, Jacob.  Thanks for your interest.

> 1. I'm curious to know what the output code actually looks like;

Each genome in our genetic system consists of a series of parse trees,  
which look something like this.  Each parse tree encodes a  
mathematical expression representing the processing of a single  
neuron.  Connections between neurons can be encoded as special kinds  
of nodes within the tree.

Here is a sample tree from one of our recent genomes:

((((Y0 NEG ) NUL ) MAX (((X2 SY0 ) - (N5 STP Y0)) MOD ((D2 + (R0 STP  
(D9 + R1))) SY0 ))) THR (((X0 * (Y0 MOD N14)) MAX ((R0 + N12) SR0 )) *  
((D6 NEG ) % ((Y0 SR1 ) MIN (D14 % X1)))))

A genome encodes a cluster of neurons.  Multiple instantiations of  
this cluster can be combined like legos to form a brain.  For example,  
to spawn the brains for the 3pi, which has five reflectance sensors,  
we join together five neural clusters, one for each input.

Parse trees are used in the genetic algorithm subfield called genetic  
programming.  Many other methods are available for genetically  
encoding evolvable mathematical expressions.  The great advantage of  
using parse trees is the process by which they are mutated...

> 2. Where in the code (what portions) are the changes being made as a  
> result of this process,

There are two general types of mutation to a parse tree.

Point mutations simply change one node to a different kind of node.   
For example, (5 + 3) can become (5 + 7), or (5 * 3).

Crossover mutations swap branches between two trees.  For example, ((5  
+ 3) * 2) can combine with (1 - (7 * 8)) to produce ((5 + 3) * (7 *  
8)) and (1 - 2).

Another type of crossover mutation swaps entire sections of one genome  
(comprising many trees) with entire sections of another genome.

> 3. and what kinds of things within the code are being changed?

Any kind of internal node can mutate to any other kind of internal  
node, and any terminal node can mutate to any other kind of terminal  
node; and any pairs of branches can be swapped between any two trees.

I mentioned that parse trees have a big advantage regarding mutation,  
and it is this:  all mutations, whether point or cross-over, will  
result in new trees that are guaranteed to be syntactically valid.   
That is, there are no "nonsense" mutations.

> 4. Does the code have some measure of success so that it knows which  
> traits are more desirable for the next iteration?

No, success (i.e. fitness) is measured externally.  In the case of our  
line-following brains, success is measured simply as proximity to the  
center of the line.  The brains know the current values of the  
sensors, so they know where they are relative to the line, so in that  
sense they know how well they are doing, but they do not know what  
their fitness scores are.

Mutations are completely random, so the brains have no way of choosing  
which traits to pass on to the next generation.

> Nice to meet everyone and look forward to competing again.



-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://list.dprg.org/pipermail/dprglist/attachments/20081126/ef9fe5d8/attachment.html

More information about the DPRG mailing list