Re: [stack] Evolutionary Programming

Hi, you would probably be really interested in the work of Jurgen
Schmidhuber, in particular the 'OOPS' optimal ordered problem solver[1].

It is an algorithm to optimally find the solution to any problem, via
a brute force search of the program space. Now, it has been known for a
while that there exists a simple provably optimal solution to all
definable problems (see LSEARCH and HSEARCH), however, it was of purely
theoretical interest since the constant factor was on the order of
2^500.

OOPS has actually made this sort of algorithm practical via the clever
use of.. a concatinative language, in particular a varient of forth. (it
is described in the paper). The novel use of forth in OOPS was taking
advantage of the fact that a program that solves a subset of a certain
problem is more likely to be of use to a program that solves the general
problem, and that the concatination of valid forth programs is a valid
program. In particular, it attempts to solve problems in order from
smallest to larger, incrementally expanding the forth programs biased
towards using succesful runs of smaller functions.

As to a couple other points mentioned, when it comes to exceptions, you
actually, perhaps counterintuitivly, want to abort programs that come
across an exception rather than trying to handle it. in fact, you should
be ultra paranoid. You want to weed out the bad programs as soon as
possible so they don't take up time when you could be testing other
candidates, in particular, you want the most 'dense' encoding possible,
in that you don't want to spend time testing algorithms that have
already been tested, by ignoring exceptions, you have increased your
search space with a lot of 'duplicate' entries. a program that has an
ignored exception and one that never attempted the invalid op in the
first place behave identically, and you will end up running both to
completion needlessly. Of course, there is no way to remove all
redundancy, but you certainly can make it less likely by allowing
exceptions to kill your program.

Also, when it comes to automatcally generating joy programs, you can
avoid having to deal with the bit of syntax joy has by using the floy[2]
variant of joy. floy is joy where are quotations are restricted to a
single symbol. it turns out to be just as expressive as joy, but you
don't need to worry about matching quotations, your primitive 'base
pairs' are simple the joy primitives and the quoted versions of each
and nothing else.

When it comes to recursion, no need to fear, you actually can express
arbitrary recursion without bindings by use of a y combinator[3], which
is easy enough to provide as a primitive in joy, if you include it as a
choice in your genetic code, you are not limited by your lack of
definitions in any way.

I think the following works... but someone check my work.

fix == dup [fix] dip i;


        John



[1] http://www.idsia.ch/~juergen/oops.html
[2] http://www.latrobe.edu.au/philosophy/phimvt/joy/jp-flatjoy.html
[3] http://en.wikipedia.org/wiki/Fixed_point_combinator

-- 
John Meacham - ⑆repetae.net⑆john⑈