Adventures in Hipster Programming: Solving a Math Puzzle Using a Genetic Algorithm Programmed in OCaml

*
Accepted Session
Short Form
Intermediate
Scheduled: Wednesday, June 27, 2012 from 3:45 – 4:30pm in B201

Excerpt

I heard Will Shortz pose a mathematical puzzle on NPR on a Sunday Morning in January and I thought, "Hey, I can solve that with a genetic algorithm!" In OCaml. I'll show you how in this talk.

Description

Genetic algorithms (GAs) can be used to solve a wide range of optimization and search problems that are considered very difficult if not impossible to solve with a polynomial-time algorithm (NP Hard problems). The Travelling Salesman problem is one such example that can be solved with a genetic algorithm giving reasonable results.

On a Sunday morning in early January while sleepily listening to NPR, I heard Will Shortz pose a puzzle that seemed to me to be a good candidate for solving with a genetic algorithm. In a nutshell, the problem is to come up with a set of math operations on the numbers 1 through 9 such that the resulting answer is 2012. I’ll go over the problem and show how I wrote a genetic algorithm in OCaml to solve it. Along the way you’ll learn about obscure things like genetic algorithms and functional programming in OCaml, a functional programming language in the ML family. Hopefully you’ll be inspired to apply GAs to solve problems you come across… and maybe you’ll even try it in OCaml.

Speaking experience

I gave a talk on FPGAs at last year's OSBridge. I've also given a couple of OSCON talks as well as talks at various programming groups around town.

Speaker