Monday, August 12, 2013

icfp 2013 contest

This year's ICFP contest is in program generation. Niel had the most experience with genetic programming and advised us while Loftie and I did most of the coding.

We used DEAP (which is an evolutionary computation framework) and random code generation (which does not take into account programs from previous iterations). We used the builtin python multiprocessing library to run multiple versions with different parameters and strategies concurrently.

To run the generated lisp-like expressions, the program is translated into Python source code strings (containing lambda's) and compiled with eval into real python functions. The evaluation of the compiled python functions on inputs is fast enough (at least 70k evalutations per second on a single cpu). Python's eval compilation is more limiting (about 5k compilations per second). A better solution should probably generate partially evaluated functions, but there where variable scope issues that I didn't feel like debugging.

This didn't matter much though because the processing time was distributed over the code base: Expression compilation, evaluation, expression parsing, DEAP's individual construction/mutation and individual fitness calculation all took about the same time.

We used PyPy2.1, which seems to have helped. It's difficult to profile exactly as it was run over different machines with different architectures and there were stochastic behavior. Most of the problems (up to size 12) we ran on a 8 core laptop. For later problems we started up a few servers and ended running on 40 cores.

We had a good solution strategy which was solving problems at a good rate. Unfortunately we just started running things too late and ran out of time. There were still a lot of easy problems left on the servers. With another 2 hours we believe we could have ended in the top 25.

The contest was very well done. We encountered no problems with the server or problem specs. Many thanks to the organizers!

No comments: