Re: [Infinitemonkeys-devel] GA/GP (was: Re: Infinite Monkeys)

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 454-5900

Hi Erik,

Thanks for starting this up again...

Indeed Karva notation does represent expression trees.  There's a =
one-to-one mapping between Karva string and expression string.  I'll =
read into this Koza stuff further.

The main benefit of the Karva notation is that mutation and crossover =
always lead to syntactically correct expression trees.

The main areas I'd like to tackle next fit together nicely.  The first =
is allowing variable-length genomes.  The second is to introduce a =
penalty tactic whereby smaller genomes (arguably more elegant solutions) =
are favoured.  In my experience, penalties are trickly and delicate =
parameters for GAs.

Drew
  ----- Original Message -----=20
  From: Erik Doernenburg=20
  To: dn...@th...=20
  Cc: inf...@li...=20
  Sent: Monday, October 06, 2003 10:15 AM
  Subject: [Infinitemonkeys-devel] GA/GP (was: Re: Infinite Monkeys)

  Hi Drew,

  let's continue this on the infinitemonkeys list...

  Doing this kind of functional optimisation is probably the most common =
problem for GAs. That said, it could get you to solve the fist infinite =
monkeys problem quite easily.

  Rather than Karva notation have you considered using a tree-based =
notation for your expressions, somewhat like Koza proposes?

      http://www.geneticprogramming.com/Tutorial/

  There are problems with this approach (Most notably: deep trees which =
you can't prune because the important nodes are down near the leaves) =
but it has its advantages.

  cheers
  erik

  Drew Noakes
  18/09/2003 08:18

  To: Mike Mason/UK/ThoughtWorks@ThoughtWorks
  cc: Adam Murdoch/OZ/ThoughtWorks@ThoughtWorks, Ahmed M =
Hassan/Corporate/ThoughtWorks/US@ThoughtWorks, Amit =
Rathore/India/ThoughtWorks@ThoughtWorks, Anand =
Vishwanath/India/ThoughtWorks@ThoughtWorks, Ashok =
Subramanian/India/ThoughtWorks@ThoughtWorks, Aslak =
Hellesoy/UK/ThoughtWorks@ThoughtWorks, Brett =
Dargan/OZ/ThoughtWorks@ThoughtWorks, Brilly =
Tsang/Corporate/ThoughtWorks/US@ThoughtWorks, Chris =
Stevenson/UK/ThoughtWorks@ThoughtWorks, Chris =
Tarttelin/UK/ThoughtWorks@ThoughtWorks, Darrell =
Deboer/OZ/ThoughtWorks@ThoughtWorks, Dragos =
Manolescu/US/ThoughtWorks@ThoughtWorks, Ed =
Turnock/UK/ThoughtWorks@ThoughtWorks, Erik =
Doernenburg/UK/ThoughtWorks@ThoughtWorks, Ian =
Bourke/UK/ThoughtWorks@ThoughtWorks, Ivan =
Moore/UK/ThoughtWorks@ThoughtWorks, James E =
Weaver/Corporate/ThoughtWorks/US@ThoughtWorks, Jason C =
Yip/Corporate/ThoughtWorks/US@ThoughtWorks, Jeremy =
Stell-Smith/Corporate/ThoughtWorks/US@ThoughtWorks, Joe =
Walnes/UK/ThoughtWorks@ThoughtWorks, Jon =
Tirs=E9n/UK/ThoughtWorks@ThoughtWo
   rks, Lakshminarasimhan Sudarshan/India/ThoughtWorks@ThoughtWorks, =
Luke T Maxon/Corporate/ThoughtWorks/US@ThoughtWorks, Manoj K =
Bharadwaj/Corporate/ThoughtWorks/US@ThoughtWorks, Martin =
Andrews/OZ/ThoughtWorks@ThoughtWorks, Matthew P =
Foemmel/Corporate/ThoughtWorks/US@ThoughtWorks, Michael L =
Royle/Corporate/ThoughtWorks/US@ThoughtWorks, Mike =
Roberts/UK/ThoughtWorks@ThoughtWorks, Neil =
Fletcher/UK/ThoughtWorks@ThoughtWorks, Owen =
Rogers/Canada/ThoughtWorks@ThoughtWorks, Patrick B =
Sarnacke/Corporate/ThoughtWorks/US@TWorks, Paul =
Hammant/UK/ThoughtWorks@ThoughtWorks, Rajeev M =
Bhat/Corporate/ThoughtWorks/US@ThoughtWorks, Rebecca J =
Parsons/Corporate/ThoughtWorks/US@ThoughtWorks, Roger =
Marlow/UK/ThoughtWorks@ThoughtWorks, Sri Harsha K. =
M./India/ThoughtWorks@ThoughtWorks, Stacy =
Curl/UK/ThoughtWorks@ThoughtWorks, Steve =
Purcell/UK/ThoughtWorks@ThoughtWorks, Tim =
Bacon/UK/ThoughtWorks@ThoughtWorks, Tim =
Mackinnon/UK/ThoughtWorks@ThoughtWorks, William E =
Caputo/Corporate/ThoughtWorks/US@Thought
   Works, Xiao Guo/Corporate/ThoughtWorks/US@ThoughtWorks, Yasser M =
Helmi/Corporate/ThoughtWorks/US@ThoughtWorks
  Subject: Re: Infinite Monkeys

  Hi All,

  I've only just picked up this thread -- being home ill all of =
yesterday.

  This topic is near to my heart.  I've been working with GAs for the =
last six months of my free time, and have come up with some interesting =
results.  The framework I've been writing is in .NET, and can evolve a =
wide range of problem cases.  The case I've solved which is closest to =
the goal of this project involves discovering mathematical expressions =
to fit known data points.

  A side-project that spawned from this covers parsing, notation, =
recombination and evaluation of expressions.  Evaluation is performed in =
a variety of ways, but the snappiest uses System.Reflection.Emit to =
generate types at runtime from dynamically generated bytecode.

  For example, with a target dataset for function f(x,y) =3D z...

  x =3D 3, y =3D 4, z =3D 5
  x =3D 1, y =3D 2, z =3D 2.236
  x =3D 1.414, y =3D 1.414, z =3D 1.414

  ...and a random initial population of expressions, using these =
elements (reduced to characters for simplified presentation only -- each =
is an IExpressionElement object as a gene):

  + (addition)
  * (multiplication)
  Q (square root)
  x (parameter)
  y (parameter)

  At the moment, I'm using a PostFix notation (the most common notation =
is InFix) in which expression 'a + b' is written as 'ab+', and 'Sqrt( =
(a*a) + (b*b) )' is written as 'aa*bb*+Q'.  I'm currently working on =
support for Karva notation, which guarantees valid expressions (as with =
PostFix notation, crossover and mutation will mostly generate noisy =
expressions, such as '+a+bbQ' which can only be evalulated as =
'Sqrt(b)').

  The above sample data is from Pythagorus' theorem, and the GA =
successfully evolves a solution about 50% of the time.  Through using =
Karva notation, a new set of mutation functions and variable length =
genomes (I'm currently only using fixed length genomes) I'm hoping to =
get even better results.

  Whilst this work deals with mathematical expressions, the general =
approach could be extended to work with higher-level procedural code =
trees.  Graph reduction theory and sub-genome (gene) sharing techniques =
bring to mind method/variable extraction.

  I've also coded solutions (well, GAs are non-deterministic, so I don't =
know if you call them 'solutions') to other non-programming problems, =
such as the travelling salesman problem (a GA classic), the napsack =
problem, mastermind (the board game), the Chinese Hat problem, and =
functional optimisation (maximising or minimising a functional value, =
exemplified most easily on 3D functions with many local max/minima, and =
a single global max/minimum).

  Some reading:

  http://web.media.mit.edu/~lieber/PBE/
  =
http://www.testdriven.com/modules/newbb/viewtopic.php?viewmode=3Dflat&top=
ic_id=3D206&forum=3D6

  (Aaargg!  There's a site out there by a =
Fowler/Gamma/Jeffries/Beck/someone on this, but I can't find it...)

  I was going to hold a session on this at the away day -- it's a shame =
I didn't go through with the idea.  I'd really like to bounce these =
ideas off some people.  Anyone fancy meeting up at Peek House sometime?

  Drew Noakes

  ThoughtWorks, Inc. UK

  -------------------------------------------------------
  This sf.net email is sponsored by:ThinkGeek
  Welcome to geek heaven.
  http://thinkgeek.com/sf
  _______________________________________________
  Infinitemonkeys-devel mailing list
  Inf...@li...
  https://lists.sourceforge.net/lists/listinfo/infinitemonkeys-devel