Guess-a-function

Inspiration

I have been interested in genetic programming for some time now, and wanted to do a small project in it. This is my first time writing something serious in Clojure (the lisp-like language that is commonly used for genetic programming), so I am very proud of what I have accomplished during this hackathon.

What it does

The program takes in 10 test cases input/output of any function. So, for example, if you want x^2, the cases could be 1-1, 2-4, 5-25, 6-36, 10-100, etc. In order to make testing easier, I generate the 10 test cases programmatically. The program starts by generating random programs based on defined grammar. My grammar involves just numbers from 1 to 10, and operators plus, minus, divide and multiply. There is also support for increment/decrement a number by x, x being the parameter. Then, these random programs are tested based on the earlier generated test cases. Of course, since programs are random, most of them will perform terribly. But some will still perform better than others, perhaps passing one or two test cases. We take those better-performing programs, and use them as parents, to evolve next generations of the program, using mutation and crossover (this terminology comes from real-life genetic processes, and the concept is the same). Eventually, after a few generations (could be a lot of generations), the program evolves itself into the right formula. It may look differently from what we are used to, because of how the formula was generated, but it will work. For example, instead of x^2+1, it might say x*x*x/x + x/x, or similar. Again, because of a lot of randomization in the evolution of the program, every time you run my program, you might get a different-looking formula, which will, however, simplify to the same thing. I find that fascinating.

How I built it

I am using a fungp library that I found online to do the backbone of the evolution, such as crossover and mutation. I specify the test cases, and parameters of the evolution, many of which are functions themselves. There are a lot of different ways to do evolutionary programming, and the library is flexible with which methods I want to use, which also means I need to program in my method, and then input it as a parameter into the library. For example, in order to select the best-fitting programs to be the parents, I am using what is called "tournament selection". That essentially means running several tournaments among randomly chosen programs, and making the best of them parents. I choose the best ones based on exactly how far from the test cases's outputs the programs' outputs are. I also have 6 islands, which are isolated groups of programs, that evolve within their own communities, and occasionally evolve across these communities as well. This helps to keep the population of programs diverse, thus speeding up the process of finding the right solution.

Challenges I ran into

For one thing, I am just starting to learn Clojure, the language I used for this project, and it is a fairly confusing language, especially for someone like me, who has no prior experience with lisp-based, or even functional languages. I had a lot of complications due to not knowing the language well, and it was hard to figure out how to import the library I am using, fungp. The error messages were very hard to understand, and testing and debugging Clojure is generally not very easy. There is no IDE that supports debugging in Clojure. In fact, I found it faster and easier to run it from terminal instead of an IDE.

Accomplishments that I'm proud of

I am proud of being able to complete this project in the given timeframe in the first place, especially so, because I do not know the language I used for the project very well. It was an amazing experience. I am also proud of being able to figure out the configurations that this project required, which I did mostly by trial and error, occasionally googling the problem to see if someone else ran into it. But not that many people use Clojure or genetic programming, so I did not find much.

What I learned

I learned how to figure out things myself instead of googling for solutions (as stated before, often the solutions were not available online), and I learned a great deal about Clojure and genetic programming.

What's next for Guess-a-function

I want to explore genetic programming further, by trying out different ways to evolve the program to guess the functions, and then use statistical models to determine which performs better.

Built With

• clujure
• fungp-library