A Genetic Algorithm in Google's Go Language

Like many programmers, I tracked the announcement of the Go Programming Language by Google last month, and like many programmers, I've been having a play around with it. Because of the newness of the language, there is very little code to look at to get a feeling for the language. I spent what time I could find looking through the code for the golang API in an attempt to gleam useful idioms. I've started a learning-go project for myself on github to collect links and code from tutorials and examples I come across.

Beyond the syntax, I'm interested in exploring how to make effective use of goroutines and channels in program design. I've spent some free time over the last week or so writing a simple genetic algorithm in go, and now that it compiles and looks ok-enough to talk about, I think that making good use of this language requires a slight shift in thinking about an application toward flows of information.

Having spent so many years researching computational intelligence and evolutionary computation, the genetic algorithm is burned into my brain. It's one of the first simple non-trivial programs I like to build to play-test a new language or platform (for example, see a genetic algorithm in lua from earlier this month).

The algorithm implemented is the classical Genetic Algorithm (GA) applied to the onemax problem, where the system must induce a bitstring of unity (all ones) from a cost function that only specifies the number of ones located anywhere in a candidate solution without specifying where the errors are located. The algorithm uses a bitstring representation, one-point crossover, point mutations, and tournament selection. The file is located in my learning go project, or you can access the go file for the genetic algorithm directly. See below for an embedded gist version of the file (sorry to those in RSS feed readers that don't like javascript).



I started out by trying to build an object-oriented version of the algorithm, but shifted to a procedural implementation for simplicity. Go does have objects, but they involve defining a struct for data and associating functions with the struct. Inheritance is not provided in favor for a compositional pattern. The language is young but it already has (what initially feels like) inconsistent rules for things like semi-colons and multiple ways for doing the simplest things like variable declarations. Nevertheless, the script-language like feel quickly becomes comfortable (compared to some ANSI C which I've been using at work recently).

My algorithm implementation is not optimal or efficient, and it's not event that pretty. What it does show is basically a port of a procedural implementation of a genetic algorithm in go language syntax. The code has examples of objects (solution), multiple return values, some library usage (data structures and random numbers) and some of the concurrent features. A genetic algorithm is embarrassingly parallel, so there are numerous ways to implement the algorithm to exploit this. I chose a simple step-wise multiplexing of operations like fitness evaluation, selection, and reproduction that used goroutnes to issue the work to execute in parallel and used a channel in a barrier pattern to wait for and collect the aggregation of these tasks.

I really like the ease with which one can manage tasks in parallel without resorting to explicit synchronisation blocks and patterns or booting threads. What became apparent while lashing my GA together was that this ease of parallelism promotes a different structure to programming. Rather than writing a linear procedural application and marking-up the parallelisable parts of the code after the fact, one should better design a program to exploit the parallel constructs (no shit!). This is obvious in retrospect, and would have been if I'd sat down and actually designed a parallel simple genetic algorithm.

This leads me to thoughts about the flow of information in the program. These observations should resonate if you've worked with message passing or event-driven infrastructure. Consider the prime number filter provided on the go website (or my implementation), it provides a great example of this type of thinking where goroutines manage the branching in the flow of data down through the filters, and channels bring the results back to where they are needed. The same pattern may be adopted for the GA, where each iteration of the algorithm may be represented as a pipeline of channels and data reservoirs where goroutnes consume, compute, and produce moving candidate solutions through to the next iteration. If I find some time, I'll wire up an example.

Enough from me, go play!

Great Science and Technology Podcasts

I've had a few people asking me what podcasts I consume so I thought I'd put it in a post.

I've been a heavy podcast consumer since about the time I bought my first iPod (a first generation back 2GB ipod nano, bought in 2004 or 2005). I've always listened to podcast's on my run (a few times a week). When working on my research, I used to go for an hour long walk each day for lunch and consume. These days, I'll consume on my daily commute to and from my day job.

In no particular order of priority, here are the awesome podcasts I consume:

Science
I removed Science, and the Naked Scientist feeds from by diet about 2-3 years ago, there was far too much redundancy in the science stories when listened in conjunction with Nature, The Science Show, SciFri, and Science Times.

• Nature. Weekly science news, and interviews with authors from nature articles. One of the best science podcasts around!
  
• Science Show. Australian science show with a veteran science reporter. My favourite because it's great quality with a local twist.
  
• Science. Similar format to Nature, although not quiet as good. Format may have changed as I haven't listened to it in quite some time.
  
• The Naked Scientists. Great format with 'live' experiments at schools, science news, and interviews. At the time when I was listening to this (a few years ago), there was a lot of overlap with nature, I think because some of the same people were working on both podcasts. Things may be different now.
  
• NY Science Times. I am really into the format of this brief podcast. They have science news, health information, and reporting with columnists for the science part of the NYTimes. They also don't just focus on hard science and include health and social sciences.
• NPR Science Friday. A callback science show on NPR with another veteran science reporter. I have always enjoy this show because of the mixture of hard and softer science shows. This weekly show typically consists of interviews with the scientists involved with the breaking science stories of the week or upcoming science books and shows. The call in questions are typically cringe-worthy.
  

Technology

• ITConversations. This is a fire hose of technology conferences. I subscribe to the master feed and filter ruthlessly with my skip-track button. I've also back-listened on many of the O'Reilly conferences. Some (weekly?) fixtures I enjoy the most include: Jon Udell's Interviews With Innovators, Phil Windley's Technometria, and Moira Gunn's tech nation.
  
• Robots. News and interviews in the field of robotics. I'm not a huge robot freak, but I really do appreciate the application of artificial intelligence and machine learning techniques in physical systems. These guys are a little amateurish (English as a second language?), although the science is hard the way I like it and their intro soundtrack is awesome!
  
• Software Engineering Radio. Interviews and discussions on software engineering topics. I'm new to this one, so I cannot accurately comment. It seems good so far, although sometimes a little dry or textbook (maybe a little too close to my undergrad).
• CSIRO HAIL Seminar Series. CSIRO is a premiere government research institution in Australian and HAIL stands for Human Factors, Artificial Intelligence, Language Technology. There are occasional gems in this stream on AI and interesting research, although many lectures are in topics I am not that interested in listening through on a run. CSIROpod is a new podcast on the scene from the same organization and I'm itching to give it a try.
  
• Singularity Summit. Talks from the annual conference on the technological singularity. The talks provide interesting insight into the current frontiers of Artificial Intelligence and I always get a lot out of them! They can be slow at releasing the audio for the talks, but here are links to the files for 2006, 2007 and 2008.

Other

• The Boyer Lectures. An annual lecture series delivered by prominent Australians. The 2008 series by Rupert Murdoch on the changes to journalism where particularly interesting.
  
• A Short History of Nearly Everything, by Bill Bryson (check itunes or amazon). This is an excellent book, and an excellent audio book on the history of science. I used to get through a chapter or two on a long run, and I think I've listened to it at least twice.

I also remember listening to a few semesters of biology lectures one year. I can't remember which school, but it was likely somewhere in the mess of MIT Open Courseware. I remember the content being very detailed and learning a lot about plant reproduction, genomes, and detailed critique of Darwin's origin of species.

There may be others, but these are all the great one's that come to mind. If you listen to any similarly awesome podcasts on science or technology, please spreed the word!

A Genetic Algorithm in Lua

I've been evaluating the Lua Programming Language at work for some embedded project. I really like this scripting language, if for nothing else other than it is so small and lightweight, yet almost as expressive as Ruby.

Anyway, I've created a small 'learning lua' project on github and collected a bunch of useful resources for developers to get started. I also made an attempt to use the language in anger and wrote a simple genetic algorithm in lua. If there are any Lua pro's out there, I'd love to hear about tweaks and idioms I could use to improve the example. I've copied the code into a gist and embedded it below, enjoy:



The genetic algorithm uses tournament selection, one-point crossover, point mutations and a binary string representation. The algorithm is applied to the classical OneMax problem. Some exercises for the reader my include changing the bitstring representation to tables, and to change the organization of the algorithm to use objects in a strategy pattern (for the problem and the algorithm).