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
A few days back I decided I should release an update including a new update platform to some of my old applications. Apparently I had deleted the source of my little class library that I used for these applications a while back, and had to do a binary search through my backup archives to find the latest version. While implementing the new update platform in one of these apps, BN+ Brute Force Hash Attacker, I did a bunch of high level refactoring, both in the app itself and the used library, and decided to put them both freely available on SourceForge. I also decided to make some changes to the interface of BN+ BFHA, and replace the usage of a C# library for BigInteger support with the stuff that comes natively with .Net framework 4.0. So basically, after having put this app on the shelve for about a year, here is a new version, which might very well be the final one for this app.
Changes in 1.2.0
* Replaced custom BigInteger class by native .Net 4.0 class. * Replaced update platform with native ClickOnce deployment updater. * Refactored code structure and reduced required assemblies to BN+ Framework core. * Improved Help menu links. * Fixed Import/Export issue. * Redesigned about screen.
Downloads
Links
This is a screen shot of the previous version. This part of the interface is pretty much unchanged.
I’m also planning to release the new version of my class library that’s used for this app, which I renamed to BN+ Library, in the near future 
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.
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
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
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
To practice some AI methods I’ve been reading about, I created a genetic algorithm (GA) implementation to tackle the travelling salesman problem (TSP). I decided to do this in C#, to practice myself in some more advanced aspects of the language, and mess some more around with the new stuff of .Net 4.0, and with WPF as interface to get a better grip on the basics of WPF and XAML.
I started with creating a general data structure for any GA algorithm (Classes Population and Individual, interface IIndividual and some others), and then added handling for the TSP problem by creating a Route class. This class holds the crossover, mutation and random initialization methods for routes. Each instance of Route, which derives from Individual and implements IIndividual, contains it’s own genotype, which is a List<Int64>. This list contains the numbers of the ‘cities’ the ’salesman’ travels along. In the code behind my main window, I then create an instance of a Population<Route>, and do a calculation of the distances between all points, which is then stored in a static field of Route.
I’m going to put the complete project on SourceForge when it’s a little more finished. Although the algorithm is working it can still be optimized a lot (especially the genetic operations). Also, the interface is far from ready, and I’d like to do another simple implementation with the general GA structure to tackle some other problem.
In any case, here are some nice sceenshots
The dots represent cities.
The shortest route after several generations. The gray line represents an attempted, but failed, mutation or combination.
After a while the shortest route, or at least one that's very close, is found.
.
Over the last few days, I’ve done some work on .Net download library, the successor to my FileDownloader class. I started working on this project about half a year ago, and had quite some difficulties picking up the thread again after GSoC 2009, since I was in the middle of rewriting the code I was simultaneously translating from MyDownloader, mainly with the handling of the worker threads. The core work has been completed now, meaning that you can use the lib to download files, and track their progress. This is still in experimental stage though, and the pause and resume functionality has not yet been adapted to my new worker implementation.
In any case, the first release, which will be 0.1, is in sight now. This release will cover the basic functionality promised by the library; segmented downloads in the background that you can pause and resume, and can track the progress of (percentage, speed, downloaded bytes, remaining bytes, remaining time, elapsed time). After this, I’m planning to do some big rewrites of things that come from MyDownloader I’m not really happy with. This will mainly be making the whole library more OOP and event based. Only after that I’ll start on the other things I originally scheduled, such as prioritizing downloads and bandwidth limitations. By that time, .Net fw 4.0 will probably be released, and it’s a good possibility I’ll start using post .Net 2.0 technologies then, mainly things found in the Task Parallel Library.
Yesterday I spend about an hour creating the most useless application I’ve ever come up with. The main motivation for this was proving to a friend that solving a certain problem can be achieved with an algorithm containing only 1 loop and 1 if else structure. (And no GoTo’s! :p) It was also a nice opportunity to freshen up my C# skills and mess around a little more with the Beta 2 of Visual Studio 2010.
The application allows to generate a list containing random indexes of that list as values, and with a few special values. The application then allows you to find out whether by following the indexes route, you’ll end up with a special value (and which one), or get into an infinite loop. It also allows to slow down each step, enabling you to track the followed route.
You can has downloads:
Two days I go I got the beta 2 of Visual Studio 2010, which is scheduled to be released in the first half of next year. With it, came .Net Framework 4 beta 2. I’ve taken a good look at the changes in these new versions, and am really excited about the new features included in them.
The new WPF interface of VS is obviously cool, but it includes heaps of improvements, making life for the user easier. I’m still in the process of finding all goodies
The changes in the new .Net Framework are even more exciting. It includes a new parallel programming model, enabling you to create multi threaded applications without having to bother the low level work like locks and thread pools that was required until now. Also new are code contracts, a very handy feature allowing you to specify certain conditions for your code state (see this blog post). On top of that, there are various new features that where lacking in previous versions of the framework, like biginteger support, tuples and complex numbers, as well as multiple others.
Last few months I haven’t really done a lot of .Net work, apart from the .Net DownloadLib project, and therefore also not released anything. After someone on The Code Project gave me a poke on an update to my custom made ProgressbarWithPercentage component I had promised, I made an update to that component and released it.
ProgressbarWithPercentage is not at version 1.0.10. The changes I made since the last release are:
I also updated the demo, to include both an XP and a Vista/Win7 layout, and added a property grid that enables you to change the properties of the progress bars at runtime. On top of that, I decided it was a good idea to create a repository for this component on SourceForge, where you can now freely download and browse the code. I’ve send an update request to TCP with a new version of my article, but this has yet to appear.
Downloads:
Some nice screenshots of the new demo (click to enlarge):
Categories
Tag Cloud
Blog RSS
Comments RSS
Void « Default
Life 
Earth 
Wind 
Water 
Fire Light
Previous Entries
Last 50 Posts
Back