Disclaimer
The opinions expressed herein are my own personal opinions and do not represent anyone else's view in any way, including those of my employer.
© Copyright 2010
The opinions expressed herein are my own personal opinions and do not represent anyone else's view in any way, including those of my employer.
© Copyright 2010
I’ve been so fortunate enough to be able to attend FOSDEM 2010, which stands for Free and Open Source Developers’ European Meeting, and is the biggest yearly open source event in the world, again this year. It took place last weekend in Brussels, as usual. I mainly attended talks of the Mozilla Foundation, covering topics such as HTML 5, the nature of the Mozilla foundation, hackability and new services. Anyway, I had a great time there, and learned a lot. Not going to go into detail, cause I’m pretty busy getting into a few new projects about which I’ll post later on 
Today I released Maps and Semantic Maps 0.5.3. Both releases mainly include bug-fixes, some of which quite important:
I also discovered an oversight in the hook system of Maps, which is kind of a dormant bug, that could have caused errors for certain implementations of extensions to Maps. The oversight was that a mapping service does not necessary support a sub feature, like the parser function display_point, of a feature, like the parser functions. A check is now in place, together with a defaulting mechanism that also allows you to set the default per sub feature. I’m planning on changing this to a more recursive algorithm in the future though.
A last change is the adding of initial Google Maps v3 support. It’s only implemented for the display_map parser function, and has a rather limited set of customisation parameters at the moment, not to forget a whole load of issues. My conclusion from trying to implement this is that the GMaps 3 API is definitely not in it’s final state yet, since it’s lacking vital methods needed for basic functionality. The support for GMaps v3 is therefore sort of an alpha release, and won’t be put on the documentation page until it’s more stable and complete.
Downloads
As you can see, I changed the location of the releases from my forums to 2 brand new Google Code projects [ Maps, Semantic Maps ].
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
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
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.
Over the last week I’ve done some effort to update the Maps usage examples on my wiki to match the current version of Maps. Since I hadn’t made any real change to them since 0.3, most examples where seriously outdated, and in some cases even caused people to use deprecated syntax. Now all Maps examples have been updated, the example pages have been restructured, and new navigation bars have been added.
You can check out the examples on the following pages:
A screenshot of the Maps documentation page:
I’m also busy with updating the Semantic Maps examples, but that’s still a work in progress.
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
It’s been quite a while since the last release, but 0.5.2 is finally here! It’s not a big release, but features quite some fixes and improvements in the area of marker and pop-up layout.
You can now specify the icon to be used for all markers for both display_point(s) in Maps and result formats in Semantic Maps. A template= and showtitle= parameter have been added to the result formats as well, allowing you to remove the title from a pop-up, and further specifying what should be shown, in which format, by using templates.
On this map you can see that several markers use different icons. This is now easier then in previous versions due to a bug fix.
This map is created by Semantic Maps by querieng some demo data on my wiki. The title of the location is hidden by setting showtitle=no, and the template parameter is used to have a nice little text with the queried data in it as pop-up, contents.
Downloads
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?
What still needs to be finished/added?
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
I did a thorough overhaul of my wiki. I cleaned out the mess, put in some nice demo data, installed the latest version of Semantic Bundle, upgraded to MediaWiki 1.16alpha, put in a new logo and switched to the new (and awesome) vector skin. I also finally created decent templates and semantic data structures for my events and Semantic Maps demo’s.
A few friends of me created their very own completely awesome (audio) track. It’s titled “Abandoned”, and my friends named themselves “Metal Bunnies”. ATM there only is an instrumental version, but they are working on lyrics.
I’ve done an audiosurf run on the track with Ninja Mono on Ironmode with options bankcam, steep and 4lane. This one is HD btw
Over the last week, I’ve been rewriting my Genetic Algorithm (GA) implementation of the Travelling Salesman Problem (TSP). I’ve rewritten pretty much everything, but the two most notable changes are:
1. I split the code into 2 projects: one holding the general GA code, which is now called GALib, and one holding the code specific to the TSP, now called Skynet (lol 
). This allows for making any other GA implementation using GALib, even in .Net languages different from C#. The underneath diagram should give you a good idea of how the who thing works. The 4 most left classes are of Skynet, all remaining classes and interfaces are of GALib.
2. I rewrote the genotype of the Route individual type, the core of the TSP implementation. Instead of having a list of integers, referring to cities, I now have a list of Connection, each containing 2 instances of Location. I’ve done this to allow smarter crossover, decreasing the chance of not finding a better solution while it’s still in the converged search space significantly. As a result of this change, I also had to rewrite pretty much everything else of the Route class, including random initialization, mutation and fitness assessment. The biggest challenge here was preventing the creation of multiple loops in the crossover algorithm.
The interface of the TSP app (now called Skynet) also has seen quite some work. I figured out quite a lot of WPF stuff by further creating it. Some extra controls and progress indicators still need to be added though, and I also haven’t created the Cancel/Stop functionality.
Although the algorithm is efficient in the way that it takes relatively few generations to find a close to optimal solution, there remain a few mayor performance issues. If I compare the speed of evolution (measured in generations) with similar applications tackling the TSP, there are those performing up to 3 orders of magnitude faster. Although the fastest of those are written in C++ or C, I should be able to significantly speed up my application. Tracking down resource eating parts of code will be one of my next steps in developing this app. Another possible issue is diversity of the population. I have the suspicion that the diversity shrinks pretty fast, resulting into evolution driven only by mutation. I’m not sure of this though, and also have to investigate how I can prevent this from happening.
Here you have a few screenshots of the app in action
Categories
Tag Cloud
Blog RSS
Comments RSS
Void « Default
Life 
Earth 
Wind 
Water 
Fire Light
Previous Entries
Last 50 Posts
Back