Jeroens blog

During the last 3 months I’ve been doing Stanfords online machine learning class. This as a great experience, and I now at least have a solid feel on the subjects covered in the course.

I actually started off doing the Artificial Intelligence class, and then found that the Machine Learning one was more interesting for me, and even of higher quality. So I decided to do both classes. After a few weeks I found this was really to much to do on top of my regular work, and decided to drop the AI class, so I could focus on the ML class and get good results there, rather then mediocre results on both. The ML class is made up of 18 lessons, each consisting of a set of videos with in-video mini-quizzes, review questions and programming exercises (in GNU Octave, similar to MatLab). Although I don’t have the official score yet, by my own counting I have 800 of 890 points, of which 70 I lost by not making all of the last set of programming exercises due to being sick.

Stanford offered 3 such online classes during Q4 of 2011 (AI, ML and databases), and is tripping this number in Q1 2012. As a response, MIT is going to extend on it’s OpenCourseWare platform. This is great news for online education, which has made huge strides in the last few years with things such as Khan Academy, these online courses by universities and the Wikipedia Education Program (more on which in my next blog post). If you want to teach yourself some new things, definitely check out these awesome programs

Today I released the first public beta of Skynet, which is now at version 0.1.3. Skynet is an implementation of GALib with WPF GUI that solves the Travelling Salesman Problem (TSP) using Genetic Algorithms (GA). It’s completely open source and available under the GNU General Public License.

Downloads

• Skynet 0.1.3.zip 99.4 KB
• Skynet 0.1.3 setup.zip 331.3 KB
• Download GNU tarball (latest version of the source project, straight from SVN)

You can also download the project code directly via SVN from the SourceForge source code repository, at https://csgalib-tsp.svn.sourceforge.net/svnroot/csgalib-tsp. From a command line, you can call the following: svn checkout https://csgalib-tsp.svn.sourceforge.net/svnroot/csgalib-tsp

Application features

• Graphical WPF interface
• Multiple selection algorithms
• Pause, resume and cancellation support
• Control over mutation ratio’s and elitism percentage
• Optional removal of identical twins or individuals
• “Take over the world” button

Background

The idea for creating this application came to me after reading the first part of Bio-Inspired Artificial Intelligence by Dario Floreano and Claudio Mattiussi. I figured I needed to do an implementation of what I’ve read to test myself. I split up the general GA code from the application itself and created GALib, a small C# Library that provides the scaffolding for Genetic Algorithm based functionality. All work was done in my free time.

See this page for more screenshots.

Using the application

Although the application interface should be pretty straight forward to use, I’ve written some documentation, which can be found here. If you have any questions, let me know

How it works

This section on my wiki explains how Skynet works as an implementation of GALib. If you are not familiar with how genetic algorithms work, you are advised to first have a good look at this Wikipedia article and related pages. This section will introduce you to how GA logic specific to the TSP works in a bottom-up fashion. For more information on the actual evolution, see GALib. I’m also planning to write a Code Project article about this implementation of GALib.

This is a full dependency digram generated in a Visual Studio solution containing both the GALib and Skynet projects.

Points of interest

Since my main motivation for creating this application was exercise, I learned a lot from building it. It’s my first decent C# application, as well as the first time I’ve created one using WPF and the first time I’ve done any GA programming (or AI in general). It also gave me the chance to familiarize myself with some of the new things of .Net 4.0, some profiling tools (see screenshot below), and have some fun with navigation based windows. The biggest challenge in the application itself (so not counting GALib), was definitely creating the crossover algorithm for the Route individual type. At first I simply took half of the connections of one parent, and then the other half from the other parent, but I rewrote this to take all common connections. Although the crossover algorithm works fine now, it’s pretty heavy on the cpu, and limiting the maximum speed of the application severely. If anyone finds a way to speed it up, be sure to let me know

I’ve been working on this application on an off for a month now, and have implemented everything I’ve planned and more. Although a lot of cool stuff could still be added, I’m quitting active development of both this application and GALib, so I can focus on new projects that allow me to further expand my understanding of AI.

Yesterday I released GALib version 0.1, a small C# Library that provides the scaffolding for Genetic Algorithm based functionality. It’s completely open source and available under the GNU General Public License. (See other blog posts about GALib) You can download both the source and compiled .dll from SourceForge.

I’ve done the effort to do some core documentation, in the form of comments in the source code, and an article explaining the usage of the library that I’ve put both on my wiki and on The Code Project.

Since my main motivation for creating this library was exercise, I learned a lot from building it. This is the first C# library I’ve ever written, as well as the first time I’ve done any GA programming (or AI in general). Abstracting the library in a way so that it can be used for GA in general was very interesting, and required me to expanded my knowledge of how to use interfaces and inheritance and use generics in a non-basic way for the first time.

I’m not planning to further develop this lib, although I might when I can re-use it for a future project. I hope to similarly release the first version of DownloadLib, which I’m having some lame multithreading issues with, before halfway through next week, after which I’ll start doing some development on Semantic MediaWiki.

Downloads

• GALib 0.1 dll.zip (11.1KB)
• GALib 0.1 source.zip (58.4 KB)
• GNU tarball

Over the past 2 weeks I’ve been putting time in creating a general purpose Genetic Algorithm (GA) library in C#. It provides the scaffolding for any GA based functionality. Although it’s not fully finished yet, it is now available under the GPL licence at SourceForge.

What does it provide and can it do ATM?

• An abstract Individual class that can be inherited from to make your own individual type, with it’s own mutation, crossover, initialization and fitness functions and genotype.
• A population class, which is basically a List<IndividualType>, which enables you to do the actual GA evolution. The evolution is done on a background thread, and events keep you up to date by reporting every time a generation has evolved, a new fittest individual is found, or the evolution is complete due to reaching the maximum amount of generations, reaching the stagnation limit or being cancelled. For the evolution you can choose between rank based selection, truncated rank based selection, and roulette wheel selection. You can also set properties like the mutation ratio, and elitism percentage.

What still needs to be finished/added?

• The library contains a IslandGroup class, allowing you to do simultaneous evolution on multiple ‘islands’. This class still needs to be finished though.
• The Population class contains a method for tournament based selection, but the code is not complete yet.
• The performance of the library could probably be improved.
• A lot of other neat things could be added, like multiple reproduction methods and varying genotype size support.

This is a class diagram of the library as it is at the moment.

I’m going to release the TSP implementation I made with this lib on-line in a similar fashion, after the interface is fully finished. Also, once the library itself is finished, I’m going to create an article explaining how it works and should be used, and put it both on The Code Project and my wiki

Resources

• Project home @ SourceForge
• SVN repository @ SourceForge
• Related posts