[Haskell-cafe] [Haskell] ANNOUNCE: genprog-0.1

[Alberto G. Corona]

Off topic

I was deeply involved in genetic programming in the past (in fact I
discovered Haskell on looking for a functional language  for genetic
programing with better syntax than LISP).

But I soon realized that GP was not the holy grial after all. The problem
with evolving arbitrary  programming code is the fitness
landscape<http://www.google.com/search?hl=en&q=fitness+landscape>.
 Any evolutionary process needs a way to produce small changes that produces
small increases or decreases of fitness (parsimony). This is why it is
relatively easy to evolve a continuous function towards a desired value. A
smal change in a parameter has a small effect in the resulting fitness, so
the algoritm can step up trough the smooth fitness landscape upto a local
maximum.

But programs are non lineal. If I change  the expression in a conditional,
the flow of the program becomes radically different, so the fitness
landscape, instead of a smoth continuous surface is a fractal where there
are no way to climb up the mount improbable (Dawkins dixit).

http://www.google.com/search?hl=en&q=mount+improbable+dawkins

The only way to overcome this is to indentify the smooth parts of the
fitness landscape and restrict the exploration to them trough some
techniques such is the use of rules, division of the problem in subproblems
and ...well any trick programmers use in their ordinary work to restrict and
direct the  program mutations.

 It is theoretically possilble to define metalevels of genetic algoritms
where rules and strategies are selected by extracting sucessful patterns
after evolving a big number of sucessful programs, These metaleves can
discover from simple rules such are "if a push is inserted, a pop must be
inserted somewhere else (push-pop gene mutation rule), upto the re-discovery
of complex rules above mentioned. These rules later would be used to
restrict the mutations of the lower levels. Finally the rules could become
so accurate that no mutation at the lower level is necessary because the
evolved higuer level rules give the solution at the first try.  So the
genetic algoritms have the potential to design arbitrary complex programs
right from scratch, but it may require a few billion years of computing.

Anyway this stuff is really interesting and I suspect that the combination
of rules and metalevels has some future, at least for helping programmers
with intelligent IDEs.

2010/12/8 Kenneth Hoste <kenneth.hoste at ugent.be>

> Hi Jan,
>
> 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, ...)!
>
> 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).
>
> 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 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.
>
> 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?
>
> 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?
>
>
> Anyway, great job, I hope I'll find the time to play around with this.
>
> _______________________________________________
> Haskell mailing list
> Haskell at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20101208/c159cef7/attachment.htm>