New Adventures in Software by Dan Dyer

While some of us can just about muddle through a Sudoku, others are aiming higher. The BBC has the story of how a team from the University of Alberta has solved Checkers (or “Draughts” as we like to call it in this part of the world). The Chinook program was already well capable of beating the best human players, now it’s not worth even trying since it can’t be beaten. Earlier incarnations of Chinook made use of evolutionary approaches. The latest release is the result of a phenomenal amount of CPU time dedicated to analysing every possible game position and determining the best move for each. A solution for Chess is still some way off.

Everybody loves Sudoku (probably), and evolutionary computation is kind of neat, so what could possibly be better than an animated evolutionary Sudoku solver?

The applet’s animation gives a good feel for how the randomly directed search eventually converges on the right solution through the power of cumulative selection. Have a play with the population size setting to trade-off performance with reliability (harder puzzles will typically require a larger population).

I’ve got lots of ideas for improvements to the Watchmaker Framework for Evolutionary Computation, but before I could get started, I first had to finish off the stuff I had been playing with. So that’s what I’ve been up to this evening and the result is version 0.4.1.

• Changelog
• API Documentation

I discovered the Open Source project directory Ohloh yesterday (thanks to Andres Almiray’s post that I noticed on JavaBlogs). Oddly the name Ohloh is instantly forgettable and I’m having to look up the URL each time I go there.

By querying CVS and Subversion repositories, Ohloh generates information about the state of a project and ties individual contributions to developer profiles. It also allows individuals to list which Open Source projects they are users of. The site uses Google Maps to show how both contributors and users are distributed geographically.

I added my Watchmaker evolutionary computation project (the Ohloh entry is here). Unfortunately java.net‘s strategy of hosting web content in the Subversion repository does skew the statistics somewhat (my contributions appear to be mostly HTML content, but this is mainly generated Javadoc output).

Of the information presented, most pleasing for me is the nice green tick the project gets for being well commented:

Across all Java projects on Ohloh, 35% of all source code lines are comments. For Watchmaker Evolution Framework, this figure is 45%.

This high number of comments puts Watchmaker Evolution Framework among the highest one-third of all Java projects on Ohloh.

A high number of comments might indicate that the code is well-documented and organized, and could be a sign of a helpful and disciplined development team.

That’s a good reference for my CV: “Dan is a helpful and disciplined development team.” 🙂

I’ve just stumbled upon Scholarpedia, a MediaWiki-based encyclopedia. The key difference between it and Wikipedia is its focus on peer-review of content. Of course, this immediately means that it has substantially less content than Wikipedia but less is more, right? Contributors are nominated and voted in by the public based on their reputation in their area of expertise, most being notable academics.

At present Scholarpedia seems to have quite a narrow focus (most current articles are about various kinds of adaptive systems in computer science). It will be interesting to see how the project progresses. Perhaps the most promising aspect is the quality of authors who have apparently signed up to write various sections. For example, if you could ask anybody to explain Genetic Algorithms, it would probably be John Holland. And who better to write about Hopfield Networks than John Hopfield himself?

Version 0.4.0 of the Watchmaker Framework for Evolutionary Computation is now available for download. This release adds support for interactive evolutionary algorithms. An example applet, based on Richard Dawkin’s famous Biomorph program, demonstrates how the framework can be used with an interactive selection strategy. Using the applet you can direct the evolution of recursive pictures that resemble biological entities such as plants and insects.

The new release also adds a blazingly fast random number generator (a Java port of Tony Pasqualoni’s cellular automaton RNG). This RNG out-performs even the Mersenne Twister. By offering this RNG as an option, the framework provides potential for improved evolutionary performance.

• Change Log
• API Documentation
• Introductory Tutorial
• Travelling Salesman Example Applet
• Biomorphs Example Applet

Version 0.3.0 of the Watchmaker Framework for Evolutionary Computation is now available for download. The release includes several refinements to the API, one major bug fix (for Roulette Wheel Selection), and a new example program based on the first exercise in An Introduction to Genetic Algorithms.

This release can be considered the first stable release of the framework. There ought to be no major bugs and it is unlikely that any changes will be made to the API that will break backwards compatibility prior to the 1.0 release.

There are more features to be added (including support for GP and distributed fitness evaluations) before the framework is ready for its 1.0 release.

As always, I’m keen to receive suggestions for improvements and new features.

• Changelog
• API Documentation
• Travelling Salesman Example Applet

The Travelling Salesman problem is a good demonstration of where evolutionary algorithms (EAs) can be useful for finding good solutions to difficult problems. This applet allows you to compare evolutionary and brute force approaches to the Travelling Salesman problem for up to 15 cities. You can tweak the parameters of the evolution to see how it affects results. The applet uses the Watchmaker Framework to implement the EA.

In a quarter of a second we can find a solution to a problem that would take three days to brute force (WARNING: Don’t try to brute force a result for 15 cities unless you have a seriously powerful machine). The EA solution is not guaranteed to be optimal (from observations it seems to be optimal about 90% of the time for this example and is “near”-optimal in the other 10% of cases).

Version 0.2 of the Watchmaker Framework for Evolutionary Algorithms is now available for download from the project website (Document & Files section).

This version includes several minor tweaks plus support for concurrent fitness evaluations to take advantage of multi-core and multi-processor machines. It also includes improved example programs (more on that later).

API Documentation

To accompany the first release of the Watchmaker Framework, I’ve posted the first two parts of a tutorial that shows how to use it:

• Part 1 – A Brief Introduction to Evolutionary Algorithms
• Part 2 – Implementing Evolutionary Algorithms in Java with the Watchmaker Framework

Part 3 will be up sometime soon(ish) and will demonstrate how to solve a real problem with Watchaker and EAs.

As usual, constructive comments, corrections and suggestions are all welcome.

Version 0.1 of the Watchmaker Framework for Evolutionary Algorithms is now available for download from the project page on java.net (where you will also find details of implemented and planned features). The framework requires Java 5.0 and a familiarity with generics.

Feel free to download and play. You can leave comments and suggestions here or on the project site.