Tuesday, February 8, 2011

Haskell Evolutionary Algorithm Library on Git

I've uploaded the Haskell Evolutionary Library to GitHub- https://github.com/noahryan/heal. Its come a long way from its humble beginnings- I starting writing it ss my first little Haskell program in order to understand how to use the state monad. It is not a framework, and it doesn't provide a lot of structure- I need it to be fairly loose and easy to modify in order to do my research.
One nice thing about it is that it is less than 400 lines of code (more counting imports, blanks, comments,. etc) and supports Genetic Algorithms, Prefix Gene Expression Programming, and of course it is the first ever implementation of Robust Gene Expression programming, complete with a postfix evaluator for (as far as I know) the first time in any GEP. Although there are things I want to change, I am pretty happy with it and I find it pleasant to work with.
While it is hardly required that a user actually use the main loop provided, there is a small function called ea and another called ga in the EA module. These are the main entry point and are intended to capture the notion of an evolutionary algorithm and a genetic algorithm respectively. The RGEP and PGEP modules export functions call rgep and pgep to help set up problems with those techniques.
The EAMonad module exports the monad in which all evolutionary computation takes place- it allows randomness (as these are stochastic meta-heuristics so randomness is an inherent quality) a generation count, the ability to write to a log at any time, and the ability to keep any additional state that you want. This is a bit of a kludge- there is a type parameter for EAMonad that is intended to be the "rest of the environment" not included in the generation count or population if such an environment is included. I really don't know how else to allow a user to set up a problem that keeps track of many different types of state that I don't know about as the designer. The PGEP symbolic regression sample uses this to keep track of a number used to scale the population.
I am making use of a beautiful data structure called a 2-3 finger tree- the paper on this data structure is very fun and a good read. Also, there is some heavy use of the Traversable class as found in the functional pearl "Clowns and Jokers - Clowns to the Left of me, Jokers to the Right" by Conor Mcbride (a paper I highly recommend).
There are no real tricks or advanced Haskell techniques in this library unless monad transformers are considered advanced. This type of computation is specified by the techniques involved and there is a sense in which there is not room for a huge amount of cleverness. Maybe it would be an interesting research topic to look into functional EAs that investigates the opportunities to modify and implement EAs using techniques known to the functional programming community.

Well, back to work on my thesis!

No comments:

Post a Comment