[Haskell-cafe] ANNOUNCE: genprog-0.1

[Jan Snajder]

(Moved from haskell at haskell.org)

Hi Kenneth,

I'm sorry for the very late reply.

On Wed, 2010-12-08 at 10:01 +0100, Kenneth Hoste wrote:
> Hi Jan,
> 
> On 11/29/2010 12:55 PM, Jan Snajder wrote:
> > Dear Haskellers,
> > 
> > I am pleased to announce the release of genprog-0.1, a genetic
> > programming library.
> >
> > (snip)
> 
> Very interesting, and nice job on the code (elegant, well-structured,
> well-documented, ...)!

Thank you. This was my first shot at building a Haskell library and I'm
flattered to receive such positive comments :-)

> Genetic programming recently got my attention because one of the bots in
> the Google AI contest was built using this technique (see
> http://ai-contest.com/forums/viewtopic.php?f=17&t=1136), and it
> performed really well (way better than my hand-crafted bot).

Interesting, thanks for the link.

> I have a bit of experience with genetic algorithms, on a practical and
> pragmatic level. The field of genetic programming is something I hope to
> look at and play with in the upcoming months (just for fun).
> 
> I was kind of planning to implement my own genetic programming library
> in Haskell as I became familiar with the field, but after diving into
> your code it quickly became clear to me you've done a way better job
> than I would have.
> 
> I really like the example you provided for evolving an expression that
> computes a specified integer value. 

I kept this example deliberatly simple so to make it clear how you can
use the library. The example is actually a degenerated case of symbolic
regression, in which you are given only a single instance to train at,
rather than a set of instances. You can find much more interesting
examples in Koza's book.

> I plan to start playing with that
> and improve the example (faster convergence to a perfect solution, and
> also tweaking the current GP config to obtain smaller solutions).
> 
> 
> A couple of questions (some fairly unrelated to Haskell):
> 
> How hard would it be to extend the current version to support the
> evolution of actual Haskell programs? As far as I can tell, the current
> version has support for (simple?) self-defined expressions, but this
> seems like a long way from supporting Haskell programs with
> multi-argument functions that operate on lists, etc., even if you just
> limit it to non-monadic Haskell98 code.

Actually, I have no idea. :-) I don't know if there is a data structure
that can represent an AST of a Haskell program. I guess there is,
because I guess at some point a compiler like GHC has to maintain such a
structure internally, but I never looked into this. At present, I am
more than satisfied to be able to evolve custom-made data structures.

Another issue with evolving arbitrary Haskell (or whatever) programs is
the "closure property". When doing crossover, you have to ensure that
what you get by exchanging two subtrees still is a valid program. In
other words, if F is a set of (arbitrary arity) functional nodes and T
is a set of terminal nodes, then, given a functional node
F(x1,...,xi,...xn), you should be able to substitute for argument xi
each element of F `union` T. Obviouslly, this will not work for
programms in general and you would have to either introduce specialized
crossover operations or treat the nodes differently depending on their
types. In genprog, I have kept things simple and closure propery is
ensured by allowing crossover to take place only at nodes that are of
the same type as the root node. This is certainly a limitation, but
still I think one can do interesting stuff with it.

> 
> Have you considered playing with dynamic values for the various
> parameters that steer the evolution, i.e. population size,
> crossover/mutation probabilities, etc.?
> One thing I've always wanted to try (but never really got to it) is e.g.
> increasing the mutation probability as the evolution seems to be getting
> stuck in a (local?) optimum. Also, shrinking the population size if
> enough progress is being made could be interesting, to speed up the
> evolutionary process. Are you aware of studies that do such a thing?

Yes, definitely! Variable mutation probability is often used in genetic
algorithms to improve the results. The idea is to have higher mutation
probability in the beginning, so to encourage exploration, and then
decrease the mutation probability as the evolution progresses, so to
encourage exploitation. This increases the chances of not getting stuck
in a local optima.

But I didn't include this into genprog because I don't need variable
mutation right now. I will probably do it in the next release. The most
straightforward to do it, I guess, would be make the mutation prob. (and
pop. size) a function of the evolution state. There are also other
things that I plan to include in the next release. I hope I will find
time to do it.

Btw., mutation is actually rarely used in GP (unlike in GA). Koza, for
example, used mutation in one example only. The thing is that, if you
think of mutation as a replacement of a subexpression with a randomly
generated subexpression, then you already can do this with crossover.
Now, this only true for this default type of mutation. If you have a
custom-defined mutation operator, one that changes a node depending on
its value and/or type, than this cannot be accomplished by crossover
anymore. Whether or not you need custom-defined mutations depends on the
task at hand. E.g., if the expressions you're evolving feature values
from a very large domain set, than a crossover operation alone will not
get you enough genetic diversity. For this reason I've defined in
genprog the mutation operation as a function of an expression that is
being mutated.

> Are you planning to actively maintain and extend this library? Are you
> using it for research purposes, or did you hack this together just for
> fun (if so, nice job!). What do you plan to use it for?

Yes, I will maintain the library actively. I did this for fun, of
course :-), and also for research, which I also do for fun :-) I am
using the library for solving specific problems related to natural
language processing.

> Anyway, great job, I hope I'll find the time to play around with this.

So do I. Please let me know if you have any suggestions on how to
improve the library. If you do interesting stuff with it, please let us
know what it is.

Cheers,
Jan