Monday, February 14, 2011

Gluap: an attempt at PushGP in Lua

Eventually got around to implementing a basic genetic programming system in Lua, using the subset of the Push 3.0 language as explained in the previous post.

The results on my amazingly simple test function () are not great so far, though. Some runs produce a good result, while others get stuck in bad local optima:

best program so far with fitness 4.7958315233127 (integer.dup integer.+)
best program so far with fitness 71.917763204878 (integer.dup 231 298 integer./ integer./ integer.+)
best program so far with fitness 772.44948974278 (true)

Some of this may be due to using parsimony pressure, which can prioritise suboptimal solutions that are shorter in length. I'll have to read the tome on GP that's sitting upstairs.

Also, I've only implemented very simplistic mutation so far; maybe crossover will work better?
Even for mutation, selecting from the Push 3.0 instruction set with a uniform probability might be bad, since there are so many weird EXEC and CODE instructions, which are probably less likely to be useful than the simple arithmetic and stack instructions like FLOAT.* and INTEGER.DUP.

Tuesday, February 08, 2011

Mini-side-procrastination-project: Gluap (PushGP in Lua)

Rather than procrastinate uselessly this week, I decided to implement a barebones interpreter and library for Push 3.0, a stack-based language intended for use in evolutionary computation. For me, that means genetic programming. Never having tried Forth, this will be the first stack-based language I've ever used... the idea is interesting, especially with the gimmicky exec and code stacks, bringing up all sorts of weird possibilities for code which evolves its own control flow.

The language du jour is Lua, which feels a bit like a mix between Ruby and Python and maybe Tcl, and has a ravishingly fast JITted interpiler called LuaJIT on most x86/x64 systems.

It's going to be a mess, but hopefully a fun mess. After a few hours' work, I've got it to the point where it can do... almost nothing! It can interpret programs that consist of single number literals, though...

Edit, 2 groggy hours later

Finally, it can parse and evaluate very simple Push programs like this:
local result =
gluap.eval_program '( 5 1.23 + (4) - 5.67 FLOAT.*)'
assert_equal(1, result.pop('integer'))
assert_equal(6.9741, result.pop('float'))

If I can find time on Wednesday, the rest of the basic logic (I haven't got beyond basic arithmetic instructions yet) and maybe the beginnings of actual GP... or sleep, whichever.

Edit, 1 day and not enough sleep later

Instead of sleeping, it was more fun to add to the interpreter so that it can now execute each of the Push 3.0 simple examples correctly, including such madness as "( ARG FLOAT.DEFINE EXEC.Y ( ARG FLOAT.* 1 INTEGER.- INTEGER.DUP 0 INTEGER.> EXEC.IF ( ) EXEC.POP ) )", in some 346 lines of clumsy Lua. However, there's an intimidatingly long "type dictionary" which contains a great number of instructions of varying confusingness. Meh, maybe I can leave most of them for now and get with the GP part.